Algoritmus Boyer-Moore-Horspool

Algoritmus Boyer-Moore-Horspool  je algoritmus pro nalezení podřetězce v řetězci , zjednodušená verze algoritmu Boyer-Moore . ABMX funguje lépe než Boyer-Mooreův algoritmus na náhodných textech, průměrné skóre je od do do jednoho znaku textu [1] . Kromě toho je vynechána výpočetně náročná heuristika shody s příponou.

Nicméně odhad ( v nejhorším případě na neperiodických šablonách) pro ABMX je | jehla |·| kupka sena | (místo 3 | kupka sena | pro Boyer-Moore).

Popis algoritmu

Algoritmus je modifikací Boyer-Mooreova algoritmu . Myšlenka algoritmu je taková.

1. Skenování zleva doprava, porovnání v režimu "černá skříňka". Stejně jako v primitivním algoritmu je začátek textu a šablony kombinován, srovnání se provádí pomocí obvyklého postupu „ porovnat paměťové sekce “ . Pokud se všechny znaky vzoru shodovaly s překrývajícími se znaky řetězce, pak byl podřetězec nalezen a hledání je u konce.

Pokud některý znak vzoru neodpovídá odpovídajícímu znaku řetězce, vzor se posune o několik znaků doprava. Těchto „pár“ se vybírá podle takové heuristiky.

2. Změněna heuristika symbolu zastavení. Bereme charakter textu, který se objevil nad posledním znakem vzoru (bez ohledu na to, kde k neshodě došlo!). Na obrázku je "b".

↓ symbol zastavení Text abadb * * * * abbad vzor Další abbad kontrola

Šablonu posuneme tak, aby písmeno „b“ šablony bylo pod symbolem dorazu. To je realizováno pomocí offsetové tabulky: pro každý znak abecedy ukládáme maximální možný posun, který nepřeskočí znak stop. To znamená (při číslování řádků 1): posun ( c ) = | needle |−lastpos( c , needle [1..| needle |−1]) , kde lastpos je poslední výskyt znaku v řetězci, needle [ a .. b ]  je operace podřetězce.

U vzoru "abbad" vypadá tabulka takto.

Symbol A b (jiný)
Zaujatost jeden 2 5

Pro symboly, které nejsou zahrnuty v šabloně, je hodnota offsetu nastavena na délku šablony - 5. Poslední symbol šablony není při výpočtu tabulky offsetů zohledněn (je plný zacyklení ).

Je pohodlnější vypočítat tabulku procházením všech symbolů šablony:

pro c=MIN_CHAR..MAX_CHAR posun[c] = |jehla| pro i=1..|jehla|-1 posun[jehla[i]] = |jehla|-i

Příklad toho, jak algoritmus funguje

Požadovaný vzor je "abbad" (tabulka pro tento vzor je sestavena výše).

abeccacbadbabbad abbad

Na linku vložíme vzorek. Poslední znak zdrojového řetězce "c" není ve vzoru obsažen. Posuňte vzor doprava o 5 pozic podle hodnoty offsetu pro "c":

abeccacbadbabbad abbad

Tři znaky vzoru se shodovaly, ale čtvrtý ne. Posuňte vzor doprava o 5 pozic podle hodnoty offsetu pro "d":

abeccacbadbabbad abbad

Poslední znak řetězce "a" neodpovídá znaku vzoru. Posuňte vzor doprava o 1 podle hodnoty posunu pro "a" a získejte požadovaný výskyt vzoru:

abeccacbadbabbad abbad

Možnosti

Sandiho algoritmus

Za znak stop vezmeme znak následující za jehlou .

Wrightův algoritmus

Empirický algoritmus optimalizovaný pro anglické texty. Porovná poslední znak, pak první, pak prostřední a potom všechny ostatní; v případě nesouladu směna Horspool.

Výhody

Velmi rychle v průměru[ specifikovat ] . Snadná implementace. Používá standardní funkci pro porovnání paměťových oblastí, zpravidla optimalizovaných na úrovni assembleru pro konkrétní procesor.

Nevýhody

Stejně jako ostatní algoritmy z rodiny Boyer-Moore není upraven pro přibližné vyhledávání, současné vyhledávání několika řetězců.

K regresi na "špatných" datech dochází o něco častěji než v algoritmu Boyer-Moore. Čím rozmanitější jsou znaky ve zdrojovém textu, tím lépe se ABMX chová.

Literatura

Poznámky

  1. ↑ Algoritmus Horspool . Získáno 12. srpna 2012. Archivováno z originálu dne 29. srpna 2012.

Odkazy

 Struny
Míry podobnosti řetězců
Hledání podřetězců
palindromy
Sekvenční zarovnání
Struktury přípon
jiný