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 t
f(0,0):=0
f(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=z2
d(z1,z2)=1, sonst
Das 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-