Damerau-Levenstein-MaßDas Damerau-Levenstein-Maß ist ein Ähnlichkeitsmaß, welches sozusagen die Tippfehler im Suchbegriff gegenüber den vorhandenen Begriffen in der Datenbank zählt. Es berechnet die minimale Anzahl von Operationen, um den String s in den String t zu überführen.Die erlaubten Operationen dabei sind Einfügen, Löschen, Ersetzen von einem Zeichen oder Vertauschen zweier benachbarter Zeichen. Das Damerau-Levenstein-Maß(s,t)=f(n,m)n=Länge von s, m=Länge von tf(0,0):=0f(i,j):=min { f(i-1,j)+1, f(i,j-1)+1, f(i-1,j-1)+d(s(i),t(i)), f(i-2,j-2)+d(s(i-1),t(j)) +d(s(i),t(j-1))+1 }d(z1,z2)=0, falls z1=z2d(z1,z2)=1, sonstDas Abstandsmaß zwischen zwei Zeichen d(z1,z2) kann anders aussehen. Bespielsweise könnte man ein Maß d(z1,z2) konstruieren, welches den Abstand der Zeichen z1 und z2 auf der Tastatur beschreibt.Der Aufwand zur Berechnung von f(n,m) kann aufgrund der Rekursion sehr hoch sein. In [PFEIFER95] wurde die Suche durch einen Scan über die gesamte Datenbank realisiert. Für reale Anwendungen ist das Damerau-Levenstein-Maß in der Form deshalb nicht anwendbar.Durch Verwendung von Clusteralgorithmen oder durch Kombination des Damerau-Levenstein-Maßes mit anderen Ähnlichkeitsmaßen wird es trotzdem anwendbar. Zum Beispiel könnte das Damerau-Levenstein-Maß zur Nachverarbeitung der Suchergebnisse, die mit dem Soundex-Algorithmus erzeugt wurden, verwendet werden.