Levenshtein-Distanz

[Nicolai1234]

Hallo,
ich bin gerade dabei ein Programm meines Vaters zu überarbeiten. Er benutzte eine Funktion zur prozentualen Abweichung zweier Strings an Hand der Levenshtein Distanz, von der er leider nicht mehr weiß, woher er sie hat.
Die Funktion sieht wie folgt aus:

Delphi-Quellcode:

function Levenshtein(S,T:String):integer;

  var D:array[0..255,0..255] of integer;
      M:Integer;           // length of t
      N:Integer;           // length of s
      I:Integer;           // iterates through s
      J:Integer;           // iterates through t
      SI:Char;             // ith character of s
      TJ:Char;             // jth character of t
      Cost:Integer;        // cost
  begin
    N:=Length(S);
    M:=Length(T);
    if (N=0) then begin
      Result:=M;
      Exit;
    end;
    if (M=0) then begin
      Result:=N;
      Exit;
    end;

    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 begin
      SI:=S[I];
      for J:=1 to M do begin
        TJ:=T[J];
        if (SI=TJ) then Cost:=0
        else Cost:=1;

        if (D[I-1,J-1]+Cost >= D[I,J-1]+1) then
           begin
           if (D[I-1,J]+1 >= D[I,J-1]+1) then
           D[I,J]:= D[I,J-1]+1
           else
           D[I,J]:= D[I-1,J]+1
           end
        else
           begin
           if (D[I-1,J]+1 >= D[I-1,J-1]+Cost)then
           D[I,J]:= D[I-1,J-1]+Cost
           else
           D[I,J]:= D[I-1,J]+1

        end;
      end;
    end;
    Result:=D[N,M]*100 div M;

  end;

Leider ist diese nicht besonders schnell, da sie in diesem Programm rund 12 Millionen mal hintereinander aufgerufen werden muss. Ich frage mich, ob es schnelle bzw. bessere Funktionen gibt, die diese Arbeit erledigen. Oder aber was man an der oberen noch verbessern könnte.

Zitat:

19 x 99 Dezibel(A) - ein gesicherter Befund der Lärmwirkungsforschung?
19x99 dB (A) - gesicherter Befund Lärm-wirkungs-Forschung

Es geht in diesem Programm darum, Strings wie diese als gleich zu erkennen. Da hilft das einfache Soundex leider nicht mehr weiter.

Naja, vielleicht habt ihr ja eine Idee...

Vielen Dank im voraus
Nicolai