Последовательное сравнение нескольких строк: различия между версиями

Алгоритм Ахо-Корасик вначале строит бор <math>T(\mathcal{P})</math> – цифровое дерево, распознающее шаблоны <math>\mathcal{P}</math>. Бор <math>T(\mathcal{P})</math> представляет собой дерево, ребра которого помечены буквами, а вдоль ветвей можно прочесть шаблоны <math>\mathcal{P}</math>. Вершина p бора <math>T(\mathcal{P})</math> ассоциируется с уникальным словом w, «написанным» по пути в <math>T(\mathcal{P})</math>, ведущему из его корня в p. Сам корень идентифицируется с пустым словом ". Заметим, что если w является вершиной в <math>T(\mathcal{P})</math>, то w является префиксом некоторого шаблона Pi 2 P. Если вдобавок к этому 2 £, то child(w, a) совпадает с wa, если wa является вершиной в <math>T(\mathcal{P})</math>, и равно NIL в противном случае.

На втором этапе, когда шаблоны добавляются к бору, алгоритм инициализирует выходную функцию out. Он ассоциирует одноэлементное множество {Pi} с вершинами Pi (1 < i < k) и пустое множество – со всеми другими вершинами <math>T(\mathcal{P})</math>.

Чтобы избежать возвратов по ссылкам для несовпадений при вычислении этих ссылок, а также для обхода символов текста, для которых не был определен переход от корны на этапе поиска, к корню бора добавляется цикл для этих символов. В результате получаем механизм поиска совпадений с шаблонами или конечный автомат Ахо-Корасик (см. рис. 1).

Комменц-Уолтер [ ] обобщила алгоритм точного сравнения строк Бойера-Мура для случая нескольких строк. Ее алгоритм строит бор для обращенных шаблонов в <math>\mathcal{P}</math> вместе с двумя таблицами сдвига и применяет стратегию сканирования справа налево. Однако он довольно сложен в реализации и имеет квадратичную временную сложность в наихудшем случае.

Алгоритм сравнения с помощью ОАГС (DAWG) является обобщением алгоритма BDM для точного сравнения строк. Он включает построение точной индексной структуры для обращенных строк <math>\mathcal{P}</math>, такой как фактор-автомат или обобщенное суффиксное дерево, вместо протого бора, как в предыдущем варианте (см. рис. 2). Алгоритм в целом может быть сделан оптимальным за счет использования как индексной структуры для обращенных шаблонов, так и конечного автомата Ахо-Корасик для шаблонов. Поиск в этом случае включает сканирование некоторых фрагментов текста слева направо, а некоторых – справа налево. Это позволяет пропускать большие фрагменты текста T.