String-Suchalgorithmus - String-searching algorithm

In der Informatik sind String-Suchalgorithmen , manchmal auch String-Matching-Algorithmen genannt , eine wichtige Klasse von String-Algorithmen , die versuchen, eine Stelle zu finden, an der eine oder mehrere Strings (auch als Muster bezeichnet) innerhalb einer größeren Zeichenfolge oder eines größeren Textes gefunden werden.

Ein grundlegendes Beispiel für die Suche nach Zeichenfolgen ist, wenn das Muster und der gesuchte Text Arrays von Elementen eines Alphabets ( endliche Menge ) sind Σ. Σ kann ein menschliches Alphabet sein, zum Beispiel die Buchstaben A bis Z und andere Anwendungen können ein binäres Alphabet (Σ = {0,1}) oder ein DNA-Alphabet (Σ = {A,C,G,T}) verwenden. in der Bioinformatik .

In der Praxis kann das Verfahren des durchführbaren String-Suchalgorithmus durch die String-Codierung beeinflusst werden. Insbesondere wenn eine Codierung mit variabler Breite verwendet wird, kann es langsamer sein, das N- te Zeichen zu finden , was möglicherweise Zeit proportional zu N erfordert . Dies kann einige Suchalgorithmen erheblich verlangsamen. Eine von vielen möglichen Lösungen besteht darin, stattdessen nach der Sequenz von Codeeinheiten zu suchen, dies kann jedoch zu falschen Übereinstimmungen führen, es sei denn, die Codierung ist speziell darauf ausgelegt, dies zu vermeiden.

Überblick

Der einfachste Fall der String-Suche umfasst einen (oft sehr langen) String, der manchmal als Heuhaufen bezeichnet wird , und einen (oft sehr kurzen) String, manchmal als Nadel bezeichnet . Ziel ist es, ein oder mehrere Vorkommen der Nadel im Heuhaufen zu finden. Zum Beispiel könnte man nach bis innerhalb suchen : 

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

Man könnte das erste Vorkommen von "to" verlangen, das das vierte Wort ist; oder alle Vorkommen, von denen es 3 gibt; oder das letzte, das das fünfte Wort vom Ende ist.

Sehr häufig werden jedoch verschiedene Einschränkungen hinzugefügt. Zum Beispiel könnte man die "Nadel" nur dann abgleichen wollen, wenn sie aus einem (oder mehreren) vollständigen Wörtern besteht - vielleicht so definiert , dass sie auf beiden Seiten keine anderen Buchstaben unmittelbar benachbart haben. In diesem Fall sollte eine Suche nach "hew" oder "low" für den obigen Beispielsatz fehlschlagen, obwohl diese Literalstrings vorkommen.

Ein weiteres gängiges Beispiel ist die "Normalisierung". Für viele Zwecke sollte eine Suche nach einer Phrase wie "sein" sogar dort gelingen, wo zwischen dem "to" und dem "be" etwas anderes liegt:

  • Mehr als ein Raum
  • Andere "Whitespace"-Zeichen wie Tabulatoren, geschützte Leerzeichen, Zeilenumbrüche usw.
  • Seltener ein Bindestrich oder weicher Bindestrich
  • In strukturierten Texten, Tags oder auch beliebig großen, aber "einklammernden" Dingen wie Fußnoten, Listennummern oder anderen Markierungen, eingebetteten Bildern usw.

Viele Symbolsysteme enthalten Zeichen, die synonym sind (zumindest für einige Zwecke):

  • Lateinische Alphabete unterscheiden Kleinbuchstaben von Großbuchstaben, aber für viele Zwecke wird erwartet, dass die Zeichenfolgensuche diese Unterscheidung ignoriert.
  • Viele Sprachen enthalten Ligaturen , bei denen ein zusammengesetztes Zeichen zwei oder mehr anderen Zeichen entspricht.
  • Viele Schreibsysteme beinhalten diakritische Zeichen wie Akzente oder Vokalpunkte , die in ihrer Verwendung variieren können oder bei der Übereinstimmung von unterschiedlicher Bedeutung sind.
  • DNA-Sequenzen können nicht-kodierende Segmente umfassen, die für einige Zwecke ignoriert werden können, oder Polymorphismen, die zu keiner Veränderung der kodierten Proteine ​​führen, was für andere Zwecke möglicherweise nicht als echter Unterschied gilt.
  • Einige Sprachen haben Regeln, bei denen am Anfang, in der Mitte oder am Ende von Wörtern ein anderes Zeichen oder eine andere Zeichenform verwendet werden muss.

Schließlich werden bei Zeichenfolgen, die natürliche Sprache darstellen, Aspekte der Sprache selbst einbezogen. Zum Beispiel möchte man vielleicht alle Vorkommen eines "Wortes" finden, obwohl es alternative Schreibweisen, Präfixe oder Suffixe usw.

Eine andere komplexere Art der Suche ist die Suche mit regulären Ausdrücken , bei der der Benutzer ein Muster aus Zeichen oder anderen Symbolen erstellt und jede Übereinstimmung mit dem Muster die Suche erfüllen sollte. Um beispielsweise sowohl das amerikanisch-englische Wort "color" als auch das britische Äquivalent "colour" zu erfassen, könnte man, anstatt nach zwei verschiedenen Literalstrings zu suchen, einen regulären Ausdruck wie den folgenden verwenden: 

   colou?r

bei dem die "?" macht herkömmlicherweise das vorangehende Zeichen ("u") optional.

In diesem Artikel werden hauptsächlich Algorithmen für die einfacheren Arten der String-Suche diskutiert.

Ein ähnliches Problem, das im Bereich der Bioinformatik und Genomik eingeführt wurde, ist das maximale exakte Matching (MEM). Bei zwei Strings sind MEMs gemeinsame Teilstrings, die nicht nach links oder rechts erweitert werden können, ohne eine Abweichung zu verursachen.

Beispiele für Suchalgorithmen

Naive String-Suche

Eine einfache und ineffiziente Methode, um zu sehen, wo eine Zeichenfolge in einer anderen vorkommt, besteht darin, jede Stelle, an der sie sich befinden könnte, einzeln zu überprüfen, um zu sehen, ob sie dort ist. Zuerst sehen wir also, ob es eine Kopie der Nadel im ersten Zeichen des Heuhaufens gibt; wenn nicht, schauen wir, ob es eine Kopie der Nadel gibt, die beim zweiten Zeichen des Heuhaufens beginnt; wenn nicht, beginnen wir mit dem dritten Zeichen und so weiter. Im Normalfall müssen wir für jede falsche Position nur ein oder zwei Zeichen betrachten, um zu sehen, dass es sich um eine falsche Position handelt. Im Durchschnitt dauert dies also O ( n + m ) Schritte, wobei n die Länge von ist der Heuhaufen und m ist die Länge der Nadel; aber im schlimmsten Fall, wenn Sie nach einer Zeichenfolge wie "aaaab" in einer Zeichenfolge wie "aaaaaaaaab" suchen, dauert es O ( nm )

Finite-State-Automaten-basierte Suche

DFA-Suche mommy.svg

Bei diesem Ansatz vermeiden wir Backtracking, indem wir einen deterministischen endlichen Automaten (DFA) konstruieren , der gespeicherte Suchstrings erkennt. Diese sind teuer in der Konstruktion – sie werden normalerweise in der Powerset-Konstruktion erstellt –, sind aber sehr schnell zu verwenden. Zum Beispiel kann die DFA erkennt die rechts abgebildete das Wort „MAMA“. Dieser Ansatz wird in der Praxis häufig verallgemeinert, um nach beliebigen regulären Ausdrücken zu suchen .

Stubs

Knuth–Morris–Pratt berechnet einen DFA , der Eingaben mit dem zu suchenden String als Suffix erkennt, Boyer–Moore beginnt mit der Suche am Ende der Nadel, sodass er normalerweise bei jedem Schritt um eine ganze Nadellänge vorspringen kann. Baeza-Yates verfolgt, ob die vorherigen j Zeichen ein Präfix des Suchstrings waren und ist daher an die Fuzzy-String-Suche anpassbar . Der Bitap-Algorithmus ist eine Anwendung des Ansatzes von Baeza-Yates.

Indexmethoden

Schnellere Suchalgorithmen verarbeiten den Text vor. Nach dem Erstellen eines Teilstringindexes , beispielsweise eines Suffixbaums oder Suffixarrays , können die Vorkommen eines Musters schnell gefunden werden. Als Beispiel kann ein Suffixbaum in der Zeit erstellt werden, und alle Vorkommen eines Musters können in der Zeit gefunden werden, unter der Annahme, dass das Alphabet eine konstante Größe hat und alle inneren Knoten im Suffixbaum wissen, welche Blätter sich darunter befinden. Letzteres kann erreicht werden, indem ein DFS-Algorithmus von der Wurzel des Suffixbaums ausgeführt wird.

Andere Varianten

Einige Suchmethoden, zum Beispiel die Trigrammsuche , sollen eher eine "Nähe"-Bewertung zwischen der Suchzeichenfolge und dem Text als eine "Übereinstimmung/Nichtübereinstimmung" finden. Diese werden manchmal als "unscharfe" Suchen bezeichnet .


Klassifizierung von Suchalgorithmen

Klassifizierung nach einer Reihe von Mustern

Die verschiedenen Algorithmen können nach der Anzahl der jeweils verwendeten Muster klassifiziert werden.

Single-Pattern-Algorithmen

In der folgenden Zusammenstellung ist m die Länge des Musters, n die Länge des durchsuchbaren Textes, k = |Σ| die Größe des Alphabets ist und f eine durch SIMD- Operationen eingeführte Konstante ist .

Algorithmus Vorlaufzeit Spielzeit Platz
Naiver String-Suchalgorithmus keiner (mn) keiner
Optimierter naiver String-Suchalgorithmus (libc++ und libstdc++ string::find) keiner Θ(mn/w) keiner
Rabin-Karp-Algorithmus (m) Durchschnitt Θ(n + m),
schlechteste Θ((n−m)m) 		O(1)
Knuth–Morris–Pratt-Algorithmus (m) (n) (m)
Boyer-Moore-String-Suchalgorithmus (m + k) bestes Ω(n/m),
schlechtestes O(mn) 		(k)
Bitap-Algorithmus ( shift-or , shift-and , Baeza-Yates-Gonnet ; Fuzzy; Agrep) (m + k) O(mn)
Zwei-Wege-String-Matching-Algorithmus (glibc memmem/strstr) (m) O(n+m) O(1)
BNDM (Rückwärts nicht-deterministisches DAWG-Matching) (unscharf + regex; nrgrep) O(m) Auf)
BOM (Rückwärts-Oracle-Abgleich) O(m) O(mn)
FM-Index Auf) O(m) Auf)
1. ^ Asymptotische Zeiten werden mit O-, Ω- und -Notation ausgedrückt .

Der Boyer-Moore-String-Suchalgorithmus ist der Standard-Benchmark für die praktische String-Suchliteratur.

Algorithmen, die eine endliche Menge von Mustern verwenden

Algorithmen mit unendlich vielen Mustern

Natürlich können die Muster in diesem Fall nicht endlich aufgezählt werden. Sie werden normalerweise durch eine reguläre Grammatik oder einen regulären Ausdruck dargestellt .

Klassifizierung durch den Einsatz von Vorverarbeitungsprogrammen

Andere Klassifizierungsansätze sind möglich. Eines der häufigsten verwendet die Vorverarbeitung als Hauptkriterium.

Klassen von String-Suchalgorithmen
Text nicht vorverarbeitet Text vorverarbeitet
Muster nicht vorverarbeitet Elementare Algorithmen Indexmethoden
Muster vorverarbeitet Konstruierte Suchmaschinen Signaturmethoden:

Klassifizierung nach Matching-Strategien

Ein anderer klassifiziert die Algorithmen nach ihrer Matching-Strategie:

  • Passen Sie zuerst das Präfix an (Knuth-Morris-Pratt, Shift-And, Aho-Corasick)
  • Passen Sie zuerst das Suffix an (Boyer-Moore und Varianten, Commentz-Walter)
  • Passen Sie zuerst den besten Faktor an (BNDM, BOM, Set-BOM)
  • Andere Strategie (Naiv, Rabin-Karp)

Siehe auch

Verweise

  1. ^ Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L. (2004). "Vielseitige und offene Software zum Vergleich großer Genome" . Genombiologie . 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). „Ein praktischer Algorithmus zum Finden maximaler exakter Übereinstimmungen in großen Sequenzdatensätzen mit spärlichen Suffix-Arrays“ . Bioinformatik . 25 (13): 1609–1616. doi : 10.1093/bioinformatics/btp275 . PMC  2732316 . PMID  19389736 .
  3. ^ Kumar, Aditya. "libc++: String::find-Algorithmus verbessern" . Cite Journal erfordert |journal=( Hilfe )
  4. ^ Kumar, Aditya. "libstdc++: String::find-Algorithmus verbessern" . Cite Journal erfordert |journal=( Hilfe )
  5. ^ Crochemore, Maxime; Perrin, Dominique (1. Juli 1991). "Zwei-Wege-String-Matching" (PDF) . Zeitschrift der ACM . 38 (3): 650–674. doi : 10.1145/116825.116845 . S2CID  15055316 .
  6. ^ Navarro, Gonzalo; Raffinot, Mathieu (1998). "Ein bitparalleler Ansatz für Suffix-Automaten: Schneller erweiterter String-Matching" (PDF) . Kombinatorischer Musterabgleich . Skript zur Vorlesung Informatik. Springer Berlin-Heidelberg. 1448 : 14–33. doi : 10.1007/bfb0030778 . ISBN 978-3-540-64739-3.
  7. ^ Ventilator, H.; Yao, N.; Ma, H. (Dezember 2009). "Schnelle Varianten des Rückwärts-Oracle-Marching-Algorithmus" (PDF) . 2009 Vierte Internationale Konferenz über Internet-Computing für Wissenschaft und Technik : 56–59. doi : 10.1109/ICICSE.2009.53 . ISBN 978-1-4244-6754-9. S2CID  6073627 .
  8. ^ Hume; Sonntag (1991). "Schnelle String-Suche" . Software: Praxis und Erfahrung . 21 (11): 1221–1248. doi : 10.1002/sp.4380211105 . S2CID  5902579 .
  9. ^ Melichar, Borivoj, Jan Holub und J. Polcar. Textsuchalgorithmen. Band I: Forward String Matching. vol. 1. 2 Bände, 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 , 33rd International Conference on Very Large Data Bases (VLDB)
  11. ^ Gonzalo Navarro; Mathieu Raffinot (2008), Flexible Pattern Matching Strings: Praktische Online-Suchalgorithmen für Texte und biologische Sequenzen , ISBN 978-0-521-03993-2

Externe Links