Диссертация (1137276), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Та­ким образом получается построить АСД заведомо ограниченное по глубине.Предварительна подготовка текста заключается в формировании строкдлины, начинающихся с 1, 2, 3 и т.д. слова текста. Первая строка для построенияАСД состоит из 1, 2 и 3 слова в тексте, вторая – 2, 3 и 4, и так далее. Обозначимтакие строки через 1 , . . . , . Длина всех фрагментов не превышает , где –максимальная длина строки в символах, поэтому не возникает необходимостидобавлять терминальный символ к концам фрагментов.Как пример, построим АСД для строки = “mining”.

Для суффиксовпервых трех суффиксов = “mining”, = “ining”, = “ning” и последне­го суффикса = “g” совпадений не будет найдено. Поэтому в дерево будутдобавлены соответствующие цепочки с частотами равными 1. При добавлениичетвертого суффикса [4 :] = “ing” будет найдено непустое совпадение “in”,поэтому частота узлов из совпадения будет увеличена на 1, а у узла с меткой“n” будет создан новый потомок с меткой “g” и частотой 1. Аналогично, придобавлении суффикса [5 :] = “ng” будет найдено совпадение из одного узла сметкой “n” Следуя алгоритму, частота узла будет увеличена на 1 и у него будетсоздан новый потомок с меткой “g” и частотой 1.Если к уже построенному для строки = “mining” АСД требуется до­бавить строку = “dining”, то для первого суффикса = “dining” не будетнайдено совпадений, поэтому будет создана новая цепочка узлов с частотами 1.Для всех остальных суффиксов строки будут найдены совпадения, полностьюпокрывающие суффиксы, поэтому у всех узлов в дереве частоты будут увеличе­ны вдвое, но новых узлов создано не будет.

Результирующее АСД представленона 1.5.Опишем наивный алгоритм построения АСД на псевдокоде и оценим егосложность по времени и по памяти, следуя [60].Анализ сложности по времени и памяти данного алгоритма достаточнопрост. Перебирая строки, мы посимвольно просматриваем все ее суффиксы,затрачивая на -ю строку длины количество операций, пропорциональное33Algorithm 2 Построение АСД для коллекции строк 1 , . . .

, Вход: Коллекция строк 1 , . . . , Выход: АСД для коллекции строк 1 , . . . , Инициализация: создаем пустую структуру, в которой будет храниться АСД.Обозначим ее ast. Далее итеративно будем добавлять в ast фрагменты вход­ной коллекции.for ∈ {1, } dofor ∈ {1,}, = | | doДля каждого суффикса [ :] ищем в ast совпадение – путь от корня, сов­падающий с максимальным префиксом суффикса [ :].

Пусть match –совпадение [ :], |match | = .if = thenЧастоты всех узлов в найденном совпадении |match | увеличиваютсяна 1.else < . Требуется создать новые узлы для фрагмента строки [ +1 : ].Для этого создаем у последнего узла в найденном совпадении новогопотомка, помечаем его символом [+1] и приписываем ему частоту 1.Таким же образом последовательно создаем узлы для всех оставших­ся символов в фрагменте. В результате будет создана новая цепочкаузлов, кодирующая текущий суффикс. Если совпадения не найдено = 0, поступаем аналогичным образом, создавая новую цепочку откорня ast.end ifend forend for34Рисунок 1.5 — Аннотированное суффиксное дерево для строки = “mining”Algorithm 3 NaiveConstruction(C)Вход: Коллекция фрагментов = 1 , .

. . , Выход: АСД для for ← 1 to dofor ← 1 to = | | do1. do ← длина совпадения [ :] с АСДfor узел из [ : ( + − 1)] do2. do присвоить () ← () + 1end forfor ← + to do3. вставить узел 4. присвоить () ← 1end forend forend for351 + 2 + · · · + = Θ(2 ). Общее время работы алгоритма для коллекции изстрок, таким образом, может быть оценено как Θ(21 + · · · + 1 ), или, еслииспользовать более грубую оценку, (2 ).

Отметим, что определенное спо­собом выше АСД невозможно построить с использованием меньшего числа опе­раций, так как само оно занимает в памяти место, квадратично зависящее отдлины закодированных в нем строк.1.6Выводы по главеВ первой главе представлены и описаны четыре основных класса моделейпредставления коллекций текстов: векторная модель, языковая модель, модельна основе скрытых тем и теоретико-множественная модель.

Под формальнымпредставлением коллекций текстов понимаются следующие структуры: вектор­ное пространство термов, Марковские цепи, системы распределений вероятно­стей и суффиксные деревья – частный вид помеченных графов. Каждая из мо­делей представлений текстов удобна для использования в определенном классезадач автоматической обработки текстов. Проведен обзор задач автоматиче­ской обработки текстов и показано, какая модель представления текста исполь­зуется для решения той или иной задачи. Сформулирована собственная теоре­тико-множественная модель представления текста и предложено использоватьаннотированное суффкисное дерево для быстрого вычисления частот в теоре­тико-множественной модели.

Введено понятие аннотированного суффиксногодерева как структуры данных, используемой для хранения и вычисления всехфрагментов и их частот одного текстового документа или входной коллекциитекстовых документов. В дальнейшем будет показано, как эта модель можетбыть адаптирована к решению конкретных задач анализа текстов.36Глава 2. Оценивание релевантности строки тексту с использованиемметода аннотированного суффиксного дерева (АСД)2.1Проблема оценивания релевантности строки тексту и основныеподходы к ее решениюПроблема оценивания релевантности строки тексту формулируется следу­ющем образом.

Пусть дана некоторая коллекция текстов и некоторая строка.Под строкой понимается, как правило, одно слово или согласованное словосо­четание. Требуется определить, насколько релевантна строка каждому текстуиз коллекции, то есть, встречается она или ее фрагменты в тексты, и, если да,насколько строка соответствует содержанию текста. Другими словами, необхо­димо ранжировать тексты по степени релевантности им данной строки.

Чис­ленные оценки релевантности тому или иному тексту сами по себе не имеютсмысла и интересны исключительно с сравнительной точки зрения: какомутексту более релевантна строка. Понятие релевантности имеет двойственныйхарактер. С одной стороны, чаще всего термин релевантность возникает в обла­сти информационного поиска (поиска по запросу). В задаче поиска по запросутребуется показать пользователю релевантные его запросу (строке) докумен­ты (тексты).

Говорят, что релевантные документы – это такие тексты, которыеудовлетворяют информационные нужды пользователя [61; 62]. С другой сто­роны, в формальных моделях релевантность строки тексту определяется поблизости между формальными представлениями строки и текста или по веро­ятности появления строки в тексте.

Как правило, в таких моделях отсутствуетпользователь и его информационные нужды. Они появляются позже, в качественадстройки над математическими моделями и учитывают не непосредственныехарактеристики строки или текста, а их контекст, время, место появления идругие свойства [63]. В этой работе мы будем обращаться исключительно кматематическим мерам релевантности. Перечислим основные математическиемодели и меры релевантности.372.1.1Теоретико-множественные меры релевантностиВ качестве примитивной меры релеватности можно использовать теоре­тико-множественные меры близости между множествами термов, на которыеразбиваются строка и текст.

В [47] приведен исчерпывающий обзор теоретико­множественных мер близости. Каждая мера близости тем или иным образомучитывает количество совпадающих термов (мощность пересечения двух мно­жеств термов), так же как и мощности каждого множества по отдельности илимощность объединения множеств.Перечеслим данные коэффициенты. Обозначим множество термов, на ко­торые разбивается строка, через , а множество термов, на которые разбиваетсятекст, через . Будем оценивать по мере близости строки и текста релевантностьстроки тексту: relevance(,) = (, ). Тогда:– Расстояние городских кварталов (или манхэттенское расстояние) [48]предполагает, что каждые терм – это одна из координат в многомерномпространстве размерности , где – общее число термов в строке и в∑︀тексте. (, ) = =1 | − |, , – частоты соответствующих -тойкоординате термов;2|∩ |– Коэффициент Дайса [49]: (, ) = ||+||;|– Коэффицинт Жаккара [50]: (, ) = |∩|∪ | ;– Количество совпавших элементов – это абсолютное количество совпав­ших термов в множествах , ;|∩ |– Коэффициент Симпсона [51]: (, ) = min[||,||] ;– Коэффициент Отиаи [52]: (, ) = √|∩ | .||·| |Заметим, что перечисленные выше меры близости являются симметрич­ными.

При необходимости, например, в задаче поиска по запросу могут бытьиспользованы несимметричные меры близости – т.н. меры включения382.1.2Релевантность в векторной моделиРелевантность строки тексту определяется в векторной модели так: тексти строка представляются векторами в общем пространстве слов, а релевант­ность определяется по сходству двух построенных векторов.Пусть дана строка и коллекция текстов, в которой текстов. Тре­буется определить релевантность relevance(,) строки одному из тек­стов из коллекции. Для начала зададим координаты векторного простран­ства: – словарь, содержащий все слова коллекции текстов, ∈ – слова.Каждому слову соответствует своя координата. Тогда тексту соответствуетвектор = (1 , . .

Характеристики

Список файлов диссертации