Zeichenkettenalgorithmus
Zeichenkettenalgorithmen (englisch: string algorithms) sind Verfahren der Informatik zur algorithmischen Bearbeitung endlicher Symbolsequenzen über einem gegebenen Alphabet. Sie umfassen Methoden zur Lokalisation von Teilsequenzen, zur Generierung komprimierter Indizes sowie zur Transformation und Analyse digitaler Texte. Ihre Anwendung erstreckt sich auf Bereiche wie die Bioinformatik, Datenkompression, Plagiaterkennung und das Information Retrieval.
Grundbegriffe
Alphabet
Ein Alphabet ist eine endliche Menge von Symbolen.<ref name="hopcroft" /> Die Symbole eines Alphabets werden auch als Zeichen (englisch: characters) bezeichnet.<ref name="wagenknecht" /> Häufig verwendete Alphabete umfassen das binäre Alphabet <math display="inline">\sum = \{0,1\}</math>, das ASCII-Alphabet mit 128 Zeichen oder das Unicode-Alphabet mit über 100.000 Zeichen.<ref name="hopcroft" />
Zeichenkette
Eine Zeichenkette (englisch: string) ist eine endliche Sequenz von Symbolen über einem Alphabet.<ref name="hopcroft" /> Eine Zeichenkette <math display="inline">w</math> wird typischerweise als <math display="inline">w = w_1 w_2 \dotsc w_n</math> geschrieben, wobei jedes <math display="inline">w_i</math> ein Symbol aus dem zugrunde liegenden Alphabet ist.<ref name="grainger" /> Die Länge einer Zeichenkette ist definiert als die Anzahl der Symbole in dieser Sequenz und wird mit <math display="inline">|w|</math> notiert.<ref name="hopcroft" />
Teilzeichenkette, Präfix und Suffix
Eine Teilzeichenkette (englisch: substring) ist eine zusammenhängende Teilfolge von Zeichen innerhalb einer Zeichenkette.<ref name="charras" /> Ein Präfix ist eine Teilzeichenkette, die am Anfang einer Zeichenkette beginnt, also bei Index 0 startet.<ref name="kracht" /> Ein Suffix ist eine Teilzeichenkette, die am Ende einer Zeichenkette endet.<ref name="giuliani" /> Formal gilt: Ein String <math display="inline">u</math> ist ein Präfix von <math display="inline">w</math>, wenn ein String <math display="inline">v</math> existiert, sodass <math display="inline">w = uv</math> gilt. Entsprechend ist <math display="inline">u</math> ein Suffix von <math display="inline">w</math>, wenn ein String <math display="inline">v</math> existiert, sodass <math display="inline">w = vu</math> gilt.<ref name="charras" />
Konkatenation
Die Konkatenation ist die Verkettung zweier Zeichenketten, bei der die zweite Zeichenkette an das Ende der ersten angefügt wird. Für zwei Zeichenketten <math display="inline">x</math> und <math display="inline">y</math> wird ihre Konkatenation als <math display="inline">xy</math> notiert. Die Länge der konkatenierten Zeichenkette entspricht der Summe der Längen der beiden Ausgangszeichenketten: <math display="inline">|xy| = |x| + |y|</math>.<ref name="hopcroft" />
Historische Entwicklung
Die systematische Erforschung von Zeichenkettenalgorithmen begann in den späten 1960er Jahren mit der Veröffentlichung des ersten Bandes von The Art of Computer Programming durch Donald E. Knuth im Jahr 1968. Dieses Werk legte die theoretischen Grundlagen für die Analyse von Algorithmen und etablierte den Begriff der asymptotischen Komplexität in der Informatik.<ref name="pomona" /><ref name="knuth-8" />
Im Jahr 1970 veröffentlichten James H. Morris jr. und Vaughan R. Pratt einen Technical Report, der die Grundlage für den später nach ihnen und Knuth benannten Algorithmus legte.<ref name="nicaud" /><ref name="morris" /> Die endgültige Version des Knuth-Morris-Pratt-Algorithmus erschien 1977 in der Fachzeitschrift SIAM Journal on Computing und stellte den ersten linearen String-Matching-Algorithmus dar.<ref name="amir" /><ref name="knuth-7" />
Im selben Jahr 1977 wurde der Boyer-Moore-Algorithmus von Robert S. Boyer und J Strother Moore vorgestellt, der durch seine rückwärts gerichtete Suche und seine Verschiebungsheuristiken eine deutliche Beschleunigung in der Praxis ermöglichte.<ref name="wu" /><ref name="boyer" />
Der Rabin-Karp-Algorithmus, der auf dem Prinzip des Fingerprinting basiert, wurde 1980 entwickelt und nutzt Rolling-Hash-Funktionen für effiziente Mustersuche.<ref name="karp" />
Ein bedeutender Meilenstein in der Entwicklung von Datenstrukturen für Zeichenketten war die Einführung der Suffixarrays durch Udi Manber und Eugene Myers im Jahr 1993. Diese Datenstruktur bot eine platzsparende Alternative zu Suffixbäumen.<ref name="ko" /><ref name="manber" />
Die erste lineare Konstruktion von Suffixarrays wurde erst im Jahr 2003 erreicht, als mehrere Forschergruppen unabhängig voneinander lineare Algorithmen entwickelten.<ref name="karkkainen" />
Algorithmen für das String-Matching
Das String-Matching-Problem, auch als Mustersuche (englisch: pattern matching) bezeichnet, besteht darin, alle Vorkommen eines Musters <math display="inline">P</math> in einem Text <math display="inline">T</math> zu finden.<ref name="charras" /> Die Länge des Textes wird typischerweise mit <math display="inline">n</math> und die Länge des Musters mit <math display="inline">m</math> bezeichnet.<ref name="crochemore-2" />
Hauptalgorithmen
Knuth-Morris-Pratt-Algorithmus
Der Knuth-Morris-Pratt-Algorithmus (KMP-Algorithmus) wurde 1977 von Donald E. Knuth, James H. Morris und Vaughan R. Pratt veröffentlicht. Der Algorithmus vergleicht das Muster von links nach rechts mit dem Text. Die zentrale Innovation des KMP-Algorithmus besteht in der Verwendung einer Präfixfunktion (auch Failure-Funktion genannt), die für jede Position im Muster die Länge des längsten echten Präfix angibt, das auch Suffix des aktuellen Präfixes des Musters ist.<ref name="knuth-7" />
Der KMP-Algorithmus weist eine lineare Zeitkomplexität von <math display="inline">\mathcal{O}(m + n)</math> auf.<ref name="knuth-7" /> Bei der Suche werden höchstens <math display="inline">2n - 1</math> Textzeichenvergleiche durchgeführt.<ref name="breslauer" /> Die Raumkomplexität beträgt <math display="inline">\mathcal{O}(m)</math> für die Speicherung der Präfixfunktion.<ref name="knuth-7" />
Boyer-Moore-Algorithmus
Der Boyer-Moore-Algorithmus, 1977 von Robert S. Boyer und J Strother Moore veröffentlicht, gilt als einer der effizientesten String-Matching-Algorithmen in typischen Anwendungen.<ref name="sharma" /> Im Gegensatz zum KMP-Algorithmus vergleicht der Boyer-Moore-Algorithmus das Muster von rechts nach links.<ref name="nxt" />
Der Algorithmus verwendet zwei Verschiebungsfunktionen: die Bad-Character-Heuristik und die Good-Suffix-Heuristik. Die Bad-Character-Heuristik verschiebt das Muster basierend auf dem rechts vom aktuellen Fenster stehenden Zeichen, während die Good-Suffix-Heuristik die Information über übereinstimmende Suffixe nutzt.<ref name="ahmed" />
In der Praxis erreicht der Boyer-Moore-Algorithmus oft eine sublineare Laufzeit, da bei großen Alphabeten viele Zeichen des Textes übersprungen werden können. Die Worst-Case-Komplexität beträgt <math display="inline">\mathcal{O}(nm)</math>, während die Best-Case-Komplexität <math display="inline">\mathcal{O}(n/m)</math> beträgt.<ref name="galil" /> Die Raumkomplexität liegt bei <math display="inline">\mathcal{O}(m + |\sum|)</math>, wobei <math display="inline">|\sum|</math> die Größe des Alphabets bezeichnet.
Rabin-Karp-Algorithmus
Der Rabin-Karp-Algorithmus wurde 1987 von Richard M. Karp und Michael O. Rabin entwickelt. Der Algorithmus verwendet das Prinzip des Rolling-Hash für effiziente Mustersuche.<ref name="karp" /> Dabei wird für das Muster und für jedes Fenster der Länge <math display="inline">m</math> im Text ein Hashwert berechnet.<ref name="gluck" /> Statt direkter Zeichenvergleiche werden zunächst die Hashwerte verglichen, und nur bei Übereinstimmung erfolgt ein exakter Vergleich.<ref name="gg-5" />
Der Rabin-Karp-Algorithmus ist besonders effektiv für die Mehrfachmustersuche, bei der mehrere Muster gleichzeitig gesucht werden.<ref name="gg-5" /> Die durchschnittliche Zeitkomplexität beträgt <math display="inline">\mathcal{O}(n)</math>, während der Worst-Case <math display="inline">\mathcal{O}(m \times n)</math> beträgt.<ref name="programiz" /> Die Raumkomplexität ist <math display="inline">\mathcal{O}(1)</math>, da keine zusätzlichen Datenstrukturen benötigt werden.<ref name="gluck" />
Aho-Corasick-Algorithmus
Der Aho-Corasick-Algorithmus wurde 1975 von Alfred V. Aho und Margaret J. Corasick entwickelt. Er löst das Problem des Mehrfachmuster-Matchings, bei dem mehrere Muster gleichzeitig in einem Text gesucht werden.<ref name="aho" />
Der Algorithmus basiert auf einem endlichen Automaten, der aus einem Trie der Muster mit zusätzlichen Failure-Links konstruiert wird. Die Zeitkomplexität beträgt <math display="inline">\mathcal{O}(n + m + z)</math>, wobei <math display="inline">z</math> die Anzahl der gefundenen Übereinstimmungen ist.<ref name="aho" /> Die Raumkomplexität liegt bei <math display="inline">\mathcal{O}(m \times L)</math>, wobei <math display="inline">L</math> die maximale Musterlänge ist.
Anwendungen des Aho-Corasick-Algorithmus umfassen die Tokenisierung von Texten und die Erkennung von Eindringlingen in Netzwerken (Intrusion Detection).<ref name="lakhotiya" />
Weitere String-Matching-Algorithmen
Neben den genannten Hauptalgorithmen existieren zahlreiche weitere Verfahren für das String-Matching:
Der Horspool-Algorithmus (1980) stellt eine vereinfachte Variante des Boyer-Moore-Algorithmus dar, die ausschließlich die Bad-Character-Heuristik verwendet.<ref name="horspool" /> Der Sunday-Algorithmus (1990), auch als „Quick-Search“ bekannt, nutzt das Zeichen unmittelbar nach dem aktuellen Suchfenster für die Verschiebungsberechnung.<ref name="alhaj" /><ref name="sunday" /> Der Zhu-Takaoka-Algorithmus (1987) erweitert die Bad-Character-Heuristik auf zwei Zeichen.<ref name="berry" /> Der Turbo-BM-Algorithmus (1992) führt den Turbo-Shift ein, der den Worst-Case des Boyer-Moore-Algorithmus verbessert.<ref name="crochemore-2" /> Der Apostolico-Giancarlo-Algorithmus (1986) bietet eine einfache lineare Schranke für das String-Matching.<ref name="crochemore-3" /> Der Two-Way-Algorithmus (1991) arbeitet in-place mit <math display="inline">\mathcal{O}(n)</math>-Zeitkomplexität und wird in der GNU-C-Bibliothek (glibc) verwendet.<ref name="crochemore-1" /> Der Commentz-Walter-Algorithmus (1979) kombiniert die Strategien von Boyer-Moore und Aho-Corasick für die Mehrfachmustersuche.<ref name="wu" /><ref name="commentz" /> Die Shift-Or- und Shift-And-Algorithmen (1992) nutzen bit-parallele Operationen für das String-Matching.<ref name="navarro-0" />
Datenstrukturen
Suffixbäume
Ein Suffixbaum ist eine komprimierte Trie-Datenstruktur, die alle Suffixe einer gegebenen Zeichenkette speichert.<ref name="sahni" /> Die Entwicklung von Suffixbäumen begann mit Peter Weiner, der 1973 den ersten Linearzeitalgorithmus zur Konstruktion vorstellte.<ref name="hendrian" /> Der Weiner-Algorithmus hat eine Zeitkomplexität von <math display="inline">\mathcal{O}(n)</math>, benötigt jedoch Speicherplatz von <math display="inline">\mathcal{O}(n \cdot |\sum|)</math> Speicherplatz.<ref name="gusfield" />
Edward McCreight verbesserte 1976 den Algorithmus und reduzierte den Speicherbedarf auf <math display="inline">\mathcal{O}(n)</math>.<ref name="gusfield" /> Der McCreight-Algorithmus ist platzsparender als der Weiner-Algorithmus, arbeitet jedoch offline und benötigt den gesamten Text im Voraus.<ref name="hendrian" /> Esko Ukkonen entwickelte 1995 einen Online-Algorithmus zur Suffixbaum-Konstruktion mit <math display="inline">\mathcal{O}(n)</math>-Speicherbedarf.<ref name="ukkonen" /> Der Ukkonen-Algorithmus baut den Suffixbaum schrittweise auf und kann Zeichen für Zeichen verarbeiten.<ref name="kumar-4" /> Eine umfassende Darstellung von Algorithmen auf Suffixbäumen und verwandten Datenstrukturen bietet das Lehrbuch Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology von Dan Gusfield aus dem Jahr 1997.<ref name="gusfield" />
Suffixarrays
Ein Suffixarray ist eine sortierte Liste aller Suffixe einer Zeichenkette, die als Array von Startindizes repräsentiert wird.<ref name="ko" /> Die Einführung von Suffixarrays erfolgte 1993 durch Udi Manber und Eugene Myers.<ref name="manber" /> Der Manber-Myers-Algorithmus zur Konstruktion hat eine Zeitkomplexität von <math display="inline">\mathcal{O}(n \log n)</math>, während die Suche nach einem Muster Zeit von <math display="inline">\mathcal{O}(m \log n)</math> benötigt.<ref name="ko" />
Die Entwicklung linearer Konstruktionsalgorithmen für Suffixarrays war ein bedeutender Forschungsschwerpunkt.<ref name="ko" /> Erst 2003 wurden mehrere unabhängige Algorithmen mit linearer Laufzeit vorgestellt.<ref name="karkkainen" /> Ein eleganter Algorithmus zur Konstruktion von Suffixarrays wurde von Rajasekaran und Nicolae 2014 beschrieben.<ref name="rajasekaran" />
Tries und Patricia-Trees
Ein Trie (auch Präfixbaum genannt) ist eine baumbasierte Datenstruktur zur Speicherung von Zeichenketten, bei der jeder Knoten ein Zeichen repräsentiert.<ref name="briandais" /> Tries werden für Autocomplete-Funktionen, Rechtschreibprüfungen und IP-Routing eingesetzt.<ref name="gg-7" />
Der Patricia-Trie (Practical Algorithm To Retrieve Information Coded In Alphanumeric) wurde 1968 von Donald R. Morrison vorgestellt.<ref name="morrison" /> Patricia-Tries sind platzoptimierte Varianten von Tries, die Pfadkomprimierung verwenden und <math display="inline">\mathcal{O}(n)</math>-Speicher benötigen.<ref name="sedgewick" /><ref name="knuth-3" />
Burrows-Wheeler-Transformation
Die Burrows-Wheeler-Transformation (BWT) wurde 1994 von Michael Burrows und David Wheeler am DEC Systems Research Center (SRC) in Palo Alto entwickelt.<ref name="fenwick-7" /> Die BWT ist eine reversible Transformation, die eine Zeichenkette in eine permutierte Form überführt, in der gleiche Zeichen typischerweise gruppiert auftreten.<ref name="fenwick-6" /> Diese Eigenschaft macht die BWT besonders geeignet für die Datenkompression.<ref name="landau" />
Die BWT bildet die Grundlage für viele moderne Kompressionsalgorithmen, darunter bzip2.<ref name="ethw-9" /> Verbesserungen der Burrows-Wheeler-Kompression wurden von verschiedenen Forschern vorgeschlagen.<ref name="fenwick-7" />
FM-Index
Der FM-Index wurde 2000 von Paolo Ferragina und Giovanni Manzini entwickelt. Der FM-Index ist ein komprimierter Volltext-Index, der die Burrows-Wheeler-Transformation mit Rang- und Selektionsoperationen kombiniert. Der Index benötigt etwa 0,5 Bytes pro Zeichen und ermöglicht effiziente Suchoperationen.<ref name="ferragina" />
Der FM-Index wird in der Bioinformatik für die Sequenzalignment eingesetzt, insbesondere in Tools wie Bow-Tie und Burrows-Wheeler-Aligner (BWA).<ref name="gaz" />
Komplexitätsanalyse
Zeitkomplexität
Die Zeitkomplexität von String-Matching-Algorithmen beschreibt die Anzahl der benötigten Operationen in Abhängigkeit von der Textlänge <math display="inline">n</math> und der Musterlänge <math display="inline">m</math>.<ref name="crochemore-2" />
Der naive Algorithmus hat eine Best-Case-Komplexität von <math display="inline">\mathcal{O}(n)</math>, eine Average-Case-Komplexität von <math display="inline">\mathcal{O}(nm)</math> und eine Worst-Case-Komplexität von <math display="inline">\mathcal{O}(nm)</math>.<ref name="gg-4" /> Der Knuth-Morris-Pratt-Algorithmus garantiert eine Zeitkomplexität von <math display="inline">\mathcal{O}(n + m)</math> in allen Fällen.<ref name="gg-0" /> Der Boyer-Moore-Algorithmus erreicht im Best-Case <math display="inline">\mathcal{O}(n/m)</math>, im Average-Case ebenfalls <math display="inline">\mathcal{O}(n/m)</math> und im Worst-Case <math display="inline">\mathcal{O}(nm)</math>.<ref name="gg-3" /> Der Rabin-Karp-Algorithmus hat eine Best- und Average-Case-Komplexität von <math display="inline">\mathcal{O}(n + m)</math> und einen Worst-Case von <math display="inline">\mathcal{O}(nm)</math>.<ref name="programiz" /> Die Z-Algorithmus bietet eine Zeitkomplexität von <math display="inline">\mathcal{O}(n + m)</math>.<ref name="gg-8" /> Der Aho-Corasick-Algorithmus arbeitet in <math display="inline">\mathcal{O}(n + m + z)</math>, wobei <math display="inline">z</math> die Anzahl der Ausgaben ist.<ref name="rosetta" />
Raumkomplexität
Die Raumkomplexität beschreibt den zusätzlichen Speicherbedarf neben dem Eingabetext und dem Muster.
Der naive Algorithmus und der Rabin-Karp-Algorithmus benötigen zusätzlichen Speicher von <math display="inline">\mathcal{O}(1)</math>.<ref name="rasool" /> Der Knuth-Morris-Pratt-Algorithmus benötigt Speicher von <math display="inline">\mathcal{O}(m)</math> für die Präfixfunktion.<ref name="vashchegin" /> Der Boyer-Moore-Algorithmus benötigt Speicher von <math display="inline">\mathcal{O}(m + |\sum|)</math> für die Verschiebungstabellen.<ref name="gg-3" /> Der Z-Algorithmus benötigt Speicher von <math display="inline">\mathcal{O}(n + m)</math> für das Z-Array.<ref name="gg-8" /> Der Aho-Corasick-Algorithmus benötigt Speicher von <math display="inline">\mathcal{O}(m \times L)</math> für den Automaten.<ref name="gg-2" />
Untere Schranken
Ronald L. Rivest bewies 1977, dass für das String-Matching mindestens Zeichenabfragen von <math display="inline">n - |p| + 1</math> notwendig sind. Diese untere Schranke gilt für deterministische Algorithmen im Worst-Case.<ref name="rivest" />
Zsolt Tuza zeigte, dass mehr als 50 Prozent aller binären Muster „evasive“ sind, was bedeutet, dass alle Zeichen abgefragt werden müssen.<ref name="he" />
Anwendungsgebiete
Bioinformatik
Die Bioinformatik ist eines der wichtigsten Anwendungsgebiete für Zeichenkettenalgorithmen.<ref name="retha" /> Die Analyse biologischer Sequenzen wie DNA, RNA und Proteine erfordert effiziente Algorithmen für das Muster-Matching und das Sequenzalignment.<ref name="kroll" />
Der Needleman-Wunsch-Algorithmus, 1970 entwickelt, löst das Problem des globalen Alignments zweier Sequenzen mit einer Zeitkomplexität von <math display="inline">\mathcal{O}(mn)</math>.<ref name="chan" /><ref name="needleman" /> Der Smith-Waterman-Algorithmus, 1981 veröffentlicht, berechnet lokale Alignments zwischen Sequenzen.<ref name="smith" /> Die Burrows-Wheeler-Transformation und der FM-Index bilden die Grundlage für moderne Sequenzierungswerkzeuge wie Bow-Tie und BWA.<ref name="ferragina" /> Diese Tools ermöglichen die effiziente Kartierung von kurzen DNA-Sequenzen auf Referenzgenome.<ref name="langmead" />
Textverarbeitung
In der Textverarbeitung werden Zeichenkettenalgorithmen für Suchen-und-Ersetzen-Funktionen, reguläre Ausdrücke und Texteditoren eingesetzt.
Der Boyer-Moore-Algorithmus ist etwa drei bis fünf Mal schneller als der Knuth-Morris-Pratt-Algorithmus (KMP) in typischen Anwendungen und wird im GNU-grep-Programm verwendet.<ref name="dawood" /> Die Implementierung des KMP-Algorithmus wird in verschiedenen akademischen Kursen behandelt.<ref name="crochemore-2" />
Datenkompression
Die Datenkompression nutzt Zeichenkettenalgorithmen zur Reduktion der Speichergröße von Texten.
Die Burrows-Wheeler-Transformation ist eine Kernkomponente des Kompressionsprogramms bzip2.<ref name="nelson" /> Die Lempel-Ziv-Kompressionsalgorithmen (LZ77 und LZ78), 1977 und 1978 entwickelt,<ref name="ethw-4" /> bilden die Grundlage für viele moderne Kompressionsformate wie ZIP und Gzip.<ref name="gnu" />
Information Retrieval
Im Information Retrieval werden Zeichenkettenalgorithmen für die Indexierung und Suche in großen Textsammlungen eingesetzt.<ref name="baeza" />
Suffixarrays und Suffixbäume ermöglichen effiziente Volltextsuchen in großen Dokumentensammlungen.<ref name="manber" /> Tries werden für Autocomplete-Funktionen, Rechtschreibprüfungen und IP-Routing-Tabellen verwendet.<ref name="kumar-5" /> Das approximative String-Matching ermöglicht die Suche nach ähnlichen Zeichenketten und wird für fehlertolerante Suchen eingesetzt.<ref name="navarro-1" />
Plagiaterkennung
Die Plagiaterkennung nutzt Zeichenkettenalgorithmen zur Identifikation von Textüberlappungen und ähnlichen Dokumenten.
Der Rabin-Karp-Algorithmus mit Rolling-Hash wird für die effiziente Erkennung von Textplagiaten eingesetzt.<ref name="simanjuntak" /> Der Winnowing-Algorithmus basiert auf k-gram-Hashes und wird für die Dokumentensignatur verwendet.<ref name="pc" /> String-Ähnlichkeitsmaße wie Tf-idf, Cosine-Similarity, Jaro-Winkler-Distanz und Levenshtein-Distanz werden für die Plagiaterkennung eingesetzt.<ref name="wibowo" />
Forensik
Weitere Anwendungen der Zeichenkettenalgorithmen in der Forensik umfassen die Restricted Forensic Levenshtein Distance für die Analyse von DNA-Spuren.<ref name="petty" />
Einzelnachweise
<references responsive="1"> <ref name="ahmed">Ubaid Ahmed: Boyer Moore Algorithm with Bad character Heuristic. Topcoder, 15. November 2021, abgerufen am 17. Februar 2026.</ref> <ref name="aho">Alfred V. Aho, Margaret J. Corasick: Efficient String Matching: An Aid to Bibliographic Search. In: Communications of the ACM. Jg. 18, Nr. 6. New York 1975, S. 333–340, doi:10.1145/360825.360855.</ref> <ref name="alhaj">Mosleh M. Abu-Alhaj et al.: An innovative platform to improve the performance of exact-string-matching algorithms. In: International Journal of Computer Science and Information Security. Band 7, Nr. 1, 2010, S. 280–283, doi:10.48550/ARXIV.1002.2222.</ref> <ref name="amir">Amihood Amir et al.: Dynamic Text and Static Pattern Matching. In: ACM Transactions on Algorithms. Jg. 3, Nr. 2. New York 2007, doi:10.1145/1240233.1240242.</ref> <ref name="baeza">Ricardo Baeza-Yates et al.: Searching large text collections. In: James Abello, Panos M. Pardalos (Hrsg.): Handbook of massive data sets. Kluwer, Dordrecht 2002, ISBN 978-1-4020-0489-6, S. 195–243, doi:10.5555/779232.779240.</ref> <ref name="berry">Thomas Berry, Somasundaram Ravindran: Tuning the Zhu-Takaoka string matching algorithm and experimental results. In: Kybernetika. Jg. 38, Nr. 1. Prag 2002, S. 67–80.</ref> <ref name="boyer">Robert S. Boyer, J Strother Moore: A Fast String Searching Algorithm. In: Communications of the ACM. Jg. 20. New York 1977, S. 762–772.</ref> <ref name="breslauer">Dany Breslauer et al.: Tight Comparison Bounds for the String Prefix-Matching Problem. In: Information Processing Letters. Band 47, Nr. 1. Amsterdam 1993, S. 51–57, doi:10.1016/0020-0190(93)90156-4.</ref> <ref name="briandais">René de la Briandais: File Searching Using Variable Length Keys. In: Proceedings AFIPS Western Joint Computer Conference. Band 15. San Francisco 1959, S. 295–298, doi:10.1145/1457838.1457895.</ref> <ref name="chan">Alexander Chan: An Analysis of Pairwise Sequence Alignment Algorithm Complexities: Needleman-Wunsch, Smith-Waterman, FASTA, BLAST and Gapped BLAST. Doug Brutlag, abgerufen am 18. Februar 2026.</ref> <ref name="charras">Christian Charras, Thierry Lecroq: Handbook of Exact String-Matching Algorithms. London 2004, ISBN 0-9543006-4-5 (univ-mlv.fr [PDF]).</ref> <ref name="commentz">Beate Commentz-Walter: A String Matching Algorithm Fast on the Average. In: Hermann A. Maurer (Hrsg.): Automata, Languages and Programming. Springer, Berlin 1979, S. 118–132, doi:10.1007/3-540-09510-1_10.</ref> <ref name="crochemore-1">Maxime Crochemore, Dominique Perrin: Two-Way String-Matching. In: Journal of the ACM. Jg. 38, Nr. 3. New York 1991, S. 650–674, doi:10.1145/116825.116845.</ref> <ref name="crochemore-2">Maxime Crochemore, Thierry Lecroq: Pattern-Matching and Text-Compression Algorithms. In: ACM Computing Surveys. Jg. 28, Nr. 1. New York 1996, S. 39–41, doi:10.1145/234313.234331.</ref> <ref name="crochemore-3">Maxime Crochemore: A unifying look at the Apostolico–Giancarlo string-matching algorithm. In: Journal of Discrete Algorithms. Jg. 1, Nr. 1. Amsterdam 2003, S. 37–52, doi:10.1016/S1570-8667(03)00005-4.</ref> <ref name="dawood">Sarhan S. Darwood, Saman A. Barakat: Empirical Performance Evaluation of Knuth Morris Pratt And Boyer Moore String Matching Algorithms. In: Journal of Duhok University. Band 23, Nr. 1, 2020, S. 134–143, doi:10.26682/sjuod.2020.23.1.14.</ref> <ref name="ethw-4">Milestones: Lempel-Ziv Data Compression Algorithm, 1977. Engineering and Technology History Wiki (ETHW), 31. Oktober 2024, abgerufen am 18. Februar 2026.</ref> <ref name="ethw-9">History of Lossless Data Compression Algorithms. Engineering and Technology History Wiki (ETHW), 22. Januar 2019, abgerufen am 18. Februar 2026.</ref> <ref name="fenwick-6">Peter M. Fenwick: The Burrows-Wheeler Transform for Block Sorting Text Compression – Principles and Improvements. In: The Computer Journal. Jg. 39, Nr. 9. Oxford 1996, S. 731–740, doi:10.1093/comjnl/39.9.731.</ref> <ref name="fenwick-7">Peter M. Fenwick: Burrows-Wheeler compression: Principles and reflections. In: Theoretical Computer Science. Band 387, Nr. 3. Amsterdam 2007, S. 200–219, doi:10.1016/j.tcs.2007.07.012.</ref> <ref name="ferragina">Paolo Ferragina, Giovanni Manzini: The FM-Index: A Compressed Full-Text Index Based on the BWT. DIMACS, abgerufen am 18. Februar 2026.</ref> <ref name="galil">Zvi Galil: On Improving the Worst Case Running Time of the BoyerMoore String Matching Algorithm. In: Communications of the ACM. Jg. 22, Nr. 9. New York 1979, S. 505–508, doi:10.1145/359146.359148.</ref> <ref name="gaz">bvSFM: a tool for sequence alignment. GAZ – I3A Research Group, abgerufen am 18. Februar 2026.</ref> <ref name="gg-0">KMP Algorithm for Pattern Searching. GeeksforGeeks, 10. Oktober 2025, abgerufen am 18. Februar 2026.</ref> <ref name="gg-2">Aho-Corasick Algorithm for Pattern Searching. GeeksforGeeks, 23. Juli 2025, abgerufen am 18. Februar 2026.</ref> <ref name="gg-3">Boyer Moore Algorithm for Pattern Searching. GeeksforGeeks, 23. Juli 2025, abgerufen am 18. Februar 2026.</ref> <ref name="gg-4">Naive algorithm for Pattern Searching. GeeksforGeeks, 20. April 2024, abgerufen am 18. Februar 2026.</ref> <ref name="gg-5">Rabin-Karp Algorithm for Pattern Searching. GeeksforGeeks, 1. August 2025, abgerufen am 17. Februar 2026.</ref> <ref name="gg-7">Applications, Advantages and Disadvantages of Trie. GeeksforGeeks, 23. Juli 2025, abgerufen am 17. Februar 2026.</ref> <ref name="gg-8">Z algorithm (Linear time pattern searching Algorithm). GeeksforGeeks, 5. August 2025, abgerufen am 18. Februar 2026.</ref> <ref name="giuliani">Sara Giuliani et al.: When a Dollar Makes a BWT. In: Theoretical Computer Science. Band 857. Amsterdam 2021, S. 123–146, doi:10.1016/j.tcs.2021.01.008.</ref> <ref name="gluck">Robert Glück, Tetsuo Yokoyama: Reversible Programming: A Case Study of Two String-Matching Algorithms. In: Electronic Proceedings in Theoretical Computer Science. Band 373, Nr. 6. Sydney 2022, doi:10.4204/EPTCS.373.1.</ref> <ref name="gnu">GNU Gzip: General file (de)compression. GNU, Free Software Foundation, abgerufen am 18. Februar 2026.</ref> <ref name="grainger">Models of Computation. Lecture 1: Strings. The Grainger College of Engineering, 2018, abgerufen am 16. Februar 2026.</ref> <ref name="gusfield">Dan Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge 1997, Kap. 5: Introduction to Suffix Trees, S. 89–93, doi:10.1017/CBO9780511574931.007.</ref> <ref name="he">Xiaoyu He et al.: On the Decision Tree Complexity of String Matching. DROPS, Schloss Dagstuhl – LZI, 2012, abgerufen am 18. Februar 2026.</ref> <ref name="hendrian">Diptarama Hendrian et al.: Linear Time Online Algorithms for Constructing Linear-size Suffix Trie. In: Theoretical Computer Science. Band 1015, C. Amsterdam 2024, doi:10.1016/j.tcs.2024.114765.</ref> <ref name="hopcroft">John E. Hopcroft et al.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. überarb. Auflage. Pearson, München 2002, ISBN 978-3-8273-7020-4.</ref> <ref name="horspool">R. Nigel Horspool: Practical Fast Searching in Strings. In: Software: Practice & Experience. Jg. 10, Nr. 6. Chichester 1980, S. 501–506.</ref> <ref name="karkkainen">Juha Kärkkäinen, Peter Sanders: Simple Linear Work Suffix Array Construction. In: Jos C. M. Baeten et al. (Hrsg.): Automata, Languages and Programming. Springer, Berlin 2003, doi:10.1007/3-540-45061-0_73.</ref> <ref name="karp">Richard M. Karp, Michael O. Rabin: Efficient Randomized Pattern-Matching Algorithms. In: IBM Journal of Research and Development. Jg. 31. New York 1987, S. 249–260, doi:10.1147/rd.312.0249.</ref> <ref name="knuth-3">Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Addison-Wesley, Reading 1973.</ref> <ref name="knuth-7">Donald E. Knuth et al.: Fast Pattern Matching in Strings. In: SIAM Journal on Computing. Jg. 6, Nr. 2. Philadelphia 1977, S. 323–350, doi:10.1137/0206024.</ref> <ref name="knuth-8">Donald E. Knuth: The Art of Computer Programming. Band 1. Addison-Wesley, Upper Saddle River 1968.</ref> <ref name="ko">Pang Ko, Srinivas Aluru: Space Efficient Linear Time Construction of Suffix Arrays. In: Journal of Discrete Algorithms. Jg. 3, Nr. 2–4. Amsterdam 2005, S. 143–156, doi:10.1016/j.jda.2004.08.002.</ref> <ref name="kracht">Marcus Kracht: Formale Methoden. Universität Bielefeld, 2018, abgerufen am 16. Februar 2026.</ref> <ref name="kroll">José Eduardo Kroll et al.: A tool for integrating genetic and mass spectrometry‐based peptide data: Proteogenomics Viewer: PV: A genome browser‐like tool, which includes MS data visualization and peptide identification parameters. In: Bioessays. Jg. 39, Nr. 7. Hoboken 2017, doi:10.1002/bies.201700015.</ref> <ref name="kumar-4">Amarjeet Kumar: Suffix Tree-Ukkonen's Algorithm. Coding Ninjas, 27. März 2024, abgerufen am 17. Februar 2026.</ref> <ref name="kumar-5">Anish Kumar: Trie in Javascript: the Data Structure behind Autocomplete. StackFull.dev, 24. April 2025, abgerufen am 18. Februar 2026.</ref> <ref name="lakhotiya">Rushikesh Lakhotiya: Lexical Analyzer. In: International Research Journal of Engineering and Technology. Jg. 10, Nr. 1, 2023, S. 384–388.</ref> <ref name="landau">Shir Landau, Elad Verbin: The Burrows-Wheeler compression algorithm is even better than what you have thought. University of California, Davis, 8. April 2005, abgerufen am 18. Februar 2026.</ref> <ref name="langmead">Ben Langmead et al.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. In: Genome Biology. Jg. 10, Nr. 3. London 2009, doi:10.1186/gb-2009-10-3-r25.</ref> <ref name="manber">Udi Manber, Eugene W. Myers: Suffix Arrays: A New Method for On-Line String Searches. In: SIAM Journal on Computing. Jg. 22, Nr. 5. Philadelphia 1993, S. 935–948, doi:10.1137/0222058.</ref> <ref name="morris">James H. Morris jr., Vaughan R. Pratt: A Linear Pattern-Matching Algorithm. Berkeley 1970.</ref> <ref name="morrison">Donald R. Morrison: PATRICIA – Practical Algorithm To Retrieve Information Coded in Alphanumeric. In: Journal of the ACM. Jg. 15, Nr. 4. New York 1968, S. 514–534, doi:10.1145/321479.321481.</ref> <ref name="navarro-0">Gonzalo Navarro, Mathieu Raffinot: Fast and Flexible String Matching by Combining Bit-Parallelism and Suffix Automata. In: Journal of Experimental Algorithmics. Jg. 5, Nr. 4. New York 2000, doi:10.1145/351827.384246.</ref> <ref name="navarro-1">Gonzalo Navarro: A Guided Tour to Approximate String Matching. In: ACM Computing Surveys. Jg. 33, Nr. 1. New York 2001, S. 31–88, doi:10.1145/375360.375365.</ref> <ref name="needleman">Saul B. Needleman, Christian D. Wunsch: A general method applicable to the search for similarities in the amino acid sequence of two proteins. In: Journal of Molecular Biology. Band 48, Nr. 3. Amsterdam 1970, S. 443–453, doi:10.1016/0022-2836(70)90057-4.</ref> <ref name="nelson">Mark Nelson: Data Compression with the Burrows-Wheeler Transform. In: Dr. Dobb’s Journal. San Francisco 1996 (digiater.nl).</ref> <ref name="nicaud">Cyril Nicaud et al.: Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms. In: Leibniz International Proceedings in Informatics. Band 331. Saarbrücken 2025, S. 8:1–8:17, doi:10.4230/LIPIcs.CPM.2025.8.</ref> <ref name="nxt">Boyer–Moore Algorithm: Fast String Searching Explained. NxtWave, 7. Januar 2025, abgerufen am 17. Februar 2026.</ref> <ref name="pc">Fingerprinting (hash-based methods) for plagiarism detection. PlagPointer Plagiarismchecker.net, 12. Juli 2025, abgerufen am 18. Februar 2026.</ref> <ref name="petty">Taylor Petty et al.: A New String Edit Distance and Applications. In: Algorithms. Jg. 15, Nr. 7. Basel 2022, doi:10.3390/a15070242.</ref> <ref name="pomona">History of Algorithmic Analysis. Pomona College, abgerufen am 16. Februar 2026.</ref> <ref name="programiz">Rabin-Karp Algorithm. Programiz, Parewa Labs, abgerufen am 17. Februar 2026.</ref> <ref name="rajasekaran">Sanguthevar Rajasekaran, Marius Nicolae: An elegant algorithm for the construction of suffix arrays. In: Journal of Discrete Algorithms. Band 27. Amsterdam 2014, S. 21–28, doi:10.1016/j.jda.2014.03.001.</ref> <ref name="rasool">Akhtar Rasool et al.: String Matching Methodologies: A Comparative Analysis. In: International Journal of Computer Science and Information Technologies. Jg. 3, Nr. 2, 2012, S. 3394–3397 (ijcsit.com [PDF]).</ref> <ref name="retha">Ahmad Retha: Practical algorithms for biological sequence analysis: methods and applications. King’s College London, 2019, abgerufen am 18. Februar 2026.</ref> <ref name="rivest">Ronald L. Rivest: On the Worst-Case Behavior of String-Searching Algorithms. In: SIAM Journal on Computing. Jg. 6, Nr. 4. Philadelphia 1977, S. 669–674, doi:10.1137/0206048.</ref> <ref name="rosetta">Aho-Corasick algorithm. Rosetta Code, 6. Februar 2026, abgerufen am 18. Februar 2026.</ref> <ref name="sahni">Sartaj Sahni: Data structures, algorithms, and applications in Java. 2. Auflage. Silicon Press, Summit 2005, ISBN 0-929306-33-3.</ref> <ref name="sedgewick">Robert Sedgewick: Algorithms in C. Addison-Wesley, Reading 1990, ISBN 0-201-51425-7.</ref> <ref name="sharma">Priya Sharma: Boyer-Moore String Algorithm: How It Works with Examples. ACTE, 22. April 2025, abgerufen am 17. Februar 2026.</ref> <ref name="simanjuntak">Ruth Rani Simanjuntak et al.: Application of the KARP RABIN Algorithm for Plagiarism Detection System in Thesis Proposal Submission in the Department of Informatics Engineering STMIK Kaputama. In: Journal of Artificial Intelligence and Engineering Applications. Band 4, Nr. 1, 2024, S. 396–403, doi:10.59934/jaiea.v4i1.644.</ref> <ref name="smith">Temple F. Smith, Michael S. Waterman: Identification of common molecular subsequences. In: Journal of Molecular Biology. Band 147. Amsterdam 1981, S. 195–197, doi:10.1016/0022-2836(81)90087-5.</ref> <ref name="sunday">Daniel M. Sunday: A very fast substring search algorithm. In: Communications of the ACM. Jg. 33, Nr. 8. New York 1990, S. 132–142, doi:10.1145/79173.79184.</ref> <ref name="ukkonen">Esko Ukkonen: On-line construction of suffix trees. In: Algorithmica. Band 14. New York 1995, S. 249–260, doi:10.1007/BF01206331.</ref> <ref name="vashchegin">Roman Vashchegin: Conquer String Search with the Aho-Corasick Algorithm. Toptal, 25. Oktober 2023, abgerufen am 18. Februar 2026.</ref> <ref name="wagenknecht">Christian Wagenknecht, Michael Hielscher: Formale Sprachen, abstrakte Automaten und Compiler: Lehr- und Arbeitsbuch für Grundstudium und Fortbildung. 1. Auflage. Vieweg+Teubner, Wiesbaden 2009, ISBN 978-3-8348-0624-6.</ref> <ref name="wibowo">Fahrudin Mukti Wibowo et al.: Lightweight String Similarity Approaches for Duplicate Detection in Academic Titles. In: Journal of Informatics and Web Engineering. Band 4, Nr. 3, 2025, S. 416–426, doi:10.33093/jiwe.2025.4.3.25.</ref> <ref name="wu">Sun Wu, Udi Manber: A Fast Algorithm for Multi-Pattern Searching. Tucson 1994 (arizona.edu [PDF]).</ref> </references>