Sprachunterricht: Verfahren zur fehlertoleranten Worterkennung

Auch einem Computer, der im Prinzip nur mit Wahr- und Falsch-Werten arbeitet, lassen sich ohne weiteres typischmenschliche Aussagen wie »ziemlich ähnlich« entlocken, wenn es darum geht, zwei Wörter miteinander zu vergleichen.

Der Erfolg der Computer beruht zu einem großen Teil auf dessen Genauigkeit bei Rechenoperationen. Leider wird diese Fähigkeit dem Benutzer oft genug zum Verhängnis. Bei der Eingabe eines Befehls begnügt die Maschine sich nicht mit dem ungefähren Wortlaut des Kommandos, sondern erwartet eine absolut korrekte »Rechtschreibung«.

Bedingt durch die Binärlogik, kennt der Computer Aussagen wie »ein bißchen falsch« aber »noch ziemlich richtig« nicht. Deshalb ist die Eingabe von »auflisten« genauso falsch für den Rechner wie »mach was du willst«, wenn er eigentlich »list« erwartet. Dies ist auch der Grund für die große Beliebtheit der grafischen Oberflächen. Hier sieht der Anwender auf einen Blick, welche Befehle - repräsentiert durch einen Button oder Menüeintrag - im Moment erlaubt sind. Doch auch in Programmen mit grafischer Oberfläche stellen sich Probleme obiger Art: Wenn zum Beispiel ein Begriff in einem Text zu suchen ist, dessen genauer Wortlaut aber in den dunklen Tiefen des Unterbewußtseins verloren ging. Hieß es noch »Demonstration« oder »Demo-Beispiel«?

Für solche Fälle bieten Textverarbeitungen und Editoren sogenannte »Wildcards« an, die sich in ein Suchmuster einbinden lassen. Mit dem Suchmuster »Demo*« findet man sicher alle Textstellen die mit »Demo« beginnen, allerdings bleibt einem nicht die Arbeit erspart, jede der vielleicht hundert passenden Stellen auf die richtige hin zu überprüfen. Dabei war man sich eigentlich ziemlich sicher, daß es doch »Demonstration« hieß. Nachdem die 37. Stelle immer noch nicht paßt, kommen dann Zweifel auf, ob »Demo« überhaupt in dem Wort vorkam. Und wehe das Wort hieß »Einführungsdemonstration«, was mit dem eingegebenen Suchmuster unentdeckt bleibt.

Wieso nur kann der Computer nicht zuerst nach irgendwas mit »Demonstration« suchen, und - falls nicht vorhanden - hinterher noch alles mit »Demo« aufstöbern? Das Problem ist also erkannt und eine passende Lösung ist ein ganzes Stück näher gerückt.

Wohlklang

Zum oben gezeigten Fall gesellen sich auch die verschiedenen Schreibweisen für gleich oder ähnlich ausgesprochene Worte. Handelt es sich dabei noch um Fachbegriffe, deren Her- oder Ableitung dem Anwender ohnehin unbekannt sind (heißt es »Kontroller« oder »Controller«?), ist nach Murphys Gesetz erst die letzte Eingabe ein Treffer Eine enorme Erleichterung wäre da eine Schreibweise in Lautschrift. Nur unterscheidet die Lautschrift zwischen mehr als 60 Fällen. Damit tun wir der Person an der Tastatur auch keinen Gefallen.

Da der Ansatzpunkt der Lautschrift aber recht gut ist, erspart man sich Arbeit, indem man ähnlich klingende Laute zusammenfaßt. Wer würde schließlich bei einem »Äsel« schon etwas anderes als einen »Esel« verstehen?

Wenn wir bei diesem letzten Beispiel bleiben, gilt es einen Algorithmus zu entwerfen, der »Äsel« und »Esel« in irgendeine, dafür aber gleiche Form bringt. Um bei der einfachsten Methode zu bleiben, ändert unsere neue Routine alle »Ä«s in »E«s. Zwischen Groß- und Kleinbuchstaben unterscheiden wir ab sofort auch nicht mehr.

Der »Äsel« zeigt gleich ein weiteres Problem auf. Im Zuge der Internationalisierung des Alphabets (oder einfacher ausgedrückt: fehlendem deutschen Tastaturtreiber) würde dieser nämlich »Aesel« heißen. Außerdem soll unsere Funktion mit so häßlichen Eigenheiten der deutschen Sprache, wie die Umwandlung von »ck« zu »k-k« beim Trennen zurechtkommen. Zusammenfassend kristallisieren sich am Ende fünf zu bearbeitende Fälle heraus.

1. Alle Buchstaben in Großbuchstaben wandeln
2. Doppelte Buchstaben zusammenfassen: »Hallo« zu »Halo«
3. Eine Buchstabenkombination zu einem Buchstaben zusammenfassen: »schlucken« zu »schluken«
4. Umlaute ändern:»ändern« in »endern«
5. Bestimmte Buchstaben weglassen: »Hilfe« zu »ilfe« Die letzten drei Schritte lassen sich allerdings nicht exakt definieren, so daß unsere Routine anhand von drei Tabellen überprüft, ob das Ausgangswort diese Buchstaben(-kombinationen) enthält und diese ersetzt.

Die Funktion »GetSound()« auf der TOS-Diskette enthält bereits entsprechende Tabellen, die allerdings nur als Vorschlag zu verstehen sind. Durch weiteres Probieren stellen sich mit Sicherheit noch bessere Resultate ein. Wichtig ist einzig der Zweck: So könnte die Funktion zum Beispiel alle Wörter aus einem Wörterbuch heraussuchen, die ein gleiches Klangbild haben, was beim Schreiben von Reimen nützlich ist.

Soll sie allerdings nur Rechtschreibfehler tolerieren, fallen die drei Übersetzungstabellen entsprechend kleiner aus.

Mit diesem Algorithmus vergleicht man also nicht mehr zwei Worte direkt, zum Beispiel mit »strcmp()«, sondern die reduzierte Form der Wörter. Der Vergleich liefert aber weiterhin nur »Übereinstimmung« oder »nicht Übereinstimmung«.

Gewichtete Levenshtein-Distanz

Schöner wäre jedoch ein Algorithmus, der von zwei Wörtern einen Ähnlichkeitswert berechnet, mit dem Ziel, eine Liste von Wörtern anzulegen, die aufsteigend dem gesuchten Wort immer ähnlicher sind. Ein Verfahren, das dieser Forderung gerecht wird, ist die Berechnung der Levenshtein-Distanz. Ausgehend davon, daß man durch das mehrfache Einfügen, Löschen und Ersetzen von Buchstaben von jedem Ausgangswort zu jedem Zielwort gelangt, läßt sich also eine Ähnlichkeit zweier Worte über die Anzahl der Operationen bei der Umwandlung ausdrücken. Weniger Umwandlungen bedeuten »ähnlichere« Worte. Natürlich würden die beiden Transformationen »Einfügen» und »Löschen« ausreichen, um ein Wort in ein anderes zu wandeln: Schließlich erreicht man auch durch das Löschen und Einfügen das Ersetzen eines Buchstabens. Nur sind dafür zwei Operationen notwendig, die die Distanz zweier Worte unnötig vergrößern. Gerade unter dem Aspekt des Eintippens von Kommandos ist ein Vertippen aber am wahrscheinlichsten, und demnach am wenigsten streng zu ahnden.

Doch nun zum Verfahren selbst. Dazu vergleichen wir einmal «dirigieren» mit «djriikiren»:

   1 2 3 4 5 6 7 8 9 0 1
1. d i r i   g i e r e n
2. d j r i i k i   r e n
       r     i r     d 

mit
i = einfügen r = ersetzen d = löschen

Mit zwei Ersetzungen, einer Einfügung und einer Löschung, wandelt sich »dirigieren« in »djriikiren«. Intuitiv würde man wohl wie oben beschrieben vorgehen. Ob man an Position fünf zuerst ein »i« einfügt und dann »g« durch »k« ersetzt, oder aber das »g« durch »i« ersetzt und dann »k« einfügt, spielt hier keine Rolle: Die Distanz bleibt in beiden Fällen gleich. Versuchen wir nun unsere Vorgehensweise formal zu beschreiben, sieht das etwa so aus:

1. Der erste Buchstabe beider Wörter ist gleich, also den Rest betrachten
2. Der dritte Buchstabe des ersten Wortes entspricht nicht dem zweiten Buchstaben des zweiten Wortes -> nicht löschen.
3. Der zweite Buchstabe des ersten Wortes entspricht nicht dem dritten des zweiten Wortes -> nicht einfügen.
4. Aus 2. und 3. folgt ersetzen.

Diese Methode ist leider zu schön, um wahr zu sein, denn: was passiert beim Vergleich der beiden Worte »Schreiber« und »Kugelschreiber«?

Da die ersten paar Buchstaben nicht übereinstimmen, wäre nach fünf Ersetzungen noch die Distanz von »Kugeliber« mit »Kugelschreiber« zu berechnen. Fazit: Auch wenn an einer Position die Buchstaben der näheren Umgebung vom zu vergleichenden Wort nicht übereinstimmen, kann es trotzdem günstiger sein, den Buchstaben zu löschen oder einzufügen, als ihn zu ersetzen. Im Falle des Einfügens nimmt man natürlich den Buchstaben, der mit dem Zielwort übereinstimmt.

Folglich sind die Mutationen der Worte für alle drei Fälle (Einfügen, Löschen, Ersetzen) weiter zu verfolgen, auch wenn zum momentanen Zeitpunkt ein Fall wenig erfolgversprechend erscheint.

Die Distanz von »basis« zu »siss« ist dann das Minimum der drei Distanzen

dist( »asis«, »siss« ) (für löschen von »b«) dist( »sasis«, »siss« ) (für ersetzen von »b« durch »s«) dist( »sbasis«, »siss« ) (für einfügen von »s«)

Plus 1 für die hier durchgeführte Operation: Wenn die ersten beiden Buchstaben gleich waren, ist das Ersetzen keine Operation, und man darf diese nicht hinzuzählen.

Um nun beim zweiten Schritt wie oben vorzugehen, also wieder jeweils den ersten Buchstaben zu bearbeiten, ändern wir das Ersetzen und Einfügen im Ausgangswort durch das Löschen des ersten Buchstabens beider Worte:

dist( »asis«, »iss« ) (für ersetzen von »b« duch »s«) dist( »basis«, »iss«) (für einfügen von »s«)

Spätestens jetzt ist klar, daß der Algorithmus rekursiv arbeitet, und sich an jeder Position dreimal aufruft, womit das nächste Problem auftaucht. Sind nämlich viele Wörter miteinander zu vergleichen, artet das Ganze auch für den Computer in richtige Arbeit aus. Bekanntlich gehören Rekursionen nur selten zu den schnellen Verfahren, deshalb befindet sich auf der TOS-Diskette eine dynamische Variante des Algorithmus, der in der Funktion «GetGLD()» implementiert ist. Ganz vernachlässigt wurde bisher der Umstand, daß Ersetzungen vom Gefühl her eher zu akzeptieren sind als Einfügungen, und Einfügungen der Transformation wiederum weniger schaden als Auslöschungen.

Daher gewichten wir die drei Operationen verschieden stark. Vorgeschlagen wird ein Verhältnis von 1:2:3 für Ersetzen, Einfügen und Löschen (1:2:3 = r:i:d).

Leider tritt hier schon das nächste Problem auf. Beim Vergleich von »sie« mit »nun« ist die Distanz wesentlich kleiner als beim Vergleich von »geschmacksneutral« mit »geschmack«, obwohl dem zweiten Beispiel eine gewisse Ähnlichkeit nicht abzusprechen ist. Nebenbei wachsen die Distanzen weiter, je größer die Gewichtungen ausfallen. Deshalb berechnet »GetGLD()« unter Berücksichtigung der Wortlängen und Gewichtungen einen Prozentsatz der Gleichheit zweier Wörter. Mit den drei statischen Variablen »del«, »ins« und »rep« stellen Sie die Gewichtungen für das Löschen, Einfügen und Ersetzen ein.

In dem hier vorgestellten Algorithmus lassen sich auch leicht die Wildcards»?« und »« implementieren. Dazu gewichtet man an der Position »?« die Ersetzung und bei »« die Einfügung mit Null.

Kon-Fusion

Da die zwei hier vorgestellten Verfahren noch nicht der Weisheit letzter Schluß sind, lassen sich durch die Kombination beider Algorithmen die besten Ergebnisse erzielen. Also berechnen wir mit »GetGLD()« nicht die Distanz zweier Worte, sondern die Distanz der von »GetSound()« reduzierten Ausdrücke.

Auf der TOS-Diskette finden Sie im Archiv »Levenshtein« eine Beispielanwendung mit Quelltext. Unter Angabe eines Suchwortes listet das Programm alle ähnlich lautenden Wörter einer Textdatei auf.

Literaturhinweise: [1] T. Kohonen, H. Riittinen, E. Reuhkala, S. Haltsonen, »Online recognition of spoken words from a large vocabulary«, Information Sciences 3/1984, S. 3ff [2] T. Okuda, E. Tanaka, T. Kasai, »A Method for the correction of garbled words based on the Levenshtein metric«, IEEE Transactions on Computers C-25-2/1976, S. 172ff

Jürgen Lietzow

---

---