LEA

Stand der Forschung und eigene Vorarbeiten

  1. Stand der Forschung
    1. Lineare Indexstrukturen zur fehlertoleranten Mustersuche
    2. Indexstrukturen mit superlinearem Platzverbrauch
    3. Algorithm Engineering
  2. Eigene Vorarbeiten

Stand der Forschung

Ein Textindex ist eine Datenstruktur, die es ermöglicht, in einem Textdokument oder einer ganzen Sammlung von Dokumenten effizient nach den Vorkommen bestimmter Textabschnitte (Teilwörter oder Muster) zu suchen. Dabei wird, im Gegensatz zu den klassischen Verfahren der Mustersuche (Pattern Matching), der Text vorverarbeitet und indiziert, so dass später gestellte Mustersuchanfragen möglichst schnell beantwortet werden können.

Aufgrund der rapide wachsenden Datenmengen, denen eine bestimmte Form von Text zugrundeliegt (z.B. WWW-Seiten im Internet, molekularbiologische Sequenzdatenbanken) kommt den Verfahren zum schnellen und speicherplatzsparenden Indizieren von Texten eine enorme Bedeutung zu. In der Vergangenheit wurden dabei besonders zwei Datenstrukturen mit Erfolg eingesetzt: zunächst Suffix-Bäume (suffix trees) [Wei73,McC76,Ukk95] und später auch Suffix-Arrays [MM93].

Eine besondere Schwierigkeit in der Praxis des Pattern Matchings stellt die Tatsache dar, dass man meistens nicht nur nach genauen Treffern des Suchmusters in den Dokumenten sucht (exact matching), sondern auch nach ungenauen Treffern, die vom Suchmuster innerhalb eines bestimmten Rahmens abweichen können (approximate matching). Kanonische Beispiele für Anwendungen dieser Form der fehlertoleranten Mustersuche sind alle sequentiellen Daten, deren Erfassung in irgendeiner Form fehlerbehaftet ist, z.B. natürliche Texte, in denen Schreibfehler enthalten sind, oder Folgen von Nukleinsäuren (DNA, RNA), deren Sequenzierung mit einer bestimmten Fehlerwahrscheinlichkeit an jeder Stelle verbunden ist. Es gibt auch weitere Beispiele, in denen nicht die fehlerhafte Datenerfassung im Mittelpunkt steht, bei denen es aber ebenso auf eine gewisse Ähnlichkeit zwischen Suchmuster und zu findenden Treffern ankommt, z.B. bei der Suche nach ähnlichen Proteinsubstrukturen in einer Proteinstrukturdatenbank [TBG06].

Um die erlaubte Abweichung zu quantifizieren, wird dabei meist ein Distanzmaß spezifiziert, das den Abstand (oder umgekehrt die Ähnlichkeit) zwischen zwei Sequenzen in einem Zahlenwert ausdrückt. Die am weitesten verbreiteten Fehlermaße berücksichtigen dabei nur den Austausch von Zeichen (Hamming-Distanz) oder zusätzlich dazu auch Einfügungen (insertions) und Auslassungen (deletions) von Zeichen (Edit- bzw. Levenshtein-Distanz). Man kann den Distanzwert hier als minimale Anzahl notwendiger Operationen ansehen, die nötig sind, um den einen String in den anderen umzuwandeln. Weitere Maße verallgemeinern die beiden Standardmaße durch unterschiedliche Gewichte in Abhängigkeit von der Operation und den beteiligten Zeichen. Andere Maße lassen auch Verschiebungen von Zeichen und/oder die Umkehrung der Zeichenreihenfolge in einem Block (inversion, reversal) zu.

Für den Fall, dass keine Vorverarbeitung der Dokumente vorgenommen werden soll, existiert eine ganze Reihe von Algorithmen für die unterschiedlichen Fehlermaße (siehe [Nav01]). In der letzten Zeit wurden zwar auch einige theoretische Fortschritte auf dem Gebiet der Indizierung für fehlertolerante Suche gemacht [AKL+00,BGW00,CGL04,CO06]. Im Wesentlichen ist dieses Problem jedoch weiterhin ungenügend gelöst.

Im Folgenden betrachten wir fehlertolerante Mustersuche in einem einzigen vorverarbeiteten Text. Die Lösungen und Methoden für diesen Fall lassen sich in der Regel auch auf die entsprechenden Varianten, z.B. fehlertolerante Suche in mehreren Texten oder in einem Wörterbuch, verallgemeinern.

Indexdatenstrukturen für fehlertolerante Suche stellen sowohl theoretisch als auch praktisch eine Herausforderung für Algorithmiker dar. Im einfachsten Fall sucht man in einem Text der Länge n ein Muster der Länge m mit d=O(1) Fehlern. Naive Lösungen generieren entweder alle Wörter, deren Abstand (Hamming, Edit-Distanz) vom Suchmuster höchstens d ist, und suchen diese exakt im Text. Dieser Ansatz hat eine Suchzeit von Ω(md). Im anderen Extrem kann man mögliche Fehler schon bei der Indizierung des Textes berücksichtigen. Ein solcher Index hätte allerdings einen Platzbedarf von Ω(nd), was für praktische Anwendungen viel zu groß ist. Forschungsarbeiten zu Indexstrukturen für fehlertolerante Mustersuche lassen sich grob in zwei Klassen einteilen. Die erste Art der Indizes zielt auf eine möglichst geringe Suchzeit bei Verwendung linearer (in der Textlänge) Indexstrukturen ab. Die zweite Klasse dagegen setzt eine lineare (oder nur schwach superlineare) Zugriffszeit voraus. Die Größe der Indexdatenstruktur kann superlinear sein, soll aber natürlich auch minimiert werden.

Lineare Indexstrukturen zur fehlertoleranten Mustersuche

Lineare Indexstrukturen lassen sich wiederum grob in zwei Klassen einteilen. Indizes der ersten Art benutzen Suffixbäume, Suffixarrays, aber auch DAWGs (gerichtete azyklische Wortgraphen), also Indexstrukturen linearer Größe, die auch zur exakten Mustersuche verwendet werden. Es gibt zahlreiche Arbeiten, die fehlertolerante Mustersuche auf (komprimierten) Tries bzw. Suffixbäumen untersuchen [Ukk93,Cob95,SM96,NBY00,AN07]. Im Wesentlichen basieren alle Ansätze auf einer beschränkten Baumtraversierung, d.h. die Knoten des Baumes werden abgelaufen, z.B. durch Tiefensuche, und die Suche wird abgebrochen, sobald kein Treffer im entsprechenden Unterbaum mehr möglich ist. Die Knoten werden in allen zitierten Arbeiten mittels dynamischer Programmierung bewertet. Zudem werden verschiedene Beschleunigungsmechanismen vorgeschlagen, die jedoch den Worst Case nicht verbessern, d.h. die Suchzeit ist im schlechtesten Fall Ω(n). Chan et al. [CLS+06] beschreiben einen Index der Größe O(n), der ein Muster der Länge m in Zeit O(m+occ+(log n)d(d+1)log log n) mit d Fehlern findet. Der Index unterscheidet lange und kurze Suchwörter. Der praktische Nutzen dieses Ansatzes ist unklar und soll unter anderem in diesem Projekt untersucht werden.

Die zweite Art der Indexstrukturen basiert auf spezialisierten Filteralgorithmen, also Algorithmen, die versuchen möglichst große Teile des Textes, in denen aufgrund bestimmter Bedingungen kein Treffer des Suchmusters vorkommen kann, zu verwerfen. Beispiele finden sich in [JU91,Mye94,JTU96,ST96,NBY98]. Die meisten bekannten Filteralgorithmen zerlegen das Suchmuster in Teilmuster und suchen diese exakt im Text. Es wird dann versucht, die Treffer der Teilmuster zu einem Treffer (mit Fehlern) des Gesamtmusters zusammen zu setzen. Die Vorverarbeitung der Texte dient dem schnellen Auffinden der exakten Treffer der (kurzen) Teilmuster. Hierzu werden sogenannte text q-grams, Teilwörter des Textes der Länge q, sowie deren Position im Text verwendet. Durch Sampling wird nur eine Teilmenge der Teilwörter auf diese Weise indiziert. Die Filtermethoden unterscheiden sich hauptsächlich in der Art und Weise, wie das Sampling des Textes und des Suchmusters durchgeführt wird. Desweiteren gibt es Unterschiede in der Methodik bei der Zusammensetzung der Treffer der Teilmuster. Filterindizes haben in der Regel einen geringeren Speicherbedarf als z.B. Suffixbäume. Allerdings sind die Suchzeiten schlecht, wenn man mit hoher Fehlertoleranz sucht.

Indexstrukturen mit superlinearem Platzverbrauch

Im Vergleich zu den zuvor beschriebenen Methoden wird in den in diesem Abschnitt beschriebenen Arbeiten mehr als linear-viel Speicherplatz verwendet, um damit eine geringere Anfragezeitkomplexität zu erreichen. Amir et al. veröffentlichten in [AKL+00] ein Indexverfahren für Edit-Distanz mit einem Fehler. Der Index verwendet dabei O(n log2n) Speicher und erlaubt Anfragen in Zeit O(m log n log log n + occ). Dies wurde später von Buchsbaum et al. [BGW00] verbessert, die mit einer speziellen Range-Query-Methode die Komplexitäten auf O(n log n) (Platz und Konstruktionszeit) und O(m log log n + occ) (Anfragezeit) verringern konnten.

Chávez und Navarro präsentierten in [NC06] einen Index, der für beliebige konstante Fehlergrößen Anfragen in durchschnittlicher Zeit O(m log2n + m2 + occ) (Average Case) beantworten kann. Der Index hat dabei eine durchschnittliche Größe von O(n log n) und wird durchschnittlich in Zeit O(n log2n) konstruiert. Maaß und Nowak [MN05b] entwickelten einen anderen Index, der für den Fall von einem Fehler (d=1) die gleichen Average-Case-Komplexitäten sogar mit hoher Wahrscheinlichkeit (with high probability, whp) erreicht. Im Fall einer beliebigen (konstanten) Anzahl von Fehlern d hat der Index eine Größe von O(n logd n) und wird in Zeit O(n logd+1n) konstruiert. Dabei sind in einer Variante die Größe des Index und die Konstruktionszeit als Durchschnitt und mit hoher Wahrscheinlichkeit (Average Case, whp) zu verstehen und die Anfragezeit als Worst Case. In einer zweiten Variante ist es genau umgekehrt. Später wurde von Gabriele et al. [GMRS03,EGM05] ein Verfahren vorgestellt, das auf ähnlichen Ideen beruht, jedoch nur für Hamming-Distanz funktioniert.

Cole et al. [CGL04] veröffentlichten einen Index, der ähnliche Größe und Konstruktionszeit O(n logdn) (allerdings im Worst Case) aufweist, dessen Anfragekomplexität O(m + logdn log log n + occ) jedoch auch von der Größe des Textes abhängig ist. Dieser Index ermöglicht auch den Umgang mit Don't-Care-Symbolen (Wildcards).

Algorithm Engineering

Für exakte Mustersuche gibt es Indexstrukturen, die auch unter Gesichtspunkten des Algorithm Engineering untersucht sind. Insbesondere gibt es mehrere neuere Arbeiten, die sich mit Suffixbäumen für sehr große Datenmengen beschäftigen (d.h. im Sekundärspeichermodell). Algorithmen, die die Anzahl der notwendigen Festplattenzugriffe zur Konstruktion von Suffixbäumen minimieren, finden sich in [BH04,FCFM00,HAI02,TTHP05]. Die Suche nach einem Pattern in einem Suffixbaum im Sekundärspeicher wurde zunächst von Clark und Munro untersucht [CM96]. Die Anzahl der notwendigen Festplattenzugriffe ist abhängig von der Höhe des Suffixbaums. Obwohl die Höhe im Average Case logarithmisch in der Länge des zu indizierenden Textes ist [Szp01], kann diese im schlechtesten Fall auch linear sein. Ferragina und Grossi [FG99] führen String-B-Trees ein, um auch theoretisch beweisbare gute Schranken für die Suche nach einem Pattern im Sekundärspeicher, sowie für die Aktualisierung der Datenstruktur zu erhalten. Ko und Aluru [KA06] und Bedathur und Haritsa [BH05] zeigen schließlich, dass auch Suffixbäume mit entsprechender Layoutstrategie als effiziente Sekundärspeicherindexstrukturen für exaktes Pattern Matching nutzbar sind.

Navarro und Baeza-Yates [NBY00] vergleichen in einer experimentellen Studie auf Suffixbäumen basierende Indexmethoden und den Index von Myers [Mye94] als Repräsentanten der Filteralgorithmen. Dabei werden relativ kurze Suchmuster (m=10 und m=20) in englischen Texten und DNA auf verschiedenen Niveaus der Fehlertoleranz gesucht. Zusätzlich wird analysiert, welche Auswirkung die Verwendung von Suffixarrays hat. Die Ergebnisse der Studie implizieren, dass Suffixarrays gegenüber Suffixbäume Vorteile bringen. Einerseits sind die Speicherplatzanforderungen an Arrays geringer, andererseits scheint die bessere Speicherlokalität der Arrays effizientere Cache-Nutzung zu bedingen. Desweiteren belegt die Studie, dass die komplexeren Traversierungsalgorithmen aus [Cob95] keinen praktischen Nutzen bringen. Während der Index von Myers nur einen geringen Speicherplatzbedarf hat, fällt die Sucheffizienz gegenüber den auf Suffixbäumen basierenden Methoden in der Praxis deutlich ab.

Eigene Vorarbeiten

Auf dem Gebiet der Indexstrukturen hat unsere Arbeitsgruppe eine ganze Reihe von Arbeiten vorzuweisen. Maaß entwickelte einen linearen, bidirektionalen Algorithmus zur Online-Konstruktion von Affix-Bäumen [Maa03]. Der selbe Autor analysierte die durchschnittliche Laufzeit verschiedener Verfahren zur fehlertoleranten Suche in Tries [Maa04]. Ein Index für die Suche im Hamming-Distanz-Modell mit genau einem Fehler wurde von Nowak vorgestellt [Now04]. Auf dieser Grundlage entwickelten Maaß und Nowak zunächst einen Index, der auch Suchen mit genau einem Fehler im Edit-Distanz-Modell erlaubt [MN05a]. Später wurde dieses Verfahren auf einen Index für die Suche mit beliebiger konstanter Edit-Distanz verallgemeinert [MN05b,MN07].

Täubig, Buchner und Griebsch entwickelten ein Verfahren, dass die räumliche Struktur von Proteinen in Zeichenketten repräsentiert und mit Hilfe von Suffix-Bäumen eine schnelle Substruktursuche auf der riesigen Proteinstrukturdatenbank (Protein Data Bank, PDB) realisiert [TBG04,TBG06].

Maaß untersuchte die Anwendbarkeit von Suffix-Arrays zur Berechnung sogenannter Matching Statistics und stellte einen praktischen Algorithmus zur Lösung des Multiple Common Substring Problems vor [Maa06].

In einer aktuellen Forschungsarbeit untersuchen Arslan und Nowak [AN07] fehlertolerante Wörterbuchsuche in sogenannten Prefix-Partitioned Look-Up Trees, einer Verallgemeinerung von PATRICIA-Bäumen. Die Effizienz der auf Dynamischer Programmierung basierenden Suchalgorithmen hängt ab von der Höhe und Weite (Verzweigungsgrad) des verwendeten Baumes. Eine -gerade in Hinsicht auf Verwendung der Datenstruktur im Sekundärspeicher- nützliche Eigenschaft der Prefix-Partitioned Look-Up Trees ist, dass ein Trade-Off zwischen Höhe und Weite besteht, d.h. die Höhe des Baumes kann auf Kosten der Weite entsprechend skaliert werden.

Ein aktuelles Forschungsprojekt unserer Arbeitsgruppe beschäftigt sich mit der Smoothed Complexity der Höhe von Tries. Erste Resultate befinden sich in Vorbereitung zur Veröffentlichung [EKN07].