0

次の問題を解決するためのデータ構造を探しています。かなり短い文字列（たとえば、5,000万、30文字未満）の大規模なコレクションを入力として受け取り、必要に応じてインデックスを付けます。次に、新しい文字列を指定し、提供された文字列に類似した初期セットからの文字列を提供するクエリに回答します（たとえば、そのような文字列の中で最も優れたもの10個）。「類似性」の概念は、理想的には編集距離やジャロウィンクラー距離、またはそれらの近似値のようなものですが、スペルや語順の小さな変更、およびジャンク単語の追加に対して回復力がある必要があります。（たとえば、標準のインデックス作成タスクとは異なり、「foo bar」をリクエストすると、コレクション内で実際に最も近い文字列である場合は「foo」が生成されます）。

例を挙げると、文字列コレクションが{"Charles Dickens"、 "Mary Shelley"、"RobertStephenson"}であるとします。「ディケンズ、チャールズ」をクエリすると、「チャールズディケンズ」が見つかります。「byShelley」をクエリすると、「MaryShelley」が返されます。

コレクション内のすべての文字列に対するクエリ文字列の類似性を1つずつ計算する簡単なアプローチは、大規模なコレクションには遅すぎます。そのようなクエリにより効率的に答えるための良いデータ構造は何でしょうか？理想的には、これの優れたJava実装を探しています。

4

2 に答える 2

0

単純なアプローチの代わりに、次の 2 つの手順で問題を解決できます。

  1. すべての文字列に出現する単語のインデックスを作成します。これにより、特定の単語を含む文を見つけることができます。これは、5,000 万よりもはるかに小さいはずです (自然言語について話している場合)。また、「foop bar」->「foo」は単語しかないので気にしないかもしれません。
  2. クエリを単語に分割します。各単語について、この単語を含むすべての文を見つけます。各文について、メトリクスを使用してクエリ文字列との類似性を計算します。

もう 1 つの利点は、多くの場合、単語インデックスを再構築せずにメトリックを変更できることです。

于 2012-05-16T20:17:10.227 に答える
0

次の 2 つの提案が思い浮かびます。

1) 三角形の不等式を満たす距離関数を選択し、http://en.wikipedia.org/wiki/Cover_treeを使用します- 多少の速度向上はあるかもしれませんが、おそらく桁違いではありません。

2) 最も近い一致には、2 つの文字列間で完全に一致する k 個の連続した文字のストレッチが少なくとも 1 つ含まれると推測します。たとえば、ハッシュ テーブル ルックアップを使用して、クエリ文字列の一部と同じ少なくとも k 個の連続した文字を含むコレクション内のすべての文字列を検索できるデータ構造を構築し、距離関数を使用して、どの文字列から返された文字列を確認します。これがベストマッチです。速いはずですが、正しい答えを見逃すことがあります。

于 2012-05-16T18:47:08.980 に答える