CODEWITHSUNDEEP
algorithmdelphilevenshtein-distance
mjn
mjn

Reputation: 36654

Levenshtein algorithm - fail-fast if edit distance is bigger than a given threshold

For the Levenshtein algorithm I have found this implementation for Delphi.

I need a version which stops as soon as a maximum distance is hit, and return the distance found so far.

My first idea is to check the current result after every iteration:

for i := 1 to n do
    for j := 1 to m do
    begin
      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]));

      // check   
      Result := d[n, m];
      if Result > max then
      begin
        Exit;
      end; 

    end;

Upvotes: 4

Views: 909

Answers (1)

Qnan
Qnan

Reputation: 3744

I gather what you want is to find the levenstein distance, if it is below MAX, right?

If so, reaching a value larger than MAX is not enough, since it only means that some path is longer than that, but not that there exists no shorter path. To make sure no path shorter than MAX can be found, one has to monitor the minimum possible length of a path until the current point, i.e. the minimum over a column in the distance table.

I'm not good at Delphi, but I think the code should look something like this:

for i := 1 to n do
begin;
    min := MAX + 1
    for j := 1 to m do
    begin;
      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]));
      min := Min(min, d[i,j])
    end;
    if min >= MAX then
        Exit;
end;

Upvotes: 5

Related Questions