Рубрики

Поиск по шаблону с использованием дерева суффиксов

Учитывая текст txt [0..n-1] и шаблон pat [0..m-1], напишите функцию поиска (char pat [], char txt []), которая печатает все вхождения pat [] в txt. []. Вы можете предположить, что n> m.

Шаблон предварительной обработки или текст предварительной обработки?
Мы обсуждали следующие алгоритмы в предыдущих постах:

Алгоритм КМП
Алгоритм Рабина Карпа
Алгоритм на основе конечных автоматов
Алгоритм Бойера Мура

Все вышеперечисленные алгоритмы предварительно обрабатывают шаблон, чтобы ускорить поиск шаблона. Наилучшая временная сложность, которую мы могли бы получить с помощью шаблона предварительной обработки, — это O (n), где n — длина текста. В этом посте мы обсудим подход, который предварительно обрабатывает текст. Суффиксное дерево строится из текста. После предварительной обработки текста (построение дерева суффиксов текста) мы можем искать любой шаблон за O (m) время, где m — длина шаблона.
Представьте, что вы сохранили полную работу Уильяма Шекспира и предварительно обработали ее. Вы можете искать любую строку во всей работе во времени, пропорциональном длине шаблона. Это действительно большое улучшение, потому что длина шаблона, как правило, намного меньше, чем текст.
Предварительная обработка текста может стать дорогостоящей, если текст часто меняется. Это хорошо для фиксированного текста или реже меняющегося текста.

Дерево суффиксов для данного текста — это сжатый набор для всех суффиксов данного текста . Мы обсуждали стандартное три . Давайте разберемся с Compressed Trie со следующим набором слов.

{bear, bell, bid, bull, buy, sell, stock, stop}

Ниже приведено стандартное слово для указанного выше набора слов.

Ниже приводится сжатый файл. Сжатие Trie получается из стандартного Trie путем объединения цепочек из отдельных узлов. Узлы сжатого дерева могут быть сохранены путем сохранения диапазонов индексов на узлах.

Как построить дерево суффиксов для данного текста?
Как обсуждалось выше, Suffix Tree — это сжатый набор всех суффиксов, поэтому ниже приведены очень абстрактные шаги для построения дерева суффиксов из заданного текста.
1) Генерация всех суффиксов данного текста.
2) Рассмотрите все суффиксы как отдельные слова и создайте сжатый текст.

Давайте рассмотрим пример текста «банан / 0», где «/ 0» — символ завершения строки. Ниже приведены все суффиксы «банан / 0»

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

Если мы рассмотрим все вышеприведенные суффиксы как отдельные слова и построим дерево, мы получим следующее.

Если мы объединяем цепочки из отдельных узлов, мы получаем следующий сжатый файл, который представляет собой суффиксное дерево для данного текста «банан / 0»

Обратите внимание, что описанные выше шаги предназначены только для создания суффиксного дерева вручную. Мы будем обсуждать фактический алгоритм и реализацию в отдельном посте.

Как искать шаблон во встроенном дереве суффиксов?
Выше мы обсуждали, как построить Суффикс-дерево, которое необходимо в качестве шага предварительной обработки при поиске по шаблону. Ниже приведены абстрактные шаги для поиска шаблона во встроенном дереве суффиксов.
1) Начиная с первого символа шаблона и корня дерева суффиксов, выполните следующие действия для каждого символа.
… .. a) Для текущего символа шаблона, если есть ребро из текущего узла дерева суффиксов, следуйте за ребром.
… .. б) Если края не заданы, выведите «образец не существует в тексте» и вернитесь.
2) Если все символы шаблона были обработаны, т. Е. Есть путь от корня для символов данного шаблона, выведите «Pattern found».

Давайте рассмотрим пример шаблона как «nan», чтобы увидеть процесс поиска. Следующая диаграмма показывает путь для поиска «nan» или «nana».

Как это работает?
Каждый шаблон, который присутствует в тексте (или мы можем сказать каждую подстроку текста), должен быть префиксом одного из всех возможных суффиксов. Это утверждение кажется сложным, но это простое утверждение, нам просто нужно взять пример, чтобы проверить его достоверность.

Приложения Суффикс Дерева
Суффикс-дерево можно использовать для решения широкого круга задач. Ниже приводятся некоторые известные проблемы, когда деревья суффиксов обеспечивают оптимальное решение по сложности времени.
1) Поиск по шаблону
2) Нахождение самой длинной повторяющейся подстроки
3) Нахождение самой длинной общей подстроки
4) Нахождение самого длинного палиндрома в строке

Есть еще много приложений. Смотрите это для более подробной информации.

Построение дерева суффиксов Укконена обсуждается в следующих статьях:
Построение суффикс-дерева Укконена — часть 1
Построение Суффикса Укконена — Часть 2
Построение Суффикса Укконена — Часть 3
Построение суффикс-дерева Укконена — часть 4
Построение Суффикса Укконена — Часть 5
Построение Суффикса Укконена — Часть 6

Ссылки:
http://fbim.fh-regensburg.de/~saj39122/sal/skript/progr/pr45102/Tries.pdf
http://www.cs.ucf.edu/~shzhang/Combio12/lec3.pdf
http://www.allisons.org/ll/AlgDS/Tree/Suffix/

Рекомендуемые посты:

Поиск по шаблону с использованием дерева суффиксов

0.00 (0%) 0 votes