Algoritm för strängsökning

Inom datavetenskap är strängsökningsalgoritmer , ibland kallade strängmatchningsalgoritmer , 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 arrayer av element i ett alfabet ( finit set ) Σ. Σ 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 kodning med variabel bredd används, kan det vara långsammare att hitta det N :te tecknet, vilket 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 att göra det kan ge falska matchningar om inte kodningen är speciellt utformad för att undvika det. [ citat behövs ]

Översikt

Det mest grundläggande fallet med strängsökning involverar en (ofta mycket lång) sträng, ibland kallad höstacken, 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 till inom: 

Vissa böcker ska smakas, andra ska sväljas och några få tuggas och smälts.

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

Mycket vanligt är dock att olika begränsningar läggs till. Till exempel kanske man vill matcha "nålen" bara där den består av ett (eller flera) kompletta ord – kanske definierat som att det inte finns andra bokstäver omedelbart intill på någon sida. I så fall bör en sökning efter "hew" eller "low" misslyckas för exemplet 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 mellan "att" och "vara":

  • Mer än ett utrymme
  • Andra "blanksteg"-tecken som tabbar, icke-avbrytande 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 inkluderar tecken som är synonyma (åtminstone för vissa ändamål):

  • Latinbaserade alfabet skiljer små bokstäver från versaler, men för många ändamål förväntas strängsökning ignorera distinktionen.
  • Många språk inkluderar ligaturer , där ett sammansatt tecken motsvarar två eller flera andra tecken.
  • Många skrivsystem involverar diakritiska tecken som accenter eller vokalpunkter , som kan variera i deras användning, eller vara av varierande betydelse vid matchning.
  • DNA-sekvenser kan involvera icke-kodande segment som kan ignoreras för vissa ändamål, eller polymorfismer som inte leder till någon förändring i de kodade proteinerna, vilket kanske inte räknas som en sann skillnad för vissa andra ändamål.
  • Vissa språk har regler där ett annat tecken eller 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 kan man vilja 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 reguljära 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 "color" och den brittiska motsvarigheten "colour", istället för att söka efter två olika bokstavliga strängar, kan man använda ett reguljärt uttryck som: 

Färg

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

Den här artikeln diskuterar främst algoritmer för enklare typer av strängsökning.

Ett liknande problem som introducerats inom området bioinformatik och genomik är maximal exakt matchning (MEM). Med tanke på två strängar är MEMs vanliga delsträngar som inte kan förlängas åt vänster eller höger utan att orsaka en missmatchning.

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 vid varje index, en efter en. Först ser vi om det finns en kopia av nålen som börjar vid höstackens första tecken; om inte, tittar vi efter om det finns en kopia av nålen som börjar vid den andra tecknet i höstacken, och så vidare. I normalfallet behöver vi bara titta på ett eller två tecken för varje felposition för att se att det är en felposition, så i genomsnittsfallet tar detta O ( n + m ) steg, där n är längden av höstacken och m är nålens längd; men i värsta fall, om du söker efter en sträng som "aaaab" i en sträng som "aaaaaaaaab", tar det O ( nm )

Finita-state-automatbaserad sökning

DFA search mommy.svg

I detta tillvägagångssätt undviks backtracking genom att konstruera en deterministisk finit automat (DFA) som känner igen lagrad söksträng. Dessa är dyra att konstruera – de skapas vanligtvis med hjälp av powerset-konstruktionen – men är mycket snabba att använda. Till exempel, DFA som visas till höger känner igen ordet "MOMMY". 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 indata med strängen att söka efter som ett suffix, Boyer–Moore börjar söka från slutet av nålen, så den kan vanligtvis hoppa fram en hel nållängd vid varje steg. Baeza–Yates håller reda på om de tidigare j- tecknen var ett prefix till söksträngen och är därför anpassningsbar till fuzzy strängsökning . Bitap -algoritmen är en tillämpning av Baeza-Yates tillvägagångssätt.

Indexmetoder

Snabbare sökalgoritmer förbearbetar texten. Efter att ha byggt ett delsträngsindex , till exempel ett suffixträd eller suffixarray , kan förekomsterna 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 att 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 av 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 som var och en använder.

Enkelmönsteralgoritmer

I följande sammanställning är m längden på mönstret, n längden på den sökbara texten och k = |Σ| är storleken på alfabetet.

Algoritm Förbehandlingstid Matchningstid Plats
Naiv algoritm ingen Θ(mn) ingen
Rabin–Karp Θ(m)
Θ(n) i genomsnitt, O(mn) i värsta fall 		O(1)
Knuth–Morris–Pratt Θ(m) Θ(n) Θ(m)
Boyer–Moore Θ(m + k)
Ω(n/m) i bästa fall, O(mn) i värsta fall 		Θ(k)
Tvåvägsalgoritm Θ(m) På) O(1)
Bakåt icke-deterministisk DAWG- matchning (BNDM) O(m)
Ω(n/m) i bästa fall, O(mn) i värsta fall
Backward Oracle Matching (BOM) O(m) O(mn)
1. ^ Asymptotiska tider uttrycks med O, Ω och Θ notation .
2. ^ Används för att implementera sökfunktionerna memmem och strstr i standardbiblioteken glibc och musl C.
3. ^ Kan utökas för att hantera ungefärlig strängmatchning och (potentiellt oändliga) uppsättningar av mönster representerade som vanliga språk . [ citat behövs ]

Boyer –Moores strängsökningsalgoritm har varit standardriktmärket för den praktiska strängsökningslitteraturen.

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

I följande sammanställning är M längden på det längsta mönstret, m deras totala längd, n längden på den sökbara texten, o antalet förekomster.

Algoritm Förlängning av Förbehandlingstid Matchningstid Plats
Aho–Corasick Knuth–Morris–Pratt Θ(m) Θ(n + o) Θ(m)
Commentz-Walter Boyer-Moore Θ(m)
Θ(M * n) värsta fallet sublinjär i genomsnitt 		Θ(m)
Set-BOM Bakåt Oracle-matchning

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

Naturligtvis kan mönstren inte räknas upp ändligt i detta fall. De representeras vanligtvis av en vanlig grammatik eller ett reguljärt uttryck .

Klassificering genom användning av förbearbetningsprogram

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 ej förbearbetade Elementära algoritmer Indexmetoder
Mönster förbehandlade Konstruerade sökmotorer Signaturmetoder:

Klassificering genom matchande strategier

En annan klassificerar algoritmerna efter deras matchningsstrategi:

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

Se även

  1. ^     Kurtz, Stefan; Philippy, 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 genom" . Genombiologi . 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 (2009-07-01). "En praktisk algoritm för att hitta maximala exakta matchningar i stora sekvensdatauppsättningar med hjälp av glesa suffixarrayer" . Bioinformatik . 25 (13): 1609–1616. doi : 10.1093/bioinformatics/btp275 . PMC 2732316 . PMID 19389736 .
  3. ^   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 . Arkiverad (PDF) från originalet den 24 november 2021 . Hämtad 5 april 2019 .
  4. ^   Navarro, Gonzalo; Raffinot, Mathieu (1998). "A bit-parallel approach to suffix automata: Fast extended string matching" (PDF) . Kombinatorisk mönstermatchning . Föreläsningsanteckningar i datavetenskap. Springer Berlin Heidelberg. 1448 : 14–33. doi : 10.1007/bfb0030778 . ISBN 978-3-540-64739-3 . Arkiverad (PDF) från originalet 2019-01-05 . Hämtad 2019-11-22 .
  5. ^    Fan, H.; Yao, N.; Ma, H. (december 2009). "Snabba varianter av bakåt-Oracle-marschalgoritmen" (PDF) . 2009 Fjärde internationella konferensen om Internetberäkning för vetenskap och teknik : 56–59. doi : 10.1109/ICICSE.2009.53 . ISBN 978-1-4244-6754-9 . S2CID 6073627 . Arkiverad från originalet 2022-05-10 . Hämtad 2019-11-22 .
  6. ^ "glibc/string/str-tvåvägs.h" . Arkiverad från originalet 2020-09-20 . Hämtad 2022-03-22 .
  7. ^ "musl/src/string/memmem.c" . Arkiverad från originalet den 1 oktober 2020 . Hämtad 23 november 2019 .
  8. ^   Hume; söndag (1991). "Snabb strängsökning" . Programvara: Övning och erfarenhet . 21 (11): 1221–1248. doi : 10.1002/spe.4380211105 . S2CID 5902579 . Arkiverad från originalet 2022-05-10 . Hämtad 2019-11-29 .
  9. ^   Commentz-Walter, Beate (1979). En strängmatchningsalgoritm snabbt i genomsnitt (PDF) . Internationellt kollokvium om automater, språk och programmering . LNCS . Vol. 71. Graz, Österrike: Springer. s. 118–132. doi : 10.1007/3-540-09510-1_10 . ISBN 3-540-09510-1 . Arkiverad från originalet (PDF) 2017-10-10.
  10. ^ Melichar, Borivoj, Jan Holub och J. Polcar. Algoritmer för textsökning. Volym I: Forward String Matching. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ Arkiverad 2016-03-04 på Wayback Machine .
  11. ^ Riad Mokadem; Witold citat }} : Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Fast nGramBased String Search Over Data Encoded Using Algebraic Signatures , 33rd International Conference on Very Large Data Bases (VLDB) {{ Extern länk i |efternamn2= ( hjälp )
  12. ^   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

Hämtad från " https://en.wikipedia.org/w/index.php?title=String-searching_algorithm&oldid=1137152883 "