Wie kann ich einen Unterschied zwischen zwei Strings berechnen?

Question

Ich möchte eine Funktion in Delphi erstellen, die verschiedene Ebenen von zwei Strings berechnet. Wenn zwei Zeichenfolgen gleich sind (Groß-/Kleinschreibung wird ignoriert), sollte sie 0 zurückgeben, wenn sie jedoch nicht gleich sind, sollte sie die Anzahl der verschiedenen Zeichen zurückgeben. Diese Funktion kann sehr nützlich sein, um die Rechtschreibung zu überprüfen.

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

Proben Code:

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

Schnelle und kompakte Implementierung.

Ungefähr dreimal so schnell wie die Implementierung von Smasher mit normalen Strings. Mehr als 100 mal so schnell, wenn einer der Strings leer ist.

Smasher-Funktion ist case insensitive obwohl, was auch nützlich sein kann.

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; 

Hinweis: Die inline Richtlinie reduziert die Ausführungszeit auf weniger als 70% auf meinem Rechner, sondern nur für die win32 Zielplattform. Wenn Sie auf 64Bits (Delphi XE2) kompilieren, macht das Inlining es tatsächlich ein bisschen langsamer.

Answer 2

Was Sie wollen, ist als Levenshtein distance (die Mindestanzahl der Änderungen bekannt als eine Zeichenfolge in die andere zu verwandeln, wo eine Bearbeitung entweder ein Zeicheneinfügung ist, Löschen Zeichen oder Zeichensubstitution). Die Wikipedia-Seite hat eine Pseudocode-Implementierung.

Delphi Umsetzung:

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;