私は逆インデックスを持っています。各トークンは、(document_id, score)というペアのリストにマップされています。各トークンの値リストは降順スコアでソートされるため、最も高いランクの文書が最初に表示されます。逆インデックスのアウトオブオーダー値配列の交差を見つけるための優れたデータ構造ですか？
残念ながら、ドキュメント内のトークンのコンテキストに基づいてスコアが調整されるため、ソートされたスコアがすべてのトークンに対して同時にソートされることを保証することはできません。たとえば、私の "ドキュメント"が(id, score) = (1, 105)の文字列で、 "赤ワイン"が(id, score) = (2, 100)の場合、 "赤"と "ワイン"は "赤ワイン"では同等の重要度を持ちますが、 "ワイン"では< "赤逆索引は、私がIDにこれらのリストの交差点を見つける必要があり
"red" -> [(2, 100), (1, 95)]
"wine" -> [(1, 105), (2, 100)]
"iPhone" -> [(1, 115)]
のように見えるようにスコアが調整される可能性がありますので、ワインレッドiPhone 『の重要性『「<』iPhone』、戻りますすべてのトークンセットを含む文書IDのランク付けされたリスト（標準検索問題）。上記の例では、IDを持つ別の文書「白ワイン」があると仮定= 3、スコア= 50、その転置インデックスは次のようになります。検索トークンが{"red", "wine"}であれば、
"red" -> [(2, 100), (1, 95)]
"wine" -> [(1, 105), (2, 100), (3, 50)]
"white" -> [(3, 50)]
"iPhone" -> [(1, 115)]
その後、問題を本質的には2つのトークン（この場合は[(2, 100), (1, 95)]と[(1, 105), (2, 100), (3, 50)]）の値を引き出し、それらをドキュメントIDと交差させるため、結果は[(2, f(100, 100)), (1, f(95, 105))]のようになります。 fはいくつかの平均化関数であり、重要ではありません。
これは高速で、できるだけ少ないメモリを消費する必要があります（ただし、ディスク容量は問題ありません）。場合によっては、何百万ものユニークなドキュメントIDに対応する数百万のユニークなトークンを格納します。これまでのところ、私の制約を満たすためにしようとする
、私は基本的にメモリ内の圧縮のために、（各(id, score)ペアは一つの値である場合）、キーと値のストアであることを修正トライにデータを格納巻き取ってきました。 inverted_index.get(token)は配列全体を反復し、id -> scoreのハッシュマップを返します。また、getは、そのようなハッシュマップを引数としてとり、その交点が配列を反復処理して次のマップを組み立てながら行われるようにすることができます。リストをプライマリリストとフォールバックリスト、シリアル化/デシリアライゼーション、さらにはblah blah blahに分割することについては、マイナーな最適化がいくつかあります。彼らはもっと大きな問題に対処していない、問題の正しいデータ構造とアルゴリズムを実際に使用しているわけではない、すべての種類のバンデイズです。現在、私の最大のユースケースは約20mのユニークなドキュメントIDを持ち、完全にメモリにロードされると約400MBを要します。
現在のところ、これは私のアプリケーションでのパフォーマンスの最大のボトルネックです。特に、トークンのセットに非常に大きな値のトークンが含まれている場合は、私は既存のライブラリを使用すること、最初から何かを書くこと、現在のメソッドに最適化することなどを公開しています。私の主なスタックはPythonですが、この部分はC++とCythonで書かれています。既存のソースを知っていれば、Pythonラッパーを書くことができる限り、どの言語にも対応できます。
ありがとうございました！
これをもう少し明確に説明できますか？あなたの入力と出力の明確な例を書いてください。私は「これらのリストの交差点」が何を意味するのか理解していません。 –
@robertkingしました、今はっきりしていますか？フィードバックをお寄せいただきありがとうございます。 – gmoss
もしソートされたスコアがID別にソートされることを保証できないなら、あなたはそれらが正しいとふりだこにして、即時に訂正をするために順序のずれたハッシュテーブルを使用できますか？ –