Algoritmus Aho - Korasik

Az Aho-Korasik algoritmus egy részkarakterlánc- kereső algoritmus , amelyet Alfred Aho és Margaret Korasik fejlesztett ki 1975-ben [1] , amely egy adott karakterláncban lévő szótárból keres alsztringeket .

Széles körben használják a rendszerszoftverekben, mint például a grep [2] kereső segédprogramban .

Hogyan működik

Az algoritmus létrehoz egy állapotgépet , amelyhez továbbítja a keresési karakterláncot. Az automata egyenként fogadja a karakterlánc összes karakterét, és a megfelelő élek mentén mozog. Ha az automata elérte a végső állapotot, akkor a megfelelő szótári karakterlánc megtalálható a keresési karakterláncban.

Több keresési karakterlánc kombinálható egy keresési fává, az úgynevezett bórfává (előtagfa). A Bor egy állapotgép, amely egy sort felismer - de azzal a feltétellel, hogy a sor eleje ismert. $m$

Az algoritmus első feladata, hogy megtanítsa az automatát arra, hogy „helyreállítsa magát”, ha a részkarakterlánc nem egyezik. Ugyanakkor az automata kiindulási állapotba állítása nem megfelelő betűk esetén nem megfelelő, mivel ez egy részkarakterlánc kihagyásához vezethet (például egy karakterlánc keresésekor a aababkövetkezővel találkozik , az ötödik karakter beolvasása után a automata a kezdeti állapotába egy részkarakterlánc kihagyásához vezet – helyes lenne állapotba lépni , majd újra feldolgozni az ötödik karaktert). Ahhoz, hogy az automata öngyógyító legyen, az üres ⌀ szimbólummal töltött utótag hivatkozásokat adják hozzá (így a determinisztikus automata nem determinisztikussá válik). Például, ha a karakterlánc elemzett , akkor a , , utótagok . Az utótag hivatkozás egy olyan csomópontra mutató hivatkozás, amely megfelel a leghosszabb utótagnak, amely nem vezeti a furatot zsákutcába (ebben az esetben ). aabaababaaabaababaaa

A gyökércsomópont esetében az utótag hivatkozása egy hurok. A többire a szabály a következő: ha az utolsó felismert karakter , akkor a szülő utótag hivatkozása kikerül, ha onnan van egy ív betöltött a karakterrel, akkor az utótag hivatkozás arra a csomópontra irányul, ahol ez az ív vezet. Ellenkező esetben az algoritmus újra és újra bejárja az utótag hivatkozást, amíg vagy áthalad a gyökérhurok hivatkozáson, vagy meg nem talál egy szimbólummal töltött ívet . $c$ $c$ $c$

* ···Ø···> * ···Ø···> * ···Ø···> * | | c c ↓ ↓ [*] Ø Ø új utótag hivatkozás

Ez az automata nem determinisztikus. Egy nem-determinisztikus véges automata determinisztikussá alakítása általában a csúcsok számának jelentős növekedéséhez vezet. De ez az automata determinisztikus automatává alakítható anélkül, hogy új csúcsokat hoznánk létre: ha egy csúcsnak nincs hova mennie a szimbólum mellett, újra és újra végigmegyünk az utótag hivatkozáson, amíg vagy el nem találjuk a gyökért, vagy van hova menni. szimbólum által . $v$ $c$ $c$

Kényelmes minden meghatározást rekurzívan elvégezni. Például egy utótag hivatkozáshoz:

alg sufflink(v) ha v.cacheSuffRef ≠ Ø // gyökér esetén, kezdetben root.cacheSuffRef = root return v.cacheSuffReference u := v.szülő c := v.szimbólum ismétlés u := SuffReference(u) előtt (u = gyök) vagy (van egy u --c→ w útvonal) ha van átmenet u —c→ w majd v.cacheSuffref := w egyébként v.cacheSuffReference := root return v.cacheSuffReference

A meghatározás növeli a végcsúcsok számát: ha egy csúcsból az utótag hivatkozások a végcsúcshoz vezetnek , akkor azt is végnek nyilvánítják. Ehhez úgynevezett véghivatkozásokat hoznak létre: a véglink az utótaghivatkozásokhoz legközelebbi végcsomóponthoz vezet; a záró hivatkozások bejárása az összes egyező sort visszaadja. $v$ $u$ $v$

alg OutputResult(v, i) nyomtatás "Found" + v.needle + " at position " + (i - v.depth + 1) alg MainPartSearch állapot := gyökér hurok i=1..|szénakazal| állapot := Átmenet(állapot, szénakazal[i]); ha állapot.tű ≠ Ø Kimeneti Eredmény(állapot, i) timeStat := állapot míg FinalRef(timeConst) ≠ Ø tempst := EndRef(timestst); OutputResult (TimeConst, i)

Az automatában lévő utótag és vég hivatkozások már a keresési fázisban szükség szerint kiszámíthatók. Oldalátmenetek - gyorsítótárazás nélkül a helyszínen számolhat, minden csomóponthoz gyorsítótárazhat, a legfontosabbakhoz megteheti (mindez nem befolyásolja az algoritmus aszimptotikus becslését).

Számítási összetettség

Az algoritmus számítási bonyolultsága az adatok szerveződésétől függ. Például:

Ha az automata ugrótáblázata indextömbként van tárolva - memóriafelhasználás , számítási összetettség , ahol - a szöveg hossza, amelyben a keresést végezzük, - a szótárban található összes szó teljes hossza, - az ábécé mérete, - az összes mérkőzés teljes hossza. $O(n\sigma )$ $O(n\sigma +H+k)$ $H$ $n$ $\sigma$ $k$
Ha az automata átmeneti tábláját piros-fekete faként tároljuk , a memóriafelhasználás -ra csökken , de a számítási bonyolultság -ra emelkedik . $Tovább)$ $O((H+n)\log \sigma +k)$

Jegyzetek

↑ Alfred V. Aho, Margaret J. Corasick. Hatékony karakterláncillesztés: segédlet a bibliográfiai kereséshez // Communications of the ACM . - 1975. - T. 18 , 6. sz . - S. 333-340 . - doi : 10.1145/360825.360855 .
↑ grep-2.26 megjelent [stabil ] . www.mail-archive.com. Letöltve: 2016. október 4. Az eredetiből archiválva : 2016. október 5.. (határozatlan)

Linkek

https://xlinux.nist.gov/dads/HTML/ahoCorasick.html

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Mintaillesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc