Аноним

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

Материал из WEGA
 
(не показаны 3 промежуточные версии 1 участника)
Строка 18: Строка 18:




Наконец, последним этапом предварительной обработки является создание ссылок для случаев несовпадения для каждой вершины префиксного дерева и одновременное завершение создания выходной функции. Функция несовпадения ''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>.
Наконец, последним этапом предварительной обработки является создание ссылок для случаев несовпадения для каждой вершины префиксного дерева и одновременное завершение создания выходной функции. Функция несовпадения ''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>.




Строка 32: Строка 32:




'''Теорема 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>.'''
'''Теорема 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>.'''




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




Строка 55: Строка 55:




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




Строка 61: Строка 61:




Алгоритм Ву и Манбера [11] рассматривает блоки длины <math>\ell</math>. Блоки такой длинны хэшируются при помощи функции h в значения меньше ''maxvalue''. Значение функции сдвига ''shift''[h(B)] определяется как минимальное значение из <math>|P^i| - j</math> и <math>\ell min - \ell + 1</math> с <math>B = p^i_{j - \ell + 1}...p^i_j</math> для <math>1 \le i \le k</math> и <math>1 \le j \le |P^i|</math>. Значение <math>\ell</math> варьируется в зависимости от минимальной длины строк в <math>\mathcal{P}</math> и размера алфавита. Значение ''maxvalue'' варьируется в зависимости от объема доступной памяти.
Алгоритм Ву и Манбера [11] рассматривает блоки длины <math>\ell</math>. Блоки такой длинны хэшируются при помощи функции h в значения меньше ''maxvalue''. Значение функции сдвига ''shift''[h(B)] определяется как минимальное значение из <math>|P^i| - j</math> и <math>\ell min - \ell + 1</math>, положив <math>B = p^i_{j - \ell + 1}...p^i_j</math> для <math>1 \le i \le k</math> и <math>1 \le j \le |P^i|</math>. Значение <math>\ell</math> варьируется в зависимости от минимальной длины строк в <math>\mathcal{P}</math> и размера алфавита. Значение ''maxvalue'' варьируется в зависимости от объема доступной памяти.




На этапе поиска этого алгоритма производится чтение блоков B длины <math>\ell</math>. Если shift[h(B)] > 0, то выполняется сдвиг на длину shift[h(B)]. В противном случае при shift[h(B)] = 0 шаблоны, оканчивающиеся на блок B, проверяются в тексте один за другим. Первым сканируется блок <math>t_{\ell mjn - \ell + 1} ... t_{\ell mjn}</math>. Данный метод встроен в команду agrep [10].
На этапе поиска этого алгоритма производится чтение блоков B длины <math>\ell</math>. Если shift[h(B)] > 0, то выполняется сдвиг на длину shift[h(B)]. В противном случае при shift[h(B)] = 0 шаблоны, оканчивающиеся на блок B, проверяются в тексте один за другим. Первым сканируется блок <math>t_{\ell min - \ell + 1} ... t_{\ell min}</math>. Данный метод встроен в команду agrep [10].


== Применение ==
== Применение ==
Строка 105: Строка 105:


11. Wu, S., Manber, U.: A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ (1994)
11. Wu, S., Manber, U.: A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ (1994)
[[Категория: Совместное определение связанных терминов]]