Ахо-Коразик алгоритам подударности ниски

Из Википедије, слободне енциклопедије

У рачунарству, Ахо-Коразик алгоритам за подударност ниски је алгоритам за претрагу ниски, измишљен од стране Алфреда В. Ахоа и Маргарет Ј. Корасик. То је алгоритам по принципу претраге речника који налази елементе коначног скупа ниски („речника“) у оквиру унетог текста. Врши симултано подударање шаблона. Теорија сложености израчунавања алгоритма је линеарна у дужини шаблона, плус дужини претраженог текста, плус броја подударности на излазу. Узмимо у обзир да, пошто су све подударности нађене, може бити квадратни број подударања ако је подударан сваки подстринг.

Алгоритам гради машину коначног стања која подсећа на дрво, са додатним везама између различитих унутрашњих чворова. Ове додатне унутрашње везе допуштају брзе прелазе између неуспелих поклапања шаблона(претрага за мачка у дрвету које не садржи мачка али садржи мачевалац не би успела на чвору са префиксом мач) и осталих грана које деле заједнички префикс. Ово омогућава аутоматизацију преласка између подударних шаблона без потребе за бектрекингом.

Када је речник шаблона познат унапред, конструкција аутомата може бити извршена офлајн и компајлирани аутомат сачуван за каснију употребу. У овом случају, његово време извршавања је линеарно у дужини улаза плус број подударних улаза.

Ахо-Коразик алгоритам за подударност стрингова засновао је базу оригиналне листе Јуникс програма.

Граф испод је Ахо-Коразик структура података, направљена из наведеног речника, са сваким редом у табели који представља чвор у стаблу, са путањом колона која указује на јединствен низ карактера из корена ка чвору.

Структура података има по један чвор за сваки префикс сваког стринга у речнику. Ако је (bca) у речнику онда ће постојати чворови за (bca), (bc), (b) и (). Постоји црна усмерена грана детета из сваког чвора до чвора чије име се добија надовезивањем једног карактера. Самим тим постоји црна грана од (bc) до (bca). Постоји плава усмерена суфикс грана од сваког чвора до чвора који је најдужи могући стриктни суфикс тог чвора у графу. На пример, за чвор (caa) стриктни суфикси су (aa), (a) и (). Најдужи од њих који постоји у графу је (a), тако да постоји плава грана од (caa) до (a). Постоји зелена грана речничког суфикса од сваког чвора до следећег чвора у речнику до ког се може доћи пратећи плаве гране. На пример, постоји зелена грана од (bca) до (a) због тога што је (a) први чвор у речнику (тзв. бели чвор) до кога се долази пратећи плаве гране до (ca), а онда до (a).

A diagram of the Aho-Corasick string search algorithm.svg
Речник {a, ab, bc, bca, c, caa}
Путања У речнику Суфикс Речнички суфикс
() -
(a) + ()
(ab) + (b)
(b) - ()
(bc) + (c) (c)
(bca) + (ca) (a)
(c) + ()
(ca) - (a) (a)
(caa) + (a) (a)

На сваком кораку, тренутни чвор се продужава тражећи своје дете, а ако оно не постоји, налазећи његово дете суфикс, а ако то не успе налазећи дете суфикс његовог суфикса итд. завршавајући на крају у корену ако ништа није виђено пре тога.

Када алгоритам дође до чвора, избацује све речничке улазе који се завршавају на тренутној позицији карактера у унетом тексту. Ово се ради штампањем сваког чвора до кога се дошло пратећи суфикс везе речника почевши од тог чвора, и настављајући све док се не дође до чвора који нема речничку суфикс везу. Као додатак, и тај чвор се штампа ако представља улаз у речник.

Извршење на улазном стрингу abccab повлачи следеће кораке:

Analysis of input string abccab
Node Remaining String Output:End Position Transition Output
() abccab   start at root
(a) bccab a:1 () to child (a) Current node
(ab) ccab ab:2 (a) to child (ab) Current node
(bc) cab bc:3, c:3 (ab) to suffix (b) to child (bc) Current Node, Dict suffix node
(c) ab c:4 (bc) to suffix (c) to suffix () to child (c) Current node
(ca) b a:5 (c) to child (ca) Dict suffix node
(ab) ab:6 (ca) to suffix (a) to child (ab) Current node

Литература[уреди]

  • Aho, Alfred V.; Margaret J. Corasick (June 1975). „Efficient string matching: An aid to bibliographic search“. Communications of the ACM 18 (6): 333–340. DOI:10.1145/360825.360855.  (Access to the full text may be restricted.)

Спољашње везе[уреди]