4

レーベンシュタイン アルゴリズムについては、この Delphi の実装を見つけました。

最大距離に達するとすぐに停止し、それまでに見つかった距離を返すバージョンが必要です。

私の最初のアイデアは、反復ごとに現在の結果を確認することです。

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;
4

1 に答える 1

5

あなたが望むのは、レーベンスタイン距離を見つけることMAXです。

もしそうなら、より大きな値に到達するMAXだけでは十分ではありません。これは、パスがそれよりも長いことを意味するだけであり、より短いパスが存在しないことを意味しないためです。MAX見つけられるよりも短いパスがないことを確認するには、現在のポイントまでのパスの最小可能長さ、つまり距離テーブルの列の最小長を監視する必要があります。

私は Delphi が苦手ですが、コードは次のようになるはずです。

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;
于 2012-07-31T10:05:58.500 に答える