Strängsökande algoritm - String-searching algorithm

I datavetenskap , sträng sökalgoritmer , som ibland kallas strängmatchningsalgoritmer , är en viktig klass av strängalgoritmer som försöker hitta en plats där en eller flera strängar (även kallade mönster) finns inom en större sträng eller text.

Ett grundläggande exempel på strängsökning är när mönstret och den sökta texten är matriser med element i ett alfabet ( ändlig uppsättning ) Σ. Σ kan vara ett mänskligt språkalfabet, till exempel kan bokstäverna A till Z och andra applikationer använda ett binärt alfabet (Σ = {0,1}) eller ett DNA -alfabet (Σ = {A, C, G, T}) inom bioinformatik .

I praktiken kan metoden för genomförbar strängsökningsalgoritm påverkas av strängkodningen. I synnerhet, om en variabel bredd kodning är i bruk, kan det vara långsammare för att hitta den N : te tecken, kanske kräver tid proportionell mot N . Detta kan avsevärt bromsa vissa sökalgoritmer. En av många möjliga lösningar är att söka efter sekvensen av kodenheter istället, men det kan ge falska matchningar om inte kodningen är speciellt utformad för att undvika den.

Översikt

Det mest grundläggande fallet med strängsökning innefattar en (ofta mycket lång) sträng, ibland kallad höstack och en (ofta mycket kort) sträng, ibland kallad nålen . Målet är att hitta en eller flera förekomster av nålen i höstacken. Till exempel kan man söka efter att inom: 

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

Man kan begära den första förekomsten av "till", vilket är det fjärde ordet; eller alla förekomster, av vilka det finns 3; eller det sista, vilket är det femte ordet från slutet.

Mycket vanligt adderas dock olika begränsningar. Till exempel kanske man bara vill matcha "nålen" där den består av ett (eller flera) fullständiga ord - kanske definierat som att de inte har andra bokstäver omedelbart intill varandra på vardera sidan. I så fall bör en sökning efter "hugg" eller "låg" misslyckas med exemplets mening ovan, även om dessa bokstavliga strängar förekommer.

Ett annat vanligt exempel är "normalisering". För många ändamål bör en sökning efter en fras som "att vara" lyckas även på platser där det finns något annat som ingriper mellan "till" och "vara":

  • Mer än ett utrymme
  • Andra "blanksteg" tecken som flikar, icke-brytande mellanslag, radbrytningar, etc.
  • Mindre vanligt, bindestreck eller mjukt bindestreck
  • I strukturerade texter, taggar eller till och med godtyckligt stora men "parentetiska" saker som fotnoter, listnummer eller andra markörer, inbäddade bilder och så vidare.

Många symbolsystem innehåller tecken som är synonyma (åtminstone för vissa ändamål):

  • Latinbaserade alfabet skiljer gemener från versaler, men för många ändamål förväntas strängsökning ignorera skillnaden.
  • Många språk inkluderar ligaturer , där ett sammansatt tecken motsvarar två eller flera andra tecken.
  • Många skrivsystem innefattar diakritiska tecken som accenter eller vokalpunkter , som kan variera i deras användning eller vara av varierande betydelse vid matchning.
  • DNA-sekvenser kan innefatta icke-kodande segment som kan ignoreras för vissa ändamål, eller polymorfismer som inte leder till någon förändring av de kodade proteinerna, vilket kanske inte räknas som en verklig skillnad för andra ändamål.
  • Vissa språk har regler där ett annat tecken eller en annan teckenform måste användas i början, mitten eller slutet av ord.

Slutligen, för strängar som representerar naturligt språk, blir aspekter av själva språket involverade. Till exempel kanske man vill hitta alla förekomster av ett "ord" trots att det har alternativa stavningar, prefix eller suffix, etc.

En annan mer komplex typ av sökning är sökning med vanligt uttryck , där användaren konstruerar ett mönster av tecken eller andra symboler, och varje matchning till mönstret ska uppfylla sökningen. Till exempel, för att fånga både det amerikanska engelska ordet "färg" och den brittiska motsvarigheten "färg", istället för att söka efter två olika bokstavliga strängar, kan man använda ett vanligt uttryck som: 

   colou?r

där den "?" konventionellt gör föregående tecken ("u") valfritt.

Denna artikel diskuterar huvudsakligen algoritmer för de enklare typerna av strängsökning.

Ett liknande problem som introduceras inom bioinformatik och genomik är maximal exakt matchning (MEM). Med tanke på två strängar är MEM vanliga underlag som inte kan förlängas till vänster eller höger utan att orsaka en felaktig matchning.

Exempel på sökalgoritmer

Naiv strängsökning

Ett enkelt och ineffektivt sätt att se var en sträng förekommer i en annan är att kontrollera varje plats det kan vara, en efter en, för att se om den finns där. Så först ser vi om det finns en kopia av nålen i höstackens första tecken; om inte, ser vi om det finns en kopia av nålen som börjar med höstackens andra tecken; om inte, tittar vi på det tredje tecknet och så vidare. I det vanliga fallet behöver vi bara titta på ett eller två tecken för varje fel position för att se att det är en fel position, så i det genomsnittliga fallet tar detta O ( n + m ) steg, där n är längden på höstacken och m är nålens längd; men i värsta fall, när du söker efter en sträng som "aaaab" i en sträng som "aaaaaaaaab", tar det O ( nm )

Finite-state-automaton-based search

DFA -sökning mommy.svg

I detta tillvägagångssätt undviker vi backtracking genom att konstruera en deterministisk ändlig automat (DFA) som känner igen lagrad söksträng. Dessa är dyra att bygga - de är vanligtvis skapade med hjälp av poweret -konstruktionen - men är mycket snabba att använda. Till exempel känner DFA till höger igen ordet "MAMMA". Detta tillvägagångssätt generaliseras ofta i praktiken för att söka efter godtyckliga reguljära uttryck .

Stubbar

Knuth – Morris – Pratt beräknar en DFA som känner igen inmatningar med strängen att söka efter som ett suffix, Boyer – Moore börjar söka från nålens ände, så den kan vanligtvis hoppa fram en hel nål-längd vid varje steg. Baeza – Yates håller reda på om de tidigare j -tecknen var ett prefix för söksträngen och kan därför anpassas till suddig strängsökning . Den bitap algoritmen är en tillämpning av Baeza-Yates' tillvägagångssätt.

Indexmetoder

Snabbare sökalgoritmer förbehandlar texten. Efter att ha byggt ett understrängindex , till exempel ett suffixträd eller en suffixmatris , kan förekomsten av ett mönster snabbt hittas. Som ett exempel kan ett suffixträd byggas i tid, och alla förekomster av ett mönster kan hittas i tid under antagandet att alfabetet har en konstant storlek och alla inre noder i suffixträdet vet vilka löv som finns under dem. Det senare kan åstadkommas genom att köra en DFS -algoritm från roten till suffixträdet.

Andra varianter

Vissa sökmetoder, till exempel trigramsökning , är avsedda att hitta en "närhet" -poäng mellan söksträngen och texten snarare än en "matchning/icke-matchning". Dessa kallas ibland "fuzzy" sökningar .


Klassificering av sökalgoritmer

Klassificering efter ett antal mönster

De olika algoritmerna kan klassificeras efter antalet mönster varje använder.

Enkelmönsteralgoritmer

I följande sammanställning är m mönstrets längd, n längden på den sökbara texten, k = | Σ | är storleken på alfabetet och f är en konstant som introduceras av SIMD -operationer.

Algoritm Förbehandlingstid Matchningstid Plats
Naiv strängsökningsalgoritm ingen Θ (mn) ingen
Optimerad Naiv strängsökningsalgoritm (libc ++ och libstdc ++ sträng :: hitta) ingen Θ (mn/f) ingen
Rabin – Karp algoritm Θ (m) genomsnitt Θ (n + m),
värsta Θ ((n − m) m) 		O (1)
Knuth – Morris – Pratt -algoritm Θ (m) Θ (n) Θ (m)
Boyer – Moore strängsökningsalgoritm Θ (m + k) bästa Ω (n/m),
sämsta O (mn) 		Θ (k)
Bitap-algoritm ( skift-eller , skift-och , Baeza – Yates – Gonnet ; luddig; instämmer) Θ (m + k) O (mn)
Tvåvägs strängmatchande algoritm (glibc memmem/strstr) Θ (m) O (n+m) O (1)
BNDM (Backward Non-Deterministic DAWG Matching) (fuzzy + regex; nrgrep) O (m) På)
BOM (Backward Oracle Matching) O (m) O (mn)
FM-index På) O (m) På)
1. ^ Asymptotiska tider uttrycks med O, Ω och Θ notation .

Den Boyer-Moore sträng sökalgoritm har varit standard riktmärke för det praktiska stränglitteratursökning.

Algoritmer som använder en ändlig uppsättning mönster

Algoritmer som använder ett oändligt antal mönster

Naturligtvis kan mönstren inte räknas slutligt i det här fallet. De representeras vanligtvis av en vanlig grammatik eller ett reguljärt uttryck .

Klassificering genom användning av förbehandlingsprogram

Andra klassificeringsmetoder är möjliga. En av de vanligaste användningsområdena förbehandling som huvudkriterier.

Klasser av strängsökningsalgoritmer
Texten är inte förbehandlad Text förbehandlad
Mönster inte förbehandlade Elementära algoritmer Indexmetoder
Mönster förbehandlade Konstruerade sökmotorer Signaturmetoder:

Klassificering efter matchningsstrategier

En annan klassificerar algoritmerna efter deras matchningsstrategi:

  • Matcha prefixet först (Knuth-Morris-Pratt, Shift-And, Aho-Corasick)
  • Matcha först suffixet (Boyer-Moore och varianter, Commentz-Walter)
  • Matcha den bästa faktorn först (BNDM, BOM, Set-BOM)
  • Annan strategi (Naiv, Rabin-Karp)

Se även

Referenser

  1. ^ Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L (2004). "Mångsidig och öppen programvara för att jämföra stora genomer" . Genombiologi . 5 (2): R12. doi : 10.1186/gb-2004-5-2-r12 . ISSN  1465-6906 . PMC  395.750 . PMID  14759262 .
  2. ^ Khan, Zia; Bloom, Joshua S .; Kruglyak, Leonid; Singh, Mona (2009-07-01). "En praktisk algoritm för att hitta maximala exakta matchningar i datamängder med stor sekvens med hjälp av glesa suffix -matriser" . Bioinformatik . 25 (13): 1609–1616. doi : 10.1093/bioinformatics/btp275 . PMC  2732316 . PMID  19389736 .
  3. ^ Kumar, Aditya. "libc ++: Förbättra sträng :: hitta algoritm" . Citera journal kräver |journal=( hjälp )
  4. ^ Kumar, Aditya. "libstdc ++: Förbättra sträng :: hitta algoritm" . Citera journal kräver |journal=( hjälp )
  5. ^ Crochemore, Maxime; Perrin, Dominique (1 juli 1991). "Tvåvägs strängmatchning" (PDF) . Journal of the ACM . 38 (3): 650–674. doi : 10.1145/116825.116845 . S2CID  15055316 .
  6. ^ Navarro, Gonzalo; Raffinot, Mathieu (1998). "En bitparallell metod för suffixautomater: Snabb utökad strängmatchning" (PDF) . Kombinerande mönstermatchning . Föreläsningsanteckningar i datavetenskap. Springer Berlin Heidelberg. 1448 : 14–33. doi : 10.1007/bfb0030778 . ISBN 978-3-540-64739-3.
  7. ^ Fan, H .; Yao, N .; Ma, H. (december 2009). "Snabba varianter av algoritmen för bakåt-orakel-marschering" (PDF) . 2009 Fjärde internationella konferensen om internetdatorer för vetenskap och teknik : 56–59. doi : 10.1109/ICICSE.2009.53 . ISBN 978-1-4244-6754-9. S2CID  6073627 .
  8. ^ Hume; Söndag (1991). "Snabbsträngsökning" . Programvara: Practice and Experience . 21 (11): 1221–1248. doi : 10.1002/spe.4380211105 . S2CID  5902579 .
  9. ^ Melichar, Borivoj, Jan Holub och J. Polcar. Textsökningsalgoritmer. Volym I: Matcha framåtsträngar. Vol. 1. 2 vol., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ .
  10. ^ Riad Mokadem; Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Snabb nGramBased strängsökning över data kodade med hjälp av algebraiska signaturer , 33: e internationella konferensen om mycket stora databaser (VLDB)
  11. ^ Gonzalo Navarro; Mathieu Raffinot (2008), Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences , ISBN 978-0-521-03993-2

externa länkar