Algoritmus prohledávání řetězců - String-searching algorithm - Wikipedia

v počítačová věda, algoritmy prohledávání řetězců, někdy nazývané algoritmy shody řetězců, jsou důležitou třídou řetězcové algoritmy kteří se snaží najít místo, kde jeden nebo několik struny (nazývané také vzory) se nacházejí ve větším řetězci nebo textu.

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

V praxi může být metoda proveditelného algoritmu prohledávání řetězců ovlivněna kódováním řetězců. Zejména pokud a kódování s proměnnou šířkou se používá, pak může být pomalejší najít Nth znak, 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 vést k falešným shodám, pokud není kódování speciálně navrženo tak, aby se tomu zabránilo.[Citace je zapotřebí ]

Přehled

Nejzákladnější případ vyhledávání řetězců zahrnuje jeden (často velmi dlouhý) řetězec, někdy nazývaný kupka senaa 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 by se dalo hledat na v rámci:

   Některé knihy je třeba ochutnat, jiné polknout a některé málo rozkousat a strávit.

Jeden může požadovat první výskyt „do“, 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í. Například by se mohlo chtít shodovat s „jehlou“ pouze tam, kde se skládá z jednoho (nebo více) úplných slov - možná definovaných jako ne mít další písmena bezprostředně sousedící na obou stranách. V takovém případě by hledání výrazu „hew“ nebo „low“ mělo selhat pro výše uvedenou příkladovou větu, přestože se tyto doslovné řetězce vyskytují.

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

  • Více než jeden prostor
  • Další znaky „bílých mezer“, jako jsou karty, nerozdělitelné mezery, zalomení řádků atd.
  • Méně často pomlčka nebo měkká pomlčka
  • Ve strukturovaných textech značky nebo dokonce libovolně velké, ale „závorkové“ věci, jako jsou poznámky pod čarou, čísla seznamů nebo jiné značky, vložené obrázky atd.

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

  • Latinské abecedy 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ů zahrnuje ligatury, kde jeden složený znak odpovídá dvěma nebo více dalším znakům.
  • Mnoho systémů psaní zahrnuje diakritická znaménka jako jsou akcenty nebo samohláskové body, které se mohou lišit v jejich použití, nebo mohou mít různou důležitost při párování.
  • Sekvence DNA mohou zahrnovat nekódování segmenty, které mohou být pro některé účely ignorovány, nebo polymorfismy, které nevedou k žádné změně v kódovaných proteinech, což se pro některé jiné účely nemusí považovat za skutečný rozdíl.
  • Některé jazyky mají pravidla, kdy na začátku, uprostřed nebo na konci slov musí být použit odlišný znak nebo forma znaku.

A konečně, pro řetězce, které představují přirozený jazyk, se zapojí aspekty samotného jazyka. Například si můžete přát najít všechny výskyty slova, přestože má alternativní hláskování, předpony nebo přípony atd.

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

   barva

Kde "?" konvenčně dělá předchozí znak ("u") volitelným.

Tento článek pojednává hlavně o algoritmech pro jednodušší druhy vyhledávání řetězců.

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

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ř jiného, ​​je zkontrolovat každé místo, kde by to mohlo být, jeden po druhém, a zjistit, zda tam je. Nejprve tedy uvidíme, jestli je v prvním znaku kupky sena kopie jehly; pokud ne, podíváme se, jestli existuje kopie jehly začínající na druhém znaku kupky sena; pokud ne, podíváme se na třetí znak atd. V normálním případě se musíme jen podívat na jeden nebo dva znaky pro každou nesprávnou pozici, abychom zjistili, že jde o špatnou pozici, takže v průměrném případě to zabere Ó (n + m) kroky, kde n je délka kupky 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á Ó (nm)

Hledání založené na automatu s konečným stavem

Vyhledávání DFA mommy.svg

V tomto přístupu se vyhýbáme zpětnému sledování konstrukcí a deterministický konečný automat (DFA), který rozpozná uložený vyhledávací řetězec. Konstrukce je nákladná - obvykle se vytvářejí pomocí konstrukce výkonové sady —Ale jsou velmi rychlé. Například DFA napravo rozpozná slovo „MOMMY“. Tento přístup je v praxi často zobecněn k hledání libovolného regulární výrazy.

Pahýly

Knuth – Morris – Pratt počítá a DFA který rozpoznává vstupy s řetězcem, který má hledat jako příponu, Boyer – Moore začne hledat od konce jehly, takže obvykle může v každém kroku vyskočit o celou délku jehly. Baeza – Yates sleduje, zda předchozí j znaky byly předponou vyhledávacího řetězce, a proto je lze je přizpůsobit fuzzy vyhledávání řetězců. The bitapový algoritmus je aplikace přístupu Baeza – Yates.

Indexové metody

Rychlejší vyhledávací algoritmy předzpracovávají text. Po vybudování index podřetězce, například a příponový strom nebo pole přípon, výskyty vzoru lze rychle najít. Jako příklad lze zabudovat strom přípon čas a všechno výskyty vzoru lze najít v čas 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 a Algoritmus DFS z kořene stromu přípon.

Další varianty

Některé metody vyhledávání, například trigramové vyhledávání, jsou určeny k nalezení skóre „blízkosti“ mezi hledaným řetězcem a textem, nikoli „shoda / nesouhlas“. 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 m je délka vzoru, n délka prohledávatelného textu, k = | Σ | je velikost abecedy a F je konstanta zavedená SIMD operace.

AlgoritmusDoba předběžného zpracováníOdpovídající čas[1]Prostor
Naivní algoritmus pro vyhledávání řetězcůžádnýΘ (mn)žádný
Optimalizovaný naivní algoritmus vyhledávání řetězců (řetězec libc ++ a libstdc ++ :: find)[3][4]žádnýΘ (mn / f)žádný
Algoritmus Rabin – KarpΘ (m)průměr Θ (n + m),
nejhorší Θ ((n − m) m)		O (1)
Algoritmus Knuth – Morris – PrattΘ (m)Θ (n)Θ (m)
Algoritmus vyhledávání řetězců Boyer – MooreΘ (m + k)nejlepší Ω (n / m),
nejhorší O (mn)		Θ (k)
Bitapový algoritmus (posun-nebo, shift-and, Baeza – Yates – Gonnet; fuzzy; souhlasit)Θ (m + k)O (mn)
Obousměrný algoritmus shody řetězců (glibc memmem / strstr)[5]Θ (m)O (n + m)O (1)
BNDM (zpětně nedeterministické shody DAWG) (fuzzy + regex; nrgrep)[6]O (m)Na)
BOM (zpětná shoda Oracle)[7]O (m)O (mn)
FM indexNa)O (m)Na)
1.^ Asymptotické časy jsou vyjádřeny pomocí O, Ω a Θ notace.

The Algoritmus vyhledávání řetězců Boyer – Moore byl standardním měřítkem pro praktickou literaturu pro vyhledávání řetězců.[8]

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

Algoritmy využívající nekonečné množství vzorů

V tomto případě přirozeně nelze vzory vyjmenovat s konečnou platností. Jsou obvykle zastoupeny a běžná gramatika nebo regulární výraz.

Klasifikace podle programů předzpracování

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

Třídy algoritmů prohledávání řetězců[9]
Text nebyl předzpracovánText předzpracován
Vzory nejsou předzpracoványZákladní algoritmyIndexové metody
Předzpracované vzoryVytvořené vyhledávačePodpisové metody:[10]

Klasifikace podle strategií shody

Další klasifikuje algoritmy podle jejich strategie shody:[11]

  • 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 (Naïve, 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ů“. Genome Biology. 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í řídkých příponových polí". 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". Citovat deník vyžaduje | deník = (Pomoc)
  4. ^ Kumar, Aditya. "libstdc ++: Vylepšit řetězec :: najít algoritmus". Citovat deník vyžaduje | deník = (Pomoc)
  5. ^ Crochemore, Maxime; Perrin, Dominique (1. července 1991). „Obousměrné shody řetězců“ (PDF). Deník ACM. 38 (3): 650–674. doi:10.1145/116825.116845. S2CID  15055316.
  6. ^ Navarro, Gonzalo; Raffinot, Mathieu (1998). "Bitparalelní přístup k příponovým automatům: Rychlé rozšířené porovnává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 zpětně pochodového algoritmu“ (PDF). 2009 Čtvrtá mezinárodní konference o počítačových výpočtech 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 obj., 2005. http://stringology.org/athens/TextSearchingAlgorithms/.
  10. ^ Riad Mokadem; Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Rychlé vyhledávání řetězců nGramBased přes data kódovaná pomocí algebraických podpisů, 33. mezinárodní konference o velmi velkých databázích (VLDB)
  11. ^ Gonzalo Navarro; Mathieu Raffinot (2008), Flexibilní řetězce odpovídající vzorům: Praktické online vyhledávací algoritmy pro texty a biologické sekvence, ISBN  978-0-521-03993-2

externí odkazy