Vyhledávání v textu

Princip vyhledávání hrubou silou, metody Rabin–Karp, Knuth–Morris–Pratt, Boyer–Moore, principy algoritmů - složitosti.

Problém vyhledávání v textu se dá vyjádřit jako problém nalezení určitého řetězce v jiném řetězci. Často tedy hledáme "jehlu v kupce sena". Často přidáváme k hledanému řetězci další podmínky, jako je například začínající písmeno nesmí být velké, řetězec musí začínat mezerou, před řetězcem se mohou nacházet další dva libovolné znaky apod. Nebo nás může zajímat kolikrát se daný řetězec v textu vyskytuje, či naopak, jaká je pozice prvního výskytu námi hledaného řetězce.

Úvodní pojmy

  • Haystack: Řetězec, ve kterém se snažíme nalézt jiný řetězec. Lze reprezentovat jako pole znaků (array).

  • Needle: Hledaný řetězec, také můžeme reprezentovat jako pole znaků.

  • Abeceda: Množina obsahující všechny znaky, jež se v tetu vyskytují.

Nyní budou následovat algoritmy pro vyhledávání v textu.

Jedná se o:

  • Naivní přístup

  • Rabin–Karp

  • Knuth–Morris–Pratt

  • Boyer–Moore

Naivní přístup (hrubá síla)

Náš haystack tvoří řetězec M: aaaaaaaaab a hledáme needle N ve tvaru aaab.

Naivní přístup spočívá v tom, že půjdeme index po indexu haystack řetězce a budeme ho porovnávat s needle řetězcem. Pokud bude znak v řetězci M souhlasit s prvním znakem v řetězci N, tak porovnáme druhý znak obou řetězců. Takto porovnáváme znaky dokud nedojdeme nakonec řetězce N, nebo dokud nenarazíme na znaky, jež se neshodují. V prvním případě jsme úspěšně nalezli hledaný řetězec. V tom druhém případě přejdeme na další znak v našem hlavním M řetězci a celý postup opakujeme, dokud neprojdeme celý řetězec M.

Průměrná složitost algoritmu: O(n+m); Pro více řetězců k: O(n+m)k
Nejhorší případ: O(n*m) - musíme projít celý hlavní řetězec a pro každý prvek hledaného řetězce projít celý hledaný řetězec až do konce a porovnat ho s hlavním řetězcem.

Rabin–Karp

Jedná se o vyhledávací algoritmus založený na principu hashovací funkce a pohyblivého okénka o velikosti vyhledávaného řetězce.

  • Nejprve algoritmus ohodnotí jednotlivé znaky abecedy.

  • Z těchto ohodnocení algoritmus vytvoří hash hodnotu pro vyhledávaný řetězec.

  • Algoritmus prochází vyhledávacím okénkem prvek po prvku hlavní řetězec, přičemž spočte hash hodnotu okénka v závislosti na tom, jaké znaky se v něm nacházejí.

  • Pokud hodnota hash okénka souhlasí s hash hodnotou vyhledávaného řetězce, tak algoritmus projde prvek po prvku tento subset znaků ve vyhledávacím okénku a porovná ho s vyhledávaným řetězcem podobně jako v případě naivního přístupu (prochází pouze podřetězec o velikosti vyhledávacího okénka, nikoliv celý řetězec, v němž vyhledáváme)

  • Pokud došlo ke shodě hash hodnot, ale řetězec ve vyhledávacím okénku neodpovídá tomu, který hledáme nazýváme tuto situaci spurious hit. Algoritmus pokračuje. Pokud odpovídá, našli jsme shodný řetězec.

  • Algoritmus pokračuje, dokud tímto způsobem neporovná celý hlavní řetězec s vyhledávaným řetězcem.

Výhodou tohoto algoritmu je možnost přeskakovat ty části hlavního řetězce, které mají jinou hash hodnotu nežli vyhledávaný řetězec.

Využití je hlavně v případech, kdy potřebujeme nalézt více řetězců k v hlavním řetězci. Jedno z hlavním využití tohoto algoritmu je například při kontrolách plagiátorství diplomových prací.

Průměrná složitost algoritmu: O(n+m) | Pro více řetězců k: O(n+km)
Nejhorší případ: O(n*m) - všechny nálezy budou spurious hit.

Knuth–Morris–Pratt

Algoritmus pracuje se dvěma řetězci, hlavní řetězec S a vyhledávaný řetězec W. Jeho hlavním cílem je redukce "backtrackingu", tedy nutnosti procházet znaky v řetězci S, které nepovedou ke shodě s řetězcem W.

Zavádí tedy prefix W. Jedná se o jeden či více znaků, kterými tento řetězec začíná. Pokud algoritmus nalezne shodu s S v prefixu, ale na nějakém dalším znaku se již S a W neshoduje, můžeme tyto znaky přeskočit. Pakliže algoritmus nalezne shodu s prefixem, bude v dalším kroku pokračovat od tohoto prefixu.

Průběh algoritmu:

  • Ulož si prefix W (jeden či více znaků).

  • Začni prvním prvkem v S a porovnej s prvním prvkem W. Pokud se neshoduje, opakuj tento krok s dalším prvkem W, dokud nenarazíš na shodu.

  • Pokud jsme našli shodu, porovnáváme následující prvek W s následujícím prvkem S. Pokud máme shodu, přecházíme na další prvek W a S. Pokud v průběhu nacházíme v S prvky, které odpovídají prefixu, ukládáme je do samostatného pole a číslujeme je.

  • Při neshodě algoritmus začíná tam, kde nalezl prefix. Pokud žádný prefix nenalez, začíná na dalším prvku v S, jež se nachází hned za tím, u kterého došlo k neshodě.

  • Postup se opakuje dokud algoritmus neprojde celý řetězec S.

Průměrná složitost algoritmu: O(n+k) kde n je velikost S a k je velikost W. Tato složitost je také jediná možná, díky tomu, že algoritmus si udržuje pozici nalezeného prefixu v S při porovnávání s W a na tuto pozici je schopen se vrátit, čímž přeskakuje hodnoty v S kterými W nezačíná. Není zde nejhorší případ.

Boyer–Moore

Tento algoritmus si zakládá na obráceném porovnávání. Namísto toho, aby porovnával prefix, tedy začátek hledaného řetězce W s hlavním řetězcem S, porovnává suffix, tedy koncové znaky řetězce W s řetězcem S.

V první fázi jsou řetězce S a W srovnány "pod sebe" a algoritmus porovnává znaky zprava doleva. Pokud je nalezen charakter v S, který není v řetězci W, tak zde nemůže být žádná shoda a celý řetězec W může být přesunut tak, aby začínal za pozicí, na které se nachází neshodný charakter v S.

To zda je tento posun ideální či nikoliv je třeba nejdříve ověřit. Algoritmus to dělá pomocí dvou heuristik:

  • Bad Character Heuristics
  • Good Suffix Heuristics

Bad Character Heuristics

Jedná se o případ, kdy nalezneme charakter v S, který nesedí s W.

  • Pokud charakter není obsažen ve vyhledávaném řetězci W, posuneme celý řetězec W za tento charakter v S.

  • Pokud je charakter obsažený ve vyhledávaném řetězci, posuňme vyhledávaný řetězec W tak, aby se charakter ve W shodoval s tím v S.

Hledaný řetězec W obsahuje Bad Character
obr. 1: Hledaný řetězec W obsahuje Bad Character
Převzato z: https://www.javatpoint.com/daa-boyer-moore-algorithm
Hledaný řetězec W neobsahuje Bad Character
obr. 2: Hledaný řetězec W neobsahuje Bad Character
Převzato z: https://www.javatpoint.com/daa-boyer-moore-algorithm

V některých případech se může tímto způsobem řetězec W začít vůči S posouvat zpět, klidně do negativních hodnot. Abychom tomuto zabránily, ukládáme si poslední nalezenou pozici každého charakteru, jež tvoří set W (Někdy také nazývaný abeceda řetězce W)

Good Suffix Heuristics

Good suffix je takový suffix, který se úspěšně shoduje s charaktery, nalezenými v S. Pokud nalezneme pomocí Bad Character Heuristics špatný charakter, který by znamenal negativní posun, zkontrolujeme, zdali souhlasí suffix W s charaktery v S. Pokud ano, posuneme řetězec W o délku, na které se suffix nachází. (Před suffixem se nachází bad character, není tedy možné aby jsme nalezli shodu při posunu zpět)

Posun po aplikování Good Suffix
obr. 3: Posun po aplikování Good Suffix
Převzato z: https://www.javatpoint.com/daa-boyer-moore-algorithm

Průběh algoritmu:

  • Řetězce S a W jsou zarovnány tak, že začínají pod sebou.

  • Kontrolují se shodné znaky zprava doleva.

  • V případě neshody aplikuj Bad Character Heuristics, v případě že toto vyvolá negativní posun, tak aplikuj Good Suffix Heuristics

  • Pokračuj znovu v kontrole zprava doleva.

  • Opakuj postup, dokud nenajdeš shodný řetězec

Nejhorší možná složitost algoritmu: O(m+n) pokud S neobsahuje W nebo O(m*n) pokud S obsahuje W.

Zdroje

  • Wikipedia: Open encyclopedia: String-searching algorithm [online]. c2023 [citováno 23. 04. 2023].
    Dostupný z: https://en.wikipedia.org/wiki/String-searching_algorithm

  • Parewa Labs Pvt. Ltd.: Rabin-Karp Algorithm [online]. c2023 [citováno 23. 04. 2023].
    Dostupný z: https://www.programiz.com/dsa/rabin-karp-algorithm

  • Javapoint: The Rabin-Karp-Algorithm [online]. c2023 [citováno 23. 04. 2023].
    Dostupný z: https://www.javatpoint.com/daa-rabin-karp-algorithm

  • GeeksForGeeks: Rabin-Karp Algorithm for Pattern Searching [online]. c2023 [citováno 23. 04. 2023].
    Dostupný z: https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/

  • Educative, Inc.: What is the Knuth-Morris-Pratt algorithm? [online]. c2023 [citováno 23. 04. 2023].
    Dostupný z: https://www.educative.io/answers/what-is-the-knuth-morris-pratt-algorithm

  • Wikipedia: Open encyclopedia: Knuth–Morris–Pratt algorithm [online]. c2023 [citováno 23. 04. 2023].
    Dostupný z: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

  • Javapoint: The Boyer-Moore Algorithm [online]. c2023 [citováno 23. 04. 2023].
    Dostupný z: https://www.javatpoint.com/daa-boyer-moore-algorithm