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

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

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

Эти параметры представляют некоторые свойства АСД, изменяя кото­рые можно повысить эффективность метода оценивания релевантности строкитексту.45Глубина АСДГлубина АСД – это количество узлов в максимальной по длине цепочке.Очевидно, что глубина АСД определяется количеством символов в самой длин­ной цепочке. Очевидно, что глубина АСД не превосходит длину строк, которыена него накладываются (с поправкой на 1-10 символов). При разбиении тек­ста на строки следует учитывать, что от длины строк зависит глубина АСДи выбирать длину строки, т.е. количество слов в строке разумным способом.Например, если заранее известно, что большая часть входных строк состоят изтрех слов, то и текст следует разбивать на строки из трех слов, как это сдела­но в [65].

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

Первыйуровень характеризует частоты отдельных символов, второй – частоты упорядо­ченных пар символов, третий – частоты упорядоченных троек и т.д. Очевидно,что такие короткие элементы текста не могут нести особой семантической на­правленности. Поэтому возникает гипотеза, что вклады узлов начальных уров­ней АСД в оценки релевантности носят характер шума, и оценка релевантностистанет более адекватной, если ее очистить от вклада узлов начальных уровней.Для проверки этой гипотезы мы обнуляли частоты узлов на первом, втором ит.д.

уровнях.Обозначим очистку АСД от шума через ., где – вид шкалирующейфункции, а – уровень в АСД, до которого обнулялись частоты.46Размах АСДПод размахом АСД понимается среднее количество потомков у одного уз­ла. Чем больше цепочек в АСД, не имеющих разветвлений, тем меньше размахАСД.

Определим размах следующим образом:∑︀||,range() = ∈ | |где – множество узлов, у которых есть потомки (т.е. которые неявляются листьями). Так, например, размах АСД, показанного на Рис. 1.5 со­ставляет 1.18.АСД, построенные по разным коллекциям строк, могут отличаться междусобой по размаху.

Чем больше и разнообразнее коллекция строк, тем большеразмах соответствующего АСД.2.2.4Нормирование оценки релевантностиЧасто возникает потребность сравнить оценки сходства строк с двумя илиболее АСД. Получаемые оценки могут сильно зависеть от размаха АСД. Чембольше узлов в АСД, тем больше разброс оценок, получаемых при сличениистрок с этим деревом. Для того, чтобы сделать оценки по разным деревьямсравнимыми между собой, в формуле 2.5 введем нормирование на длину суф­фикса, а ?? – модифицируем так, чтобы нормировать результаты по длинестроки.

(node)∈ℎ ( (node ) )∑︀score(match( ,)) =| |∑︀relevance(,) = SCORE(,) =,(2.7) score(match( ,))||(2.8)В случае линейной в формуле 2.7 имеет смысл условной вероятности,приходящейся на одну букву суффикса в совпадении match. Это делает оцен­ки сравнимыми как по текстам, так и по словосочетаниям. Приведем пример47вычисления оценки релевантности. Оценка релевантности строки “dine” при ис­пользовании линейной шкалирующей функции АСД, изображенному на Рис 1.5равна, согласно вышеприведённому определению:0 + score(“′′ ,)/3 + score(“′′ ,)/2 + 0=relevance(,) =4( 49 ) + ( 16 ) 4/9 + 1/6=== 0.152442.2.5Распространение линейных алгоритмов построениясуффиксных деревьев на случай АСДОпределенное выше аннотированное суффиксное дерево, строго говоря,не является суффиксным деревом, поскольку не обладает одним из основныхсвойств суффиксных деревьев, приведенных в [59]. В суффиксном дереве у каж­дой внутренней вершины, отличной от корня, должно быть не менее двух детей,а в АСД в большом количестве присутствуют цепочки узлов, т.е.

узлы с един­ственным потомком. В [60] показано преобразование АСД, необходимые длявыполнения этого условия, а именно схлопывание вершин. Схлопывание вер­шин заключается в объединение каждой цепи узлов с единственным потомкомв одну вершину и переносе пометки на входящее в нее ребро. Метка ребра полу­чается конкатенацией символов, которыми были помечены узлы в цепи. Частотасамой вершины остается неизменной, так как у всех вершин в цепи она былаодинаковой.

Преобразовав таким образом исходное дерево, получим структуруданных, изображенную на Рис. 2.1 (АСД построено для строки ‘mining’).Реализованное таким образом АСД требует Θ(2 ) памяти из-за необ­ходимости хранить все метки ребер в явном виде. Если использовать приемсжатия дуговых меток, описанный в [60] получится снизить объем используе­мой деревом памяти до линейного относительно длин строк в коллекции. Приемсжатия дуговых меток заключается в том, чтобы хранить в каждом ребре толь­ко индексы начала и конца соответствующей подстроки, а не всю подстроку вявном виде.

Окончательный вид АСД после всех описанных оптимизаций пред­ставлен на Рис. 2.2.48Рисунок 2.1 — Оптимизация представления АСД. Схлопывание вершин для = “mining”Рисунок 2.2 — Оптимизация представления АСД. Сжатие меток для = “mining”49Значительное снижение объема используемой для хранения АСД памятипозволяет использовать асимптотически менее трудоемкие алгоритмы для по­строения АСД, чем наивный алгоритм, который был описан выше. Существуетцелый ряд линейных по времени алгоритмов построения обычных (неанноти­рованных) суффиксных деревьев. В [60] приведен обзор основных алгоритмов:алгоритмов П.

Вайнера (1973), Э. МакКрейга (1976) и Э. Стонена (1995). Ис­пользование этих алгоритмов для построение АСД становится возможным бла­годаря Свойству 1 АСД: сначала построим обычное суффиксное дерево, затем,во время обхода снизу, аннотируем его частотами. После несложной обработ­ки входных строк частоты листьев будут равны 1, а затем частоты узлов науровнях выше получаются как сумма частот потомков. Предобработка строкзаключается в добавлении уникального терминального символа в конец каж­дой строки.

Будем обозначать терминальные символы через $ . Таким образом,каждая подстрока, соответствующая одному из путей от корня до листа, встре­чается в исходном наборе строк только один раз. Приведем псевдокод такогоалгоритма построения АСД и покажем, что построение АСД осуществляетсяза линейное время.Algorithm 4 LinearConstruction(C)Вход: Коллекция фрагментов = 1 , . . . , Выход: Обобщенное АСД для 1. Построить ′ = 1 $1 , . . .

, $2. Построить обобщенное суффиксное дерево для коллекции ′ , используяалгоритм с линейной сложностью.for ∈ leaves( ) do3. do присвоить () ← 1end for4. Выполнить обход дерева снизу вверх; в каждом внутреннем узле при­∑︀своить () ← ∈ :()= ()Обход дерева требует времени, пропорционального числу вершин. Такимобразом, все шаги алгоритма выполняются за линейное время, и общая оценкаего трудоемкости составляет Θ(1 + · · · + ) или ( ).Заметим, что при представлении АСД, показанном на Рис. 2.2, необходимовидоизменить формулы 2.5 или 2.6:50∑︁score(match( ,)) =node∈match( (node)) + |match| − node(2.9)или (node)node∈match ( node )∑︀score(match( ,)) =|ℎ|+ |match| − ,(2.10)где |ℎ| – длина фактического совпадения в символах, – количе­ство узлов в совпадении.

Заметим, что при таком преобразования смысл обеихформул останется без изменения. В [60] приведен эксперимент, в ходе которогосравнивается эффективность обоих алгоритмов на стандартных тестовых кол­лекциях текстов. Показано, что, действительно, линейный алгоритм работаетбыстрее, чем наивный. Сложность линейного алгоритма по памяти не отли­чается от сложности наивного алгоритма, поскольку тем или иным образомприходится хранить в памяти одинаковое количество символов и их частот.2.2.6Построение таблицы релевантности «Строка – Текст»С помощью метода nAST-k построим таблицу релевантности «строка –текст» (РСТ таблица), в которой строки соответствуют отдельным входнымстрокам, столбцы – отдельным текстам, а элементы – оценки релевантностистрок соответствующим текстам. Основное отличие РСТ таблицы от традицион­ного построения матрица терм-текст, многократно использованного в учебниках[7] и [15], заключается в том, что РСТ таблица строится для зафиксированногомножества входных строк, а матрица терм–текст строится по термам, извле­ченным из текстов.

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

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