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, Übergängen 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 bezglich 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örterbcher nicht praktikabel. Im Allgemeinen ist dieser Ansatz
nur für bis zu 2 Korrekturen maximal sinnvoll. Die größte 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
Üereinstimmung aufweist. Es gibt jedoch (nach bisherigem Wissen)
keine im Handel erhältliche 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örterbücher ab.
Der größte Nachteil der neuralen Netze ist die fehlende Ergebnistransparenz.
Die Ergebnisse und ihre Plausibilität hängen unmittelbar von
den zufälligen Faktoren während des Lernenprozesses ab. Im Allgmeinen
ist dieser Ansatz für approximative Hochleistungssuchanwendungen
aufgrund mangelnder 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 unerwnschte 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än der Wörterbucheinträ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.
|