Boyerův–Mooreův algoritmus

Boyerův–Mooreův algoritmus pro vyhledávání řetězců je v matematické informatice efektivní algoritmus pro vyhledávání v textu, který je standardním benchmarkem v literatuře o praktickém vyhledávání řetězců.^[1] Algoritmus vytvořil Robert S. Boyer a J Strother Moore v roce 1977.^[2] Původní článek obsahoval statické tabulky pro výpočet posunutí vzorku bez vysvětlení, jak je získat. Algoritmus pro vytváření tabulek byl publikován v navazujícím článku; ten obsahoval chyby, které v roce 1980 opravil Wojciech Rytter.^[3]^[4]

Algoritmus předzpracovává vzorek, jehož výskyt se má vyhledávat. Je tedy vhodný v případech, kdy vzorek je mnohem kratší než text nebo když se stejný vzorek používá ve více hledáních. Boyerův–Mooreův algoritmus používá informace získané během předzpracování pro přeskakování částí textu, díky čemuž je násobně rychlejší než mnoho jiných algoritmů vyhledávání vzorků. Algoritmus obecně pracuje rychleji pro větší délku vzorku. Jeho klíčovou vlastností je, že vzorek porovnává od konce místo od začátku, a že místo porovnávání každého jednotlivého znaku v textu přeskakuje kusy textu o více znaků.

Definice

A	N	P	A	N	M	A	N	-
P	A	N	-	-	-	-	-	-
-	P	A	N	-	-	-	-	-
-	-	P	A	N	-	-	-	-
-	-	-	P	A	N	-	-	-
-	-	-	-	P	A	N	-	-
-	-	-	-	-	P	A	N	-

Zarovnání vzorku PAN k textu ANPANMAN,
od k=3 do k=8. Shoda se objevuje na pozici k=5.

T označuje vstupní text, který se má prohledávat. Jeho délka je n.
P označuje řetězec, který se má vyhledat, nazývaný vzorek. Jeho délka je m.
S[i] označuje znak s indexem i v řetězci S, čísluje se od 1.
S[i..j] označuje podřetězec řetězce S od indexu i po index j, včetně.
předpona S je podřetězec S[1..i] pro nějaké i v rozsahu [1, l], kde l je délka S.
přípona S je podřetězec S[i..l] pro nějaké i v rozsahu [1, l], kde l je délka S.
zarovnání P s T je index k v T takový, že poslední znak P je zarovnaný s indexem k v textu T.
ke shodě nebo výskytu P dojde při zarovnání k, pokud P se rovná T[(k-m+1)..k].

Popis

Boyerův–Mooreův algoritmus hledá výskyty vzorku $P$ v textu $T$ explicitním porovnáváním znaků v různých pozicích. Místo zkoušení všech zarovnání (kterých je $n-m+1$ ) Boyerův–Mooreův algoritmus používá informace získané předzpracováním $P$ , aby bylo možné co nejvíc zarovnání přeskočit.

Starší algoritmy vyhledání kontrolují, zda se každý znak textu neshoduje s prvním znakem vzorku. Pokud je nalezena shoda v prvním znaku, kontrolují se následující znaky textu s dalšími znaky vzorku. Pokud není nalezena úplná shoda, pak je text opět kontrolován znak po znaku ve snaze najít shodu. Musí být tedy prověřen téměř každý znak textu.

Základním principem tohoto algoritmu je, že se začátek vzorku přiloží na začátek textu (jinak řečeno konec vzorku se zarovná s indexem $m$ textu) a porovná se poslední znak vzorku s příslušným znakem textu; pokud znaky nesouhlasí, pak není nutné prohledávat další znaky ve vzorku. Naopak, pokud se znak z textu ve vzorku vůbec nevyskytuje, je možné vzorek posunout o celou jeho délku $m$ ; pokud se vyskytuje, je možné posunout vzorek tak, aby znak v textu byl zarovnaný s jedním z výskytů téhož znaku ve vzorku. Toto skákání po textu místo kontroly každého znaku v textu snižuje počet porovnání, které bylo třeba provést, což je klíčem k efektivitě algoritmu.

Formálněji algoritmus začíná se zarovnáním $k=m$ , kdy je začátek $P$ je zarovnaný se začátkem $T$ . Znaky v $P$ a $T$ se pak porovnávají počínaje indexem $m$ v $P$ a $k$ v $T$ . Řetězce se porovnávají pozpátku od konce $P$ k začátku $P$ . Porovnání pokračuje, dokud není dosažen začátek $P$ (což znamená, že byla nalezena úplná shoda) nebo dokud se neobjeví neshoda; pak je vzorek posunut dopředu (vpravo) podle maximální hodnoty povolené několika pravidly. Porovnání se provádí znovu v novém zarovnání, a proces se opakuje, dokud vzorek není posunut za konec $T$ , což znamená, že další shoda již neexistuje.

Pravidla pro posun jsou realizována vyhledáváním v tabulce v konstantním čase; tabulka se vytvoří během předzpracování vzorku $P$ .

Posunová pravidla

Posun se určí aplikací dvou pravidel: pravidla pravidlo špatného znaku a pravidla dobré přípony. Skutečné posunutí je maximum posunutí určených těmito pravidly.

Pravidlo špatného znaku

Popis

-	-	-	-	X	-	-	K	-	-	-
A	N	P	A	N	M	A	N	A	M	-
-	N	N	A	A	M	A	N	-	-	-
-	-	-	N	N	A	A	M	A	N	-

Ukázka pravidla špatného znaku se vzorkem P = NNAAMAN. Ve sloupci označeném X je neshoda – ve vstupním textu je N, zatímco ve vzorku je A. Vzorek je posunut doprava (v tomto případě o 2), takže je nalezen další výskyt znaku N (ve vzorku P) vlevo od aktuálního znaku (kterým je prostřední A).

Pravidlo špatného znaku se týká znaku v $T$ , který se neshoduje se znakem v $P$ . Pokud se najde další výskyt tohoto znaku vlevo v $P$ , zkusí se posun který tento výskyt uvede do souladu s chybným výskytem v $T$ . Pokud se neshodující se znak vlevo v $P$ nevyskytuje, zkusí se posun, který posune celé $P$ za místo neshody.

Předzpracování

Předzpracování závisí na přesném tvaru, jaký má mít tabulka pro pravidlo špatného znaku, ale jednoduché řešení vyhledávání v konstantním čase je následující: vytvořit dvojrozměrnou tabulku, jejíž jeden index je index znaku $c$ v abecedě a druhý index $i$ ve vzorku. Hodnotou bude výskyt $c$ v $P$ s následujícím indexem $j<i$ , nebo -1, pokud žádný takový výskyt neexistuje. Navržený posun pak bude $i-j$ , s časovou složitostí vyhledávání $O(1)$ a prostorovou složitostí $O(km)$ , kde $k$ je počet symbolů abecedy.

Implementace v jazyce C a Javě níže mají prostorovou složitost $O(k)$ (make_delta1, makeCharTable). To je totéž jako původní delta1 a BMH tabulka špatného znaku. Tato tabulka převádí znak na pozici $i$ na posunutí o velikosti $\operatorname {len} (p)-1-i$ , přičemž přednost má poslední výskyt s nejmenším posunutím. Všechny nepoužité znaky jsou nastaveny na $\operatorname {len} (p)$ , což je hodnota plnící roli zarážky.

Pravidlo dobré přípony

Popis

-

X

-

K

-

M

A

N

P

A

N

A

M

A

N

A

P

-

A

N

A

M

P

N

A

M

-

A

N

A

M

P

N

A

M

-

Ukázka pravidla dobré přípony se vzorkem P = ANAMPNAM. t je v tomto případě T[6..8] a t' je P[2..4].

Myšlenka i implementace pravidla dobré přípony je mnohem složitější než pravidlo špatného znaku. Stejně jako pravidlo špatného znaku také využívá toho, že algoritmus začíná porovnávat na konci vzorku a postupuje směrem k začátku vzorku. To lze popsat takto:^[5]

Předpokládejme, že pro dané zarovnání P a T podřetězec t textu T je shodný s nějakou příponou P a předpokládejme, že t je největší takový podřetězec pro dané zarovnání.

Potom najdeme (pokud existuje) nejpravější kopii t' řetězce t v P takovou, že t' není příponou P a znak vlevo od t' v P se liší od znaku vlevo od t v P. Posuneme P vpravo , takže podřetězec t' v P je zarovnaný s podřetězcem t v T.

Pokud t' neexistuje, pak posuneme levý konec P doprava o nejmenší množství (za levým koncem t v T) tak, že předpona posunutého vzorku se shoduje s příponou t v T (včetně případů, kdy t je přesnou shodou P.

Pokud takový posun není možný, pak posuneme P o celou jeho délku vpravo.

Předzpracování

Pravidlo dobré přípony vyžaduje dvě tabulky: jednu pro použití v obecném případě (když je kopie t' nalezena), a druhou pro použití, když obecný případ nevrátí smysluplný výsledek. Tyto tabulky budeme označovat $L$ a $H$ . Jejich definice jsou následující:^[5]

Pro každé $i$ je $L[i]$ největší pozice menší než $m$ taková, že řetězec $P[i..m]$ se shoduje s příponou $P[1..L[i]]$ a takový, že znak před příponou není roven $P[i-1]$ . Pokud neexistuje žádné pozice vyhovující této podmínce, $L[i]$ bude nula.

Nechť $H[i]$ označuje délku nejdelší přípony $P[i..m]$ , což je zároveň také předpona $P$ , pokud existuje. Pokud neexistuje, pak $H[i]$ je nula.

Obě tyto tabulky lze sestrojit v čase $O(m)$ a zabírají prostor $O(m)$ . Posun zarovnání pro index $i$ v $P$ popisuje vztah $m-L[i]$ nebo $m-H[i]$ . $H$ se použije pouze tehdy, když $L[i]$ je nulové nebo byla nalezena shoda.

Galilovo pravidlo

Jednoduchou ale významnou optimalizaci Boyerova-Mooreova algoritmu zveřejnil v roce 1979 Zvi Galil.^[6] Galilovo pravidlo se nezabývá posouváním, ale zrychlením skutečného porovnávání při každém zarovnání tím, že přeskakuje úseky, o nichž je známo, že se shodují. Předpokládejme, že při zarovnání $k 1$ je vzorek $P$ porovnán s $T$ až po znak $c$ v $T$ . Pak, pokud se $P$ posune na $k 2$ , tak, že jeho levý konec je mezi $c$ a $k 1$ , musí se v další fázi porovnání předpona $P$ shodovat s podřetězcem $T [(k 2 - n).. k 1]$ . Pokud tedy porovnání dojde až na pozici $k 1$ v textu $T$ , lze výskyt $P$ zaznamenat bez explicitního porovnávání za $k 1$ . Kromě zvýšení efektivity Boyerova-Mooreova algoritmu, je Galilovo pravidlo požadováno pro důkaz, že algoritmus pracuje v lineárním čase i v nejhorším případě.

Galilovo pravidlo je ve své původní verzi účinné pouze pro verze, jejichž výstupem je více shod. Rozsah podřetězců aktualizuje pouze pro $c = 0$ , tj. při plné shodě. Zobecněná verze pro popis dílčích shod byla publikována v roce 1985 jako Apostolicův–Giancarlův algoritmus.^[7]

Varianty

Boyerův–Mooreův–Horspoolův algoritmus je zjednodušením Boyerova–Mooreova algoritmu s použitím pouze pravidla špatného znaku.

Apostolicův–Giancarlův algoritmus urychluje proces kontroly, zda při daném zarovnání došlo ke shodě, tím, že vynechává explicitní porovnání znaků. Využívá informace získané během předzpracování vzorku ve spojení s délkami shod přípon zaznamenaných v každém pokusu o shodu. Ukládání délek shod přípon vyžaduje další tabulku stejné velikosti k text je searched.

Raitův algoritmus vylepšuje výkonnost Boyerova–Mooreova–Horspoolova algoritmu. Vyhledávací vzorek určitého podřetězce v daném řetězci je odlišný od Boyerova–Mooreova–Horspoolova algoritmu.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Boyer–Moore string-search algorithm na anglické Wikipedii.

↑ HUME, Andrew; SUNDAY, Daniel. Fast String Searching. Software: Practice and Experience. November 1991, roč. 21, čís. 11, s. 1221–1248. DOI 10.1002/spe.4380211105. S2CID 5902579.
↑ BOYER, Robert S.; MOORE, J Strother. A Fast String Searching Algorithm.. Comm. ACM. New York: Association for Computing Machinery, October 1977, roč. 20, čís. 10, s. 762–772. ISSN 0001-0782. DOI 10.1145/359842.359859. S2CID 15892987.
↑ KNUTH, Donald E.; MORRIS, James H., Jr.; PRATT, Vaughan R., 1977. Fast pattern matching in strings. SIAM Journal on Computing. Roč. 6, čís. 2, s. 323–350. Dostupné online. ISSN 0097-5397. DOI 10.1137/0206024.
↑ RYTTER, Wojciech, 1980. A Correct Preprocessing Algorithm for Boyer–Moore String-Searching. SIAM Journal on Computing. Roč. 9, čís. 3, s. 509–512. ISSN 0097-5397. DOI 10.1137/0209037.
↑ ^a ^b GUSFIELD, Dan, 1999. Algorithms on Strings, Trees, and Sequences. 1. vyd. [s.l.]: Cambridge University Press. ISBN 0521585198. Kapitola Chapter 2 - Exact Matching: Classical Comparison-Based Methods, s. 19–21.
↑ GALIL, Z. On improving the worst case running time of the Boyer–Moore string matching algorithm. Comm. ACM. New York: Association for Computing Machinery, September 1979, roč. 22, čís. 9, s. 505–508. ISSN 0001-0782. DOI 10.1145/359146.359148. S2CID 1333465.
↑ APOSTOLICO, Alberto; GIANCARLO, Raffaele. The Boyer–Moore–Galil String Searching Strategies Revisited. SIAM Journal on Computing. February 1986, roč. 15, s. 98–105. Dostupné online. DOI 10.1137/0215007. (anglicky)

Literatura

POKORNÝ, Jaroslav; SNÁŠEL, Václav; HÚSEK, Dušan, 1998. Dokumentografické informační systémy. Praha: Karolinum – vydavatelství Univerzity Karlovy. 158 s. ISBN 80-7184-764-X. S. 30–31.
MELICHAR, Bořivoj, 1994. Textové informační systémy. Praha: vydavatelství ČVUT. 101 s. ISBN 80-01-01206-9. S. 34–36.

Externí odkazy

Obrázky, zvuky či videa k tématu Boyerův–Mooreův algoritmus na Wikimedia Commons
Původní článek o Boyerově–Mooreově algoritmu
Příklad Boyerova–Mooreova algoritmu z domovské stránky spoluobjevitele algoritmu J Strothera Moorea
článek Richarda Colea z roku 1991 s důkazem lineární složitosti

[1] HUME, Andrew; SUNDAY, Daniel. Fast String Searching. Software: Practice and Experience. November 1991, roč. 21, čís. 11, s. 1221–1248. DOI 10.1002/spe.4380211105. S2CID 5902579.

[original-2] BOYER, Robert S.; MOORE, J Strother. A Fast String Searching Algorithm.. Comm. ACM. New York: Association for Computing Machinery, October 1977, roč. 20, čís. 10, s. 762–772. ISSN 0001-0782. DOI 10.1145/359842.359859. S2CID 15892987.

[Knuth_Morris_Pratt-3] KNUTH, Donald E.; MORRIS, James H., Jr.; PRATT, Vaughan R., 1977. Fast pattern matching in strings. SIAM Journal on Computing. Roč. 6, čís. 2, s. 323–350. Dostupné online. ISSN 0097-5397. DOI 10.1137/0206024.

[Rytter1980-4] RYTTER, Wojciech, 1980. A Correct Preprocessing Algorithm for Boyer–Moore String-Searching. SIAM Journal on Computing. Roč. 9, čís. 3, s. 509–512. ISSN 0097-5397. DOI 10.1137/0209037.

[ASTS-5] GUSFIELD, Dan, 1999. Algorithms on Strings, Trees, and Sequences. 1. vyd. [s.l.]: Cambridge University Press. ISBN 0521585198. Kapitola Chapter 2 - Exact Matching: Classical Comparison-Based Methods, s. 19–21.

[galil-6] GALIL, Z. On improving the worst case running time of the Boyer–Moore string matching algorithm. Comm. ACM. New York: Association for Computing Machinery, September 1979, roč. 22, čís. 9, s. 505–508. ISSN 0001-0782. DOI 10.1145/359146.359148. S2CID 1333465.

[7] APOSTOLICO, Alberto; GIANCARLO, Raffaele. The Boyer–Moore–Galil String Searching Strategies Revisited. SIAM Journal on Computing. February 1986, roč. 15, s. 98–105. Dostupné online. DOI 10.1137/0215007. (anglicky)

[1]

[2]

[3]

[4]

[5]

[6]

[7]