Алгоритм Ахо-Корасик на Haskell
Выложил в open source свою реализацию алгоритма Ахо-Корасик на Haskell. Код на GitHub. Пакет в HackageDB.
Алгоритм Ахо-Корасик — алгоритм поиска подстрок, созданный Альфредом Ахо и Маргарет Корасик в 1975 году. Этот алгоритм предназначен для одновременного поиска сразу большого количества подстрок. Алгоритм состоит из двух фаз: сначала строится конечный автомат по всем подстрокам которые нужно будет искать, и дальше через этот построенный автомат пропускается текст, в котором эти подстроки нужно найти.
Моя реализация обобщена для любых последовательностей значений, для которых реализован тайп-класс Hashable (т.е. искать можно не только строки, но и, скажем, последовательность из чисел).
Примеры использования
Самый простой вызов:
|
|
|
|
К искомым строкам можно привязать произвольные данные:
|
|
|
|
Созданный автомат можно запускать по шагам (если нужен поиск не по спискам, а по чему-нибудь другому):
|
|
|
|
Некоторые подробности реализации
Построение конечного автомата у меня сделано в монаде ST. Это монада используется, когда вам нужны вычисления с изменяемыми данными, но при этом никакой внешний мир не нужен (т.е. монады IO для вас слишком много), соответственно снаружи монады мы имеем чистый интерфейс, а внутри у нас есть мутабельные переменные и массивы. Там я написал простейшую FIFO очередь в этой монаде, можно почитать кому интересно.Сам поиск с использованием созданного автомата сделан уже в чистых функциях, это можно видеть в примерах выше.