In der Textverarbeitung, besonders in der Texterkennung, stellen falsch geschriebene Worte ein großes Problem dar. Selbst eine falsche Groß- und Kleinschreibung ist schon ein Hindernis, da sich die ASCII-Codes von Groß- und Kleinbuchstaben unterscheiden. Dieses Problem kann man noch recht leicht mit den Standart-C Funktionen toupper oder tolower3 in den Griff bekommen. Bei den anderen Fehlern ist das schon schwieriger.
Man kann die Fehler allgemein in zwei Gruppen einteilen: zum einen hat man die Rechtschreibfehler, die entstehen, wenn der Schreiber nicht weiß, wie ein Wort geschrieben wird, und zum anderen gibt es die Tippfehler, bei denen der Schreiber versehentlich eine oder mehrere falsche Tasten drückt. Die Tippfehler kann man noch weiter unterteilen. Es können zuviele Buchstaben vorhanden sein. Dies entsteht beim Abrutschen von einer Taste auf eine andere oder wenn zwei Tasten gleichzeitig gedrückt werden. Weiterhin gibt es fehlende Buchstaben, die entstehen, wenn eine Taste nicht fest genug gedrückt wurde. Und letztlich sind da noch die Buchstabenvertauschungen. Es gibt die sogenannten Buchstabendreher, bei denen zwei aufeinanderfolgende Buchstaben in der verkehrten Reihenfolge getippt werden, und die Ersetzung, bei der ein Buchstabe durch einen anderen ersetzt wurde.
Um ein fehlertolerantes Suchen oder Vergleichen zu ermöglichen, muß der Unterschied zwischen den zu vergleichenden Worten durch geeignete Konvertierungen entfernt werden (sprachorientierte Verfahren), so daß auf Identität getestet werden kann, oder es muß ein Fehlerabstand definiert werden (buchstabenorientierte Verfahren), der nach dem Vergleich ausgewertet werden kann (Schwellwerttest, evtl. abhängig von der Wortlänge).
Mit einem sprachorientierten Verfahren kann man sehr leicht Probleme, die durch Rechtschreibfehler entstehen, unterdrücken. Dies liegt an der grundlegenden Idee dieser Verfahren:
Beide zu vergleichende Worte werden so konvertiert, daß gleich klingende Laute auf dasselbe Zeichen oder Token abgebildet werden. Dadurch werden sich die zu vergleichenden Worte ähnlicher oder gar gleich.
Das Soundex Verfahren [KNUTH73] wurde von Margaret K. Odell und Robert C. Russell entwickelt und patentiert (U.S. Patents 1261167 (1918), 1435663 (1922)). Es wird hauptsächlich zum auffinden von Namen benutzt.
Konvertierungsalgorithmus:
|
=> 1 |
|
=> 2 |
|
=> 3 |
|
=> 4 |
|
=> 5 |
|
=> 6 |
Beispiele:
Hilberg => H416,
Bassenge => B252,
Friedrich => F636
Vorteile:
Nachteile:
Die phonetische Codierung [MEYER88] ist dem Soundex recht ähnlich. Es werden aber keine Zeichen entfernt und die Ersetzungen sind etwas umfangreicher. Die Buchstaben (-kombinationen) werden nicht durch Token, sondern durch ähnlich klingende Buchstaben (-kombinationen) ersetzt.
Algorithmus:
| Zeichenfolge | Ersetzung | Zeichenfolge | Ersetzung |
|---|---|---|---|
| SC | C | QU | KV |
| SZ | C | UE | Y |
| CZ | C | EU | OY |
| TZ | C | AE | E |
| TS | C | OE | Ö |
| DS | C | KS | X |
| PH | V | EI | AY |
| PF | V | EY | AY |
| Zeichenfolge | Ersetzung | Zeichenfolge | Ersetzung |
|---|---|---|---|
| K | C | W | V |
| G | C | F | V |
| Q | C | T | D |
| Ü | Y | ß | S |
| I | Y | P | B |
| J | Y |
Beispiele:
Hilberg => HYLBERC, Bassenge => BASENCE, Friedrich => FRYEDRYCH
Vorteile:
Nachteile:
Die buchstabenorientierten Verfahren definieren, wie ein Fehlerabstand zwischen zwei zu vergleichenden Worten bestimmt werden kann.
Die gewichtete Levenshtein-Distanz [EBNER89] geht auf den Finnen Teuvo Kohonen zurück, der die WLD bei seiner Arbeit mit einem Spracherkennungssystem benutzte. Ihr liegt die Annahme zu Grunde, daß sich sich unterscheidende Worte durch Einfügen, Löschen und Ersetzen mehrerer Zeichen ineinander überführen lassen. Wird nun jede Operation mit einem Gewicht bzw. einer Strafe (Penalty) versehen und diese während der Überführung kumuliert, so kann nach der Überführung die Levenshtein-Distanz der beiden Worte ausgewertet werden. Da es beliebig viele Möglichkeiten gibt, ein Wort in ein anderes zu überführen, ist nur die kleinste WLD von Interesse.
Formal gilt:
WLD (X, Y) = mini (pki + qmi + rni)
Es wird das Minimum von i verschiedenen Überführungen des Wortes X in das Wort Y berechnet, wobei p, q und r die Gewichte der jeweiligen Ersetzungen ki, Einfügungen mi und Löschungen ni sind.
Ein einfacher Algorithmus läßt sich leicht rekursiv wie folgt beschreiben:
WLD (Xi, Yj) = min (WLD (Xi-1, Yj-1) + p (i, j), WLD (Xi, Yj-1) + q, WLD (Xi-1, Yj) + r)
Xi (Yj) steht für die ersten i (j) Buchstaben des Wortes X (Y), die Funktion p (i, j) ist Null, wenn der i-te Buchstabe von X gleich dem j-ten Buchstaben von Y ist.
Die Randbedingungen für die Rekursion sind:
WLD (X0, Yj) = jq, WLD (Xi, Y0) = ir und WLD (X0, Y0) = 0
Vorteile:
Nachteile:
Diese Penalty-Methode ist stark an die WLD angelehnt, mit dem Unterschied, daß hier nicht nur bestimmte Strafen (Penalties) für die möglichen Fehlerarten benutzt werden. Bei Ersetzungen von Buchstaben sind die Strafen von den Buchstaben selbst abhängig. Pro Buchstabenpaar kann eine andere Strafe festgesetzt werden. Die Strafen werden hierfür in einem Array der Größe 60×60 gespeichert. Vor dem eigentlichen Vergleich werden die Worte gefiltert, d. h. sie werden in Großbuchstaben gewandelt und bestimmte Zeichen und Zeichenfolgen werden in Token gespeichert. Außerdem erkennt dieser Algorithmus Buchstabendreher und verwendet für sie eine eigene Fehlergewichtung.
Vorteile:
Nachteile:
Der Shift-AND-Algorithmus [GRONEK95] ist eigentlich ein gegenüber Einfügen, Löschen und Ersetzen von Buchstaben tolerantes Suchverfahren, welches aber auch zur Rechtschreibkorrektur verwendet wird. Es kann auch mit Wildcards wie "*" und "?" umgehen. Die Theorie dieses Verfahrens ist etwas komplizierter, als die anderen hier genannten.
In dem Text t, der die Zeichen t1 bis tn enthält, wird nicht nur nach einem Muster p, das die Zeichen p1 bis pm enthält, selbst gesucht, sondern parallel dazu auch nach allen Teilmustern. Ist das Suchmuster aabac, so sind die Teilmuster: a, aa, aab, aaba und aabac. In einem Bit-Vektor S, der soviele Bits enthält, wie Zeichen im Muster p enthalten sind, wird der Suchzustand gespeichert. Sj [i] ist das i-te Bit im Bit-Vektor S zu dem Zeitpunkt j bzw. bei dem Buchstaben tj im durchsuchten Text. Sind die ersten i Zeichen des Musters im Text aufgetreten, so ist das i-te Bit in dem Vektor S gesetzt S [i] = 1. Diese 1 wandert nun durch den Vektor, solange das jeweilige Teilmuster mit dem Text übereinstimmt. Dabei können neue 1-sen entstehen, wenn ein neuer Teilmusteranfang im Text erscheint. Eine Suche ist erfolgreich beendet, wenn S [m] = 1 ist, das heißt, daß das letzte Zeichen des Teilmusters pm gleich dem des Suchmusters tj an der aktuellen Stelle j ist (pm = tj).
Beispiel ("·" steht für "0"):
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | Ta | Tb | Tc | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Text t: | a | a | b | a | a | c | a | a | b | a | c | (TZeichen s. u.) | ||||||
| i | p | Sj=4 | ||||||||||||||||
| S | 1 | a | 1 | 1 | · | 1 | 1 | · | 1 | 1 | · | 1 | · | 1 | · | · | ||
| 2 | a | · | 1 | · | · | 1 | · | · | 1 | · | · | · | 1 | · | · | |||
| 3 | b | · | · | 1 | · | · | · | · | · | 1 | · | · | · | 1 | · | |||
| 4 | a | · | · | · | 1 | · | · | · | · | · | 1 | · | 1 | · | · | |||
| 5 | c | · | · | · | · | · | · | · | · | · | · | 1 | · | · | 1 | |||
| S1 | 1 | a | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||
| 2 | a | · | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||
| 3 | b | · | · | 1 | · | · | 1 | · | · | 1 | · | · | ||||||
| 4 | a | · | · | · | 1 | · | · | 1 | · | · | 1 | · | ||||||
| 5 | c | · | · | · | · | 1 | · | · | · | · | · | 1 | ||||||
An der Textstelle tj=4 ist an Stellen i=1 und i=4 eine 1 im Bit-Vektor Sj=4 (Spalten-Vektor), d. h. an dieser Stelle stimmt das Teilmuster a und aaba mit dem Text überein.
Damit im folgenden Schritt die nächste Stelle im Vektor S bei dem nächsten Buchstaben im Text tj+1 gesetzt wird (Sj [i] = 1 =>; Sj+1 [i+1] = 1), müssen folgende zwei Bedingungen gelten:
Diese Berechnung läßt sich schnell durchführen, wenn für jedes Zeichen, das in dem Suchmuster p enthalten ist, ein charakteristischer Bit-Vektor TZeichen angelegt wird, in dem mit einer 1 markiert ist, an welcher Stelle im Suchwort dieses Zeichen vorkommt (s. Bsp. Ta, Tb, Tc). Es wird jetzt einfach der Inhalt des alten Bit-Vektors Sj um eins nach rechts geschoben (RSHIFT, zieht eine 1 nach!). Dadurch steht eine 1 an der Stelle i+1, falls das Suchmuster bis zur Stelle j richtig war und an der Stelle 1. Anschließend wird mit dem charakteristischen Bit-Vektor TZeichen des neuen Zeichens tj+1 und dem Vektor Sj+1 eine bitweise UND-Verknüpfung durchgeführt, dadurch wird sichergestellt, daß die 1 nach dem Rechts-SHIFT nur dann stehen bleibt, wenn auch der neue Buchstabe bei dem entsprechenden Teilmuster richtig ist:
Sj+1 = RSHIFT (Sj) AND Tt(j+1)
Die Konstruktionsvorschrift für den Vektor Tz eines Zeichens z lautet:
Tz [i] = 1, wenn pi = z, sonst Tz [i] = 0
Für obiges Beispiel bedeutet das, daß bei j=5 (tj=a) ein neues Teilmuster a beginnt (Sj=5 [1] = 1) und ein passender Buchstabe a für das Teilmuster a aus dem vorangegangenen Schritt gefunden wurde. Somit ist das Teilmuster aa erkannt worden (Sj=5 [2] = 1). Das Teilmuster aabac hingegen konnte nicht erkannt werden, da der neue Buchstabe kein c ist. Das 5. Bit in Sj, das durch das schieben nach rechts entstanden ist, wird durch die bitweise UND-Verknüpfung mit dem Vektor Ta gelöscht (Sj=5 [5] = 0), da Ta [5] = 0 ist (nur Tc hat an der 5. Stelle eine 1).
Um den Shift-AND-Algorithmus für fehlertolerantes Suchen und Vergleichen einsetzen zu können, werden einfach weitere Zustands-Vektoren Sd eingeführt. Bei einer Suche mit einem Fehler heißt der Vektor S1 (s. Bsp.). Sie war erfolgreich, wenn S [m] = 1 (0 Fehler) oder S1 [m] = 1 (1 Fehler) gilt. Bei dem Beispiel wäre das bei j = 5 und j = 11 der Fall.
Die Iterationsvorschrift für den Vektor S1 ist etwas komplizierter:
| Übereinstimmung der ersten i Musterzeichen bis zur | |||
| Textstelle j+1 mit einer | Einfügung | Löschung | Ersetzung |
| wenn entweder die ersten | i Zeichen | i-1 Zeichen | i-1 Zeichen |
| bis zur | Stelle j | Stelle j+1 | Stelle j |
| exakt passen | (pi wird angefügt), | (pi wird gelöscht), | (pi wird ersetzt), |
| das heißt | Sj [i] = 1 | Sj+1 [i-1] = 1 | Sj [i-1] = 1 |
| oder wenn schon die | ersten i-1 | ersten i-1 | ersten i-1 |
| Zeichen bis zur Stelle j mit einer | Einfügung | Löschung | Ersetzung |
| passen und tj+1 = pi ist, das heißt | S1j [i-1] = 1 & pi = tj+1 | S1j [i-1] = 1 & pi = tj+1 | S1j [i-1] = 1 & pi = tj+1 |
| also insgesamt: | |||
| S1j+1 = (Tt(j+1) AND RSHIFT (S1j)) | OR Sj | OR RSHIFT (Sj+1) | OR RSHIFT (Sj) |
Sind alle drei Fehlertypen erlaubt so müssen die Ergebnisse der letzten Zeile nur
OR-verknüpft werden:
| S1j+1 | = (RSHIFT (S1j) AND Tt(j+1)) OR Sj OR RSHIFT (Sj+1) OR RSHIFT (Sj) |
| = (RSHIFT (S1j) AND Tt(j+1)) OR Sj OR RSHIFT (Sj+1 OR Sj) |
Möchte man d Fehler zulassen, so muß nur die Iterationsvorschrift in einer Schleife von k = 1 bis d durchlaufen werden und alle S durch Sk-1 und S1 durch Sd ersetzt werden.
Ein wesentliches Merkmal des Shift-AND-Algorithmus ist seine Flexibilität. Ohne Änderung am Algorithmus kann auch mit Wildcards verglichen und gesucht werden. Dafür muß nur ein spezieller T-Vektor definiert werden (s. [WU92]).
Vorteile:
Nachteile:
Um sowohl Rechtschreib- als auch Tipfehler in den Griff zu bekommen, ist es sinnvoll ein sprachorientiertes Verfahren mit einem buchstabenorientierten zu kombinieren. Mit einem sprachorientierten Verfahren ist es nicht möglich ein Maß für den Unterschied zwischen zwei Worten zu definieren, da die Worte einfach transformiert werden und danach auf Identität geprüft werden. Mit einem buchstabenorientierten Verfahren kann zwar ein Abstandsmaß definiert werden, dafür gehen sie aber nicht auf die sprachlichen Ähnlichkeiten ein. Bei den sprachorientierten Verfahren ist die phonetische Codierung dem Soundex vorzuziehen, da der Soundex nur eine begrenzte Stellenanzahl berücksichtigt, auf die englische Sprache ausgelegt ist und zu stark generalisiert. Bei den buchstabenorientierten Verfahren bietet die Penalty-Methode die größte Flexibilität. Sie kennt zum einen Buchstabendreher als eine eigene Fehlerart, die beim Schreiben mit einer Tastatur häufig vorkommt, zum anderen bietet sie die Möglichkeit bei Ersetzungen für jedes Buchstabenpaar einen speziellen Fehlerwert zu bestimmen. Dies ist weder mit der WLD noch mit dem Shift-AND-Algorithmus möglich. Der Shift-AND-Algorithmus unterscheidet noch nicht einmal zwischen den Fehlerarten. Er bietet sich nur zur Volltextsuche in einer Text-Datenbank an.
Aus diesen Gründen wurde in dieser Arbeit bei fehlertoleranten Vergleichen die phonetische Codierung (mit einer erweiterten Ersetzungstabelle) in Verbindung mit dem Penalty-Verfahren verwendet.