Ejho—Korasikin algoritam
U računarstvu, Ejho—Korasikin algoritam za podudarnost niski je algoritam za pretragu niski koji su izmislili Alfred Vejno Ejho i Margaret Dž. Korasik.[1] To je algoritam po principu pretrage rečnika koji nalazi elemente konačnog skupa niski („rečnika“) u okviru unetog teksta. Vrši simultano podudaranje šablona. Teorija složenosti izračunavanja algoritma je linearna u dužini šablona, plus dužini pretraženog teksta, plus broja podudarnosti na izlazu. Uzmimo u obzir da, pošto su sve podudarnosti nađene, može biti kvadratni broj podudaranja ako je podudaran svaki podstring.
Algoritam gradi mašinu konačnog stanja koja podseća na drvo, sa dodatnim vezama između različitih unutrašnjih čvorova. Ove dodatne unutrašnje veze dopuštaju brze prelaze između neuspelih poklapanja šablona(pretraga za мачка u drvetu koje ne sadrži мачка ali sadrži мачевалац ne bi uspela na čvoru sa prefiksom мач) i ostalih grana koje dele zajednički prefiks. Ovo omogućava automatizaciju prelaska između podudarnih šablona bez potrebe za bektrekingom.
Kada je rečnik šablona poznat unapred, konstrukcija automata može biti izvršena oflajn i kompajlirani automat sačuvan za kasniju upotrebu. U ovom slučaju, njegovo vreme izvršavanja je linearno u dužini ulaza plus broj podudarnih ulaza.
Ejho—Korasikin algoritam za podudarnost stringova zasnovao je bazu originalne liste Juniks programa.
Graf ispod je Ejho—Korasikina struktura podataka, napravljena iz navedenog rečnika, sa svakim redom u tabeli koji predstavlja čvor u stablu, sa putanjom kolona koja ukazuje na jedinstven niz karaktera iz korena ka čvoru.
Struktura podataka ima po jedan čvor za svaki prefiks svakog stringa u rečniku. Ako je (bca) u rečniku onda će postojati čvorovi za (bca), (bc), (b) i (). Postoji crna usmerena grana deteta iz svakog čvora do čvora čije ime se dobija nadovezivanjem jednog karaktera. Samim tim postoji crna grana od (bc) do (bca). Postoji plava usmerena sufiks grana od svakog čvora do čvora koji je najduži mogući striktni sufiks tog čvora u grafu. Na primer, za čvor (caa) striktni sufiksi su (aa), (a) i (). Najduži od njih koji postoji u grafu je (a), tako da postoji plava grana od (caa) do (a). Postoji zelena grana rečničkog sufiksa od svakog čvora do sledećeg čvora u rečniku do kog se može doći prateći plave grane. Na primer, postoji zelena grana od (bca) do (a) zbog toga što je (a) prvi čvor u rečniku (tzv. beli čvor) do koga se dolazi prateći plave grane do (ca), a onda do (a).
| Putanja | U rečniku | Sufiks | Rečnički sufiks |
|---|---|---|---|
| () | - | ||
| (a) | + | () | |
| (ab) | + | (b) | |
| (b) | - | () | |
| (bc) | + | (c) | (c) |
| (bca) | + | (ca) | (a) |
| (c) | + | () | |
| (ca) | - | (a) | (a) |
| (caa) | + | (a) | (a) |
Na svakom koraku, trenutni čvor se produžava tražeći svoje dete, a ako ono ne postoji, nalazeći njegovo dete sufiks, a ako to ne uspe nalazeći dete sufiks njegovog sufiksa itd. završavajući na kraju u korenu ako ništa nije viđeno pre toga.
Kada algoritam dođe do čvora, izbacuje sve rečničke ulaze koji se završavaju na trenutnoj poziciji karaktera u unetom tekstu. Ovo se radi štampanjem svakog čvora do koga se došlo prateći sufiks veze rečnika počevši od tog čvora, i nastavljajući sve dok se ne dođe do čvora koji nema rečničku sufiks vezu. Kao dodatak, i taj čvor se štampa ako predstavlja ulaz u rečnik.
Izvršenje na ulaznom stringu abccab povlači sledeće korake:
| 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 |
Reference uredi
- ^ 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.
Spoljašnje veze uredi
- 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