Диссертация (1137276), страница 6
Текст из файла (страница 6)
Для начала разобьем весь текст на строки: одиночные словаили последовательные пары или тройки слов. Найдем все возможные подстроки строк и определим их частоты в исходном тексте. Это и будет итоговойтеоретико-множественной моделью представления текста.Вычисление частоты каждой подстроки данной совокупности строк требует как минимум квадратичного от числа подстрок времени. Для произвольногодостаточно большого текста такой перебор будет малоэффективным.
Следовательно, возникает необходимость в использование эффективной структуры данных для поиска всех возможных фрагментов строк и их частот. Такой структурой является аннотированное суффиксное дерево. Прежде чем определятьданную структуру и ее свойства, совершим исторический экскурс в областьсуффиксных деревьев вообще.Суффиксные деревья были предложены в статье [53] в качестве средствадля поиска нечетких совпадениях между строками.
Суффиксные деревья получили широкое распространение в биоинформатике, где они используются, восновном, для поиска закономерностей в ДНК или в белках, которые записаны длинной последовательностью символов [54]. Иногда суффиксные деревьяиспользуются для индексации текстов и организации словарей [55] и реже – вкачестве моделей представления текста. Впервые суффиксные деревья в качестве модели представления текстовой коллекции были предложены в [4], гдесуффиксное дерево, построенное по коллекции текстов послужило основой дляпоиска кластеров – т.е.
групп – близких по смыслу текстов. Структура суффиксного дерева, использованного в [4] несколько отличалась от классическогоопределения суффиксного дерева, и предполагала определенный способ аннотирования суффиксного дерева порядковыми номерами текстов в коллекции,в результате чего стало возможным использование суффиксного дерева дляпоиска кластеров в коллекции текстов. Другие работы, в которых суффиксныедеревья использованы в качестве модели представления коллекции текстов, также предполагают тот или иной способ аннотирования дерева номерами текстовили частотами [56—58].Согласно [59], суффиксное дерево для -символьной строки представляет собой ориентированное дерево с корнем, имеющее ровно листьев, занумерованных от 1 до .
Каждая внутренняя вершина, отличная от корня, имеет неменьше двух детей, а каждая строка помечена непустой подстрой строки . Ни27Рисунок 1.1 — Суффиксное дерево для строки = xabxac [59]какие две дуги, выходящие из одной и той же вершины, не могут иметь пометок,начинающихся с одного и того же символа. Главная особенность суффиксногодерева заключается в том, что для каждого листа конкатенация меток дугна пути от корня к листу составляет / произносит / кодирует / прочитываетсуффикс строки , который начинается в позиции , то есть, [ : ].Там же приводится пример суффиксного дерева для строки = “xabxac”(Рис. 1.1).Путь до листа 1 прочитывает первый суффикс строки [1 : 6] = “xabxac”,совпадающий с исходной строкой, путь до листа 2 – второй суффикс строки[2 : 6] = “abxac”, путь до листа 3 – третий суффикс строки [3 : 6] = “bxac”,путь до листа 4 – второй суффикс строки [4 : 6] = “xac”, путь до листа 5 –второй суффикс строки [5 : 6] = “ac”.
Путь до листа 6 прочитывает последнийшестой суффикс [6 : 6] = “c”. В таком дереве всего две внутренние вершины:они помечены буквами “u”, “v”. Заметим, что с точки зрения частотного анализа,наличие внутренних вершин в таком суффиксом дереве означает, что путь откорня до внутренней вершины прочитывает повторяющийся фрагмент строки.Так, фрагмент “xa” встречается в строке = “xabxac” дважды: [1 : 2] = [4 :5]“xa”, аналогично меньший фрагмент “a” встречается в строке = “xabxac”дважды: [2] = [5] = “a”. Тем не менее, такое представление суффиксногоне дерева не позволяет учитывать сколько именно раз встречается во входнойстроке повторяющийся фрагмент.Представленное на Рис.
1.2 суффиксное дерево построено по двум строкам 1 = xabxac, 2 = babxba. Каждому листу в нем приписана своя метка –одна или две пары чисел: первое число в паре означает номер строки, второе– номер суффикса. Символ “$” использован в качестве терминального и добавлен к концу каждой строки. Использование терминального символа позволяет28Рисунок 1.2 — Суффиксное дерево для двух строк 1 = xabxac, 2 = babxba[59]различать листы и промежуточные вершины Не трудно убедиться, что пути откорня до внутренних вершин кодируют фрагменты, повторяющиеся во входныхстроках. Так, например, фрагмент “a” встречается во входных строках четырераза: дважды в качестве последнего суффикса строк – 1 [5], 2 [6] и дваждыв качестве префикса суффиксов 1 [2 : 5], 2 [2 : 6]. Заметим, что количествоповторений фрагмента “a” можно установить по количеству меток у листьев,которые покрывает соответствующая внутренняя вершина.Естественным развитием модели суффиксного дерева представляется модель аннотированного суффиксного дерева (АСД), в которой частоты всехфрагментов присутствуют явно [5].
В этой работе аннотированное суффиксноедерево определяется как суффискное дерево, в котором:– Символы стоят не на ребрах, а в узлах;– Каждому узлу соответствует один символ;– Каждый узел помечен частотой фрагмента, который прочитывает путьот корня до этого узла;– Опущены терминальные символы и метки листьев, представляющие номер суффикса и входной строки.По аналогии с [59] построим АСД для строки = “xabxac” Рис. 1.3.У этой строки шесть суффиксов: [1 : 6] = “xabxac” – этому суффиксу соответствует цепочка узлов, помеченная буквой A, [2 : 6] = “abxac”– B, [3 : 6] = “bxac” – C, [4 : 6] = “xac” – D, [3 : 6] = “ac” – E,[6 : 6] = “c” – F.
Фрагменты “xa”, “a” входной строки = “xabxac” встречаются дважды: [1 : 2] = [4 : 5] = “xa”, поэтому частоты соответствующим их29Рисунок 1.3 — Аннотированное суффиксное дерево для строки = “xabxac”узлов составляют 2, а частоты остальных узлов равны 1, поскольку они представляют уникальные фрагменты строки. Продолжая аналогию с [59] построимобобщенное суффиксное дерево для двух строк 1 = “xabxac” , 2 = “babxac”.За исключением первого суффиксы этих строк совпадают: 1 =“xabxac” ̸= 2 = “babxac”. Эти несовпадающие суффиксы представленыцепочками узлов A и G.
Частоты почти всех узлов в этих строках составляют 1. От 1 отличаются только частоты первых узлов этих цепочек “xa”, “b”,поскольку они встречаются по 3 раза во входных строках. Остальные суффиксы представлены такими же узлами, как на Рис. 1.4, но с удвоеннымичастотами.В [59] показаны два важных свойства АСД:Свойство 1. Частота любого узла равна сумме частот его узлов-детей,так как родительский узел соответствует префиксу нескольких суффиксов иего частота складывается из частот этих суффиксов. Отсюда же следует другоесвойство АСД.Свойство 2. Частота родительского узла равна сумме частот листьев,которые он покрывает.30Рисунок 1.4 — Обобщенное аннотированное суффкисное дерево для строк1 = “xabxac”, 2 = “babxac”Рассмотрим алгоритм суффиксного дерева и его адаптацию на случайаннотированного суффиксного дерева.1.5.1Наивный алгоритм построения суффиксного дереваПусть на вход поступает строка из символов , по которой требуетсяпостроить суффиксное дерево.
Следуя [59], поместим сначала в дерево простуюдугу для первого суффикса [1 : ]$, затем последовательно добавим в растущее дерево суффиксы [ : ]$, 2 ≤ ≤ .31Algorithm 1 Наивный алгоритм построения аннотированного суффиксногодереваВход: строка Выход: АСД для строки Инициализация: создаем пустую структуру, в которой будет храниться АСД.Обозначим ее astfor ∈ {2, } doДля суффикса [ : ] найти в ast совпадение match – самый длинныйпуть от корня, метки в котором совпадают с префиксом [ : ] . Такойпуть будет единственным, так как никакие две дуги, выходящие из однойвершины, не могут иметь одинаковых меток.
Пусть совпадение найдено.Тогдаif |match | = |[ : ]| – длина совпадения совпадает с длиной текущегосуффикса, то есть, текущий суффикс целиком присутствует в дереве thenАлгоритм останавливается в листе c меткой [], к которой ведет путьmatch , частоты всех узлов в найденном совпадении увеличиваются на 1.elseДлина совпадения меньше длины суффикса: |match | < |[ : ]|. Тогдаувеличим на 1 частоту всех узлов в совпадении, а к последнему совпавшему узлу = [|match |] добавим цепочку узлов [|match | : ] счастотами 1. Если совпадения не найдено = 0, поступаем аналогичнымобразом, считая корнем дерева и создавая новую цепочку от корняast.end ifend for321.5.2Построение аннотированного суффиксного дерева на основеразбиения текста на фрагментыДля построения аннотированного суффиксного дерева разобьём текст настроки: несколько (например, три) последовательно идущих слова в тексте.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
