4

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;
Community
  • 1
  • 1
mjn
  • 36,362
  • 28
  • 176
  • 378
  • That's no good. You assign to `d[i,j]`, but then test `d[n,m]`. Also, `ord()` would be more normal than `Integer()`, but I would prefer an explicit use of `IfThen()`. And result won't be assigned if n or m are less than 1. – David Heffernan Jul 31 '12 at 08:16
  • I see, the usage of Min makes it hard to optimize before the end of both loops. – mjn Jul 31 '12 at 09:45

1 Answers1

5

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;
Qnan
  • 3,714
  • 18
  • 15