Levenshtein distance - podobienstwo

witam

szukajac algorytmu na podobienstwo 2 stringow natknelem sie na pojecie Levenshtein distance

Funckja w Delphi:

function EditDistance(s, t: string): integer;
var
  d : array of array of integer;
  i,j,cost : integer;
begin

  {
  Compute the edit-distance between two strings.
  Algorithm and description may be found at either of these two links:
  http://en.wikipedia.org/wiki/Levenshtein_distance
  http://www.google.com/search?q=Levenshtein+distance
  }

  try
    //initialize our cost array
    SetLength(d,Length(s)+1);
    for i := Low(d) to High(d) do begin
      SetLength(d[i],Length(t)+1);
    end;

    for i := Low(d) to High(d) do begin
      d[i,0] := i;
      for j := Low(d[i]) to High(d[i]) do begin
        d[0,j] := j;
      end;
    end;

    //store our costs in a 2-d grid
    for i := Low(d)+1 to High(d) do begin
      for j := Low(d[i])+1 to High(d[i]) do begin
        if s[i] = t[j] then begin
          cost := 0;
        end
        else begin
          cost := 1;
        end;

        //to use "Min", add "Math" to your uses clause!
        d[i,j] := Min(Min(
                   d[i-1,j]+1,      //deletion
                   d[i,j-1]+1),     //insertion
                   d[i-1,j-1]+cost  //substitution
                   );
      end;  //for j
    end;  //for i

    //now that we've stored the costs, return the final one
    Result := d[Length(s),Length(t)];
  finally
    //cleanup
    for i := Low(d) to High(d) do begin
      for j := Low(d[i]) to High(d[i]) do begin
        SetLength(d[i],0);
      end;  //for j
    end;  //for i
    SetLength(d,0);
  end;  //try-finally
  if ((length(s)<4) or (length(t) <4)) and (result<>0) then begin result:=2; exit; end;
end;
 

wszystko super ale funkcja ta nie uwzglednia dlugosci znakow i na przykład:
EditDistance('a','b') daje 1
EditDistance('rowerek','roweerk') daje 2

Wg algorytmu czym blizej 0 tym wyrazy sa bardziej podobne (0 to 100% podobienstwo)

a i b to calkiem inne litery o 100% innym znaczeniu
natomiast w tych wyrazach przestawilem tylko 2 litery a wg algorytmu sa one bardziej nie podobne niż a i b

Czy istnieje modyfikacja tego algorytmu lub calkiem inny algorytm ktory uwzglednia przy porównaniu 2 stringow takze ich dlugosc?

Pozdrawiam

w funkcji orginalnie nie ma przedostaniej lini

 
if ((length(s)<4) or (length(t) <4)) and (result<>0) then begin result:=2; exit; end;

zapomnialem usunac, byly to moje jakies proby rozwiazania problemu krotkich wyrazow ;)

Najlepsze co mi sie udalo wymyslec to dodanie na koncu funkcji

 
  result:=100-result;
  if result<>100 then result:=result-round(cotan(((length(t)+length(s))/2)/100));

przeksztalca to funkcje zwracajac procent pokrewnosci (100% to dokladnie te same stringi a 0% to zupelnie inne) , cotangens pomaga ogarnac dlugosc podawanych ciagow, niby cos jest ale pewnie da sie to jeszcze ulepszyc, poza tym moze byc problem przy dlugich ciagach znakowych bo cotangens bedzie bezuzyteczny :/

jakies podpowiedzi? ktos to ogarnie? :D