N16

16. 16.1.

Mintaillesztés Fogalmak és jelölések

Legyen Σ véges jelkészlet, ábécé. Σ elemeit betunek ˝ nevezzük. ˝ képezheto˝ összes véges jelsorozat halmazát, beleértve az üres sorozatot is, amit λ-val jelölünk. Jelölje Σ∗ a Σ elemeibol

Σ∗ = {x1 · · · xn : xi ∈ Σ, i = 1, . . . , n} ∪ {λ} Σ∗ elemeit szavaknak hívjuk. X ∈ Σ∗ szó hossza az X = x1 · · · xn sorozat elemeinek a száma, jele |X| = n. A továbbiakban feltételezzük, hogy a szavakat tömb ábrázolja, tehát az X szó i-edik elemére az X[i] tömbelem-kiválasztással

hivatkozunk. x = x1 · · · xm , y = y1 · · · yn ∈ Σ∗ szavak konkatenációja: xy = x1 · · · xm · y1 · · · yn . ˝ Az u szó kezdoszelete, vagy prefixe v-nek, jele u v, ha ∃w ∈ Σ∗ , hogy uw = v ˝ Az u szó végzodése, vagy szuffixe v-nek, jele u v, ha ∃w ∈ Σ∗ , hogy wu = v ∗ ˝ álló prefixére az Xi = X[1..i] jelölést használjuk. Az X ∈ Σ szó elso˝ i betujéb ˝ ol Általában, egy X = x1 · · · xn ∈ Σ∗ szó és 1 ≤ i ≤ j ≤ |X| esetén Xi, j = X[i.. j] = xi · · · x j jelölést használjuk. ˝ Azt mondjuk, hogy az S szó elofordul i eltolással az A szóban (vagy más szóval S i eltolással illeszkedik az A-ra), ha A[i + 1..i + m] = S, ahol m = |S|. Mintaillesztési probléma Bemenet: A, S ⊆ Σ∗ , A a szöveg, S minta, Kimenet: A legkisebb (összes) olyan i, amelyre A[i + 1..i + m] = S, ahol m = |A| a minta hossza.

@ A

Naiv algoritmus

n := |A|; m := |S|; For i:=0 To n − m Do If A[i + 1..i + m] = S[1..m] Then Begin WriteLn(i+1); Exit End; A naiv algoritmus futási ideje: Tlr (n, m) = O(n · m). Ez akkor bekövetkezik, ha A = aaaaaa · · · aa, S = aaa · · · aaab

16.2.

Mintaillesztés véges determinisztikus automatával

Véges determinisztikus automata olyan M = (Q, q0 , F, Σ, δ) rendezett ötös, ahol

• Q véges halmaz, az állapotok halmaza, ˝ • q0 ∈ Q a kezdoállapot,

• F ⊆ Q a végállapotok (elfogadó állapotok) halmaza, • Σ véges halmaz, a bemeneti jelek halmaza, • δ : Q × Σ → Q, az automata átmenetfüggvénye. Jelölje δ∗ Q × Σ∗ → Q a δ átmentfüggvény kiterjesztését szavakra, tehát

δ (q, w) = ∗



q, δ(δ∗ (q, x1 · · · xn−1 ), xn ),

ha w = λ ha w = x1 · · · xn

Legyen M = (Q, q0 , F, Σ, δ) olyan véges determinisztikus automata, amely a Σ∗ S nyelvet ismeri fel, azaz L(M) = Σ∗ S. Mivel Σ∗ S ˝ az összes olyan szavak halmaza, amelyek az S mintára végzodnek, ezért Ai ∈ L(M) akkor és csak akkor, ha az S minta i − m ˝ eltolással elofordul az A szövegben. Tehát ha van olyan M = (Q, q0 , F, Σ, δ) véges determinisztikus automatánk, amely a Σ∗ S nyelvet ismeri fel, azaz L(M) = Σ∗ S, akkor az alábbi algoritmus mintaillesztést valósít meg.

1

q:=q0 ;

n := |A|; m := |S|; For i := 1 To n Do Begin q := δ(q, A[i]); If q ∈ F Then Begin{S=A[i-m+1..i]} WriteLn(i-m+1); Exit; End; End; ˝ ˝ O(n). Az algoritmus futási ideje, eltekintve az automata eloállítási költségétol ˝ Hogyan és mekkora költséggel lehet eloállítani az M automatát (átmenetfüggvényét)? Legyen σ : Σ∗ → {0, 1, . . . , m} az S minta szuffix-függvénye,

σ(W ) = max{k : Sk A W }

W Sk 1. ábra. A σ függvény szemléltetése

2

Nyilvánvaló, hogy az S minta akkor és csak akkor illeszkedik az A szövegre i eltolással, ha σ(Ai+m ) = m. 16.1. lemma. Ha q = σ(W ), akkor σ(W x) = σ(Sq x) minden W ∈ Σ∗ és x ∈ Σ-re.

A

A

Bizonyítás. Legyen u = σ(W x) és r = σ(Sq x). Tehát a legnagyobb olyan u, amelyre Su W x. Így Su−1 W , tehát σ definíciója miatt u − 1 ≤ q, így Su−1 Sq , ezért Su = Su−1 x Sq x. De r a legnagyobb olyan index, hogy Sr Sq x, tehát u ≤ r. Másrészt Sr Sq x W x, tehát r ≤ u. Kaptuk, hogy u = r. 

A

A

A

A

A

Su W x ... Sq ...

x

Sr 2. ábra. Az állítás bizonyításának szemléltetése

Olyan automatát akarunk szerkeszteni, amelynek δ átmenetfüggvénye a σ függvényt számítja, pontosabban:

δ∗ (0,W ) = σ(W ) Legyen Q = {0, 1, . . . , m}, ahol m = |S|. Minden 0 ≤ q ≤ m állapotra és x ∈ Σ jelre:

δ(q, x) =



q + 1, max{k : Sk A Sq x},

ha x = S[q + 1] ha x 6= S[q + 1]

Nyilvánvaló, hogy δ(q, x) = σ(Sq x). 16.2. lemma. Minden W ∈ Σ∗ szóra δ∗ (0,W ) = σ(W ). Bizonyítás. Bizonyítás W hossza szerinti indukcióval. W = λ esetén δ∗ (0,W ) = 0 = σ(W ). Legyen W = V x, V ∈ Σ∗ , x ∈ Σ és tegyük fel, hogy δ∗ (0,V ) = σ(V ) = q.

δ∗ (0,V x) = δ(δ∗ (0,V ), x) ( δ∗ definíciója miatt ) = δ(σ(V ), x) ( az indukciós feltevés miatt ) = δ(q, x) ( az indukciós feltevés miatt ) = σ(Sq x)

δ definíciója miatt

= σ(V x) (a 8.1 lemma miatt )



3

Az átmenetfüggvény kiszámítása

m := |S| ; For q := 0 To m Do For x ∈ Σ Do Begin q := min(m + 1, q + 2); Repeat

k := k − 1; A Sq x ; δ(q, x) := k; Until Sk End;

Az algoritmus futási ideje O(m3 |Σ|). ˝ látni fogjuk, hogy az átmentfüggvény kiszámítható O(m |Σ|) idoben ˝ (Késobb is.)

a a a 0

1

b

2

a a

a b 3

4

a

c 5

a 6

7

b 3. ábra. Az S = ababaca mintát felismero˝ mintailleszto˝ automata átmenetfüggvényének gráfja

a

b

c

S

0

1

0

0

a

1

1

2

0

b

2

3

0

0

a

3

1

4

0

b

4

5

0

0

a

5

1

4

6

c

6

7

0

0

a

7

1

2

0

4. ábra. Az átmenetfüggvény táblázata

4

i A[i] σ(Ai)

0

1

2

3

4

5

6

7

8

9

10 11

a

b

a

b

a

b

a

c

a

b

a

1

2

3

4

5

4

5

6

7

2

3

5. ábra. Az automata muködése ˝ az A = abababacaba szöveg esetén

5

16.3.

Knuth-Morris-Pratt (KMP) algoritmus i b

a

c

b

a

b

a

b

a

a

b

c

a

b

a

b

a

c

a

S

b

a

b

a

c

b

a

a

S

b

A

q a

k

6. ábra. Ha S[1..q] = A[i − m..i − 1], de S[q + 1] 6= A[i], akkor legalább annyit kell léptetni a mintát, hogy Sk

A Sq teljesüljön.

˝ kiszámítható a mintára, továbbá, a léptetés után az összehasonlítást nem kell a minta Alapötlet: a léptetés mértéke elore ˝ kezdeni. elejérol Legyen a minta S, és m = |S|. A minta prefix függvénye

π : {1, · · · , m} → {0, · · · , m − 1} π(q) = max{k : k < q és Sk A Sq } , q = 1, · · · m class KMP { /** * Knuth-Morris-Pratt mintailleszt˝ o algoritmus * */ public static int[] PrefixFuggveny(String minta) { int m = minta.length(); int k = 0; int[] pi = new int[m+1]; for (int q = 1; q < m; q++) { while ((k > 0) && minta.charAt(k) != minta.charAt(q)) k = pi[k-1]; if (minta.charAt(k) == minta.charAt(q)) k++; pi[q] = k; } return pi; } public static int Illeszt(String szoveg, String minta) { int n = szoveg.length(); int m = minta.length(); if (m>n) return -1; int[] pi = PrefixFuggveny(minta); int q = 0; for (int i = 0; i < n; i++) { while ((q > 0) && (minta.charAt(q) != szoveg.charAt(i)))

6

q = pi[q]; if (minta.charAt(q) == szoveg.charAt(i)) q++;

//

if (q == m) { return i-m+1; q = pi[q-1]; } } return -1;

} } A KMP algoritmus futási ideje ˝ Eloször számítsuk ki a P REFIX algoritmus futási idejét amortizált költségelemzés módszerével.

16.3. Állítás. A P REFIX eljárás futási ideje Tlr = O(m). Bizonyítás. Tekintsük a for q:=2 ... ciklus magját, mint a muveleteket. ˝ Az adatszerkezet legyen a k változó, a potenciálfüggvény értéke pedig a k változó aktuális értéke, tehát Dq := k és Φ(Dq ) = k értéke.

Φ(Dm ) ≥ Φ(D0 ) = 0 Legyen cq a for ciklus futási ideje q-ra. cq = 2+ a while ciklusmag k := P[k] végrehajtásainak száma. k := P[k] végrehajtása csök˝ kenti k értékét, mert π(k) < k, ugyanakkor k ≥ 0. Ezen kívül csak 1-el nohet k értéke, ha S[k + 1] = S[q] Tehát Φ(Dq−1 ) − Φ(Dq ) legalább annyi, mint a while ciklusmag végrehajtásainak a száma -1. cbq = cq + Φ(Dq ) − Φ(Dq−1 ) ≤ 3, tehát m Tlr (m) = ∑m q=1 cq ≤ ∑q=1 cbq ≤ 3m Hasonlóan bizonyítható, hogy a KMP algoritmus futási ideje legrosszabb esetben O(n).



A prefix függvény számításának helyessége

π∗ (q) = {π(q), π(2) (q), π(3) (q), . . . , π(t) (q)} , ahol π(i) (q) függvény iterációval van definiálva, tehát π(0) (q) = q és π(i+1) (q) = π(π(i) (q)) minden i ≥ 1 esetén, és a π∗ (q) sorozat végetér ha π(t) (q) = 0, azaz t a legkisebb érték, amelyre π(t) (q) = 0.

7

16.4. lemma. (Prefix iterációs lemma) π∗ (q) = {k : k < q ∧ Sk ˝ Bizonyítás. Eloször megmutatjuk, hogy

A Sq }, q = 1, · · · , m

i ∈ π∗ (q) ⇒ Si A Sq .

(1)

Ha i ∈ π∗ (q), akkor i = π(u) (q) valamely u > 0-ra. u szerinti indukcióval bizonyítunk. u = 1 esetén i = π(q), és mivel i < q

Sq

... Sπ(q)

...

Sπ2 (q) ...

Sπt−1 (q) Sπt (q) 7. ábra. A π∗ (q) halmaz elemeinek szemléltetése

A Sq , az állítás igaz. Felhasználva, hogy π(i) < i és Sπ(i) i ∈ π∗ (q). Tehát π∗ (q) ⊆ {k : k < q és Sk A Sq }.

és Sπ(q)

Megmutatjuk, hogy Legyen k < q és Sk

A Sq .

A Si továbbá a < és A relációk tranzitivitását, kapjuk, hogy

{k : k < q és Sk A Sq } ⊆ π∗ (q) Mivel

Sk ... Sq ... Sπi (q)

... Sπi+1 (q)

8. ábra. A {k : k < q és Sk

A Sq } ⊆ π∗ (q) tartalmazás bizonyításának szemléltetése

q > π(q) > · · · > πi (q) > πi+1 (q) > · · · > πt (q) = 0 ezért van olyan i, hogy πi (q) > k ≥ πi+1 (q). Mivel Sk

A Sq és Sπ (q) A Sq és πi (q) > k ezért Sk A Sπ (q) . i

i

πi+1 (q) = π(πi (q)) a legnagyobb olyan j, amelyre S j A Sπi (q) , ezért k = πi+1 (q).

π definíciója szerint



16.5. lemma. Ha π(q) > 0, akkor π(q) − 1 ∈ π∗ (q − 1) minden q = 1, 2, . . . , m-re.

A

Bizonyítás. Ha r = π(q) > 0, akkor r < q és Sr Sq ; tehát r − 1 < q − 1, továbbá Sr és Sq utolsó betujét ˝ elhagyva azt kapjuk, hogy Sr−1 S :q−1 . Tehát a 8.4 lemma miatt π(q) − 1 = r − 1 ∈ π∗ (q − 1). 

A

˝ q = 2, 3, . . . , m értékekre definiáljuk az Eq−1 ⊆ π∗ (q) halmazt a következoképpen:

Eq−1

= {k ∈ π∗ (q − 1) : S[k + 1] = S[q]}

= {k : k < q − 1 ∧ Sk A Sq−1 ∧ S[k + 1] = S[q]} (a 8.4. lemma miatt)

= {k : k < q − 1 ∧ Sk+1 A Sq } .

A

A

Az Eq−1 halmaz azokat a k < q − 1 értékeket tartalmazza, amelyekre Sk Sq−1 , ugyanakkor Sk+1 Sq is teljesül, mert S[k + 1] = S[q]. Tehát Eq−1 elemei olyan k ∈ π∗ (q − 1) értékek, amelyek esetén Sk -hoz hozzávéve a végén a minta k + 1-edik betujét ˝ az Sk+1 szó is szuffixe lesz Sq -nak. 8

16.6. következmény. Bármely q = 2, 3, . . . , m értékre

π(q) =



0 1 + max{k ∈ Eq−1 }

ha Eq−1 = 0/ , ha Eq−1 6= 0/ .

Bizonyítás. Ha Eq−1 üres, akkor nincs olyan k ∈ π∗ (q − 1) (beleértve k = 0-t is), amelyre Sk kiegészítheto˝ lenne úgy, hogy Sk+1 valódi szuffixe legyen Sq -nak. Tehát π[q] = 0. Ha Eq−1 nem üres, akkor minden k ∈ Eq−1 -ra k + 1 < q és Sk+1 Sq . Tehát π(q) definíciója miatt

A

π[q] ≥ 1 + max{k ∈ Eq−1 } .

(2)

Vegyük észre, hogy π[q] > 0. Legyen r = π(q) − 1 úgy, hogy r + 1 = π(q). Mivel r + 1 > 0, azt kapjuk, hogy S[r + 1] = S[q]. Továbbá a 8.5. lemma miatt r ∈ π∗ (q − 1). Ezért r ∈ Eq−1 , és így r ≤ max{k ∈ Eq−1 }, vagy ami ezzel ekvivalens:

π(q) ≤ 1 + max{k ∈ Eq−1 } .

(3)



˝ A (2) és (3) egyenlotlenségek együttesen az állítás bizonyítását adják. Most már be tudjuk bizonyítani a P REFIX algoritmus helyességét.

public static int[] PrefixFuggveny(String minta) { int m = minta.length(); int[] pi = new int[m+1]; pi[0]=0; int k = 0; for (int q = 1; q < m; q++) { while ((k > 0) && minta.charAt(k) != minta.charAt(q)) k = pi[k-1]; if (minta.charAt(k) == minta.charAt(q)) k++; pi[q] = k; } return pi; } ˝ teljesül, hogy k = π(q − 1). Kezdetben a P[0]:=0 , majd a ciklusmagban A For q:= ciklus magjának minden végrehajtása elott ˝ a P[q]:=k értékadás miatt. A While ismétlés ellenoriz minden k ∈ π∗ (q − 1) értéket, amíg olyat nem talál, amelyre S[k] = S[q]. Ekkor k az Eq−1 halmaz legnagyobb eleme lesz, így a 8.6. következmény miatt π(q) értékének k + 1 választható. Ha nincs ilyek k, akkor k = 0 lesz és P[q] := 0. A KMP algoritmus helyessége A KMP algoritmus helyességét úgy bizonyítjuk, hogy megmutatjuk, hogy megmutatjuk, hogy minden i-re a q változó értéke éppen σ(Ai ) lesz a véges automata illesztésnél definiált σ függvényre. Ez következik abból, hogy δ(q, A[i]) = 0, vagy δ(q, A[i]) − 1 ∈ π∗ (q). Az állítás bizonyításához legyen k = δ(q, A[i]). Ekkor a δ átmenetfüggvény és σ definíciója miatt Sk Sq A[i]. Ezért k = 0, vagy k ≥ 1 és Sk−1 Sq (Sk és Sq A[i] utolsó betujének ˝ elhagyásával). A második esetben k − 1 ∈ π∗ (q), tehát vagy k = 0, vagy ∗ k − 1 ∈ π (q), így az állítás igaz. ˝ a q változó értékét. A prefix iterációs lemma miatt a ciklusban a q:=P[q] értékadásokkal Jelöljük q0 -vel a while ciklus elott éppen a π∗ (q) = {k : k < q ∧ Sk Sq } halmaz elemeit vesszük sorra. π∗ (q0 ) elemeit csökkeno˝ sorrendben vizsgálva határozzuk meg δ(q0 , A[i])-t. Az állítás alapján kezdetben q = δ∗ (0, Ai−1 ) = σ(Ai−1 = és a q:=P[q] (azaz q := π(q)) értékadást addig hajtjuk végre, amíg vagy q = 0, vagy S[q] = A[i] nem lesz. Az elso˝ esetben δ(q0 , A[i]) = 0, a második esetben q a Eq0 −1 -beli legnagyobb szám, ezért a 8.6. következmény miatt δ(q0 , A[i]) = q + 1.

A

A

A

9