Как я могу вычислить разницу между двумя строками?

Question

Я хочу создать функцию в Delphi, которая вычисляет разные уровни двух строк. Если две строки равны (игнорируя случай), тогда он должен возвращать 0, но если они не равны, он должен возвращать количество разных символов. Эта функция может быть очень полезна для проверки орфографии.

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

образцов код:

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

Быстрая и компактная реализация.

Примерно в 3 раза быстрее, чем реализация smasher с нормальными строками. Более 100 раз быстрее, если одна из строк пуста.

Функция Smasher нечувствительна к регистру, хотя и может быть полезна.

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; 

Примечание: inline директива сокращает время выполнения менее чем на 70% на моей машине, но только для целевой платформы win32. Если вы скомпилируете 64-битную (Delphi XE2), вложение делает ее чуть медленнее.

Answer 2

То, что вы хотите, известен как Levenshtein distance (минимальное количество правок для преобразования одной строки в другую, где правка либо вставки символов, удаление символов или замена символов). Сайт википедии имеет реализацию псевдокода.

реализация 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;