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

Март 15, 2012, 12:05

Вы­ло­жил в open source свою ре­а­ли­за­цию ал­го­рит­ма Ахо-Ко­рас­ик на Haskell. Код на GitHub. Па­кет в Hack­ageDB.

Ал­го­ритм Ахо-Ко­рас­ик — ал­го­ритм по­ис­ка под­строк, со­здан­ный Аль­фре­дом Ахо и Мар­га­рет Ко­рас­ик в 1975 году. Этот ал­го­ритм пред­на­зна­чен для од­но­вре­мен­но­го по­ис­ка сра­зу боль­шо­го ко­ли­че­ства под­строк. Ал­го­ритм со­сто­ит из двух фаз: сна­ча­ла стро­ит­ся ко­неч­ный ав­то­мат по всем под­стро­кам ко­то­рые нуж­но бу­дет ис­кать, и даль­ше че­рез этот по­стро­ен­ный ав­то­мат про­пус­ка­ет­ся текст, в ко­то­ром эти под­стро­ки нуж­но най­ти.

Моя ре­а­ли­за­ция обоб­ще­на для лю­бых по­сле­до­ва­тель­но­стей зна­че­ний, для ко­то­рых ре­а­ли­зо­ван тайп-класс Hash­able (т.е. ис­кать мож­но не толь­ко стро­ки, но и, ска­жем, по­сле­до­ва­тель­ность из чи­сел).

При­ме­ры ис­поль­зо­ва­ния

Са­мый про­стой вы­зов:

example1 = mapM_ print $ findAll simpleSM "ushers" where
simpleSM = makeSimpleStateMachine ["he","she","his","hers"]
Position {pIndex = 1, pLength = 3, pVal = "she"}
Position {pIndex = 2, pLength = 2, pVal = "he"}
Position {pIndex = 2, pLength = 4, pVal = "hers"}

К ис­ко­мым стро­кам мож­но при­вя­зать про­из­воль­ные дан­ные:

example2 = mapM_ print $ findAll sm "ushers" where
sm = makeStateMachine [("he",0),("she",1),("his",2),("hers",3)]
Position {pIndex = 1, pLength = 3, pVal = 1}
Position {pIndex = 2, pLength = 2, pVal = 0}
Position {pIndex = 2, pLength = 4, pVal = 3}

Со­здан­ный ав­то­мат мож­но за­пус­кать по ша­гам (если ну­жен по­иск не по спис­кам, а по чему-ни­будь дру­го­му):

example3 = mapM_ print $ next sm "ushers" where
sm = makeSimpleStateMachine ["he","she","his","hers"]
next _ [] = []
next sm (s:n) = let (SMStepRes match nextSM) = stateMachineStep sm s in
(s, match) : next nextSM n
('u',[])
('s',[])
('h',[])
('e',[(3,"she"),(2,"he")])
('r',[])
('s',[(4,"hers")])

Неко­то­рые по­дроб­но­сти ре­а­ли­за­ции

По­стро­е­ние ко­неч­но­го ав­то­ма­та у меня сде­ла­но в мо­на­де ST. Это мо­на­да ис­поль­зу­ет­ся, ко­гда вам нуж­ны вы­чис­ле­ния с из­ме­ня­е­мы­ми дан­ны­ми, но при этом ни­ка­кой внеш­ний мир не ну­жен (т.е. мо­на­ды IO для вас слиш­ком мно­го), со­от­вет­ствен­но сна­ру­жи мо­на­ды мы име­ем чи­стый ин­тер­фейс, а внут­ри у нас есть му­та­бель­ные пе­ре­мен­ные и мас­си­вы. Там я на­пи­сал про­стей­шую FIFO оче­редь в этой мо­на­де, мож­но по­чи­тать кому ин­те­рес­но.

Сам по­иск с ис­поль­зо­ва­ни­ем со­здан­но­го ав­то­ма­та сде­лан уже в чи­стых функ­ци­ях, это мож­но ви­деть в при­ме­рах выше.

Ссыл­ки по теме

Сергей Лымарь © 2005-2014, Все права защищены.