Aho-Corasick и правильные подстроки - PullRequest
Новая
       33

Aho-Corasick и правильные подстроки

6 голосов
/ 22 марта 2011

Я пытаюсь понять алгоритм совпадения строк aho-corasick.Предположим, что наши шаблоны abcd и bc.В итоге получается дерево, подобное этому 

       []
       /\
    [a]..[b]
    /  :  |
   [b].: [c]
    |     :
   [c].....
    |
   [d]

Пунктирная линия показывает функцию сбоя.

Теперь предполагается, что мы вводим строку abcd.Это будет следовать за деревом и обнаруживать совпадение «abcd», однако, насколько я могу судить, совпадение bc не будет сообщено.Я неправильно понимаю алгоритм?

Ответы [ 3 ]

3 голосов
/ 22 марта 2011

Вы должны пометить узлы как real_final, если в этом узле заканчивается строка. В вашем примере такими узлами являются «abcd» и «bc». После этого вы должны вычислить конечные состояния для узлов: узел является конечным, если он действительно_финальный, или функция узла по ошибке является конечной. Таким образом, «abcd», «bc» и «abc» будут окончательными.

Другими словами - узел является конечным, если какой-то шаблон завершен здесь, или какой-то последний узел повторно подключается из текущего узла, проходящего по ошибочным ссылкам.

3 голосов
/ 22 марта 2011

Артем ответил правильно, но, возможно, не очень ясно.По сути, вам нужно: каждый раз, когда вы приходите на новый узел, изучите весь путь, начиная с этого узла и состоящий из ссылок на ошибки, и найдите совпадения на этом пути.(Это не меняет вашу текущую позицию).В вашем примере вы изучите пути b-> b (совпадений не найдено) и c-> c (совпадение bc найдено).

Обратите внимание, что из соображений эффективности необходимо кэшировать значение «следующего соответствия» на каждом узле.То есть, если вы исследуете путь, начинающийся в узле u, и после нескольких шагов находите соответствующий узел v, запомните значение next_match[u] = v, чтобы в следующий раз, когда вам понадобилось исследовать этот путь, вы могли сделать один прыжокпрямо на v.

0 голосов
/ 22 марта 2011

Часть настройки дерева AhoCorasick - это установка указателей, которые сообщают вам, куда идти в дереве, если следующий символ не совпадает. Например. если вы следуете последовательности abcq в дереве, как вы его нарисовали, вам нужно перейти с позиции abc в позицию bc, чтобы увидеть, есть ли q ниже bc. Вы можете использовать этот проход для установки другого набора указателей, чтобы он сообщал о совпадении на bcd после сигнализации о совпадении по abcd и т. Д.

При написании этого я нашел источник sgrep в http://www.cs.helsinki.fi/~jjaakkol/sgrep.html очень полезным. Насколько я помню, sgrep делает намного больше, чем просто AhoCorasick, но имеет в своем составе реализацию AhoCorsick.

...