Algoritm Aho - Korasik

Aho-Korasik- algoritmen är en sökalgoritm för delsträngar utvecklad av Alfred Aho och Margaret Korasik 1975 [1] som söker efter en uppsättning delsträngar från en ordbok i en given sträng .

Används ofta i systemprogramvara, till exempel sökverktyget grep [2] .

Hur det fungerar

Algoritmen bygger en tillståndsmaskin , till vilken den sedan skickar söksträngen. Automaten tar emot alla tecken i strängen en efter en och rör sig längs motsvarande kanter. Om automaten har nått sluttillståndet finns motsvarande ordbokssträng i söksträngen.

Flera söksträngar kan kombineras till ett sökträd, det så kallade boret (prefixträdet). Bor är en tillståndsmaskin som känner igen en linje från - men under förutsättning att radens början är känd. $m$

Den första uppgiften i algoritmen är att lära automaten att "återställa sig själv" om delsträngen inte matchade. Samtidigt är det inte lämpligt att återställa automaten till dess initiala tillstånd för en olämplig bokstav, eftersom detta kan leda till att man hoppar över en delsträng (till exempel när man söker efter en sträng aabab, stöter den på , efter att ha läst det femte tecknet, överför automaton till sitt initiala tillstånd kommer att leda till att en delsträng hoppar över - det skulle vara rätt att gå till state , och sedan bearbeta det femte tecknet igen). För att göra automaten självläkande läggs suffixlänkar laddade med den tomma symbolen ⌀ till den (så att en deterministisk automat förvandlas till en icke-deterministisk). Till exempel, om strängen tolkas , då suffixen , , . En suffixlänk är en länk till en nod som matchar det längsta suffixet som inte leder hålet till en återvändsgränd (i det här fallet ). aabaababaaabaababaaa

För rotnoden är suffixlänken en loop. För övrigt är regeln följande: om det senast igenkända tecknet är , då förbigås suffixlänken för föräldern, om det finns en båge laddad med tecknet därifrån , riktas suffixlänken till noden där denna båge leder. Annars går algoritmen igenom suffixlänken om och om igen tills den antingen korsar rotslingelänken eller hittar en båge laddad med symbolen . $c$ $c$ $c$

* ···Ø···> * ···Ø···> * ···Ø···> * | | c c ↓ ↓ [*] Ø Ø ny suffixlänk

Denna automat är icke-deterministisk. Att konvertera en icke-deterministisk finit automat till en deterministisk leder i allmänhet till en signifikant ökning av antalet hörn. Men denna automat kan omvandlas till en deterministisk automat utan att skapa nya hörn: om det inte finns någonstans för en vertex att gå med symbolen går vi igenom suffixlänken om och om igen tills vi antingen träffar roten eller det finns en plats att gå till av symbolen . $v$ $c$ $c$

Det är bekvämt att göra all beslutsamhet rekursivt. Till exempel, för en suffixlänk:

alg sufflink(v) om v.cacheSuffRef ≠ Ø // för root, initialt root.cacheSuffRef = rot return v.cacheSuffReference u := v.förälder c := v.symbol upprepa u := SuffReference(u) före (u = rot) eller (det finns en väg u --c→ w) om det finns en övergång u —c→ w sedan v.cacheSuffref := w annars v.cacheSuffReference := rot return v.cacheSuffReference

Bestämning ökar antalet ändpunkten: om suffixet länkar från en vertex leder till ändpunkten , förklaras det också vara slut. För detta skapas så kallade ändlänkar: ändlänken leder till ändnoden närmast suffixlänkarna; genomgång av efterföljande referenser returnerar alla matchande rader. $v$ $u$ $v$

alg OutputResult(v, i) skriv ut "Found" + v.needle + " vid position " + (i - v.depth + 1) alg MainPartSearch tillstånd := rot loop i=1..|höstack| tillstånd := Övergång(tillstånd, höstack[i]); om skick.nål ≠ Ø OutputResult(tillstånd, i) timeStat := tillstånd medan FinalRef(timeConst) ≠ Ø tempst := EndRef(timestst); OutputResult(TimeConst, i)

Suffix och slutlänkar i automaten kan beräknas efter behov redan i sökfasen. Sidoövergångar - du kan beräkna på plats utan att cachelagra på något sätt , du kan cache för alla noder, du kan - för de viktigaste (allt detta påverkar inte den asymptotiska uppskattningen av algoritmen).

Beräkningskomplexitet

Algoritmens beräkningskomplexitet beror på organisationen av data. Till exempel:

Om automatens hopptabell lagras som en indexmatris - minnesförbrukning , beräkningskomplexitet , där - längden på texten där sökningen utförs, - den totala längden på alla ord i ordboken, - alfabetets storlek, - den totala längden på alla matcher. $O(n\sigma )$ $O(n\sigma +H+k)$ $H$ $n$ $\sigma$ $k$
Om övergångstabellen för automaten lagras som ett röd-svart träd minskar minnesförbrukningen till , men beräkningskomplexiteten stiger till . $På)$ $O((H+n)\log \sigma +k)$

Anteckningar

↑ Alfred V. Aho, Margaret J. Corasick. Effektiv strängmatchning: ett hjälpmedel för bibliografisk sökning // Communications of the ACM . - 1975. - T. 18 , nr 6 . - S. 333-340 . - doi : 10.1145/360825.360855 .
↑ grep-2.26 släppt [stabil ] . www.mail-archive.com. Hämtad 4 oktober 2016. Arkiverad från originalet 5 oktober 2016. (obestämd)

Länkar

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

Strängar
Stränglikhetsmått	Avstånd från Damerau till Loewenstein Levenshtein avstånd Hamming avstånd Jaro-Winkler likheter
Sök efter delsträng	Boyer-Moore algoritm Boyer-Moore-Horspool-algoritm Knuth-Morris-Pratt-algoritm Rabin-Karps algoritm prefixfunktion Z-funktion Algoritm Aho - Korasik
palindromer	palindromträd Manakers algoritm
Sekvensjustering	Needleman-Wunsha algoritm Smith-Waterman algoritm
Suffixstrukturer	Suffix array Suffix automat suffixträd prefixträd
Övrig	analysera Mönstermatchning Största vanliga följden Största gemensamma delsträngen