Читать реферат по всему другому: "3. 1 Перечисление образцов в канонической форме с использованием суффиксного дерева 8" Страница 1

(Назад) (Cкачать работу)

Hiroki Arimura, Atsushi Wataki, Ryoichi Fujino, and Setsuo Arikawa

A Fast Algorithm for Discovering Optimal String Patterns in Large Text Databases

Быстрый алгоритм для обнаружения оптимальных образцов в больших базах данных

Перевод: Погорский Н.В.

2004

Содержание 3 Резюме 4 1 Введение 4 2 Предварительные сведения 5 2.1 Тексты и образцы 5 2.2 Задача получения данных (data mining problem) 5 2.3 Суффиксные деревья 6 2.4 Региональный поиск 7 3 Алгоритм 7 3.1 Перечисление образцов в канонической форме с использованием суффиксного дерева 7 3.2 Вычисление значений поддержки с использованием региональных запросов 8 4 Модифицированный алгоритм 9 5 Agnostic PAC-learning и минимизация эмпирической ошибки 11 6 Обрезание и выборка 12 7 Экспериментальные результаты. 12 8 Заключение 13 Ссылки 14

Мы рассмотрим проблему выборки данных (data mining problem) в больших наборах неструктурированных текстов, основанную на правилах зависимости между подсловами текста. Образец зависимых слов есть выражение такое как

(TATA,30,AGGAGGT)  C

- выражает правило, по которому если текст содержит подстроку TATA, и следующую за ней подстроку AGGAGGT с расстоянием между ними не более 30 символов, то свойство C с высокой вероятностью будет выполняться. Решение проблемы оптимизации доверия образца представляет собой часто встречающиеся образцы (, k,), которые оптимизируют доверие по отношению к данному набору текстов. Хотя существует прямой алгоритм, решающий эту задачу за полиномиальное время, который перечисляет все возможные образцы за время O(n5), мы сосредоточимся на рассмотрении более эффективных алгоритмов, которые могут быть применены к большим базам данных. Мы представим алгоритм, который решает задачу оптимизации доверия образца за время O(max{k,m}n2) с использованием памяти O(kn), где m и n – количество и общая длина классифицируемых исходных данных соответственно, k – небольшая константа в диапазоне около 30-50. Этот алгоритм сочетает в себе структуру данных суффиксные деревья и алгоритм регионального поиска (региональные запросы, orthogonal range query), которые ускоряют вычисления. Кроме того, для большинства случайных текстов, таких как последовательности ДНК, мы увидим, что модифицированный алгоритм работает за время O(kn*log(n)3), используя память O(kn). Мы также обсудим некоторые эвристики, такие как осуществление выборки (sampling) и обрезание (pruning) как практические усовершенствования. Затем мы оценим эффективность и работу алгоритмов для эксперимента с генетическими последовательностями. Также обсуждается связь с эффективным Agnostic PAC-learning.

Недавний прогресс связи и сетевых технологий, таких как электронная почта, всемирная паутина, и др. сделали простым накопление больших массивов неструктурированных и полуструктурированных текстовых данных [1]. Такие текстовые базы данных могут быть наборами web-страниц или SGML документов (OPENTEXT Index [26]), баз данных белков (GenBank [11]), online – словарей (OED [13]) и другими очевидными текстовыми данными в файлах. Имеется потенциальный

Похожие работы