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

• 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 ${\displaystyle 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 ${\displaystyle 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

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 ${\displaystyle j<i}$, nebo -1, pokud žádný takový výskyt neexistuje. Navržený posun pak bude ${\displaystyle i-j}$, s časovou složitostí vyhledávání ${\displaystyle O(1)}$ a prostorovou složitostí ${\displaystyle O(km)}$, kde k je počet symbolů abecedy.

Implementace v jazyce C a Javě níže mají prostorovou složitost ${\displaystyle 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 ${\displaystyle i}$ na posunutí o velikosti ${\displaystyle \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 ${\displaystyle \operatorname {len} (p)}$, což je hodnota plnící roli zarážky.

Pravidlo dobré přípony

Popis

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í.

1. 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.
2. 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.
3. 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 ${\displaystyle L[i]}$ největší pozice menší než m taková, že řetězec ${\displaystyle P[i..m]}$ se shoduje s příponou ${\displaystyle P[1..L[i]]}$ a takový, že znak před příponou není roven ${\displaystyle P[i-1]}$. Pokud neexistuje žádné pozice vyhovující této podmínce, ${\displaystyle L[i]}$ bude nula.

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

Obě tyto tabulky lze sestrojit v čase ${\displaystyle O(m)}$ a zabírají prostor ${\displaystyle O(m)}$. Posun zarovnání pro index i v P popisuje vztah ${\displaystyle m-L[i]}$ nebo ${\displaystyle m-H[i]}$. H se použije pouze tehdy, když ${\displaystyle 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₁ je vzorek P porovnán s T až po znak c v T. Pak, pokud se P posune na k₂, tak, že jeho levý konec je mezi c a k₁, musí se v další fázi porovnání předpona P shodovat s podřetězcem T[(k₂ - n)..k₁]. Pokud tedy porovnání dojde až na pozici k₁ v textu T, lze výskyt P zaznamenat bez explicitního porovnávání za k₁. 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.

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