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
//******************************************************************************
// 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,