Fehlertolerante Suche

Klassische Ansätze für fehlertolerante Suchtechnologien

Eine kurze Beschreibung der bekanntesten "klassischen" Ansätze für fehlertolerante Suche

Deterministischer endlicher Automat (DFA oder Transducer)

DFAs, die auf den regulären Sprachen basieren, werden vorallem in den Compilern und Interpretern verwendet, um schnell prüfen zu können, ob ein Wort Teil einer definierten Wortmenge ist. Bei der Abfrage einer Automatenstruktur folgt man, vom Startzustand ausgehend, über zu anderen Zuständen, die zu den Buchstaben im Abfragewort passen.

Diese Art der Suche ist normalerweise extrem schnell und unabhängig von der Wörterbuchgröße. Fehlertoleranz kann jedoch nur genutzt werden, indem man entweder alle erwarteten Varianten der Zeichenkette betrachtet oder genau diese Varianten einem Wörterbuch hinzufügt. Das reduziert den Ansatz bezüglich der approximativen Suche auf ein trial-and-error-Verfahren, das für eine effiziente Realisierung von approximativen Suchtechnologien zu begrenzt ist. Im ersten Fall wächst z.B die Zeit, um das Wort in der Wortmenge zu finden, exponentiell mit der Zahl erlaubter Fehler an. Der andere Fall ist aufgrund des hohen Speicherbedarfs für die großen Wöterbücher nicht praktikabel. Im Allgemeinen ist dieser Ansatz nur für bis zu 2 Korrekturen maximal sinnvoll. Die gröste Schwierigkeit bei der Realisierung dieses Ansatzes stellt der Ressourcen-Verbrauch dar, der in Abhängigkeit zur erlaubten Anzahl der Fehler (Grad der Fehlertoleranz) exponentiell ansteigt.

Hash-Tables

Es gibt mittlerweile ein reiches Angebot an Implementierungen von Hash-Tables. Alle haben den Vorteil, dass das Verfahren extrem schnell (konstant schnell!) ist, aber leider den Nachteil, dass Fehlertoleranz keinerlei Beachtung findet.

Fehlertoleranz bei Hash-Tables wird normalerweise dadurch erreicht, dass man die Hash-Table dupliziert und über das sogenannten "front-hash"-"back-hash"-Verfahren auf sie zugreift. Man nimmt dabei an, dass ein Fehler nur in der Hälfte eines Wortes vorkommt. Der Speicherbedarf ist dabei relativ klein.
Es gibt auch Implementierungen, die ein spezielles Hash enthalten, mit der Zeit gespart werden kann, sobald ein Wort eine ausreichende Übereinstimmung aufweist. Es gibt jedoch (nach bisherigem Wissen) keine im Handel erhätliche Lösung für approximative Suche, die auf dieser Technologie basiert.

Assoziativer Speicher (Neuronale Netze)

Dieser Lösungsansatz beruht im Wesentlichen auf der Lernfähigkeit des Systems. Der Speicherbedarf dabei ist jedoch signifikant, da eine große Menge erlernter Kopplungskonstanten (Assoziationen) gespeichert werden muss. Die Ausführungszeit hängt zwar nicht von der Anzahl der erlaubten Fehler (Grad der Fehlertoleranz), jedoch von der Größe der verwendeten Wöterbücher ab.

Der größte Nachteil der neuralen Netze ist die fehlende Ergebnistransparenz. Die Ergebnisse und ihre Plausibilität hängen unmittlerbar von den zufälligen Faktoren während des Lernenprozesses ab. Im Allgmeinen ist dieser Ansatz für approximative Hochleistungssuchanwendungen aufgrund mangelder Performanz ungenügend.

Andere Ansätze im Bereich der assoziativen Speicher versuchen einen neutrale Menge an "Eigenschaften" zu definieren (wie Bigramme), um die Ergebnistransparenz zu erhöhen. Jedoch sind diese Eigenschaften häufig nicht sehr aussagekräftig und produzieren eine Menge "cross-talk", also unerwünschte Suchtreffer in den Ergebnislisten.

Bipartites Matching

Ein völlig anderer Ansatz stellt das Bipartite Matching dar. Hier wird eine Kostenfunktion für das Ersetzen von Buchstaben in einem String verwendet.

Die Idee ist, eine Zeichenkette durch Ersetzen ihrere Buchstaben schrittweise an eine Referenz-Zeichenkette anzugleichen und die dafür notwendigen "Kosten", die durch das Ersetzen der Buchstaben entstehen (replacement costs), möglichst gering zu halten.

Leider muss bei dieser Technologie die Suchanfrage zuerst kompiliert werden, bevor sie auf der Datenbasis anwandt werden kann. Aufgrund des Kompilierungsaufwands wird dieser Ansatz für Anwendungen unattraktiv, die eine hohe Aktualisierungsrate haben. Die dabei erreichte durchschnittliche Leistungsfähigkeit ähnelt Grep oder anderen Scannern. Auch die Ergebnisse sind bezüglich ihrer Plausibilität ähnlich, auch wenn es keine klaren Kriterien gibt, um die Ergebnisqualität abschätzen zu können. Entwickler von Lösungen, die auf dieser Technologie basieren, räumen ein, dass das Anwenden dieses Ansatzes zwar deutlich zu bevorzugen ist, sie aber keinen effizienten Weg finden, den Algorithmus, der die sogenannte Edit-Distanz berechnet, performant zu programmieren.
> Implementierungen des Levenshtein Algorithmus

Longest-Common-Subsequence (LCS)

Dieses gilt als eine vereinfachte Variante des Levenshtein-Algorithmuses. Dieser Ansatz findet in der Diskussion um approximative Suchtechnologien Bedeutung, da hier direkt zusammenliegende Buchstaben-Sequenzen die gleiche Bedeutung zugewiesen bekommenen, wie Buschstaben-Sequenzen, die innerhalb des Wortes verteilt sind. In Fällen, in denen ein direktes Verhältnis zwischen der Länge der Suchanfrage und der Länge der Wöterbucheinträge nicht gegeben werden kann, ist es ein geeigneter Algorithmus für approximative Suchanfragen. Aber genauso wie beim Bipartiten Matching, gelang bisher nur der Firma Exorbyte eine performante Implementierung.

GlobStyle, Reguläre Ausdrücke

Die wohl bekannteste Methode für unpräzise Suchanfragen ist das Verwenden von Regulären Ausdrücken oder des GlobStyle-Abgleichs. Reguläre Ausdrücke (egrep) sind in ihrer Anwendung eher etwas unhandlich. Wenn die Ausdrücke nicht exakt definiert werden, können eigentlich auch korrekte Einträge nicht erkannt werden.

Verlässliche Ergebnisse und ihre Transparenz können dabei nicht garantiert werden. Desweiteren ist die Performanz von Suchanfragen auf grossen Datenmengen so unbefriedigend, dass ein Einsatz des Verfahrens für kommerzielle Suchlösungen nicht von Bedeutung ist.