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ů. Algoritmus vytvořil Robert S. Boyer a J Strother Moore v roce 1977. 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.

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

Šablona:Float begin | 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||- Šablona:Float end

• 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 Šablona:Mvar v textu Šablona:Mvar 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 Šablona:Mvar, 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 Šablona:Mvar 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 Šablona:Mvar; 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 Šablona:Mvar je zarovnaný se začátkem Šablona:Mvar. Znaky v Šablona:Mvar a Šablona:Mvar se pak porovnávají počínaje indexem Šablona:Mvar v Šablona:Mvar a Šablona:Mvar v Šablona:Mvar. Řetězce se porovnávají pozpátku od konce Šablona:Mvar k začátku Šablona:Mvar. Porovnání pokračuje, dokud není dosažen začátek Šablona:Mvar (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 Šablona:Mvar, 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 Šablona:Mvar.

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

Šablona:Float begin | -||-||-||-||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||- Šablona:Float end

Pravidlo špatného znaku se týká znaku v Šablona:Mvar, který se neshoduje se znakem v Šablona:Mvar. Pokud se najde další výskyt tohoto znaku vlevo v Šablona:Mvar, zkusí se posun který tento výskyt uvede do souladu s chybným výskytem v Šablona:Mvar. Pokud se neshodující se znak vlevo v Šablona:Mvar nevyskytuje, zkusí se posun, který posune celé Šablona:Mvar 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 Šablona:Mvar v abecedě a druhý index Šablona:Mvar ve vzorku. Hodnotou bude výskyt Šablona:Mvar v Šablona:Mvar 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 Šablona:Mvar 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 $\mathrm{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 $\mathrm{len}(p)$, což je hodnota plnící roli zarážky.

Pravidlo dobré přípony

Popis

Šablona:Float begin | -||-||-||-||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||- Šablona:Float end

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:

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 Šablona:Mvar a Šablona:Mvar. Jejich definice jsou následující:

Pro každé Šablona:Mvar je $L[i]$ největší pozice menší než Šablona:Mvar 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 Šablona:Mvar, 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 Šablona:Mvar v Šablona:Mvar popisuje vztah $m-L[i]$ nebo $m-H[i]$. Šablona:Mvar 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. 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í Šablona:Math je vzorek Šablona:Math porovnán s Šablona:Math až po znak Šablona:Math v Šablona:Math. Pak, pokud se Šablona:Math posune na Šablona:Math, tak, že jeho levý konec je mezi Šablona:Math a Šablona:Math, musí se v další fázi porovnání předpona Šablona:Math shodovat s podřetězcem Šablona:Math. Pokud tedy porovnání dojde až na pozici Šablona:Math v textu Šablona:Math, lze výskyt Šablona:Math zaznamenat bez explicitního porovnávání za Šablona:Math. 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 Šablona:Math, 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.

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

Literatura

• Šablona:Citace monografie
• Šablona:Citace monografie

Externí odkazy

• Šablona:Commonscat
• 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