DamerauLevenshteinDistance()

DamerauLevenshteinDistance() – Zur Duplikaterkennung

Die Damerau-Levenshtein-Distanz beschreibt den "Abstand" zwischen zwei Strings. Sie gibt den Wert an, um den ein String von einem anderen abweicht.
Beispielsweise ist die Levenshtein-Distanz zwischen "Tier" zu "Tor" 2. Eine mögliche Folge von Operationen ist:

Tier
Toer (Ersetze i durch o)
Tor (Lösche e)

Die Erweiterung von Damerau ermöglicht es darüber hinaus die Vertauschung von zwei Zeichen zu erkennen:
Teir => Tier wäre nach Levenshtein eine Distanz von 2, nach Damerau von 1.

Parameter	Beschreibung
aString1:C	1. Vergleichsstring
aString2:C	2. Vergleichsstring

Rückgabewert

Numerisch

Beispiel

CODE

//******************************************************************************
// Funktion ermittelt Dubletten nach dem Damerau-Levenshtein-Distanz-Verfahren
// siehe hierzu auch: http://de.wikipedia.org/wiki/Levenshtein-Distanz
//******************************************************************************
function IsDuplicateText(cString1, cString2, nAcceptableDistance, bCharOnly,
                         bIgnoreSurplusWords)
|aArr1, aArr2, aBuf, i, k, nCurrentDistance, nMaxDistance|

   // Konvertiert bestimmte Zeichen in ein anderes (hier Leerzeichen)
   function ConvertIgnoreCharsToDelimiter(cStr, cDelimiter, cIgnoreChars)
   |i, k|
      Result := '',
      for i:= 1 to Len(cStr) do
         Result += iif(SubStr(cStr, i, 1) $ cIgnoreChars, cDelimiter, SubStr(cStr, i, 1)),
      next,
   end,

   // Macht aus einem durch cDelimiter getrennten String ein Array
   function Explode(cStrToExp, cDelimiter)
   |i, cToken|
     Result := {},

     // Sonderfall: Ignorierte Zeichen durch Leerzeichen ersetzen
     if bCharOnly then
        cStrToExp := ConvertIgnoreCharsToDelimiter(cStrToExp, cDelimiter, '<>|^°²³()[]{}!§$%/\=?,.;:-_+*~#@€"' + Chr(39)),
     endif,

     for i:=1 to TokenCount(cStrToExp, cDelimiter) do
        cToken := Token(cStrToExp, cDelimiter, i),
        if Trim(cToken) <> '' then
           AAdd(Result, cToken),
        endif,
     end,
   end,

   aArr1 := Explode(cString1, ' '),
   aArr2 := Explode(cString2, ' '),

   // aArr1 sollte in jedem Fall das längere Array sein
   if ALen(aArr1) < ALen(aArr2) then
      aBuf  := aArr1,
      aArr1 := aArr2,
      aArr2 := aBuf,
   endif,

   // aArr1 passende Werte von aArr2 zuordnen
   aBuf := {},
   for i:=1 to ALen(aArr1) do
      if Len(aArr1[i]) > nAcceptableDistance then
         for k:=ALen(aArr2) downto 1 do
            nCurrentDistance := DamerauLevenshteinDistance(aArr1[i], aArr2[k]),
            if nCurrentDistance <= nAcceptableDistance then
               AAdd(aBuf, {aArr1[i], aArr2[k]}),
               ADelete(aArr2, k),
               break,
            endif,
            if not bIgnoreSurplusWords and k = 1 then
               AAdd(aBuf, {aArr1[i], ''}),
            endif,
         next,
      endif,
   next,

   if not bIgnoreSurplusWords then
      for k:=1 to ALen(aArr2) do
         if Len(aArr2[k]) > nAcceptableDistance then
            AAdd(aBuf, {aArr2[k], ''}),
         endif,
      next,
   endif,

   nMaxDistance := -1,
   for i:=1 to ALen(aBuf) do
      WriteLn(aBuf[i,1], aBuf[i,2]),
      nMaxDistance := Max(nMaxDistance, DamerauLevenshteinDistance(aBuf[i,1], aBuf[i,2])),
   next,

   Result := nMaxDistance <= nAcceptableDistance,
end,

Weitere Verknüpfungen

SoundEx()