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

Наконец, последним этапом предварительной обработки является создание ссылок для случаев несовпадения для каждой вершины префиксного дерева и одновременное завершение создания выходной функции. Функция несовпадения ''fail'' определяется на вершинах следующим образом (w является вершиной): fail(w) = u, где u – самый длинный подходящий суффикс w, принадлежащий к <math>T(\mathcal{P})</math>. Вычисление ссылок для несовпадений выполняется в процессе обхода <math>T(\mathcal{P})</math> в ширину. Завершение выходной функции выполняется в ходе вычисления функции для несовпадения с использованием следующего правила: если <math>fail(w) = u</math>, то <math>out(w) = out(w) \cup out(u)</math>.

'''Теорема 1 (Ахо и Корасик [1]). После предварительной обработки <math>\mathcal{P}</math>, поиск вхождений строк из <math>\mathcal{P}</math> в тексте T может быть выполнен за время <math>O(n \times log \; \sigma)</math>. Время выполнения соответствующего этапа предварительной обработки составляет <math>O(|\mathcal{P}| \times log \; \sigma)</math>. Обе операции требуют дополнительной памяти в объеме <math>O(|\mathcal{P}|)</math>.'''

Алгоритм Ахо-Корасик, в сущности, представляет собой расширение алгоритма Морриса-Пратта для точного сравнения конечного множества строк.

Техника битового параллелизма может применяться для моделирования ОАГС-алгоритма. В результате получается алгоритм Наварро и Раффино MultiBNDM [7]. Эта стратегия эффективно работает в случае, когда <math>k \times \ell min</math> бит помещаются в нескольких машинных словах. Префиксы строк <math>\mathcal{P}</math> длины Imin упаковываются в один битовый вектор. После этого поиск выполняется так же, как в алгоритме точного сравнения строк BNDM, и осуществляется для всех префиксов в одно и то же время.