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í.
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] .
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.
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.
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.
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 . |
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í. |
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 |
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. |
Struny | |
---|---|
Míry podobnosti řetězců | |
Hledání podřetězců | |
palindromy | |
Sekvenční zarovnání | |
Struktury přípon | |
jiný |