string - 文の単語レベルの編集距離

Question

2 つの文の間の単語レベルの編集距離を見つけることができるアルゴリズムはありますか? たとえば、「A Big Fat Dog」と「The Big House with the Fat Dog」には、1 つの代替、3 つの挿入があります。

Answer 1

文字列の編集距離を検索するために使用されるのと同じアルゴリズムを使用して、文の編集距離を検索できます。文は、各文字が英語の単語であるアルファベットから引き出された文字列と考えることができます（1つの「文字」が始まり次の「文字」が終わる場所を示すためにスペースが使用されていると仮定します）。レーベンシュタイン距離を計算するための標準動的計画法アプローチなど、編集距離を計算するための標準アルゴリズムは、この問題を解決するために適合させることができます。

Answer 2

これは、正規化されたレーベンシュタイン距離を計算する (つまり、範囲 [0..1] の値を与える) を ActionScript で @templatetypedef のアイデアを実装した例です (私にとってはうまくいきました)。

  private function nlevenshtein(s1:String, s2:String):Number {
     var tokens1:Array = s1.split(" ");
     var tokens2:Array = s2.split(" ");
     const len1:uint = tokens1.length, len2:uint = tokens2.length;
     var d:Vector.<Vector.<uint> >=new Vector.<Vector.<uint> >(len1+1);
     for(i=0; i<=len1; ++i)
        d[i] = new Vector.<uint>(len2+1);

     d[0][0]=0;

     var i:int;
     var j:int;

     for(i=1; i<=len1; ++i) d[i][0]=i; 
     for(i=1; i<=len2; ++i) d[0][i]=i;

     for(i = 1; i <= len1; ++i)
        for(j = 1; j <= len2; ++j)
           d[i][j] = Math.min( Math.min(d[i - 1][j] + 1,d[i][j - 1] + 1),
              d[i - 1][j - 1] + (tokens1[i - 1] == tokens2[j - 1] ? 0 : 1) );

     var nlevenshteinDist:Number = (d[len1][len2]) / (Math.max(len1, len2));

     return nlevenshteinDist;
  }

これが役立つことを願っています！