最も近い一致を見つけるために、コレクションに対する文字列の編集距離を計算しようとしています。私の現在の問題は、コレクションが非常に大きい (約 25000 アイテム) ことです。そのため、セットを同じような長さの文字列だけに絞り込む必要がありましたが、それでも数千の文字列に絞り込むだけであり、これはまだ非常に遅いです。同様の文字列をすばやく検索できるデータ構造はありますか、またはこの問題に対処できる別の方法はありますか?
3 に答える
8
BK ツリーが必要なようです。それらについて説明している記事があります: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees。簡単なGoogleは、いくつかの Java 実装を生成します。
于 2012-02-04T08:50:22.227 に答える
6
レーベンシュタイン オートマトンを使用すると、特定の単語から特定のレーベンシュタイン距離内に収まるように、大きな辞書から一連の単語をすばやく選択できます。
参照: Schulz K, Mihov S. (2002)レーベンシュタイン オートマトンによる高速文字列修正。
于 2012-02-04T10:32:52.023 に答える
2
「類似」の基準が全体の順序付けを定義する場合、Comparator を定義し、TreeSet を使用して最も近い一致を見つけることができるはずです (たとえば、ceiling メソッドと floor メソッドを使用)。
于 2012-02-04T08:42:32.493 に答える