Ејхо—Корасикин алгоритам
У рачунарству, Ејхо—Корасикин алгоритам за подударност ниски је алгоритам за претрагу ниски који су измислили Алфред Вејно Ејхо и Маргарет Џ. Корасик.[1] То је алгоритам по принципу претраге речника који налази елементе коначног скупа ниски („речника“) у оквиру унетог текста. Врши симултано подударање шаблона. Теорија сложености израчунавања алгоритма је линеарна у дужини шаблона, плус дужини претраженог текста, плус броја подударности на излазу. Узмимо у обзир да, пошто су све подударности нађене, може бити квадратни број подударања ако је подударан сваки подстринг.
Алгоритам гради машину коначног стања која подсећа на дрво, са додатним везама између различитих унутрашњих чворова. Ове додатне унутрашње везе допуштају брзе прелазе између неуспелих поклапања шаблона(претрага за мачка у дрвету које не садржи мачка али садржи мачевалац не би успела на чвору са префиксом мач) и осталих грана које деле заједнички префикс. Ово омогућава аутоматизацију преласка између подударних шаблона без потребе за бектрекингом.
Када је речник шаблона познат унапред, конструкција аутомата може бити извршена офлајн и компајлирани аутомат сачуван за каснију употребу. У овом случају, његово време извршавања је линеарно у дужини улаза плус број подударних улаза.
Ејхо—Корасикин алгоритам за подударност стрингова засновао је базу оригиналне листе Јуникс програма.
Граф испод је Ејхо—Корасикина структура података, направљена из наведеног речника, са сваким редом у табели који представља чвор у стаблу, са путањом колона која указује на јединствен низ карактера из корена ка чвору.
Структура података има по један чвор за сваки префикс сваког стринга у речнику. Ако је (bca) у речнику онда ће постојати чворови за (bca), (bc), (b) и (). Постоји црна усмерена грана детета из сваког чвора до чвора чије име се добија надовезивањем једног карактера. Самим тим постоји црна грана од (bc) до (bca). Постоји плава усмерена суфикс грана од сваког чвора до чвора који је најдужи могући стриктни суфикс тог чвора у графу. На пример, за чвор (caa) стриктни суфикси су (aa), (a) и (). Најдужи од њих који постоји у графу је (a), тако да постоји плава грана од (caa) до (a). Постоји зелена грана речничког суфикса од сваког чвора до следећег чвора у речнику до ког се може доћи пратећи плаве гране. На пример, постоји зелена грана од (bca) до (a) због тога што је (a) први чвор у речнику (тзв. бели чвор) до кога се долази пратећи плаве гране до (ca), а онда до (a).
| Путања | У речнику | Суфикс | Речнички суфикс |
|---|---|---|---|
| () | - | ||
| (a) | + | () | |
| (ab) | + | (b) | |
| (b) | - | () | |
| (bc) | + | (c) | (c) |
| (bca) | + | (ca) | (a) |
| (c) | + | () | |
| (ca) | - | (a) | (a) |
| (caa) | + | (a) | (a) |
На сваком кораку, тренутни чвор се продужава тражећи своје дете, а ако оно не постоји, налазећи његово дете суфикс, а ако то не успе налазећи дете суфикс његовог суфикса итд. завршавајући на крају у корену ако ништа није виђено пре тога.
Када алгоритам дође до чвора, избацује све речничке улазе који се завршавају на тренутној позицији карактера у унетом тексту. Ово се ради штампањем сваког чвора до кога се дошло пратећи суфикс везе речника почевши од тог чвора, и настављајући све док се не дође до чвора који нема речничку суфикс везу. Као додатак, и тај чвор се штампа ако представља улаз у речник.
Извршење на улазном стрингу 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 (1975). „Efficient string matching: An aid to bibliographic search”. Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855.
Спољашње везе
[уреди | уреди извор]- Set Matching and Aho–Corasick Algorithm, lecture slides by Pekka Kilpeläinen
- Aho–Corasick entry in NIST's Dictionary of Algorithms and Data Structures
- Aho–Corasick string matching in C#, a CodeProject tutorial by Tomáš Petříček
- Aho-Corasick string matching in PHP, optimized for terms-filtering
- Aho-Corasick C implementation
- Aho-Corasick Python wrapper
- Aho-Corasick Java implementation
- Animated Aho-Corasick, an animated implementation of Aho-Corasick for learning purposes