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

10

Я хочу создать функцию в 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
Смотрите также:Need a routine to detect strings that are similar but not identical. LU RD

Ваш Ответ

2   ответа
13

Примерно в 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), вставка на самом деле делает его чуть медленнее.

7

Расстояние Левенштейна (минимальное количество правок для преобразования одной строки в другую, где правка - это либо вставка символа, либо удаление символа, либо замена символа). Сайт википедии имеет реализацию псевдокода.

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;
@MajidTaheri: Вы запросили функцию, которая вычисляла бы разницу между двумя словами, и функция Smasher - ответ на ваш вопрос. Вы никогда не говорили в своем вопросеhow exactly Вы бы использовали функцию.
Вы можете выйти из функции, если одна из двух строк пуста. Это намного быстрее, когда имеется пустая строка, и в противном случае это не будет стоить дорого. Просто добавь:if Length1=0 then exit(Length2); if length2=0 then exit(length1);
@MajidTaheri, вы можете попробоватьthis реализацияLevenshtein Distance.
@LU RD, функция EditDistance лучше. MajidTaheri

Похожие вопросы