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

Первое решение задачи сравнения нескольких строк заключается в применении алгоритма точного сравнения строк для локализации каждого шаблона в <math>\mathcal{P}</math>. Сложность этого алгоритма составляет O(kn) в наихудшем случае. Существуют более эффективные решения, основанные на двух подходах. Первый подход, предложенный Ахо и Корасик [ ], представляет собой расширение алгоритма сравнения с одним шаблоном с помощью конечного автомата. Второй подход, реализованный Комменц-Уолтер [ ], расширяет алгоритм Бойера-Мура на случай нескольких шаблонов.

Алгоритм Ахо-Корасик вначале строит [[trie|префиксное дерево]] <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>.