ApacheLuceneで使用されている文字列照合アルゴリズムについて知りたいです。私はここで与えられたluceneによって使用されるインデックスファイル形式を調べてきました。luceneは、テキストに出現するすべての単語を、各ドキュメントで出現する頻度とともにそのまま保存しているようです。しかし、私が知る限り、効率的な文字列照合を行うには、ドキュメントに含まれる単語を前処理する必要があります。
例：「iamrohitbangaはstackoverflowのユーザーです」を検索します（あいまい一致を使用）
いくつかの文書で。
「rohitbanga」という文字列を含むドキュメントがある可能性があります
部分文字列rohitとbangaが検索文字列に存在することを見つけるために、いくつかの効率的な部分文字列マッチングを使用します。
それがどのアルゴリズムか知りたい。また、Java APIで関数呼び出しがトリガーする前処理を行う場合も、
Yuval が説明したように、一般的に Lucene は完全一致を対象としています (インデックス時とクエリ時の両方でアナライザーを使用して用語を正規化することによって)。
Lucene トランク コード (まだリリースされたバージョンではありません) では、実際には、正規表現、ワイルドカード、およびファジーなどの不正確な一致に対してサフィックス ツリーが使用されています。
これが機能する方法は、Lucene 用語辞書自体が実際にはサフィックス ツリーの形式であることです。これは、いくつかの場所で言及したファイル形式で確認できます。
したがって、前の用語のテキストが「bone」で、用語が「boy」の場合、PrefixLength は 2 で、接尾辞は「y」です。
ターム情報インデックスは、このツリーを特定の間隔で (デフォルトでは 128 タームごとに) インデックス付けすることにより、「ランダム アクセス」を提供します。
低レベルでは接尾辞ツリーですが、より高いレベルでは、これらのプロパティ (主に IndexReader.terms で指定されたもの) を利用して、用語辞書を決定論的有限状態オートマトン (DFA) として扱います。
指定された用語で始まるすべての用語の列挙を返します。指定された用語が存在しない場合、列挙は、指定された用語よりも大きい最初の用語に配置されます。列挙は Term.compareTo() によって順序付けられます。各用語は、列挙内でその前にあるすべての用語よりも大きくなります。
Regex、Wildcard、Fuzzy などの不正確なクエリ自体も DFA として定義されており、「一致」は単純に DFA の交差です。
Lucene の基本設計では、正確な文字列一致を使用するか、Analyzerを使用して同等の文字列を定義します。アナライザーは、テキストをインデックス可能なトークンに分割します。このプロセス中に、同等の文字列を照合する場合があります (例: 大文字と小文字、語幹文字列、分音記号の削除など)。結果のトークンは、辞書とドキュメント内のトークンの投稿リストとしてインデックスに格納されます。したがって、KMP などの文字列照合アルゴリズムを使用しなくても、Lucene インデックスを作成して使用できます。ただし、FuzzyQueryとWildCardQueryは似たようなものを使用しており、最初に一致する用語を検索し、次にそれらを使用して完全に一致します。この問題に対する新しい効率的なアプローチについては、 AutomatonQuery に関する Robert Muir のブログ投稿を参照してください。
ご指摘のとおり、Lucene はドキュメント内で発生した用語のリストのみを保存します。Lucene がこれらの単語をどのように抽出するかは、あなた次第です。デフォルトの lucene アナライザーは、スペースで区切られた単語を単純に分割します。たとえば、ソース文字列 'iamrohitbanga' に対して、'iamrohitbanga'、'i'、'am'、'rohit'、'banga' の 5 つのトークンを生成する独自の実装を作成できます。
TokenFilter クラスの lucene API ドキュメントを参照してください。