任意の文字列sが与えられた場合、すべての文字列 S ⊆ M を文字列 M (|M| > 100 万) の大規模なセットからすばやく取得するメソッドが必要です。ここで、S のすべての文字列は最小の編集距離 < t (いくつかの最小値) を持ちます。しきい値) sから。
最悪の場合、M 内の文字列がこの基準に一致しない場合、S は空になる可能性があり、せいぜい S = { s } (完全一致) です。その間のいずれの場合でも、S が非常に大きい可能性があることを完全に期待しています。
一般に、編集距離の最大しきい値を固定 (たとえば 2) にすることを期待しており、この操作を任意の文字列sに対して何度も実行する必要があります。高過ぎ。
メトリックの例として編集距離を使用しましたが、Jaccard インデックスなどの他のメトリックも使用したいと思います。
これを達成できる既存の Java 実装について誰か提案をしたり、この問題を解決するための適切なアルゴリズムとデータ構造を教えてもらえますか?
更新 #1
それ以来、メトリック ツリーはまさに私が求める構造であり、距離メトリックを利用して、メトリックを使用した相互の距離に基づいて M 内の文字列のサブセットを編成することを学びました。Vantage -Point、BK、およびその他の同様のメトリック ツリー データ構造とアルゴリズムは、この種の問題には理想的です。さて、Java で使いやすい実装を見つけるには...
更新 #2
このbk ツリーとレーベンシュタイン距離の実装を組み合わせて使用することで、100 万個の文字列のセット (M) から任意の文字列に対するサブセットを約 10 ミリ秒の取得時間で正常に取得できます。