javascript - 文字列照合アルゴリズムの最適化

Question

function levenshtein(a, b) {
  var i,j,cost,d=[];

  if (a.length == 0) {return b.length;}
  if (b.length == 0) {return a.length;}

  for ( i = 0; i <= a.length; i++) {
    d[i] = new Array();
    d[ i ][0] = i;
  }

  for ( j = 0; j <= b.length; j++) {
    d[ 0 ][j] = j;
  }

  for ( i = 1; i <= a.length; i++) {
    for ( j = 1; j <= b.length; j++) {
      if (a.charAt(i - 1) == b.charAt(j - 1)) {
        cost = 0;
      } else {
        cost = 1;
      }

      d[ i ][j] = Math.min(d[ i - 1 ][j] + 1, d[ i ][j - 1] + 1, d[ i - 1 ][j - 1] + cost);

      if (i > 1 && j > 1 && a.charAt(i - 1) == b.charAt(j - 2) && a.charAt(i - 2) == b.charAt(j - 1)) {
        d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost)
      }
    }
  }

  return d[ a.length ][b.length];
}

function suggests(suggWord) {
  var sArray = [];
  for(var z = words.length;--z;) {
    if(levenshtein(words[z],suggWord) < 2) { 
      sArray.push(words[z]);
    }   
  }
}

こんにちは。

私は上記のダメラウ・レーベンシュタインアルゴリズムの実装を使用しています。通常のPCブラウザでは十分に高速ですが、タブレットでは約2/3秒かかります。

基本的に、suggest関数に送信された単語を辞書内のすべての単語と比較し、距離が2未満の場合は、それを配列に追加します。

dicは、約600,000（699KB）の単語の配列です。これの目的は、Javascriptスペルチェッカーの単語候補機能を作成することです。

これをスピードアップする方法について何か提案はありますか？またはこれを行う別の方法ですか？

Answer 1

あるしきい値よりも短い距離だけを探している場合にできることの1つは、最初に長さを比較することです。たとえば、2未満の距離のみが必要な場合は、2つのストリングの長さの差の絶対値も2未満である必要があります。これを行うと、より高価なレーベンシュタイン計算を行うことさえ回避できることがよくあります。

この背後にある理由は、長さが2だけ異なる2つのストリングには、少なくとも2つの挿入が必要になるためです（したがって、結果として最小距離は2になります）。

次のようにコードを変更できます。

function suggests(suggWord) {
  var sArray = [];
  for(var z = words.length;--z;) {
    if(Math.abs(suggWord.length - words[z].length) < 2) {
      if (levenshtein(words[z],suggWord) < 2) { 
        sArray.push(words[z]);
      }
    }   
  }
}

私はあまりjavascriptをしませんが、これがあなたがそれを行うことができる方法だと思います。

問題の一部は、辞書の単語が多数あり、それらの単語のすべてに対して少なくともいくつかの処理を実行していることです。1つのアイデアは、異なる語長ごとに個別の配列を用意し、辞書の単語を1つの大きな配列ではなくそれらに整理することです（または、アルファルックアップなどのために1つの大きな配列が必要な場合は、インデックスの配列を使用しますその大きな配列に）。次に、5文字の長さのsuggWordがある場合は、4、5、および6文字の単語の配列を調べるだけで済みます。次に、上記のコードでMatch.Abs​​（length-length）テストを削除できます。これは、一致する可能性のある長さの単語のみを調べていることがわかっているためです。これにより、辞書の単語の大部分を処理する必要がなくなります。

レーベンシュタインは比較的高価であり、単語が長いほど高価です。レーベンシュタインが高額で何度も実行できない場合、特に長い単語の場合は、完全に一致する単語または距離が1（1回の挿入）の単語のみを考慮するというしきい値の別の副作用を利用できます。 、削除、置換、または転置）。その要件を前提として、最初の文字が一致するか、最後の文字が一致するかを確認することで、レーベンシュタイン計算の候補をさらにフィルタリングできます（ただし、いずれかの単語の長さが1または2の場合は、レーベンシュタインの方が安価です）。実際、最初のn文字または最後のn文字のいずれかが一致するかどうかを確認できます。ここで、n =（suggWord.length-1）/2です。彼らがそのテストに合格しなかった場合、あなたは彼らが合格したとみなすことができます レーベンシュタインを介して一致します。このためには、辞書の単語のプライマリ配列をアルファベット順に並べ、さらにその配列へのインデックスの配列を必要としますが、逆の文字でアルファベット順に並べます。次に、これらの配列の両方に対して二分探索を行うことができ、開始または終了のn文字がsuggWordの開始または終了と一致し、長さがで異なる単語の小さなサブセットに対してレーベンシュタイン計算を実行するだけで済みます。ほとんどの1文字。

Answer 2

同じアルゴリズムを最適化する必要がありました。私にとって最も効果的なのは、d配列をキャッシュすることでした。レーベンシュタイン関数の外部で大きなサイズ（予想される文字列の最大長）で作成するため、関数を呼び出すたびに再初期化する必要はありません。 。

私の場合、Rubyではパフォーマンスに大きな違いがありました。wordsしかしもちろん、それはあなたのアレイのサイズに依存します...

function levenshtein(a, b, d) {

var i,j,cost;

if (a.length == 0) {return b.length;}
if (b.length == 0) {return a.length;}

for ( i = 1; i <= a.length; i++) {

    for ( j = 1; j <= b.length; j++) {

        if (a.charAt(i - 1) == b.charAt(j - 1)) {

            cost = 0;

        } else {

            cost = 1;

        }

        d[ i ][j] = Math.min(d[ i - 1 ][j] + 1, d[ i ][j - 1] + 1, d[ i - 1 ][j - 1] + cost);

        if (i > 1 && j > 1 && a.charAt(i - 1) == b.charAt(j - 2) && a.charAt(i - 2) == b.charAt(j - 1)) {

            d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost)

        }

    }

}

return d[ a.length ][b.length];

}

function suggests(suggWord)
{
d = [];
for ( i = 0; i <= 999; i++) {

    d[i] = new Array();

    d[ i ][0] = i;

}
for ( j = 0; j <= 999; j++) {

    d[ 0 ][j] = j;

}


var sArray = [];
for(var z = words.length;--z;)
{
        if(levenshtein(words[z],suggWord, d) < 2)
        {sArray.push(words[z]);}    
}
}

Answer 3

すべての単語をトライに保存する必要があります。これは、単語を格納する辞書と比較すると、スペース効率が高くなります。そして、単語に一致するアルゴリズムは、トライ（単語の終わりを示す）をトラバースして単語に到達することです。

編集

コメントで述べたように。レーベンシュタイン距離が0または1の場合、すべての単語を調べる必要はありません。2つの単語が等しい場合、レーベンシュタイン距離は0になります。ここで、問題は、特定の単語に対してレーベンシュタイン距離が1になるすべての単語を予測することに要約されます。例を見てみましょう：

配列

上記の単語の場合、レーベンシュタイン距離1を求めたい場合、例は次のようになります。

• parray、aprray、arpray、arrpay、arrayp（文字の挿入）

ここで、pは他の文字に置き換えることができます。

これらの単語についても、レーベンシュタイン距離は1です。

rray、aray、arry（キャラクターの削除）

そして最後にこれらの言葉のために：

prray、apray、arpay、arrpy、arrap（キャラクターの代用）

ここでも、pは他の文字に置き換えることができます。

したがって、これらの特定の組み合わせのみを検索し、すべての単語を検索しない場合は、解決策にたどり着きます。レーベンシュタインアルゴリズムがどのように機能するかをご存知の場合は、リバースエンジニアリングを行っています。

ユースケースである最後の例：

paryが入力として取得し、辞書の一部に修正する必要がある単語である場合。したがって、paryの場合、 abで始まる単語を調べる必要はありません。たとえば、abで始まる単語の場合、レーベンシュタイン距離は1より大きくなります。

Answer 4

実行速度を大幅に向上させるために、コードで実行できる簡単なことがいくつかあります。パフォーマンス、JIT解釈への静的型付けへの準拠、およびJSLintへの準拠のために、コードを完全に書き直しました。

var levenshtein = function (a, b) {
        "use strict";
        var i = 0,
            j = 0,
            cost = 1,
            d = [],
            x = a.length,
            y = b.length,
            ai = "",
            bj = "",
            xx = x + 1,
            yy = y + 1;
        if (x === 0) {
            return y;
        }
        if (y === 0) {
            return x;
        }
        for (i = 0; i < xx; i += 1) {
            d[i] = [];
            d[i][0] = i;
        }
        for (j = 0; j < yy; j += 1) {
            d[0][j] = j;
        }
        for (i = 1; i < xx; i += 1) {
            for (j = 1; j < yy; j += 1) {
                ai = a.charAt(i - 1);
                bj = b.charAt(j - 1);
                if (ai === bj) {
                    cost = 0;
                } else {
                    cost = 1;
                }
                d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
                if (i > 1 && j > 1 && ai === b.charAt(j - 2) && a.charAt(i - 2) === bj) {
                    d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
                }
            }
        }
        return d[x][y];
    };

多次元ルックアップの各間隔で配列の長さをルックアップすることは、非常にコストがかかります。また、 http：//prettydiff.com/を使用してコードを美化し、半分の時間でコードを読み取れるようにしました。また、配列内の冗長なルックアップをいくつか削除しました。これがあなたのためにより速く実行されるかどうか私に知らせてください。