next up previous contents
Next: Interaktive Dublettenkontrolle Up: Maschinelle Dublettenkontrolle in ZACK Previous: Ähnliche Zahlen

Ä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'':


``martha'' $\Rightarrow$ {``_ma'', ``mar'', ``art'', ``rth'', ``tha'', ``ha_''}
``marta'' $\Rightarrow$ {``_ma'', ``mar'', ``art'', ``rta'', ``ta_''}



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.


next up previous contents
Next: Interaktive Dublettenkontrolle Up: Maschinelle Dublettenkontrolle in ZACK Previous: Ähnliche Zahlen

Copyright (c) 1999 Wolfram Schneider , 4-July-1999
URL: https://wolfram.schneider.org/lv/diplom/