Zobrazení zdroje stránky Boyerův–Mooreův algoritmus

'''Boyerův–Mooreův algoritmus pro vyhledávání řetězců''' je v [[Matematická informatika|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ů.<ref>{{Citace periodika
 | příjmení = Hume
 | jméno = Andrew
 | příjmení2 = Sunday
 | jméno2 = Daniel
 | s2cid = 5902579
 | datum = November 1991
 | titul = Fast String Searching
 | periodikum = Software: Practice and Experience
 | ročník = 21
 | číslo = 11
 | strany = 1221–1248
 | doi = 10.1002/spe.4380211105
 | ref = harv
}}</ref> Algoritmus vytvořil [[Robert S. Boyer]] a [[J Strother Moore]] v roce 1977.<ref name="original">
{{Citace periodika
 | příjmení = Boyer
 | jméno = Robert S.
 | odkaz na autora = Robert S. Boyer
 | příjmení2 = Moore
 | jméno2 = J Strother
 | odkaz na autora2 = J Strother Moore
 | titul = A Fast String Searching Algorithm.
 | periodikum = Comm. ACM
 | ročník = 20
 | číslo = 10
 | strany = 762–772
 | vydavatel = Association for Computing Machinery
 | místo = New York
 | datum = October 1977
 | issn = 0001-0782
 | doi = 10.1145/359842.359859
 | s2cid = 15892987
 | doi-access = free
 | ref = harv
}}
</ref> 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]].<ref name="Knuth_Morris_Pratt">{{Citace periodika
 | příjmení = Knuth
 | jméno = Donald E.
 | odkaz na autora = Donald Ervin Knuth
 | příjmení2 = Morris
 | jméno2 = James H., Jr.
 | odkaz na autora2 = James H. Morris
 | příjmení3 = Pratt
 | jméno3 = Vaughan R.
 | odkaz na autora3 = Vaughan Pratt
 | titul = Fast pattern matching in strings
 | periodikum = SIAM Journal on Computing
 | issn = 0097-5397
 | ročník = 6
 | číslo = 2
 | strany = 323–350
 | rok = 1977
 | url = http://citeseer.ist.psu.edu/context/23820/0
 | doi = 10.1137/0206024
 | citeseerx = 10.1.1.93.8147
 | ref = harv
}}</ref><ref name="Rytter1980">{{Citace periodika
 | příjmení = Rytter
 | jméno = Wojciech
 | titul = A Correct Preprocessing Algorithm for Boyer–Moore String-Searching
 | periodikum = SIAM Journal on Computing
 | ročník = 9
 | číslo = 3
 | rok = 1980
 | strany = 509–512
 | issn = 0097-5397
 | doi = 10.1137/0209037
 | ref = harv
}}</ref>

Algoritmus [[Preprocesor|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 ==
{{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||-
{{Float end|caption=Zarovnání vzorku '''PAN''' k textu '''ANPANMAN''',<br>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 {{mvar|P}} v textu {{mvar|T}} explicitním porovnáváním znaků v různých pozicích. Místo [[řešení hrubou silou|zkoušení všech zarovnání]] (kterých je <math>n - m + 1</math>) Boyerův–Mooreův algoritmus používá informace získané předzpracováním {{mvar|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 {{mvar|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 {{mvar|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 <math>k = m</math>, kdy je začátek {{mvar|P}} je zarovnaný se začátkem {{mvar|T}}. Znaky v {{mvar|P}} a {{mvar|T}} se pak porovnávají počínaje indexem {{mvar|m}} v {{mvar|P}} a {{mvar|k}} v {{mvar|T}}. Řetězce se porovnávají pozpátku od konce {{mvar|P}} k začátku {{mvar|P}}. Porovnání pokračuje, dokud není dosažen začátek {{mvar|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 {{mvar|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 {{mvar|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 ====
{{Float begin|side=right|width=340px}}
| -||-||-||-||X||-||-||K||-||-||-
|-
| A||N||P||A||<span style="color:#FF0000">N</span>||M||A||N||A||M||-
|-
| -||N||<span style="color:#0000FF">N</span>||A||A||M||A||N||-||-||-
|-
| -||-||-||N||<span style="color:#0000FF">N</span>||A||A||M||A||N||-
{{Float end|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 {{mvar|T}}, který se neshoduje se znakem v {{mvar|P}}. Pokud se najde další výskyt tohoto znaku vlevo v {{mvar|P}}, zkusí se posun který tento výskyt uvede do souladu s chybným výskytem v {{mvar|T}}. Pokud se neshodující se znak vlevo v {{mvar|P}} nevyskytuje, zkusí se posun, který posune celé {{mvar|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 {{mvar|c}} v abecedě a druhý index {{mvar|i}} ve vzorku. Hodnotou bude výskyt {{mvar|c}} v {{mvar|P}} s následujícím indexem <math>j < i</math>, nebo -1, pokud žádný takový výskyt neexistuje. Navržený posun pak bude <math>i - j</math>, s časovou složitostí vyhledávání <math>O(1)</math> a prostorovou složitostí <math>O(km)</math>, kde {{mvar|k}} je počet symbolů abecedy.

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

=== Pravidlo dobré přípony ===

==== Popis ====
{{Float begin|side=right|width=380px}}
| -||-||-||-||X||-||-||K||-||-||-||-||-
|-
| M||A||N||P||A||<span style="color:#0000FF">N</span>||<span style="color:#0000FF">A</span>||<span style="color:#0000FF">M</span>||A||N||A||P||-
|-
| A||<span style="color:#FF0000">N</span>||<span style="color:#FF0000">A</span>||<span style="color:#FF0000">M</span>||P||<span style="color:#0000FF">N</span>||<span style="color:#0000FF">A</span>||<span style="color:#0000FF">M</span>||-||-||-||-||-
|-
| -||-||-||-||A||<span style="color:#FF0000">N</span>||<span style="color:#FF0000">A</span>||<span style="color:#FF0000">M</span>||P||N||A||M||-
{{Float end|Ukázka pravidla dobré přípony se vzorkem '''P''' {{=}} '''ANAMPNAM'''. '''''t''''' je v tomto případě '''T'''[6..8] a '''''t'<nowiki />''''' 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:<ref name="ASTS">
{{Citace monografie
 | příjmení = Gusfield
 | jméno = Dan
 | titul = Algorithms on Strings, Trees, and Sequences
 | vydavatel = Cambridge University Press
 |  orig-year  = 1997
 | rok = 1999
 | vydání = 1
 | kapitola = Chapter 2 - Exact Matching: Classical Comparison-Based Methods
 | strany = 19–21
 | isbn = 0521585198
 | ref = harv
}}
</ref>

<blockquote>
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'<nowiki />''''' řetězce '''''t''''' v '''''P''''' takovou, že '''''t'<nowiki />''''' není příponou '''''P''''' a znak vlevo od '''''t'<nowiki />''''' v '''''P''''' se liší od znaku vlevo od '''''t''''' v '''''P'''''. Posuneme '''''P''''' vpravo , takže podřetězec '''''t'<nowiki />''''' v '''''P''''' je zarovnaný s podřetězcem '''''t''''' v '''''T'''''.
# Pokud '''''t'<nowiki />''''' 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.
</blockquote>

==== Předzpracování ====
Pravidlo dobré přípony vyžaduje dvě tabulky: jednu pro použití v obecném případě (když je kopie '''''t'<nowiki />''''' nalezena), a druhou pro použití, když obecný případ nevrátí smysluplný výsledek. Tyto tabulky budeme označovat {{mvar|L}} a {{mvar|H}}. Jejich definice jsou následující:<ref name="ASTS" />

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

<blockquote>
Nechť <math>H[i]</math> označuje délku nejdelší přípony <math>P[i..m]</math>, což je zároveň také předpona {{mvar|P}}, pokud existuje. Pokud neexistuje, pak <math>H[i]</math> je nula.
</blockquote>

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

== Galilovo pravidlo ==
Jednoduchou ale významnou optimalizaci Boyerova-Mooreova algoritmu zveřejnil v roce 1979 [[Zvi Galil]].<ref name="galil">
{{Citace periodika
 | příjmení = Galil
 | jméno = Z.
 | odkaz na autora = Zvi Galil
 | titul = On improving the worst case running time of the Boyer–Moore string matching algorithm
 | periodikum = Comm. ACM
 | ročník = 22
 | číslo = 9
 | strany = 505–508
 | vydavatel = Association for Computing Machinery
 | místo = New York
 | datum =  September 1979
 | issn = 0001-0782
 | doi = 10.1145/359146.359148
 |  s2cid  = 1333465
 | ref = harv
}}
</ref>
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í {{math|''k''<sub>1</sub>}} je vzorek {{math|'''''P'''''}} porovnán s {{math|'''''T'''''}} až po znak {{math|'''''c'''''}} v {{math|'''''T'''''}}. Pak, pokud se {{math|'''''P'''''}} posune na {{math|''k''<sub>2</sub>}}, tak, že jeho levý konec je mezi {{math|'''''c'''''}} a {{math|''k''<sub>1</sub>}}, musí se v další fázi porovnání předpona {{math|'''''P'''''}} shodovat s podřetězcem {{math|'''''T'''''[(''k''<sub>2</sub> - ''n'')..''k''<sub>1</sub>]}}. Pokud tedy porovnání dojde až na pozici {{math|''k''<sub>1</sub>}} v textu {{math|'''''T'''''}}, lze výskyt {{math|'''''P'''''}} zaznamenat bez explicitního porovnávání za {{math|''k''<sub>1</sub>}}. 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 {{math|1='''''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]].<ref>{{Citace periodika
 | příjmení = Apostolico
 | jméno = Alberto
 | příjmení2 = Giancarlo
 | jméno2 = Raffaele
 | titul = The Boyer–Moore–Galil String Searching Strategies Revisited
 | periodikum = SIAM Journal on Computing
 | ročník = 15
 | strany = 98–105
 | jazyk = en
 | doi = 10.1137/0215007
 | datum = February 1986
 | url = https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech
 | ref = harv
}}</ref>

== 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 ===
{{Překlad|en|Boyer–Moore string-search algorithm|1161693218}}<references />

=== Literatura ===
* {{Citace monografie
 | titul = Dokumentografické informační systémy
 | jméno = Jaroslav
 | příjmení = Pokorný
 | jméno2 = Václav
 | příjmení2 = Snášel
 | jméno3 = Dušan
 | příjmení3 = Húsek
 | vydavatel = Karolinum – vydavatelství Univerzity Karlovy
 | rok = 1998
 | místo = Praha
 | isbn = 80-7184-764-X
 | počet stran = 158
 | strany = 30–31
 | ref = harv
}}
* {{Citace monografie
 | titul = Textové informační systémy
 | jméno = Bořivoj
 | příjmení = Melichar
 | vydavatel = vydavatelství ČVUT
 | rok = 1994
 | místo = Praha
 | isbn = 80-01-01206-9
 | počet stran = 101
 | strany = 34–36
 | ref = harv
}}

=== Externí odkazy ===
* {{Commonscat}}
* [http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf Původní článek o Boyerově–Mooreově algoritmu]
* [http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html Příklad Boyerova–Mooreova algoritmu] z domovské stránky spoluobjevitele algoritmu [[J Strother Moore|J Strothera Moorea]]
* [http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps článek Richarda Colea z roku 1991 s důkazem lineární složitosti]
{{Autoritní data}}

[[Kategorie:Algoritmy pro vyhledávání v textu]]