Làm cách nào để tính toán sự khác biệt giữa hai chuỗi?

Question

Tôi muốn tạo một hàm trong Delphi tính các mức khác nhau của hai chuỗi. Nếu hai chuỗi bằng nhau (bỏ qua trường hợp), thì nó sẽ trả về 0, nhưng nếu chúng không bằng nhau, nó sẽ trả về số ký tự khác nhau. Chức năng này có thể rất hữu ích để kiểm tra chính tả.

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

mẫu mã:

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

nhanh và nhỏ gọn thực hiện.

Khoảng 3 lần nhanh như việc thực hiện của người đập bể với các chuỗi thông thường. Nhanh hơn 100 lần nếu một trong các chuỗi bị trống.

Chức năng của người đập bể không phân biệt chữ hoa chữ thường, điều này cũng có thể hữu ích.

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; 

Lưu ý: chỉ thị inline giảm thời gian thực hiện xuống dưới 70% trên máy tính của tôi, nhưng chỉ dành cho nền tảng mục tiêu win32. Nếu bạn biên dịch đến 64bits (Delphi XE2), nội tuyến thực sự làm cho nó một chút chậm hơn.

Answer 2

Những gì bạn muốn được gọi là Levenshtein distance (số lượng tối thiểu về những sửa đổi để chuyển đổi một chuỗi thành khác, nơi một chỉnh sửa hoặc là chèn nhân vật, xóa nhân vật hoặc thay thế ký tự). Trang wikipedia có triển khai mã giả.

Delphi thực hiện:

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;