String-Algorithmen
String-Algorithmen verarbeiten Symbolsequenzen – Text, DNA oder andere lineare Daten –, um Muster zu finden, große Texte für die schnelle Suche zu indizieren und Sequenzen nach Ähnlichkeit auszurichten.
Definition
String-Algorithmen sind Prozeduren und Datenstrukturen, die auf Strings – endlichen Sequenzen von Zeichen aus einem Alphabet – operieren, um Probleme wie das Auffinden von Mustern, das Indizieren für schnelles Nachschlagen und das Messen oder Ausrichten der Ähnlichkeit zwischen Sequenzen zu lösen.
Scope
Dieser Bereich umfasst Algorithmen und Datenstrukturen, die auf Strings spezialisiert sind: exakte und approximative Mustererkennung, Indexstrukturen (Tries, Suffixbäume und -arrays), die Text für wiederholte Abfragen vorverarbeiten, und Sequenz-Alignment-Methoden zum Vergleichen von Strings. Er verbindet sich mit dynamischer Programmierung (Alignment), Datenstrukturen (Bäume und Arrays) und Anwendungen in der Computerbiologie, Textretrieval und der Verarbeitung natürlicher Sprache.
Sub-topics
Core questions
- Wie kann ein Muster in einem Text schneller gefunden werden als durch naiven Zeichen-für-Zeichen-Vergleich?
- Wie wird ein großer Text vorverarbeitet, damit viele spätere Abfragen schnell sind?
- Wie wird die Ähnlichkeit zwischen zwei Strings definiert und berechnet?
- Wie beeinflussen Alphabetgröße und Stringlänge die Effizienz von String-Algorithmen?
- Wie lassen sich exakte Übereinstimmungsmethoden auf approximatives oder Mehrfachmuster-Matching erweitern?
Key concepts
- Alphabet und String
- exakte Mustererkennung
- Knuth-Morris-Pratt und Boyer-Moore
- Tries
- Suffixbäume und Suffix-Arrays
- Editierdistanz
- Sequenz-Alignment
- approximatives Matching
Key theories
- Lineare exakte Mustererkennung
- Durch Vorverarbeitung des Musters zur Nutzung von Informationen aus partiellen Übereinstimmungen finden Algorithmen wie Knuth-Morris-Pratt und Boyer-Moore alle Vorkommen eines Musters in linearer Zeit zur Textlänge, wodurch die quadratischen Kosten des naiven Matchings vermieden werden.
- Indexstrukturen für Text
- Suffixbäume und Suffix-Arrays verarbeiten einen Text vor, sodass beliebige Musterabfragen, Wiederholungen und Fragen nach der längsten gemeinsamen Teilzeichenkette schnell beantwortet werden können, wobei die Konstruktionskosten gegen eine schnelle wiederholte Suche abgewogen werden.
Clinical relevance
String-Algorithmen sind grundlegend für die Textsuche und Bioinformatik: Mustererkennung treibt Suchprogramme, Texteditoren und Intrusion Detection an; Suffixstrukturen indizieren Suchmaschinen und Genomdatenbanken; und Sequenz-Alignment ist zentral für den Vergleich von DNA-, RNA- und Proteinsequenzen in der Molekularbiologie.
History
Effiziente String-Matching-Verfahren entstanden in den 1970er Jahren mit den Algorithmen von Knuth-Morris-Pratt (1977) und Boyer-Moore (1977). Suffixbäume (Weiner, 1973; McCreight, 1976; Ukkonen, 1995) und später Suffix-Arrays (Manber und Myers, 1990) ermöglichten eine leistungsstarke Indizierung, und das Feld expandierte schnell durch die Computerbiologie, wie in Gusfields Text von 1997 beschrieben.
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Dan Gusfield
Related topics
Seminal works
- knuth1977
- gusfield1997
- cormen2009
Frequently asked questions
- Warum sollte man das Muster oder den Text vorverarbeiten, anstatt direkt zu suchen?
- Naives Matching kann eine Zeit in Anspruch nehmen, die proportional zum Produkt der Muster- und Textlängen ist. Die Vorverarbeitung des Musters (wie bei Knuth-Morris-Pratt) ermöglicht eine Suche in linearer Zeit, und die Vorverarbeitung des Textes in einen Index (Suffixbaum oder -array) lässt viele spätere Abfragen jeweils wesentlich schneller ablaufen, was sich auszahlt, wenn derselbe Text wiederholt durchsucht wird.
- Wie werden String-Algorithmen in der Biologie eingesetzt?
- DNA, RNA und Proteine werden natürlicherweise als Strings dargestellt, sodass Mustererkennung Motive lokalisiert, Suffixstrukturen Genome für schnelles Nachschlagen indizieren und Sequenz-Alignment-Algorithmen die Ähnlichkeit zwischen Sequenzen quantifizieren, um evolutionäre Beziehungen und Funktionen abzuleiten.