Loeng 1 - Täpne otsimine

1. Sissejuhatus tekstialgoritmidesse
2. Triviaalne algoritm e. jõumeetod O(nm)
3. Knuth-Morris-Pratt O(m+n)
4. Boyer-Moore O( n / m )
5. Rabin-Karp O(n)
6. Shift-OR O(n)
7. Aho-Corasick (mitme sõne otsimine)

• Lloyd Alison: String Search (kohalik)
• C code modularity

• Tekstist otsimine etteantud mustriga
• Tekstide esituse andmestruktuurid ja indekseerimine
• pakkimismeetodid

• Tekstiandmebaasid
• Tekstitoimetamine
• Multimeedia, CD-ROM
• Info-päringud ja indekseerimine (Internet)
• Keeletehnoloogia
• Biotehnoloogia/bioinformaatika

Õppematerjal

Üle tasub korrata ka Jüri Kiho Algoritmide ja Andmestruktuuride konspekt

Kursuse koduleheküljel on lisaks mitmeid linke materjalidele Internetis.

Tagasi

Täpne otsimine

Probleem

• Olgu antud stringid S = s₁ s₂ ... s_n (tekst) ning P = p₁ p₂ ... p_m (muster) tähestikus Σ , |Σ| = c.
• Kas S sisaldab alamsõnena P-d? St, kas S= S' P S" mingitele stringidele S' ja S"?
• Tavaliselt m << n ning n võib olla väga suur.

Tähelepanek: P võib esineda alates suvalisest S positsioonist (v.a. viimased m-1).

Lahendus: Üritame sobitada P'd igasse positsiooni, st alates S positsioonist 1, siis 2, jne. Igas positsioonis võrdleme S ja P järjestikuseid tähti kuni esimese erinevuseni või kuni P lõpuni (P täpne esinemine S-is).

Algoritm Jõumeetod
Sisend: Tekst S[1..n] ja muster P[1..m]
Väljund: Kõikide P esinemiste alguspunktid S-is.

1. 	i = 1
2. 	while i <= n-m-1 
3. 		j=1
4. 		while j <= m   and  S[i+j-1] == P[j] 
5. 			j = j+1 
6. 		if j > m  then  print i 
7.		i = i+1

Ajaline keerukus on võrdeline real 4 tehtavate võrdluste arvuga.

Halvimal juhul tehakse (n-m+1) * m võrdlust, ehk O(mn)

Keskmiselt tehakse O(n) eeldusel et kõikide tähtede sagedus on sama tekstis ja mustris.

Keskmiselt hea praktikas v.a. väikese tähestiku puhul, c< 5

Kas on võimalik arendada välja algoritm mis on alati garanteeritult lineaarse toimimisajaga teksti S suhtes sõltumata mustri P pikkusest?

Tagasi

KMP - Lineaarne lahendus

Kuidas vältida seda, et S sees võrreldakse samu tähti uuesti?

Oletame et mustri esimesed j-1 märki sobivad kokku S tähtedega ja P[j] != S[i+j-1]. Tuleb ära kasutada info, et P esimesed j-1 tähte langevad kokku S vastavate positsioonidega.

Näide 1: kalakarumarukalakadakasu kalakadakas kalakadakas kalakadakas kalakadakas kalakadakas kalakadakas kalakadakas kalakadakas kalakadakas Näide 2: S: aabxabcabcabdx T: abcabd abcabd abcabd abcabd abcabd

Teeme näite 2 põhjal automaadi: Samm automaadis (pidev nool) loeb tekstist ühe märgi juurde. Katkendjoonega nool näitab siirdumist automaadis juhul kui tähevordlus ebaõnnestub. See nn. fail-link näitab kuhu tasub automaadis siirduda järgmise märgi võrdlemiseks.

Näide 2: simulatsioon P: abcadb S: aabxabcabcabdx olek: 122312345645671 fail: 3 Automaat: olek siire fail 1 a:2 0 2 b:3 1 3 c:4 1 4 a:5 1 5: b:6 2 6: d:7 3 ACCEPT STATE

Algoritm Knuth-Morris-Pratt (KMP) Sisend: Tekst S[1..n] ja muster P[1..m] Väljund: Raporteeri P esimene esinemine kui see leidub 1. i=j=1 2. initfail(P) // Arvuta fail-siirded 3. repeat 4. if j==0 or S[i] == P[j] 5. then i++ , j++ 6. else j = fail[j] 7. until j>m or i>n 8. if j>m then report match at i-m

Eeltöötlus initfail() - fail[] omadused:

Prefiks: Olgu S = xu, siis x on S-i prefix. Kui x on mittetühi siis on päris prefiks.

Sufiks: Olgu S = ux, siis x on S-i sufix. Kui x on mittetühi siis on päris sufiks.

Fail siire: olgu p mustri P päris prefiks. Fail siire arvutatakse nii, et see viitaks olekule mis on kõige pikem p prefiks mis on samal ajal ka p sufiks.

fail[i] = k kui p₁...p_k-1 on samaaegselt p₁...p_i-1 pikim päris prefiks kui ka sufiks.

Definitsioonist järeldub et fail[1] = 0

Kui p_i == p_k siis fail[i+1] = fail[i]+1

Kui p_i != p_k siis siirdutakse fail[j] linke mööda kuni leitakse olek kus on sama märgiga siire P[i]==P[u] nii et fail[i+1] = u+1 (vajadusel kuni 0, nii et fail[i+1] = 1)

Algoritm KMP initfail Sisend: Muster P[1..m] Väljund: fail[] tabel mustrile P 1. i=1, j=0 , fail[1]= 0 2. repeat 3. if j==0 or P[i] == P[j] 4. then i++ , j++ , fail[i] = j 5. else j = fail[j] 6. until i>=m

Näide: Jälgime samm-sammult kõiki muutujaid (millal nende väärtused muutuvad) 1 2 3 4 5 6 P: a b c a b d i=1 j=0 m=6 fail[ 1 ] = 0 i=2 j=1 fail[ 2 ] = 1 j=0 i=3 j=1 fail[ 3 ] = 1 j=0 i=4 j=1 fail[ 4 ] = 1 i=5 j=2 fail[ 5 ] = 2 i=6 j=3 fail[ 6 ] = 3

Teoreem: Algoritm KMP initfail võtab aja O(m)
Tõestus: Tööd tehakse võrdeliselt tsüklite arvule (read 3-5on konstantne aeg).

Iga tsükli sammu juures kas

• kasvatatakse i-d ühe võrra (i ei vähene kusagil), seega kokku sooritatakse rida 4 maksimum m korda, või
• vähendatakse j-i (rida 5, sest fail[j] < j kui j> 0). Kuna vaid samm 4 võib j-i kasvatada ühe võrra, ning rida 4 sooritatakse maksimum m korda, siis ka rida 5 saab sooritada vaid kuni m korda, sest j ei kasva rohkem kui m korral. Seega j saab ka kahaneda vaid maksimum m korral.
• Kokku sooritatakse tsüklit k <= 2m korda, ehk O(m) korda.

Tõestus: Eeltöötlemine võtab aja O(m) ning automaadi sobitamine aja O(n). Automaadi sobitamise aeg tuleb tõestada analoogselt eelmise teoreemiga.

KMP algoritmi võib kiirendada efektiivse kodeerimisega (goto) ning lisaks saab pöörata tähelepanu fail-jadale kui on teada jäargmine teksti märk (et ei tehtaks asjata tööd sama märgiga võrdlemiseks).

Otsi veebist KMP algoritmi infot...

Idee: Selleks et teada kas P sobib mingisse kohta S-is, sobitame P-d alates P viimasest positsioonist, st. paremalt vasakule, mitte vasakult paremale. Kui S-is vastaval positsioonil olev märk ei ole sama mis P viimane, siis saab kasutada spetsiaalset hüpet mis tõstab P-d maksimaalselt S-is edasi. Ideaaljuhul piisab kui võrrelda S-is vaid iga m-indat märki, ehk O(n/m).

S: which-finally-halts-at-that-point at-that at-that at-that at-that at-that at-that

Kasutada saab kahte eri heuristikaga hüpet millest valitakse maksimum:

1. Esinemine - konfliktse märgi kohale asetatakse parempoolseim P märk mis sobib
2. Sobitus - juba võrreldud alale P lõpus tuleb leida sobiv vaste ning lisaks peab konfliktse märgi positsiooni tulema P-s uus märk.

 

Algoritm BM (Boyer-Moore)

Sisend:  Tekst S[1..n] ja Muster P[1..m]
Väljund: P esinemiskohad S-is

1.	preprocess_BM()  // Tekita tabelid delta1 ja delta2
2.	i=m
3.	while i <= n 
4.		for( j=m ; j > 0 and P[j] == S[i-m+j] ; j-- ) ; 
5.		if j==0 report match at position i-m+1
6.		i = i + max( delta1[S[i-m+j]+j-m] , delta2[j] ) 

delta1[a] annab esinemisheuristika siirde: delta1[a] = min{ t | t=m or ( 0<= t <= m and a=P[m-t]) }

delta2 annab sobitus-heuristika siirde: delta2[j] = min{ t | t>= 1 and (P[j-t] != P[j]) or t >= j) and ((P[k-t]=P[k] or t>=k) kõikidele k=j+1,...,m) }

Boyer-Moore'st on mitmeid variatsioone ning analüüsivaid artikleid. Keskmiselt on ajaline keerukus O(n/m) ning halvemal juhul O(nm) (kui P esinemiste arv on suur). Algoritmide kiirust on võimalik oluliselt parandada samas lihtsustades heuristikaid. Nimelt on kasulik alati siirduda viimase P märgi esinemisheuristika järgi. (Horspool (1980), Baeza-Yates(1989), Hume and Sunday(1991)).

Algoritm BMH (Boyer-Moore-Horspool) Sisend: Tekst S[1..n] ja Muster P[1..m] Väljund: P esinemiskohad S-is 1. for a in Σ do delta[a] = m 2. for j=1..m-1 do delta[P[j]] = m-j 4. i=m 5. while i <= n 6. if S[i] == P[m] 7. j = m-1 8. while ( j>0 and P[j]==S[i-m+j] ) j = j-1 ; 9. if j==0 report match at i-m+1 10. i = i + delta[ S[i] ]

Lisaks on võimalik võtta kasutusele mitmeid programmi kiirendavaid trikke. Näiteks lihtsustada peamist tsüklit. Eeldus on, et tavaliselt ei sobi märgid kokku, ning siis tasub kiire tsükli sees siirduda alati delta[S[i]] võrra kuni esimese positsioonini kus S[i] == P[m]. Alles peale seda täpsustada, kui mitu märki P lõpust sobib S-i vastavate märkidega.

Algoritm BMHHS (Boyer-Moore-Horspool-Hume-Sunday) Sisend: Tekst S[1..n] ja Muster P[1..m] Väljund: P esinemiskohad S-is 1. for a in Σ do delta[a] = m 2. for j=1..m-1 do delta[P[j]] = m-j 3. d = delta[ P[m] ] ; delta[ P[m] ] = 0 4. i=m 5. repeat 6. repeat 7. t = delta[S[i]]; i= i+t; // Use delta in a skip-loop 8. until t == 0 // Until S[i] == P[m] 9. j= m -1 10. while ( j>0 and P[j]==S[i-m+j] ) j = j-1 ; 11. if j==0 report match at i-m+1 10. i = i + d 11. until i > n

Algoritmis BMHHS eeldatakse et teksti lõppu S[n+1]..S[n+m] on lisatud P[m] et algoritm lõpetaks korrektselt.

Loop unrolling:

7.	i= i+ delta[S[i]]; 
	i= i+ delta[S[i]];
	t = delta[ S[i] ] ; 
	i= i+t   ; 

Daniel M. Sunday: A very fast substring search algorithm [PDF]
Communications of the ACM August 1990, Volume 33 Issue 8
This article describes a substring search algorithm that is faster than the Boyer-Moore algorithm. This algorithm does not depend on scanning the pattern string in any particular order. Three variations of the algorithm are given that use three different pattern scan orders. These include: (1) a Quick Search algorithm; (2) a Maximal Shift and (3) an Optimal Mismatch algorithm.

Täiendavat infot Boyer Moore kohta veebis

Tagasi

Rabin-Karp algoritm

R.Karp and M. Rabin: Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development 31 (1987), 249-260.

Kuigi Boyer-Moore põhised algoritmid on täpse otsimise jaoks kõige kiiremad, võib otsimise probleemile läheneda veel mitme teise nurga alt. Osad nendest ideedest leiavad kasutust keerukamate ülesannete juures ja seega on need väärt läbi rääkimist. Esimene, nn. Rabin-Karp algoritm põhineb ideel, et sooritada kiire läbivaatus tuvastamaks kiiresti, kas esinemine on võimalik, ning kui vastus on jah, siis uurida täpsemalt kas see oli ka tegelik esinemine. Sisuliselt on tegemist filtreerimisega, kus elimineeritakse kiiresti kindlad valed vastused ning harvadel juhtudel testitakse kas vastus on õige.

• Idee: Kasutame paiskfunktsiooni mis kuvab stringid täisarvudele: H: string -> integer.

• Arvuta H(P) ning lisaks igale voimalikule S-i piirkonnale H(S[i..i+m-1])

• Kui H(P) == H(S[i..i+m-1]) siis uuri kas P == S[i..i+m-1]

• Näiteks: H(P) = Σ ord(P[i])

• ASCII tabeli järgi ord(A)=65 , ord(C)=67, ...

Et mitte korduvalt kasutada samu S tähti järjestikuseid paiskfunktsioone arvutades, pakkusid Rabin ja Karp välja sellise paiskfunktsiooni mis lubaks kiiresti arvutada H(S[i..i+m-1]) väärtusest uue väärtuse H(S[i+1 .. i+m ]) järgmise positsiooni jaoks nii, et kasutatakse eelmist väärtust H(S[i..i+m-1]) ja uut märki S[i+m].

• Eeldame et igale Σ tähele vastab arv 0, 1, ..., c-1

• S = s₁ s₂ ... s_k

• Olgu iga s_i vastav arv n(s_i)

• String S saab esitada c-nd süsteemis täisarvuna:

• v( S ) = n(s₁) c^k-1 + n(s₂) c^k-2 + ... + n(s_k-1) c + n(s_k)

• H väärtuspiirkonnaks valime { 0, 1, ... , q-1 } nii et q on algarv.

• 32-bitise arhitektuuri peal võib valida näiteks q=33554393 (?)

• Vaatame järjestikuseid m tähe pikkuseid S-i alamstringe: S_i-1 = S[i-1 .. i+m-2 ] ja S_i = S[i .. i+m-1].

• v( S_i ) = ( v( S_i-1 ) - n(s_i-1) c^m-1 ) c + n(s_i+m-1)

• Näiteks: arvust 73568 saame uue arvu 35689 valemiga: (73568 - 7*10⁴)*10 + 9

• mod-aritmeetikas:

  (a+b) mod q = a mod q + b mod q

  (a * b) mod q = (a mod q) * ( b mod q )

• H_q (S_i) =
  = v( S_i ) mod q
  = ( H_q( S_i-1) - n( s_i-1 ) c^m-1 ) c + n(s_i+m-1)
  nii et kõik operatsioonid on mod q artitmeetikas

• Kokku 4 erinevat q-aritmeetika tehet mis on alati arvutatavad konstantse ajaga (q peaks mahtuma sõnasse)

 

Algoritm Rabin-Karp 

Sisend:  Tekst S[1..n] ja Muster P[1..m]
Väljund: P esinemiskohad S-is

1.	c=20;          /* tähestiku suurus - näiteks aminohapet arv valkudes */
2.      q = 33554393   /* Mõni algarv */
3.	cm = cm-1 mod q    // Kordaja Si esimesele positsioonile
4.	hp = 0 ; hs = 0 

5. 	for i = 1 .. m do hp = ( hp*c + n(p[i]) ) mod q    // H(P)
6. 	for i = 1 .. m do hs = ( hp*c + n(s[i]) ) mod q    // H(S[1..m])

7.	if hp == hs and P == S[1..m] report match at position 1 
8.	for i=2 .. n-m+1 
9.		hs = ( (hs - n(s[i-1])*cm) * c  +  n(s[i+m-1]) mod q 
10.		if hp == hs and P == S[i..i+m-1] report match at position i

• Kui tähestiku suurus on arvu 2 aste, siis saab c-ga korrutamise realiseerida SHIFT käsuga.

• Tuleb olla tähelepanelik et mod on alati positiivsest arvust ja ei esineks ületäitumist.

• Analüüs - kui tihti esineb õiget ja kui tihti valet häiret paiskväärtuste võrdlemisel

• Milline on tõenäosus valehäirele

• Üldistused - muutuv q ; signatuuri tehnikad jne.

Vaata Rabin-Karp koodi näidet

Ricardo Baeza-Yates , Gaston H. Gonnet
A new approach to text searching
Communications of the ACM October 1992, Volume 35 Issue 10
[ACM Digital Library:http://doi.acm.org/10.1145/135239.135243] [DOI] [PDF]

Märgime arvuti protsessori sõna pikkust w (näiteks 32 või 64). Oletame, et |P| = m <= w.

Idee - hoiame mälus m-bitist arvu E, mis näitab otsimise hetkeseisu.
Bitt E.j = 0 ainult juhul kui P esimesed 1..j märki on võrdsed vastavate märkidega stringis S.

w ... m ... 2 1 (positsioonid) 0 ... 1 ... 1 0 (E bitid)

P esinemine S-is on leitud kui bitt E.m = 0

Selleks et otsida P võimalikke esinemisi S-is, tuleb sõna E seisu uuendada iga S tähe jaoks vasakult alates.

Selleks saab kasutada ette arvutatud vektoreid T[c] iga võimaliku tähe c ∈ Σ jaoks nii, et T[c].j = 0 kui P[j]=c.

E seisu uuendatakse kahe sammuga:

1. E bitte lükatakse pügal vasakule (shift left)
2. Sooritatakse E ja T[ S[i] ] vahel OR

 

Algoritm Shift-OR 

Sisend:  Tekst S[1..n] ja Muster P[1..m]
Väljund: P esinemiste viimased positsioonid S-is

begin
1.	for c ∈ Σ do T[c] = 2m - 1 
2.	for j=1 to m do T[P[j]] = T[P[j]] - 2j-1
3. 	E =  2m - 1

4.	for i=1 to n do 
5.		E = shift_left(E) or T[S[i]]
6. 		if E.m = 0 then report match ending at position i
end

 

Näide: P=aste  S=lasteaed 

T[c]	a d e l s t  	  S:    l a s t e a e d 
1.	0 1 1 1 1 1	      1 1 0 1 1 1 0 1 1
2.	1 1 1 1 0 1	      1 1 1 0 1 1 1 1 1
3.	1 1 1 1 1 0 	      1 1 1 1 0 1 1 1 1
4.	1 1 0 1 1 1	      1 1 1 1 1 0 1 1 1

Kui tahta kasutada pikemaid mustreid, tuleks E esitada mitme sõna abil.

Otsimise keerukus (read 4.-6.) = O( n ) kui m on väiksem kui w.

Igas teksti S positsioonis tehakse sama palju tööd (va. väljundit raporteerides)

On praktikas kiirem kui KMP.

Lisaks üldistub väga hästi ligikaudse otsimise jaoks (sellest edaspidi)

Üldistub ka märgiklasside otsimiseks. Näiteks a[st][st][ae] (aste, atse, atta jne.)

Vaata SHIFT-OR koodi näidet

Vahekokkuvõte

Eespool on vaadeldud mitmeid vägagi erinevaid ideid kuidas sooritada alamsõne täpset otsimist. Praktikumides on neist mitmed realiseeritud ja esimene tunnetus algoritmide efektiivsusest on käes. Kas saab öelda, et mõni algoritm on oluliselt parem kui teised? Kas saab öelda, et viskame mõne lahenduse lihtsalt ajaloo prügikasti?

Edaspidi vaatleme mustrite otsimise keerukamaid probleeme. Ideedest mis on esitatud alternatiivsetena võib mõni osutuda vägagi kasutuskõlblikuks mõne keerukama ülesande lahendamiseks.

Vaatame järgmiseks mustrite täpse otsimise alamprobleemi kus eesmärk pole otsida mitte ühte sõne korraga, vaid paljusid. Potentsiaalselt pakub näiteks huvi leida tuhandete stringide kõik esinemised. Näiteks - otsi kas tekstis leidub mõni sõnastikku kantud sõna (näiteks roppuste välja rookimine uudistegruppidest, arvutiviiruste otsimine failidest, või tuhandete DNA praimerite otsimine üle kogu genoomi).

Praimer on DNA jupp mis on võimeline seonduma oma komplementaarse DNA peale ja selle seondumise läbi võib näiteks praimeritega piiratud piirkonda genoomis eksponentsiaalse kiirusega paljundada. Kui valida palju praimereid siis on oluline teada, millised piirkonnad genoomis võiksid osutuda amplifitseerituks.

Kui kasutada eelpool toodud algoritme siis tuleb ühe mustri otsimiseks minev aeg ilmselt korrutada läbi tegelikult otsitavate mustrite arvuga. See pole aga enam efektiivne.

Tagasi

Aho-Corasick

• KMP üldistus mitmele mustrile korraga

• Tekst S nagu varem. Kuid mustreid P = { P₁ , .., P_k }

• Kogupikkus |P| = m = Σ _i=1..k m_i

• Ülesanne - otsida S-ist kõikide P_i ∈ P esinemised...

Vahepala - kuidas salvestada indeksis sõnastikku?

Sõnade trie - hea andmestruktuur sõnade hulga esitamiseks. Näiteks sõnastiku jaoks. Iga sõna küsimiseks piisab teha maksimum sõna pikkuse võrra tööd.

trie (data structure)
Definition: A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes.
See also digital tree, digital search tree, directed acyclic word graph, compact DAWG, Patricia tree, suffix tree.
Note: The name comes from retrieval and is pronounced, "tree."

Vaata ülaltoodud trie struktuuri ning tee järeldused, kuidas otsida näiteks sõna he, sheila või hi võimalikke esinemisi etteantud sõnade hulgast.

Tagasi AC algoritmi juurde

Kasutame trie-st tehtud automaati kõikide sõnastiku sõnade üheaegseks otsimiseks. Moodustame stringide hulgale P automaadi M_P, mille osad on järgmised:

• Päris siirded: goto[j,c] loeb tekstist margi c ja siirdub olekust j olekusse goto[j,c].

• Kui olekus j pole märgiga c siiret siis hüpatakse olekusse fail[j].

• Väljundi genereerimine e. Output-funktsioon - milliste sõnade leidumine tuleks raporteerida olekus j.

Joonistame AC automaadi analoogselt KMP automaadile.

Näiteks goto[1,i] = 6. ; fail[7] = 3, fail[8] = 0 , fail[5]=2.

Output tabelid:

olek output[j] 2 he 5 she, he 7 his 9 hers

Järgmine algoritm realiseerib Aho-Corasick automaadi M_P abil otsimise.

Algoritm Aho-Corasick (otsimine) Sisend: Tekst S[1..n] ja Automaat M mustrite hulgale P Väljund: P mustrite esinemiskohad S-is (viimane positsioon) 1. j = 0 2. for i = 1 to n do 3. while goto[j,S[i]] == ∅ do j = fail[j] 4. j = goto[j , S[i] ] 5. if ( output[j] not empty ) 6. then report matches output[j] at position i

Aho-Corasick automaadi moodustamine

Esiteks, moodustame trie etteantud sõnadest. Trie esitab goto-funktsioone. Lisamise lõpus sisestatakse sõna ka vastava oleku output-funktsioonide tabelisse. Output-funktsiooni táiendatakse teises etapis.

Teiseks, etteantud trie pealt genereeritakse fail-funktsioonid ja täiendatakse output-funktsioone.

Algoritm Aho-Corasick eeltöötlus I (TRIE) Sisend: P = { P1, ... , Pk } Väljund: goto-funktsioon ja osaline output-funktsioon. Eeldused: output(s) on tühi kui olek s sünnib. goto[s,a] ei ole määratud. procedure enter(a1, ... , am) /* Pi = a1, ... , am */ begin 1. s=0; j=1; 2. while goto[s,aj] ≠ ∅ do /* järgi puus juba olevat teed */ 3. s = goto[s,aj]; 4. j = j+1 5. for p=j to m do /* lisa puuduv tee puusse */ 6. news = news+1 ; 7. goto[s,ap] = news 8. s = news 9. output[s] = a1, ... , am end begin 10. news = 0 11. for i=1 to k do enter( Pi ) 12. for a ∈ Σ do 13. if goto[0,a] = ∅ then goto[0,a] = 0 ;

Pane tähele, et rida 13 garanteerib, et olekust 0 leidub alati goto[0,a].

Järgmiseks tuleb moodustada Fail[] tabeid

Algoritm Aho-Corasick eeltöötlus II (FAIL) Sisend: MP automaat (GOTO) ja esialgne output[] eelmisest algoritmist Väljund: Fail[] funktsioon ja lõplik output-funktsioon. begin 1. queue = ∅ 2. for a ∈ Σ do if goto[0,a] ≠ 0 then 3. enqueue( queue, goto[0,a] ) 4. fail[ goto[0,a] ] = 0 5. 6. while queue ≠ ∅ 7. r = take( queue ) 8. for a ∈ Σ do if goto[r,a] ≠ ∅ then 9. s = goto[ r, a ] 10. enqueue( queue, s ) 11. state = fail[r] 12. while goto[state,a] = ∅ do state = fail[state] 13. fail[s] = goto[state,a] 14. output[s] = output[s] + output[ fail[s] ] end

AC algoritmi õigsuse tõestus. Olgu algolekust (puu juurest) olekuni j viitav string t. Tuleb tõestada, mh. et olekust j viitav fail[j] osutab t pikimale lõpuosale mis on samas ka mõne P-sse kuuluva stringi päris algusosa e. sufiks. Tõestust ei esita siin ajapuudusel, vt. artiklit millele leiate viite eestpoolt.

Aho-Corasicki algoritmi ajaline keerukus

Teoreem Auotomaadi M_P sobitamisel teksti S, |S|=n, tehakse vähem kui 2n hüpet olekute tabelis. (mis oleks parem sõnastus?)

Tõestus. Vrdl. KMP algoritmi tõestusega. Fail-siirdeid võib olla kõige rohkem goto-siirete arv miinus üks, sest iga fail-siire viib reaalselt lähemale puu juurele (olek 0). Kuna goto siirdeid on maksimum n korda, võib kokku olla hüppeid vähem kui 2n.

Pane tähele, et teoreemi järgi ei ole oluline kui mitu mustrit korraga otsitakse. Kui k kasvab, siis peab tõenäoliselt sagedamini tegema fail-hüppeid (miks?) kuid siiski alati vähem kui n korda.

Kui on piisavalt ruumi et esitada kõik goto[j,a] siirded tabelitena, siis on AC algoritm O(n).

Kui aga k ja c on suured, võib kasutada tabelite asemel liste või otsimispuid.
Sel juhul on keerukus O(n log(min(k,c)) ).

Koodi näide C ja header .h (pole kindel et see maailma parim kood oleks...)