Jak mogę obliczyć różnicę między dwoma ciągami?

Question

Chcę utworzyć funkcję w Delphi, która oblicza różne poziomy dwóch ciągów. Jeśli dwa ciągi są równe (ignorowanie wielkości liter), to powinno zwrócić 0, ale jeśli nie są równe, powinno zwrócić liczbę różnych znaków. Ta funkcja może być bardzo przydatna do sprawdzania pisowni. Kod

function GetDiffStringLevel(S1,S2:string):Integer; 
begin 
    if SameText(S1,S2) then Exit(0); 
    // i want get different chars count 
end 

próbki:

Diff:=GetDiffStringLevel('Hello','Hello');// Diff:=0; 
Diff:=GetDiffStringLevel('Hello','2Hello');// Diff:=1; 
Diff:=GetDiffStringLevel('Hello','H2ello');// Diff:=1; 
Diff:=GetDiffStringLevel('Hello','Hello W');// Diff:=2; 
Diff:=GetDiffStringLevel('Hello','World');// Diff:=6; or 5 

Answer 1

Szybka i kompaktowa realizacja.

Około 3 razy szybciej niż w wersji do smashera z normalnymi ciągami. Ponad 100 razy szybciej, jeśli jeden z ciągów jest pusty.

Funkcja Smashera nie rozróżnia wielkości liter, co może być przydatne.

function LevenshteinDistance(const s, t: string): integer;inline; 
var 
    d : array of array of integer; 
    n, m, i, j : integer; 
begin 
    n := length(s); 
    m := length(t); 
    if n = 0 then Exit(m); 
    if m = 0 then Exit(n); 

    SetLength(d, n + 1, m + 1); 
    for i := 0 to n do d[i, 0] := i; 
    for j := 0 to m do d[0, j] := j; 

    for i := 1 to n do 
    for j := 1 to m do 
     d[i, j] := Min(Min(d[i-1, j]+1, d[i,j-1]+1), d[i-1,j-1]+Integer(s[i] <> t[j])); 

    Result := d[n, m]; 
end; 

Uwaga: dyrektywa inline skraca czas wykonywania mniej niż 70% na moim komputerze, ale tylko dla platformy docelowej win32. W przypadku kompilacji do 64-bitów (Delphi XE2), wstawianie powoduje, że jest on wolniejszy.

Answer 2

Co chcesz jest znany jako Levenshtein distance (minimalna liczba edycji przekształcić jeden ciąg do drugiej, gdy edycja jest albo wprowadzania znaków, usunięcie znaków lub podstawienie postaci). Witryna wikipedia ma implementację pseudo-kodu.

wdrożenie Delphi:

function LevenshteinDistance(String1 : String; String2 : String) : Integer; 

var 
    Length1, Length2  : Integer; 
    WorkMatrix   : array of array of Integer; 
    I, J     : Integer; 
    Cost     : Integer; 
    Val1, Val2, Val3  : Integer; 

begin 
String1 := TCharacter.ToUpper (String1); 
String2 := TCharacter.ToUpper (String2); 
Length1 := Length (String1); 
Length2 := Length (String2); 
SetLength (WorkMatrix, Length1+1, Length2+1); 
for I := 0 to Length1 do 
    WorkMatrix [I, 0] := I; 
for J := 0 to Length2 do 
    WorkMatrix [0, J] := J; 
for I := 1 to Length1 do 
    for J := 1 to Length2 do 
    begin 
    if (String1 [I] = String2 [J]) then 
     Cost := 0 
    else 
     Cost := 1; 
    Val1 := WorkMatrix [I-1, J] + 1; 
    Val2 := WorkMatrix [I, J-1] + 1; 
    Val3 := WorkMatrix[I-1, J-1] + Cost; 
    if (Val1 < Val2) then 
     if (Val1 < Val3) then 
     WorkMatrix [I, J] := Val1 
     else 
     WorkMatrix [I, J] := Val3 
    else 
     if (Val2 < Val3) then 
     WorkMatrix [I, J] := Val2 
     else 
     WorkMatrix [I, J] := Val3; 
    end; 
Result := WorkMatrix [Length1, Length2]; 
end;