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

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

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

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

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

Теорема 2 (Крочмор и др., [ ]). Алгоритм сравнения с помощью ОАГС выполняет не более 2n сравнений символов. Предполагая, что сумма длин шаблонов в <math>\mathcal{P}</math> меньше lmink, алгоритм сравнения с помощью ОАГС производит в среднем O((n\oglmin)/lmin) проверок символов текста.

Узким местом ОАГС-алгоритма является объем времени и памяти, затрачиваемых на построение точной индексной структуры. Этого можно избежать, заменив точную индексную структуру оракулом фактора для множества строк. При использовании только оракула фактора получается алгоритм сопоставления с обращенным оракулом множества (Set Backward Oracle Matching, SBOM). Этот точный алгоритм демонстрирует почти такое же хорошее поведение, как и алгоритм сравнения с помощью ОАГС.

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