Algoritme Aho - Korasik

Aho-Korasik- algoritmen er en understrengssøgningsalgoritme udviklet af Alfred Aho og Margaret Korasik i 1975 [1] , der søger efter et sæt understrenge fra en ordbog i en given streng .

Udbredt i systemsoftware, såsom søgeværktøjet grep [2] .

Sådan virker det

Algoritmen bygger en tilstandsmaskine , som den derefter sender søgestrengen til. Automaten modtager alle tegn i strengen én efter én og bevæger sig langs de tilsvarende kanter. Hvis automaten har nået den endelige tilstand, er den tilsvarende ordbogsstreng til stede i søgestrengen.

Flere søgestrenge kan kombineres til et søgetræ, det såkaldte bor (præfikstræ). Bor er en tilstandsmaskine, der genkender én linje fra - men på betingelse af, at begyndelsen af linjen er kendt. $m$

Den første opgave i algoritmen er at lære automaten at "gendanne sig selv", hvis understrengen ikke matchede. Samtidig er det ikke egnet at nulstille automaten til dens oprindelige tilstand for et uegnet bogstav, da dette kan føre til, at en understreng springes over (f.eks. når du søger efter en streng aabab, støder den på , efter at have læst det femte tegn, overfører automaton til sin oprindelige tilstand vil føre til at springe en understreng over - det ville være rigtigt at gå til tilstand og derefter behandle det femte tegn igen). For at gøre automaten selvhelbredende tilføjes suffikslinks indlæst med det tomme symbol ⌀ (så en deterministisk automat bliver til en ikke-deterministisk). For eksempel, hvis strengen er parset , så suffikserne , , . Et suffikslink er et link til en node, der matcher det længste suffiks, der ikke fører boringen til en blindgyde (i dette tilfælde ). aabaababaaabaababaaa

For rodnoden er suffikslinket en løkke. For resten er reglen som følger: hvis det sidst genkendte tegn er , så omgås suffikslinket for forælderen, hvis der er en bue indlæst med tegnet derfra , ledes suffikslinket til noden hvor denne bue fører. Ellers krydser algoritmen suffikslinket igen og igen, indtil den enten krydser rodsløjfelinket eller finder en bue fyldt med symbolet . $c$ $c$ $c$

* ···Ø···> * ···Ø···> * ···Ø···> * | | c c ↓ ↓ [*] Ø Ø nyt suffikslink

Denne automat er ikke-deterministisk. Konvertering af en ikke-deterministisk endelig automat til en deterministisk fører generelt til en betydelig stigning i antallet af hjørner. Men denne automat kan omdannes til en deterministisk automat uden at skabe nye toppunkter: hvis der ikke er nogen steder for et toppunkt at gå efter symbolet , går vi gennem suffikslinket igen og igen, indtil vi enten rammer roden, eller der er et sted at gå hen ved symbolet . $v$ $c$ $c$

Det er praktisk at gøre al bestemmelsen rekursivt. For eksempel for et suffikslink:

alg sufflink(v) hvis v.cacheSuffRef ≠ Ø // for root, initialt root.cacheSuffRef = root returnere v.cacheSuffReference u := v.forælder c := v.symbol gentage u := SuffReference(u) før (u = rod) eller (der er en sti u --c→ w) hvis der er en overgang u —c→ w derefter v.cacheSuffref := w ellers v.cacheSuffReference := root returnere v.cacheSuffReference

Bestemmelse øger antallet af endehjørner: hvis suffikset forbinder fra et knudepunkt fører til endehjørnet , erklæres det også for ende. Til dette oprettes såkaldte endelinks: endelinket fører til den endenode, der er tættest på suffikslinkene; krydsning af efterfølgende referencer returnerer alle matchende rækker. $v$ $u$ $v$

alg OutputResult(v, i) print "Fundet " + v.nål + " ved position " + (i - v.dybde + 1) alg MainPartSearch tilstand := rod sløjfe i=1..|høstak| tilstand := Overgang(tilstand, høstak[i]); hvis tilstand.nål ≠ Ø OutputResultat(tilstand, i) timeStat := tilstand mens FinalRef(timeConst) ≠ Ø tempst := EndRef(timestst); OutputResult(TimeConst, i)

Suffiks og slutlinks i automaten kan beregnes efter behov allerede i søgefasen. Sideovergange - du kan beregne på stedet uden at cache på nogen måde , du kan cache for alle noder, du kan - for de vigtigste (alt dette påvirker ikke den asymptotiske estimering af algoritmen).

Beregningsmæssig kompleksitet

Algoritmens beregningsmæssige kompleksitet afhænger af organiseringen af dataene. For eksempel:

Hvis automatens springtabel er lagret som et indeksarray - hukommelsesforbrug , beregningsmæssig kompleksitet , hvor - længden af teksten, hvori søgningen udføres, - den samlede længde af alle ord i ordbogen, - alfabetets størrelse, - den samlede længde af alle kampe. $O(n\sigma )$ $O(n\sigma +H+k)$ $H$ $n$ $\sigma$ $k$
Hvis automatens overgangstabel er gemt som et rød-sort træ , falder hukommelsesforbruget til , men den beregningsmæssige kompleksitet stiger til . $På)$ $O((H+n)\log \sigma +k)$

Noter

↑ Alfred V. Aho, Margaret J. Corasick. Effektiv strengmatchning: En hjælp til bibliografisk søgning // Kommunikation af ACM . - 1975. - T. 18 , nr. 6 . - S. 333-340 . - doi : 10.1145/360825.360855 .
↑ grep-2.26 frigivet [stabil ] . www.mail-archive.com. Hentet 4. oktober 2016. Arkiveret fra originalen 5. oktober 2016. (ubestemt)

Links

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

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng