[解決済み] luceneはどのように文書をインデックスするのですか？

質問

Luceneに関するドキュメントを読みました。また、このリンクにあるドキュメントも読みました。 ( http://lucene.sourceforge.net/talks/pisa ).

Luceneがどのようにドキュメントをインデックスするのかがよくわからないのですが、Luceneがどのアルゴリズムでインデックスを作成しているのでしょうか？

上記リンク先で、Luceneはインデックス作成にこのアルゴリズムを使用すると書いてありますが、どのようなアルゴリズムなのでしょうか？

• インクリメンタルアルゴリズム。
  • セグメントインデックスのスタックを保持する
  • 各受信ドキュメントのインデックスを作成する
  • 新しいインデックスをスタックにプッシュする
  • b=10をマージファクターとし、M=8とする。

for (size = 1; size < M; size *= b) {
    if (there are b indexes with size docs on top of the stack) {
        pop them off the stack;
        merge them into a single index;
        push the merged index onto the stack;
    } else {
        break;
    }
}

このアルゴリズムは、どのように最適化されたインデックスを提供するのでしょうか？

Lucene はインデックス作成に B-tree アルゴリズムやその他のアルゴリズムを使用しますか？ - それとも特定のアルゴリズムがあるのですか？

どのように解決するのですか？

簡単に説明すると、Lucene が転置インデックスを構築するには スキップリスト ディスク上 そして、インデックスされた用語のマッピングをロードします。 をメモリにロードします。 を使用して 有限状態トランスデューサ (FST)と呼ばれている。ただし、Lucene はインデックスされた全ての用語を（必ずしも）RAMにロードしません。 というのは、Lucene のインデックス作成システムの作者である Michael McCandless 自身が説明しているとおりです。スキップリストを使用することで、インデックスをあるヒットから別のヒットまでたどることができ、次のようなことが可能になることに注意してください。 を設定します。 と、特に 範囲クエリ が可能です（B-Treeによく似ています）。また スキップリストのインデックス作成に関する Wikipedia のエントリ は、Lucene の Skip-List 実装がなぜ マルチレベル Skip-List - 基本的には O(log n) のルックアップを可能にします (これも B-Tree によく似ています)。

つまり、転置（項）インデックス - これは スキップ リストのデータ構造 - をベースとしたインデックスがドキュメントから作成されると、そのインデックスはディスクに保存されます。次に Lucene は、これらの用語を (すでに述べたように、おそらくはその一部だけを) 有限状態トランスデューサ にロードし、FST 実装では ルーズリー・インスパイア によって モルフォロジック .

マイケル・マッカンドレス（も）かなり良い、簡潔な仕事をしています。 Lucene が (最小限の非循環的な) FST を使用する方法と理由を説明しています。 を使用して、Lucene がメモリに保存する用語のインデックスを作成する方法を説明しています。 SortedMap<ByteSequence,SomeOutput> としてメモリに保存されます。そして、FST がどのように機能するかの基本的なアイデア（つまり、このマッピングのメモリ使用量を亜線形に増加させるために、FST がバイト列（つまり、インデックス付きの用語）をどのようにコンパクト化するか）を示しています。そして、彼が指摘するのは 特定の FST アルゴリズムを説明した論文 Lucene が使用している特定の FST アルゴリズムを説明した論文も紹介しています。

多くのデータベースが (B+) や (B)-Trees を使用しているのに対し、Lucene が Skip-List を使用している理由を知りたい方は、以下を参照してください。 を見てください。 の右側にある SOの答え に、この質問（Skip-Lists vs. B-Trees）についての回答があります。その回答はかなり良い、深い説明を与えています - 基本的に。 ではなく のように、インデックスの同時更新を "より快適" にするのではなく（B-Tree をすぐに再バランスしないことを決定できるため、それによって Skip-List とほぼ同じ同時パフォーマンスを獲得できます）、むしろ。 スキップ リストのおかげで (遅延があってもなくても) バランシング作業 (最終的に) B-Tree によって必要とされる (実際には、回答が示すように/参照するように、B-Tree と [マルチレベル] Skip-List の間には、どちらも正しく行われれば、おそらくほとんどパフォーマンスの違いはありません。)。