Lucene がやっていることをまとめてみた。

## Lucene のソースコードを読んでみました。

Java の勉強をしたいと思って、Lucene の ソースコードを読んでみました。簡単に言えば、下のコードの流れのソースコードを１つ１つ拾った感じです。

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.io.IOException;
import java.io.File;

import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.codecs.simpletext.SimpleTextCodec;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field.Store;
import org.apache.lucene.document.TextField;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.queryparser.classic.QueryParser;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FSDirectory;
import org.apache.lucene.queryparser.classic.ParseException;
import org.apache.lucene.util.Version;

public class LuceneSimpleTextCodecSample {

	private static File plaintextDir;
	private static String INDEX_ROOT_FOLDER = "/Users/coffeecup/Documents/programming/Java/lucene/lucene/lucene/core/src/java";

    private static File assureDirectoryExists(File dir) {
        if (!dir.exists()) {
            dir.mkdirs();
        }
        return dir;
    }

    private static void indexPlaintextDocuments() {
		plaintextDir = assureDirectoryExists(new File(INDEX_ROOT_FOLDER, "lucene-plaintext"));
		// 
		StandardAnalyzer analyzer = new StandardAnalyzer();
		IndexWriterConfig config = new IndexWriterConfig(analyzer);
		config.setOpenMode(IndexWriterConfig.OpenMode.CREATE);
		config.setCodec(new SimpleTextCodec());
		try {
			Directory luceneDir = FSDirectory.open(plaintextDir.toPath());
			IndexWriter writer = new IndexWriter(luceneDir, config);
			writer.addDocument(Arrays.asList(
					new TextField("title", "The title of my first document", Store.YES),
					new TextField("content", "The content of the first document", Store.YES)
			));
			writer.addDocument(Arrays.asList(
					new TextField("title", "The title of my second document", Store.YES),
					new TextField("content", "The content of the second document", Store.YES)
			));
			writer.close();
		} catch (IOException e) {
			System.out.println(e);
		}
    }

    private static void searchPlaintextDocuments() throws IOException {
    	plaintextDir = assureDirectoryExists(new File(INDEX_ROOT_FOLDER, "lucene-plaintext"));
    	String searchText = "second";
    	//
    	Analyzer analyzer = new StandardAnalyzer();
    	try {
	    	QueryParser parser = new QueryParser("title", analyzer);
	    	Query query = parser.parse(searchText);

	    	Directory indexDir = FSDirectory.open(plaintextDir.toPath());
	    	IndexReader indexReader = DirectoryReader.open(indexDir);
	 		IndexSearcher indexSearcher = new IndexSearcher(indexReader);
	    	//
	    	TopDocs results = indexSearcher.search(query, 10);
	    	System.out.println(results.totalHits + " documents found.");
    		for (ScoreDoc scoredoc : results.scoreDocs) {
    			Document doc = indexSearcher.doc(scoredoc.doc);
    			System.out.println("File: " + doc.get("content"));
    		}
    		
    		
    	} catch(ParseException e) {
    		System.out.println(e);
    	}
    }

	public static void main(String[] args) throws IOException {
		indexPlaintextDocuments();
		searchPlaintextDocuments();
	}
}
```

ここでは、このコードのソースコードの流れを簡単に追っていきたいと思います（但し、低レイヤー部分は読み飛ばした部分もあります）。
また、過去に投稿した記事もあるので新しい部分は、`IndexReader` と `IndexSearcher` の部分になります。

## Analyzer

[該当コード](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/analysis/standard/StandardAnalyzer.java)

```java
Analyzer analyzer = new StandardAnalyzer();
```

[attribute](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/util/AttributeSource.java#L209) やらで、[該当単語を取得したり](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/analysis/tokenattributes/CharTermAttribute.java)、[文字の位置を取得したり](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/analysis/tokenattributes/OffsetAttribute.java)、していて複雑ですが、
簡単に言えば、[Tokenizer](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/analysis/Tokenizer.java) で input を入力して、それを [incrementToken](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/analysis/standard/StandardTokenizer.java#L145-L168) で [JFlex](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/analysis/standard/StandardTokenizerImpl.jflex) でトークナイズしています。

トークナイズは、少しだけチューニングできます。詳しくは、

https://qiita.com/YmBIgo/items/6c835cc0384a4cbdbceb

https://qiita.com/YmBIgo/items/c4dc85ecea51e901382a

などを見てください。

## IndexWriter

```java
		IndexWriterConfig config = new IndexWriterConfig(analyzer);
		config.setOpenMode(IndexWriterConfig.OpenMode.CREATE);
		config.setCodec(new SimpleTextCodec());
		try {
			Directory luceneDir = FSDirectory.open(plaintextDir.toPath());
			IndexWriter writer = new IndexWriter(luceneDir, config);
			writer.addDocument(Arrays.asList(
					new TextField("title", "The title of my first document", Store.YES),
					new TextField("content", "The content of the first document", Store.YES)
			));
			writer.addDocument(Arrays.asList(
					new TextField("title", "The title of my second document", Store.YES),
					new TextField("content", "The content of the second document", Store.YES)
			));
			writer.close();
		} catch (IOException e) {
			System.out.println(e);
		}
```

ここでやっていることは、`IndexWriterConfig` で 書き出していくインデックス の設定を初期化します。ここでは 暗号化の方法を、`SimpleTextCodec` にしています。
このインデックスの書き出しは、[SimpleTextStoredFieldsWriter](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextStoredFieldsWriter.java) で行っていて、その呼び出しは [IndexingChain](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/index/IndexingChain.java) の `storedFieldsConsumer` 行っています。
詳しくは、

https://qiita.com/YmBIgo/items/e3f6c5427705f6345e76

を見てみてください。

## QueryParser

```java
QueryParser parser = new QueryParser("title", analyzer);
```

ここの実装は、JavaCC を使っていて、[ここ](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/queryparser/src/java/org/apache/lucene/queryparser/classic/QueryParser.jj) に実装が載っています。
詳細は、

https://qiita.com/YmBIgo/items/0f2cbba5b73ef72a9bac

に譲りますが、Query でパースした結果が出てきます。

## IndexReader

```java
Directory indexDir = FSDirectory.open(plaintextDir.toPath());
IndexReader indexReader = DirectoryReader.open(indexDir);
```

ここでは、ファイルを開いています。
ファイルを開いているのが、[FSDirectory.open](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/store/FSDirectory.java#L160-L166) の [MMapDirectory](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/store/MMapDirectory.java#L76) の [lookupProvider](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/store/MMapDirectory.java#L307) で呼び出される [org.apache.lucene.store.MemorySegmentIndexInputProvider](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java19/org/apache/lucene/store/MemorySegmentIndexInputProvider.java) から openInput 関数になり、readByte などの関数が [MemorySegmentIndexInput](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java19/org/apache/lucene/store/MemorySegmentIndexInput.java) に定義されています（これの継承元である [DataInput](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/store/DataInput.java#L40) を使うこともあります ）。
`DirectoryReader.open` では、[ここ](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/index/StandardDirectoryReader.java#L70-L71) がスタート地点になり、主に doBody の内容を回しています。
まず

```java
SegmentInfos sis =
    SegmentInfos.readCommit(directory, segmentFileName, minSupportedMajorVersion);
```

の部分で、インデックスを作ったフォルダでの `segments_` のファイルを開きます。この [readCommit](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/index/SegmentInfos.java#L307) を見れば分かりますが、ここでは Segmentファイルが正しいかどうか（Magic）・Codec の種類・Lucene のバージョンを取得しています。詳細は、[公式](https://lucene.apache.org/core/9_0_0/core/org/apache/lucene/index/SegmentInfos.html) を見れば概要が見て取れますが、[parseSegmentInfos](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/index/SegmentInfos.java#L371) で [公式](https://lucene.apache.org/core/9_0_0/core/org/apache/lucene/index/SegmentInfos.html) で言うところの SegName, SegID, SegCodec, DelGen, DeletionCount, FieldInfosGen, DocValuesGen, UpdatesFiles をパースしています。そして、その結果を `infos.add(siPerCommit);` で追加しています。
その結果は、`SegmentInfos sis` に代入されて、

```java
          for (int i = sis.size() - 1; i >= 0; i--) {
            readers[i] =
                new SegmentReader(sis.info(i), sis.getIndexCreatedVersionMajor(), IOContext.READ);
          }
```

の for文 で SegmentInfos ごとに SegmentReader が初期化されます。この SegmentReader で重要なのが、SegmentCoreReaders で ここで 主たるインデックスファイルである、`scf` ファイルを開いています。
ここで、

```java
cfsDir = cfsReader = codec.compoundFormat().getCompoundReader(dir, si.info, context);
```

のように [SimpleTextCompoundFormat](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextCompoundFormat.java) が出てくるのですが、その最初の方の 

```java
    // first get to TOC:
    DecimalFormat df =
        new DecimalFormat(OFFSETPATTERN, DecimalFormatSymbols.getInstance(Locale.ROOT));
    long pos = in.length() - TABLEPOS.length - OFFSETPATTERN.length() - 1;
    in.seek(pos);
    SimpleTextUtil.readLine(in, scratch);
    assert StringHelper.startsWith(scratch.get(), TABLEPOS);
    long tablePos = -1;
    try {
      tablePos = df.parse(stripPrefix(scratch, TABLEPOS)).longValue();
    } catch () ...
```

を見れば、scfファイルの最後から内容を取って来ているのが見て取れます。結果は、fileNames, StartOffsets, endOffsets の配列を生成していますね。これらの配列を使って、fileLength (長さ取得)・openInput (インプット取得, ポインター利用) などをしています。
この後は、それぞれ、coreFieldInfos は infファイル部分を、fields は pstファイル部分からフィールド情報を、fieldsReaderOrig は fldファイル部分から各文書のポインタ情報を、と情報を取得しています。

そして最後に `StandardDirectoryReader` に戻り、StandardDirectoryReader の初期化をしてその結果を返しています。ここまでが、DirectoryReader.open の概要でした。


## IndexSearcher

最後に、

```java
	 		IndexSearcher indexSearcher = new IndexSearcher(indexReader);
	    	//
	    	TopDocs results = indexSearcher.search(query, 10);
	    	System.out.println(results.totalHits + " documents found.");
    		for (ScoreDoc scoredoc : results.scoreDocs) {
    			Document doc = indexSearcher.doc(scoredoc.doc);
    			System.out.println("File: " + doc.get("content"));
    		}
```

の部分を読んでみましょう。主に見ていくのは、IndexSearcher の初期化部分 `new IndexSearcher(indexReader)` と、検索部分 `indexSearcher.search(query, 10)` です。

まずは、IndexSearcher の初期化を見てみましょう。
読んでみると、

```java
this(r.getContext(), executor);
```

の `r.getContext()` という部分に当たると思います。これは、DirectoryReader が継承している CompositeReader のメソッドで、CompositeReaderContext.create で Builder を開いています。それも、LeafReaderContext を初期化して返しているだけなので内容は簡単ですね。後は普通に初期化しているだけです。

---

では、search を見てみましょう。
search は、まず初見では [searchAfterメソッド](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java#L451) の CollectorManager が分かりづらいと思いますが、この中のオーバーライドした `newCollector` では 検索結果の文書ID から 結果の型である ScoreDoc を生成して、`reduce` では検索結果を TopDoc という型でまとめています。
search を全体で見ると、大きく分けて２つ大きなことをしている部分があります。
まず、[ここ](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java#L655)にある createWeight

```java
final Weight weight = createWeight(query, firstCollector.scoreMode(), 1);
```

次に、[ここ](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java#L744) にある `scorer.score(...)`

```java
scorer.score(leafCollector, ctx.reader().getLiveDocs());
```

そして、１つ目の `createWeight` では ある単語が文書に出てくる回数などの統計情報を、２つ目の `scorer.score(...)` では クエリに対して実際に出てきた文書の情報を取得します。
ここではクエリは `termQuery` を使っていることで進めますが、それぞれで呼び出される重要なメソッドが、
```java
reader.terms(field)
```
です。`reader` は `IndexSearcher.leaves` から取って来ていますが、基本的には前に出てきた `CompositeReaderContext.create ` で開いた Builder の内容を見れば分かりますね 単純に LeafReaderContext が入っているだけなのが分かりますね（[ここら辺](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/index/LeafReaderContext.java#L44)）。

この terms がどこから来ているのかが分かりづらいのですが、これは [CodecReader](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/index/CodecReader.java#L107) から来ています。
内容は、下の通りになります。

```java
  public final Terms terms(String field) throws IOException {
    ensureOpen();
    FieldInfo fi = getFieldInfos().fieldInfo(field);
    if (fi == null || fi.getIndexOptions() == IndexOptions.NONE) {
      // Field does not exist or does not index postings
      return null;
    }
    return getPostingsReader().terms(field);
  }
```

getFileldInfos は [SegmentReader](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/index/SegmentReader.java#L230) の部分で 上では省略しましたが `si.info.getCodec().fieldInfosFormat();` の内容になります。
むしろ重要なのは、`return getPostingsReader().terms(field);` の部分になって、ここで 上で説明した core.fields を呼び出しています。その terms は [ここ](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextFieldsReader.java#L843) にあって、ここで `SimpleTextTerms.loadTerms` (コードは[ここ](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextFieldsReader.java#L677)) を使って 単語(term)とそれに対応する 出て来た回数 と 出て来た文書数 を取得できるインデックスを作成しています。
インデックスを作成している様子は、[ここのコード](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextFieldsReader.java#L722-L726)

```java
            fstCompiler.add(
                Util.toIntsRef(lastTerm.get(), scratchIntsRef),
                outputs.newPair(
                    outputsOuter.newPair(lastDocsStart, skipPointer),
                    outputsInner.newPair((long) docFreq, totalTermFreq)));
```

から見てとることができます。
そこからこのインデックス fst を使って `termsEnum.seekExact(term.bytes()))` をして、`interetor()` から上の fst の[構造体を取得](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextFieldsReader.java#L146-L153)しています。
これらの情報をもとに Weight を作ります。
ここまでが Weight 部分の説明でした。

次に、Score、つまり文書IDの一覧の取得の部分を読んでみます。
Score は [void が返り値の search](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java#L719) で計算されます。
`leafCollector = collector.getLeafCollector(ctx);` で Collector を初期化した後で、`weight.bulkScorer` で termWeight の `scorer` を呼び出します（コードは[こちら](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/search/TermQuery.java#L102)）。
そうすると上の fst の時と同じように

```java
final TermsEnum termsEnum = context.reader().terms(term.field()).iterator();
```

が呼ばれたのが見て取れると思います（コードは[こちら](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/search/TermQuery.java#L144)）。
この Scorer の

```java
            termsEnum.postings(
                null, scoreMode.needsScores() ? PostingsEnum.FREQS : PostingsEnum.NONE),
```

部分の posting が `SimpleTextDocsEnum` (コードだと[ここ](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextFieldsReader.java#L275)) という `readDoc` が 文書ID(DOC) と頻出度(FREQ) を取得していきます。
そして、この `readDoc` を使った `nextDoc` を呼び出しているのが、`defaultBulkScorer.score` (コードは[ここ](https://github.com/apache/lucene/blob/44b4602776a63d93896d887e5000c9e3ca7c3119/lucene/core/src/java/org/apache/lucene/search/Weight.java#L224)) で、ここの `ScoreAll` の

```java
        for (int doc = iterator.nextDoc();
            doc != DocIdSetIterator.NO_MORE_DOCS;
            doc = iterator.nextDoc()) {
          if ((acceptDocs == null || acceptDocs.get(doc)) && twoPhase.matches()) {
            collector.collect(doc);
          }
        }
```

で、nextDoc がある限り、collctor で docID を collect しています。
その後は、PriorityQueue の HitQueue で docID と score を ScoreDoc に変えて、最後の reduce で結果をまとめていますが、詳細は、

https://qiita.com/YmBIgo/items/fba84cf5e7babab9d4c3

の記事に譲ります。

---

ここまでが、Lucene が Analyzer から IndexSearcher を実行するまでの流れでした。
ここまで読むのに毎日少しずつ読んで１ヶ月ちょっとかかったんですが、読んでみると意外と分かる内容でできていますね。
今後は、fst や set や AttributeSource など読み飛ばした部分を読むか、BooleanQuery など別の機能を読むか悩みどころです。

ここまでありがとうございました。