11.4. Boyer-Moore algoritmus

Az eddigi módszerek a mintát balról jobbra ellenőrizték. A Boyer-Moore algoritmus a mintát ugyancsak ebbe az irányba mozgatja, viszont ott már jobbról balra ellen őrzi az illeszkedést. Ez a módszer két heurisztikát használ a soron következő eltolás méretének meghatározására. Az első, az „utolsó karakter” heurisztika minden egyes betűhöz (karakterhez) megadja, hogy az hol fordult elő utoljára a mintában (11.4.1. és 11.4.2. ábra). Ha a szöveg épp vizsgált karaktere nem fordul elő a mintában, akkor a mintát eltolhatjuk eme karakter után. Ha viszont szerepel benne a karakter, akkor annak az utolsó előfordulását illesztjük a szöveg megfelelő karakteréhez. Ez elvileg jelenthetne negatív (bal irányú) eltolást is, de ekkor a másik heurisztikát alkalmazzuk.

11.1. ábra - 11.4.1. ábra. Utolsó pozíció heurisztika, amikor a nem egyező karakter szerepel a mintában

11.4.1. ábra. Utolsó pozíció heurisztika, amikor a nem egyező karakter szerepel a mintában

11.2. ábra - 11.4.2. ábra. Utolsó pozíció heurisztika, amikor a nem egyező karakter nem szerepel a mintában

11.4.2. ábra. Utolsó pozíció heurisztika, amikor a nem egyező karakter nem szerepel a mintában

A „jó szuffix” heurisztikánál úgy mozgatjuk a mintát, hogy a szövegnek arra a részére, amelyre már illeszkedett minta vizsgált része, újra (legalább részben) illeszkedjék. Ha az illeszkedő részminta (az ábrán ) újra előfordul a szövegben, akkor ezt a részt kell illeszteni (11.4.3. ábra), egyébként eme minta egy szuffixét (az ábrán ) kell illeszteni a szöveghez (11.4.3. ábra). A Boyer-Moore algoritmus nem illeszekedés esetén a két heurisztika közül azt választja, amellyel nagyobbat léphet. Noha a módszer bonyoltsága O(nm), a legrosszabb eset csak kivételes esetekben fordul elő, s kellően nagy ábécé esetén az algoritmus rendszerint nagyon gyors. Ez az oka annak, hogy napjainkban szinte minden szövegszerkesztőben ezt a módszert implementálták. A boyer.htm állomány egy olyan programot tartalmaz, amely véletlen módon generált szövegre és mintára végrehatja a Boyer-Moore algoritmust. A honlapon az aláhúzások jelzik az illeszkedést, a számok pedig a szöveg megvizsgált karaktereit.

11.3. ábra - 11.4.3. ábra. A jó szuffix heurisztika, mikor az újra előfordul

11.4.3. ábra. A jó szuffix heurisztika, mikor az újra előfordul

11.4. ábra - 11.4.4. ábra. A jó szuffix heurisztika, mikor az nem fordul elő újra

11.4.4. ábra. A jó szuffix heurisztika, mikor az nem fordul elő újra

Function UTOLSÓ-POZÍCIÓ(P,m,S) 
Input: P minta, m minta hossza,S ábécé 
Output: u utolsó pozíció heurisztika értékei 
1 forall the a ∊ S do 
2    u[a] = 0
3 endfall 
4 for j = 1 to m do 
5    u[P[j]] = j
6 endfor 
7 return u 

Function JÓ-SZUFFIX(P,m) 
Input: P minta, m minta hossza 
Output: g jó szuffix heurisztika értékei 
1  p1 = PREFIX-FÜGGVÉNY-SZÁMÍTÁS(P) 
2  P' = FORDÍT(P) 
3  p2 = PREFIX-FÜGGVÉNY-SZÁMÍTÁS(P') 
4  for j = 0 to m do 
5     g[j] = m − p1[m]
6  endfor 
7  for l = 1 to m do 
8     j = m − p2[l] 
9     if g[j] ≥ l − p2[l] then 
10       g[j] = l − p2[l] 
11    endif
12 endfor 
13 return g 

Procedure BOYER-MOORE-ILLESZTő(T,P,S) 
Input: T szöveg, P minta, S ábécé 
Eredmény: illeszkedés esetén figyelmeztetés 
1  n = T.hossz 
2  m = P.hossz 
3  u = UTOLSÓ-POZÍCIÓ(P,m,S) 
4  g = JÓ-SZUFFIX(P,m) 
5  s = 0 
6  while s ≤ n − m do 
7     j = m 
8     while j ≥ 0 and P[j] == T[s + j] do 
9        j = j − 1 
10    endw
11    if j == 0 then 
12       kiír ( illeszkedés az s pozíción ) 
13       s = s + g[0] 
14    else 
15       s = s + max(g[j], j − u(T[s + j])) 
16    endif 
16 endw