逆索引のファイル形式

Question

私は逆索引作成に取り組んでいます。これは文書コレクションを索引付けし、各用語を情報とともに格納し、その参照を投稿ファイル（文書ID、場所など）に格納します。

現在、私はそれを.txtファイルに格納しています。このファイルは、.txtファイルに関係するすべてのクエリに対して文字列マッチングを必要とします。

私はリンクされたリストスタイルのデータ構造のようなファイルにその情報を保存します。これはこのタイプのシナリオのために可能です....（また私はインデックス作成のためにPHP言語を使用しています）。

ありがとうございます、ありがとうございます。

Answer 1

逆インデックスのポイントは、任意の特定の用語に対する出現リスト（投稿リスト）への非常に高速なアクセスを可能にすることです。あなたはそれが簡単で、容易に利用可能なデータ構造を使用して実装したい場合、あなたはおそらくできる最善は

• が投稿への用語からのマッピングを格納するハッシュを使用しているよう
• ストア各ポスティングリストを示していますソートされた整数の連続ブロック（つまり、JavaではArrayList、C++ではstd::vectorなど）。
  • ポスティングリストはを非常に得ることができること：それはポインタ

  より適切な（そしてより洗練された）実装が考慮されてしまうために無駄なスペースの膨大な量を必要とするので、リンクリストを使用しないでください。あなたが複数のチャンクに分割してしなければならないので、それぞれが一つの連続ブロックとして保存され、大規模なポスティングリストは、圧縮されなければならないことを

これらの技術の詳細な説明は古典的な本Managing Gigabytesにあります。