Hledání podřetězců

Nalezení podřetězce v řetězci  je jedním z nejjednodušších úkolů získávání informací . Používá se jako vestavěná funkce v textových editorech , DBMS , vyhledávačích , programovacích jazycích atd.

Ve vyhledávacích úlohách je tradičně obvyklé označit vyhledávací vzor jako jehla (z  angličtiny  -  „needle“) a řetězec, ve kterém se vyhledávání provádí, jako kupka sena (z  angličtiny  -  „ haystack “). Značíme také Σ abecedu, ve které se vyhledávání provádí.

Selhání primitivního algoritmu

Pokud předpokládáme, že řádky jsou číslovány od 1, vypadá nejjednodušší algoritmus ( anglicky  brute force algorithm, naive algorithm ) takto.

pro i=0...|hromada sena|-|jehla| pro j=0...|jehla| pokud kupka sena[i+j + 1]<>jehla[j] pak dostanu 1 output("Nalezeno: ", i+1) jeden:

Nejjednodušší vyhledávací algoritmus, dokonce i v nejlepším případě , provádí | kupka sena |−| jehla |+1 srovnání; pokud existuje mnoho dílčích shod, rychlost klesne na O (| kupka sena | · | jehla |).

Bylo dokázáno, že primitivní algoritmus dokončí v průměru 2h porovnávání [1] .

Proč potřebujeme tolik algoritmů?

Dnes existuje obrovské množství algoritmů pro vyhledávání podřetězců. Programátor si musí vybrat ten správný v závislosti na těchto faktorech.

  1. Potřebujete vůbec optimalizaci, nebo stačí primitivní algoritmus? Zpravidla jsou to standardní knihovny programovacích jazyků, které jej implementují.
  2. Uživatelská nevraživost. Jinými slovy: nastaví uživatel záměrně data, na kterých bude algoritmus pomalu běžet? Existují velmi jednoduché algoritmy, jejichž nejhorší případ je O (| kupka sena |·| jehla |), ale na "normálních" datech je počet srovnání mnohem menší | kupka sena |. Až v 90. letech 20. století byly vytvořeny algoritmy, které dávají O (| kupka sena |) v nejhorším případě složitost a méně než | kupka sena | průměrný.
  3. Gramatika jazyka může být nepřátelská vůči určitým heuristikám, které zrychlují vyhledávání „v průměru“.
  4. architektura procesoru . Některé procesory mají automatické přírůstky nebo operace SIMD , které vám umožňují rychle porovnat dvě části paměti RAM (například rep cmpsdna x86 ). Na takových procesorech je lákavé použít algoritmus, který by jednoduše porovnával jehlu s kupkou sena  - samozřejmě ne na všech pozicích.
  5. Velikost abecedy. Mnoho algoritmů (zejména ty, které jsou založeny na vzájemném srovnání) má heuristiku související s neshodným znakem. Na velkých abecedách bude tabulka symbolů zabírat hodně paměti, na malých abecedách bude odpovídající heuristika neefektivní.
  6. Možnost indexace kupky sena . Pokud existuje, hledání se vážně urychlí.
  7. Je nutné hledat více řetězců současně? Přibližné hledání? Postranní vlastnosti některých algoritmů ( Aho-Korasik , binární algoritmus ) to umožňují.

Zpravidla v textovém editoru stačí vzít nejjednodušší heuristický algoritmus jako Boyer - Moore - Horspool  - i velmi pomalé PC si s hledáním poradí ve zlomku vteřiny. Pokud se objem textu měří v gigabajtech nebo vyhledávání běží na serveru, který zpracovává mnoho požadavků, musíte zvolit nejúspěšnější dostupný algoritmus. Například programy pro detekci plagiátů provádějí online kontroly pomocí vyhledávacích algoritmů podřetězců mezi velkým počtem dokumentů uložených v jejich vlastní databázi.

Algoritmy

Pro stručnost označujeme:

Výpočetní složitost je určena před prvním zápasem . Tučné písmo označuje nejdůležitější algoritmy z praktického hlediska.

Na základě srovnání jako " černá skříňka "

Ve všech těchto algoritmech se bod, kde se "jehla" neshodovala s "hromadou sena", neúčastní rozhodování. To vám umožňuje používat standardní funkce pro porovnávání oblastí paměti , často optimalizované na úrovni assembleru pro konkrétní procesor.

Do této kategorie patří také primitivní vyhledávací algoritmus.

název Předběžný léčba Složitost Poznámky
typický Max.
Primitivní algoritmus Ne 2 h _ O ( Hn )
Algoritmus Boyer-Moore-Horspool O ( n +σ) ~ 2 H / σ [2] O ( Hn ) Boyer-Mooreův algoritmus zjednodušený na maximum; používá pouze upravenou heuristiku symbolu zastávky - symbol zastávky je vždy brán jako symbol kupky sena umístěný naproti poslednímu symbolu jehly .
Algoritmus rychlého vyhledávání
Sandyho algoritmus
O ( n +σ) < H O ( Hn ) Také používá výhradně heuristiku symbolu zastavení - ale symbol zastavení se bere jako symbol kupky sena za posledním symbolem jehly .

Na základě srovnání od začátku

Tato rodina algoritmů trpí nízkou rychlostí na „dobrých“ datech, což je kompenzováno nedostatkem regrese na „špatných“ datech.

název Předběžný léčba Složitost Poznámky
typický Max.
Rabin-Karpův algoritmus O ( n ) < H + n O ( Hn ) Hašování může v průměru výrazně snížit složitost
Automatický
algoritmus Algoritmus Aho-Korasik
O ( nσ ) = H Vytváří stavový stroj , který rozpoznává jazyk skládající se z jednoho řádku. Po mírné úpravě umožňuje najít jednu linii z více v jednom průchodu kupkou sena .
Knuth-Morris-Prattův algoritmus O ( n ) ≤ 2H Jeden z prvních algoritmů s lineárním odhadem nejhoršího případu. Modifikace algoritmu Aho-Korasik, která staví automat implicitně na základě prefixové funkce.
Algoritmus Apostolico-Crochemore O ( n ) < H ≤1,5H _
Shift-Or
Algorithm Bitap Algorithm
Binární algoritmus
O ( n +σ) = H strop ( n / w ) Účinné, pokud velikost jehly (ve znacích) není větší než velikost strojového slova (v bitech, označeno w ). Snadno převedené na přibližné vyhledávání, víceřádkové vyhledávání.

Na základě srovnání od konce

V této rodině algoritmů se jehla pohybuje po kupce sena zleva doprava, ale porovnání těchto řetězců mezi sebou se provádí zprava doleva. Porovnání zprava doleva umožňuje v případě neshody posunout jehlu ne o jednu pozici, ale o několik.

název Předběžný léčba Složitost Poznámky
typický Max.
Boyer-Mooreův algoritmus O ( n +σ) < H O ( Hn ) Standardní algoritmus pro nalezení podřetězce v řetězci. Považován za nejúčinnější obecný algoritmus. [3]
Algoritmus Zhu-Takaoka O ( n +σ²) < H O ( Hn ) Boyer-Mooreův algoritmus optimalizovaný pro krátké abecedy
Algoritmus Apostolico-Giancarlo O ( n +σ) < H ≤1,5H _ Jeden z prvních pokusů získat < H v typickém případě a O ( H ) v nejhorším případě. Velmi obtížně realizovatelné.
Turbo Boyer-Mooreův algoritmus O ( n +σ) < H ≤2H _ Jeden z nejúčinnějších algoritmů, který nedává regresi na "špatná" data

Provádění srovnání v neobvyklém pořadí

název Předběžný léčba Složitost Poznámky
typický Max.
Neprimitivní algoritmus konst < H O ( Hn ) Jednoduchý algoritmus, který porovnává druhý znak, poté začíná třetím v režimu černé skříňky a nakonec prvním. S n [1]≠ n [2] [4] a nesouladem na druhém nebo třetím stupni — posun o 2 doprava.
Wrightův
algoritmus Boyer-Moore-Horspool-Wrightův algoritmus
O ( n +σ) < H O ( Hn ) 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.

Viz také

Poznámky

  1. Algoritmus hrubé síly Archivováno 21. ledna 2009 na Wayback Machine 
  2. Algoritmus Horspool . Získáno 2. května 2013. Archivováno z originálu dne 29. srpna 2012.
  3. Boyer-Mooreův algoritmus . Získáno 2. května 2013. Archivováno z originálu 6. února 2013.
  4. Připomeňme, že znaky jsou číslovány od 1, jako v Pascalu .

Literatura

Odkazy