4

私は〜150'000単語とパターン（任意の単語）のデータベースを持っており、それとパターンの間のDamerau-Levenshtein距離が指定された数よりも小さいデータベースからすべての単語を取得したいと考えています。私はそれを非常に速くする必要があります。どのアルゴリズムを提案できますか? Damerau-Levenshtein 距離の適切なアルゴリズムがない場合は、Levenshtin 距離だけでも問題ありません。

ご協力ありがとうございました。

PS SOUNDEX は使用しません。

4

5 に答える 5

2

レーベンシュタイン距離 (T-SQl または .Net) を計算する SQL 関数から始めます (はい、私は MS の人です...) 早期終了を引き起こす最大距離パラメーターを使用します。

この関数を使用して、入力を各文字列と比較して距離を確認し、しきい値を超えた場合は次の文字列に進むことができます。

また、たとえば、最大距離を 2 に設定し、長さが 1 を超えて最初の文字が異なるすべての単語をフィルタリングできると考えていました。インデックスを使用すると、これはわずかに速くなる場合があります。

完全に一致するすべての文字列をショートカットして戻すこともできます (インデックスを作成すると速度が向上します)。これらの文字列は実際には 0 のレーベンシュタイン距離を計算するのに時間がかかるためです。

ほんの少しの考え....

于 2010-01-20T08:55:09.243 に答える
0

実際にすべての行を列挙しないと、この種の関数を計算できないと思います。
したがって、解決策は次のとおりです。

  1. 非常に高速な列挙にします（ただし、これは実際にはスケーリングしません）
  2. 何らかの方法で最初のバリアントをフィルター処理します (文字によるインデックス、少なくとも x 個の一般的な文字)
  3. N-Grams などの代替 (インデックス可能な) アルゴリズムを使用します (ただし、ngram の結果の品質と DL 距離の詳細はわかりません)。
于 2010-01-20T08:35:35.123 に答える
0

私の頭の上の解決策は、データベースをソートされたセット ( std::setC++ など) に格納することかもしれません。内の指定された文字列の位置を概算するには、文字列に対してsetを使用std::upper_boundし、検出された位置から外側に向かって両方向にセットを反復処理し、移動しながら距離を計算し、特定のしきい値を下回ったときに停止します。この解決策はおそらく同じ開始文字を持つ文字列にのみ一致すると思いますが、スペルチェックにアルゴリズムを使用している場合、その制限は一般的であるか、少なくとも驚くべきことではありません.

編集:ただし、アルゴリズム自体の最適化を探している場合、この回答は関係ありません。

于 2010-01-20T08:42:23.503 に答える
-1

Ankiroを調べることをお勧めします。

精度の要件を満たしているかどうかはわかりませんが、高速です。

于 2010-01-20T08:35:10.667 に答える