Ähnliche Zeichenfolgen

  Um Tippfehler als solche zu erkennen, werden in ZACK Trigramme verwendet. Trigramme sind Zeichenfolgen der Länge 3. Die Zeichenfolgen werden am Anfang und am Ende mit dem Zeichen ``_'' aufgefüllt, um bessere Ergebnisse bei kurzen Wörtern zu erhalten. Bei der Ähnlichkeitssuche über Trigramme werden zunächst die Wörter auf die Menge der enthaltenen Trigramme abgebildet, also z.B. für das Wort ``martha'' und ``marta'':

$$\Rightarrow$$ ``martha''

$$\Rightarrow$$ ``marta''

Wort _ma mar art rth tha ha_ rta ta_

martha 1 1 1 1 1 1

marta 1 1 1 1 1

Abbildung: Trigramme für martha und marta

Danach vergleicht man die zu beiden Wörtern gehörenden Trigramme jeweils miteinander und bildet die Differenz . In diesem Beispiel gibt es insgesamt 8 verschiedene Trigramme. 3 Trigramme sind in beiden Wörtern vorhanden, 5 Trigramme gibt es in nur jeweils einem Wort. Das Löschen des Buchstabens ``h'' hat bewirkt, daß im neuen Wort marta 3 Trigramme fehlen und 2 hinzugekommen sind.

In ZACK werden bei kurzen Zeichenfolgen (Länge < 8 Zeichen) ein Tippfehler und bei längeren Zeichenfolgen (Länge >= 8 Zeichen) zwei Tippfehler toleriert.

Trigramme sind eine effiziente und wirkungsvolle Methode zur Ähnlichkeitssuche auf Zeichenfolgen. Für weitere Informationen zu Trigrammen wird auf die Literatur in [ZPZ81], [Goy84] und [Hyl96]) verwiesen.