17

Lucene など、API を一切使用しない検索エンジンの単純なインデックス機能を構築したいと考えています。転置索引には、各単語の基本情報 (docID、位置、頻度など) を記録するだけです。

さて、いくつか質問があります：

  1. 逆索引を構築するためによく使用されるデータ構造はどのようなものですか? 多次元リスト？

  2. インデックスを構築した後、それをファイルに書き込む方法は? ファイルの形式は何ですか？テーブルみたい？紙に指数表を描くのが好きですか？

4

1 に答える 1

34

TinySearchEngineで逆索引と検索の非常に単純な実装を見ることができます。

最初の質問について、単純な (メモリ内の) 転置インデックスを作成する場合、単純なデータ構造は次のようなハッシュ マップです。

val invertedIndex = new collection.mutable.HashMap[String, List[Posting]]

またはJava風：

HashMap<String, List<Posting>> invertedIndex = new HashMap<String, List<Postring>>();

ハッシュは、各用語/単語/トークンを投稿のリストにマップします。APostingは、ドキュメント内の単語の出現を表す単なるオブジェクトです。

case class Posting(docId:Int, var termFrequency:Int)

新しいドキュメントのインデックス作成は、それをトークン化 (トークン/単語で分離) するだけの問題であり、トークンごとに、ハッシュ マップの正しいリストに新しい投稿を挿入します。もちろん、その特定の docId にその用語の Posting が既に存在する場合は、termFrequency を増やします。これを行う方法は他にもあります。メモリ内の逆インデックスの場合はこれで問題ありませんが、ディスク上のインデックスの場合は、毎回更新するのではなくPostings、正しいものを一度挿入することをお勧めします。termFrequency

2 番目の質問については、通常 2 つのケースがあります。

（1）（ほぼ）不変のインデックスがあります。すべてのデータを 1 回インデックス付けすると、新しいデータがある場合は、インデックスを再作成できます。たとえば、1 時間に何度もリアルタイムでインデックスを作成する必要はありません。

(2) 新着書類が続々と届いており、新着書類をいち早く探す必要がある。

ケース (1) の場合、少なくとも 2 つのファイルを持つことができます。

1 - 逆索引ファイル。用語ごとにすべてPostings(docId/termFrequency ペア) を一覧表示します。ここではプレーン テキストで表されますが、通常はバイナリ データとして格納されます。

 Term1<docId1,termFreq><docId2,termFreq><docId3,termFreq><docId4,termFreq><docId5,termFreq><docId6,termFreq><docId7,termFreq>
 Term2<docId3,termFreq><docId5,termFreq><docId9,termFreq><docId10,termFreq><docId11,termFreq>
 Term3<docId1,termFreq><docId3,termFreq><docId10,termFreq>
 Term4<docId5,termFreq><docId7,termFreq><docId10,termFreq><docId12,termFreq>
 ...
 TermN<docId5,termFreq><docId7,termFreq>

2- オフセット ファイル。逆索引ファイル内の転置リストを検索するためのオフセットを用語ごとに格納します。ここではオフセットを文字で表していますが、通常はバイナリ データを格納するため、オフセットはバイト単位になります。このファイルは、起動時にメモリにロードできます。項転置リストを検索する必要がある場合は、そのオフセットを検索し、ファイルから転置リストを読み取ります。

Term1 -> 0
Term2 -> 126
Term3 -> 222
....

この 2 つのファイルに加えて、各用語のIDFと各ドキュメントの標準を保存するファイルを作成できます (通常は作成する予定です) 。

ケース (2) については、 Lucene (結果としてSolrとElasticSearch ) がどのようにそれを行うかを簡単に説明しようと思います。

ファイル形式は、上記で説明したものと同じでかまいません。主な違いは、インデックスを最初から再構築するのではなく、Lucene のようなシステムで新しいドキュメントのインデックスを作成すると、新しいドキュメントのみで新しいドキュメントが作成されることです。そのため、何かをインデックス化する必要があるたびに、新しい個別のインデックスでそれを行います。

この「分割された」インデックスでクエリを実行するには、異なるインデックスごとに (並列で) クエリを実行し、結果をマージしてからユーザーに返すことができます。

Lucene はこれを「小さな」インデックスと呼びますsegments。

ここでの明らかな懸念は、多くの小さなセグメントが非常に迅速に取得されることです。これを回避するには、セグメントをマージしてより大きなセグメントを作成するためのポリシーが必要です。たとえば、複数のセグメントがあるN segments場合は、より小さいすべてのセグメントを結合することを決定できます10 KBs。

于 2012-09-20T21:29:48.100 に答える