Алгоритм Ахо Корасика

Я не могу понять приведенный ниже алгоритм, который используется для сопоставления строковых шаблонов с использованием алгоритма Aho-Corasick.

Procedure AC(y,n,q0)
INPUT: y<-array of m bytes representing the text input
(SQL Query Statement)
n<-integer representing the text length
(SQL Query Length)
q0<-initial state (first character in pattern)
2: State <-q0
3: For i = 1 to n do
4: While g ( State, y[i] = = fail) do
5: State ← f (State)
6: End While
7: State ← g(State,.y[i])
8: If o(State) ???? then
9: Output i
10: Else
11: Output
12: End If
13: End for
14: End Procedure

algorithm aho-corasick
person user2967440    schedule 02.12.2013    source источник
comment
Что такое f, g и o? Это похоже на общую реализацию конечного автомата, который обновляет текущее состояние на основе каждого нового введенного символа, а затем определяет, заканчивается ли строка состоянием принятия.   -  person chepner    schedule 02.12.2013
comment
Я сделал раздаточные материалы своей лекции об Ахо-Корасике доступными на Slideshare для всех, кому они могут быть полезны: slideshare.net/PekkaKilpelinen2/aho-corasicklecture   -  person Pekka Kilpeläinen    schedule 07.08.2018

Ответы (2)


arrow_upward
26
arrow_downward

Вы, вероятно, не получите хорошего понимания алгоритма Ахо-Корасика, прочитав немного псевдокода. Если вы не понимаете таблицу переходов состояний, алгоритм не будет иметь никакого смысла.

Есть достойное объяснение вместе с анимацией в реализация и анимация Aho-Corasick.

Исходный документ, Эффективное сопоставление строк: помощь в библиографическом поиске (PDF), хорошо написан и понятен, а примеры псевдокода довольно легко преобразовать в рабочий код. Это потребует небольшого изучения, но у вас должно быть хорошее понимание после того, как вы прочитаете статью, немного подумаете, а затем прочитаете ее снова.

person Jim Mischel    schedule 02.12.2013
comment
в чем преимущества алгоритма aho-corasick? - person user2967440; 02.12.2013
comment
Преимущество заключается в том, что он может сопоставлять несколько строк за один проход по большому объему текста, тогда как поиск строк по отдельности с использованием чего-то вроде поиска Бойера-Мура потребует нескольких проходов по тексту. Прочтите статью Википедии и ссылки, указанные в ней. - person Jim Mischel; 02.12.2013

arrow_upward
7
arrow_downward

Алгоритм Ахо-Корасик используется для решения проблемы сопоставления наборов. Это означает, что у нас есть набор строк S, и здесь идет длинная строка L, чтобы проверить, содержит ли L какую-либо строку в предыдущем наборе S.

Базовым решением является использование дерева trie, т. е. дерева префиксов, см. Википедию. Обычно есть два шага для решения проблемы.

  1. Предварительно вычислить дерево дерева на основе набора строк S;
  2. Отсканируйте строку L, чтобы проверить.

Дерево trie легко понять. Он хранит префиксные подстроки с узлами, начинающимися с корня.

Алгоритм Ахо-Корасика является расширением треугольного дерева, недалеко от основной идеи. Алгоритм Ахо-Корасика добавляет ошибочный указатель к каждому узлу дерева дерева.

В случае сбоя дерево дерева будет перезапущено с корня (добавьте начальный индекс к L на 1), но алгоритм Ахо-Корасика перезапустится с узла D, на который указывает сбойный указатель (добавьте начальный индекс к L на глубину дерева). узел Д).

Ниже приведена реализация алгоритма Ахо-Корасика на C++. Он содержит некоторые ошибки. http://www.komodia.com/aho-corasick

Я исправил найденные ошибки. И вы можете получить доступ к моей версии здесь: https://github.com/elfinhe/KomodiaAhoCorasick

person Tao HE    schedule 02.12.2013
comment
если бы этих алгоритмов не было, то что нам оставалось делать? - person user2967440; 03.12.2013