String-Indizierungsstrukturen

String-Indizierungsstrukturen bereiten einen Text in eine durchsuchbare Form vor – Tries, Suffixbäume oder Suffix-Arrays –, sodass viele spätere Musteranfragen und Fragen zu Wiederholungen und gemeinsamen Teilstrings schnell beantwortet werden können.

Definition

Eine String-Indizierungsstruktur ist eine Datenstruktur, die aus einem Text (oder einer Menge von Strings) aufgebaut ist und effiziente Abfragen über den Text unterstützt – wie z. B. ob und wo ein Muster vorkommt, der längste wiederholte Teilstring oder der längste gemeinsame Teilstring zweier Texte – typischerweise durch die Darstellung der Präfixe oder Suffixe des Textes.

Scope

Dieses Thema behandelt Datenstrukturen, die Strings für schnelle wiederholte Abfragen indizieren: Tries (Präfixbäume) für Mengen von Strings, Suffixbäume, die alle Suffixe eines Textes für die Mustersuche in linearer Zeit darstellen, Suffix-Arrays als deren speichereffizientes Gegenstück und unterstützende Strukturen wie das Longest-Common-Prefix-Array. Es werden deren Konstruktionsalgorithmen und die von ihnen beschleunigten Abfragen behandelt, wobei die einmalige Mustererkennung, die den Text nicht vorverarbeitet, ausgeschlossen ist.

Core questions

• Wie organisiert ein Trie eine Menge von Strings für die präfixbasierte Suche?
• Wie stellt ein Suffixbaum alle Suffixe dar, sodass Musterabfragen in einer zur Musterlänge proportionalen Zeit erfolgen?
• Wie erreichen Suffix-Arrays eine ähnliche Leistungsfähigkeit mit weniger Speicher?
• Welche Konstruktionsalgorithmen bauen diese Strukturen effizient auf, idealerweise in linearer Zeit?
• Welche Textprobleme (Wiederholungen, gemeinsame Teilstrings) lösen diese Indizes elegant?

Key concepts

• Trie (Präfixbaum)
• Suffixbaum
• Suffix-Array
• Longest-Common-Prefix-Array
• Online-Konstruktion
• längster wiederholter Teilstring
• längster gemeinsamer Teilstring
• Raum-Zeit-Kompromisse

Key theories

Suffixbäume und Konstruktion in linearer Zeit

Ein Suffixbaum stellt jedes Suffix eines Textes kompakt dar, wodurch ein Muster in einer zur Länge proportionalen Zeit gesucht werden kann; Ukkonens Algorithmus konstruiert ihn online in linearer Zeit zur Textlänge.

Suffix-Arrays als speichereffizienter Index

Ein Suffix-Array speichert die sortierte Reihenfolge aller Suffixe in einem einfachen Integer-Array; kombiniert mit einem Longest-Common-Prefix-Array unterstützt es die schnelle Mustersuche mit wesentlich weniger Speicher als ein Suffixbaum.

Clinical relevance

Textindizes sind die Grundlage für die groß angelegte Suche und Bioinformatik: Suffix-Arrays und verwandte komprimierte Indizes bilden die Basis für Genom-Read-Aligner und Volltextsuchmaschinen, Tries unterstützen Autovervollständigung und IP-Routing-Tabellen, und diese Strukturen ermöglichen praktische wiederholte Abfragen über massive Texte, wo ein erneutes Scannen unerschwinglich wäre.

History

Peter Weiner führte 1973 Suffixbäume ein, mit einfacheren Konstruktionen in linearer Zeit von McCreight (1976) und Ukkonen (1995). Manber und Myers führten 1990 Suffix-Arrays als speichereffizientere Alternative ein, und spätere Arbeiten zu komprimierten und FM-Indizes erweiterten diese Ideen auf sehr große Texte und Genome.

Key figures

• Peter Weiner
• Edward McCreight
• Esko Ukkonen
• Udi Manber
• Gene Myers
• Dan Gusfield

Seminal works

• ukkonen1995
• manber1993
• gusfield1997

Frequently asked questions

Wann sollte ich ein Suffix-Array anstelle eines Suffixbaums verwenden?

Suffix-Arrays verbrauchen erheblich weniger Speicher als Suffixbäume und weisen ein gutes Cache-Verhalten auf, was sie für große Texte wie Genome vorzuziehen macht. Suffixbäume legen mehr Struktur direkt offen und können einige Algorithmen konzeptionell vereinfachen, jedoch zu höheren Speicherkosten; Suffix-Arrays plus ein Longest-Common-Prefix-Array stellen den Großteil dieser Leistungsfähigkeit wieder her.

Wofür ist ein Trie gut?

Ein Trie speichert eine Menge von Strings nach gemeinsamen Präfixen, was eine schnelle Präfixsuche, Autovervollständigung und geordnete Traversierung ermöglicht. Er eignet sich gut für Wörterbücher, Autovervollständigungsvorschläge und die längste Präfixübereinstimmung, wie sie im IP-Routing vorkommt, wo Schlüssel gemeinsame Anfänge teilen.