Algoritmus pro vyhledávání řetězců - String-searching algorithm

Ve výpočetní technice jsou algoritmy pro vyhledávání řetězců , někdy nazývané také algoritmy pro porovnávání řetězců , důležitou třídou řetězcových algoritmů, které se pokoušejí najít místo, kde se jeden nebo více řetězců (nazývaných také vzory) nachází ve větším řetězci nebo textu.

Základním příkladem vyhledávání řetězců je, když jsou vzor a hledaný text pole prvků abecedy ( konečná množina ) Σ. Σ může být abeceda lidského jazyka, například písmena A až Z a další aplikace mohou používat binární abecedu (Σ = {0,1}) nebo DNA abecedu (Σ = {A, C, G, T}) v bioinformatice .

V praxi může být metoda proveditelného algoritmu pro vyhledávání řetězců ovlivněna kódováním řetězců. Zejména v případě, že kódování s proměnnou šířkou je v provozu, pak to může být pomalejší, aby zjistil se N -tého charakteru, možná vyžaduje čas úměrný N . To může výrazně zpomalit některé vyhledávací algoritmy. Jedním z mnoha možných řešení je místo toho hledat posloupnost kódových jednotek, ale může to způsobit falešné shody, pokud není kódování speciálně navrženo tak, aby se tomu vyhýbalo.

Přehled

Nejzákladnější případ hledání řetězců zahrnuje jeden (často velmi dlouhý) řetězec, někdy nazývaný kupka sena , a jeden (často velmi krátký) řetězec, někdy nazývaný jehla . Cílem je najít jeden nebo více výskytů jehly v kupce sena. Například, jeden by mohl hledat až do: 

   Some books are to be tasted, others to be swallowed, and some few to be chewed and digested.

Dalo by se požádat o první výskyt „to“, což je čtvrté slovo; nebo všechny výskyty, kterých jsou 3; nebo poslední, což je páté slovo od konce.

Velmi často se však přidávají různá omezení. Někdo by například mohl chtít spojit „jehlu“ pouze tam, kde se skládá z jednoho (nebo více) úplných slov - možná definovaných tak , že na obou stranách bezprostředně sousedí jiná písmena. V takovém případě by hledání „hew“ nebo „low“ mělo selhat pro výše uvedenou příkladovou větu, přestože k těmto doslovným řetězcům dochází.

Další běžný příklad zahrnuje „normalizaci“. Pro mnoho účelů by hledání fráze jako „být“ mělo být úspěšné i v místech, kde mezi „do“ a „být“ zasahuje něco jiného:

  • Více než jeden prostor
  • Jiné znaky „mezery“, jako jsou tabulátory, nepřerušované mezery, konce řádků atd.
  • Méně často pomlčka nebo měkká spojovník
  • Ve strukturovaných textech, značkách nebo dokonce libovolně velkých, ale „závorkových“ věcech, jako jsou poznámky pod čarou, čísla seznamů nebo jiné značky, vložené obrázky atd.

Mnoho systémů symbolů obsahuje znaky, které jsou synonymní (alespoň pro některé účely):

  • Abecedy založené na latince rozlišují malá a velká písmena, ale pro mnoho účelů se očekává, že vyhledávání řetězců bude tento rozdíl ignorovat.
  • Mnoho jazyků obsahuje ligatury , kde jeden složený znak odpovídá dvěma nebo více dalším znakům.
  • Mnoho psacích systémů obsahuje diakritická znaménka, jako jsou akcenty nebo samohlásky , která se mohou lišit v jejich použití nebo mohou mít různou důležitost při porovnávání.
  • Sekvence DNA mohou zahrnovat nekódující segmenty, které mohou být pro některé účely ignorovány, nebo polymorfismy, které nevedou ke změně kódovaných proteinů, což nemusí být pro některé jiné účely považováno za skutečný rozdíl.
  • Některé jazyky mají pravidla, kde na začátku, uprostřed nebo na konci slova musí být použit jiný znak nebo forma znaku.

Nakonec u řetězců, které představují přirozený jazyk, se zapojují aspekty samotného jazyka. Někdo by si například mohl přát najít všechny výskyty „slova“, přestože má alternativní hláskování, předpony nebo přípony atd.

Dalším složitějším typem vyhledávání je vyhledávání pomocí regulárních výrazů , kdy uživatel vytvoří vzorec znaků nebo jiných symbolů a hledání by měla splňovat jakákoli shoda se vzorem. Chcete -li například zachytit jak americké anglické slovo „color“, tak britský ekvivalent „color“, místo hledání dvou různých doslovných řetězců lze použít regulární výraz, jako například: 

   colou?r

Kde "?" konvenčně činí předchozí znak („u“) volitelným.

Tento článek se zabývá hlavně algoritmy pro jednodušší typy vyhledávání řetězců.

Podobným problémem zavedeným v oblasti bioinformatiky a genomiky je maximální přesné párování (MEM). Vzhledem ke dvěma řetězcům jsou MEM běžné podřetězce, které nelze rozšířit doleva ani doprava, aniž by došlo k nesouladu.

Příklady vyhledávacích algoritmů

Naivní vyhledávání řetězců

Jednoduchý a neefektivní způsob, jak zjistit, kde se jeden řetězec vyskytuje uvnitř druhého, je zkontrolovat každé místo, kde by to mohlo být, jeden po druhém, aby se zjistilo, zda tam je. Nejprve tedy uvidíme, zda je v prvním znaku kupky sena kopie jehly; pokud ne, podíváme se, jestli tam není kopie jehly začínající na druhém znaku kupky sena; pokud ne, podíváme se počínaje třetím znakem atd. V normálním případě se musíme podívat na jeden nebo dva znaky pro každou špatnou pozici, abychom zjistili, že je to špatná pozice, takže v průměrném případě to trvá O ( n + m ) kroků, kde n je délka kupce sena a m je délka jehly; ale v nejhorším případě hledání řetězce jako „aaaab“ v řetězci jako „aaaaaaaaab“ trvá O ( nm )

Hledání na základě automatu v konečném stavu

Hledání DFA mommy.svg

V tomto přístupu se vyhýbáme zpětnému sledování vytvořením deterministického konečného automatu (DFA), který rozpoznává uložený vyhledávací řetězec. Jejich konstrukce je nákladná - obvykle se vytvářejí pomocí konstrukce mocninných sad - ale jejich použití je velmi rychlé. Například DFA zobrazená vpravo rozpoznává slovo „MAMINKA“. Tento přístup je v praxi často generalizován pro hledání libovolných regulárních výrazů .

Pahýly

Knuth – Morris – Pratt vypočítá DFA, která rozpoznává vstupy pomocí řetězce, který má hledat jako příponu, Boyer – Moore začne hledat od konce jehly, takže obvykle může v každém kroku přeskočit o celou délku jehly. Baeza – Yates sleduje, zda předchozí znaky j byly předponou vyhledávacího řetězce, a je tedy přizpůsobitelné fuzzy vyhledávání řetězců . Algoritmus bitap je aplikace přístupu Baeza-Yatese.

Indexové metody

Rychlejší vyhledávací algoritmy předzpracovávají text. Po vytvoření indexu podřetězců , například stromu přípon nebo pole přípon , lze výskyty vzoru rychle najít. Jako příklad lze strom přípon postavit v čase a všechny výskyty vzoru lze včas najít za předpokladu, že abeceda má konstantní velikost a všechny vnitřní uzly ve stromu přípon vědí, jaké listy jsou pod nimi. Toho lze dosáhnout spuštěním algoritmu DFS z kořene stromu přípon.

Jiné varianty

Některé metody vyhledávání, například hledání v trigramu , jsou určeny spíše k nalezení skóre „podobnosti“ mezi vyhledávacím řetězcem a textem než „shoda/neshoda“. Někdy se jim říká „fuzzy“ vyhledávání .


Klasifikace vyhledávacích algoritmů

Klasifikace podle řady vzorů

Různé algoritmy lze klasifikovat podle počtu vzorů, které každý používá.

Algoritmy s jedním vzorem

V následující kompilaci je m délka vzoru, n délka prohledávatelného textu, k = | Σ | je velikost abecedy a f je konstanta zavedená operacemi SIMD .

Algoritmus Doba předzpracování Čas shody Prostor
Naivní algoritmus pro vyhledávání řetězců žádný Θ (mn) žádný
Optimalizovaný naivní algoritmus pro vyhledávání řetězců (libc ++ a libstdc ++ string :: find) žádný Θ (mn/f) žádný
Rabin -Karpův algoritmus Θ (m) průměr Θ (n + m),
nejhorší Θ ((n − m) m) 		O (1)
Algoritmus Knuth – Morris – Pratt Θ (m) Θ (n) Θ (m)
Algoritmus pro vyhledávání řetězců Boyer – Moore Θ (m + k) nejlepší Ω (n/m),
nejhorší O (mn) 		Θ (k)
Bitapový algoritmus ( shift-or , shift-and , Baeza – Yates – Gonnet ; fuzzy; souhlas) Θ (m + k) O (mn)
Obousměrný algoritmus párování řetězců (glibc memmem/strstr) Θ (m) O (n+m) O (1)
BNDM (Backward Non-Deterministic DAWG Matching) (fuzzy + regex; nrgrep) O (m) Na)
BOM (Backward Oracle Matching) O (m) O (mn)
FM index Na) O (m) Na)
1. ^ Asymptotické časy jsou vyjádřeny pomocí notace O, Ω a Θ .

Boyer-Moore string-vyhledávací algoritmus byl standardní měřítko pro praktickou string-vyhledávání literatury.

Algoritmy využívající konečnou sadu vzorů

Algoritmy využívající nekonečný počet vzorů

V tomto případě přirozeně nelze vzory vyjmenovat konečně. Jsou obvykle reprezentovány pravidelnou gramatikou nebo regulárním výrazem .

Klasifikace pomocí programů předzpracování

Jsou možné i jiné klasifikační přístupy. Jedním z nejběžnějších použití předzpracování jako hlavních kritérií.

Třídy algoritmů pro vyhledávání řetězců
Text není předzpracován Text předzpracován
Vzory nejsou předzpracovány Elementární algoritmy Indexové metody
Předzpracované vzory Zkonstruované vyhledávače Metody podpisu:

Klasifikace podle párovacích strategií

Další klasifikuje algoritmy podle jejich strategie párování:

  • Nejprve porovnejte předponu (Knuth-Morris-Pratt, Shift-And, Aho-Corasick)
  • Nejprve porovnejte příponu (Boyer-Moore a varianty, Commentz-Walter)
  • Nejprve porovnejte nejlepší faktor (BNDM, BOM, Set-BOM)
  • Jiná strategie (naivní, Rabin-Karp)

Viz také

Reference

  1. ^ Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L (2004). „Všestranný a otevřený software pro porovnávání velkých genomů“ . Biologie genomu . 5 (2): R12. doi : 10,1186/GB-2004-5-2-r12 . ISSN  1465-6906 . PMC  395750 . PMID  14759262 .
  2. ^ Khan, Zia; Bloom, Joshua S .; Kruglyak, Leonid; Singh, Mona (01.07.2009). "Praktický algoritmus pro hledání maximálních přesných shod ve velkých sekvenčních datových sadách pomocí polí s řídkými příponami" . Bioinformatika . 25 (13): 1609–1616. doi : 10,1093/bioinformatika/btp275 . PMC  2732316 . PMID  19389736 .
  3. ^ Kumar, Aditya. "libc ++: Vylepšit řetězec :: najít algoritmus" . Citační deník vyžaduje |journal=( nápověda )
  4. ^ Kumar, Aditya. "libstdc ++: Vylepšit algoritmus string :: find" . Citační deník vyžaduje |journal=( nápověda )
  5. ^ Crochemore, Maxime; Perrin, Dominique (1. července 1991). „Obousměrné párování řetězců“ (PDF) . Deník ACM . 38 (3): 650–674. doi : 10.1145/116825.116845 . S2CID  15055316 .
  6. ^ Navarro, Gonzalo; Raffinot, Mathieu (1998). „Bitově paralelní přístup k příponovým automatům: Rychlé rozšířené párování řetězců“ (PDF) . Kombinatorické porovnávání vzorů . Přednášky z informatiky. Springer Berlin Heidelberg. 1448 : 14–33. doi : 10,1007/bfb0030778 . ISBN 978-3-540-64739-3.
  7. ^ Fan, H .; Yao, N .; Ma, H. (prosinec 2009). „Rychlé varianty algoritmu Backward-Oracle-Marching“ (PDF) . 2009 Čtvrtá mezinárodní konference o internetových počítačích pro vědu a techniku : 56–59. doi : 10.1109/ICICSE.2009.53 . ISBN 978-1-4244-6754-9. S2CID  6073627 .
  8. ^ Hume; Neděle (1991). „Rychlé vyhledávání řetězců“ . Software: Praxe a zkušenosti . 21 (11): 1221–1248. doi : 10,1002/spe.4380211105 . S2CID  5902579 .
  9. ^ Melichar, Borivoj, Jan Holub a J. Polcar. Algoritmy pro vyhledávání textu. Volume I: Forward String Matching. Sv. 1. 2 sv., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ .
  10. ^ Riad Mokadem; Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Fast nGramBased String Search Over Data encoded using Algebraic Signatures , 33. International Conference on Very Large Data Bases (VLDB)
  11. ^ Gonzalo Navarro; Mathieu Raffinot (2008), Flexibilní řetězce shody vzorů: Praktické on-line vyhledávací algoritmy pro texty a biologické sekvence , ISBN 978-0-521-03993-2

externí odkazy