Lucene ソースコードリーディングメモ

今日はmixiでLuceneソースコードリーディングに参加して、Scorerの部分を読んでました。

Scorerについて

Scorerは与えられたクエリに対して文章をidの昇順で返すような抽象クラスです。
検索で使われるメインの部分は以下のようになっており、collectorに対してnextDoc()によって求まる適合した文章を渡すというのを繰り返しています。

  protected boolean score(Collector collector, int max, int firstDocID) throws IOException {
    collector.setScorer(this);
    int doc = firstDocID;
    while (doc < max) {
      collector.collect(doc);
      doc = nextDoc();
    }
    return doc != NO_MORE_DOCS;
  }

nextDoc()の実装例

DisjunctionSumScorerは複数のScorerが与えられたときminimumNrMatchers以上の個数のScorerに対して適合する文章番号を返します。

複数のScorerはScorerDocQueueというScorerのためのPriorityQueueによって管理されます。
これはScorerの文章id順にScorerを保持します。nextDoc()の実装は基本的にはadvanceAfterCurrentを呼ぶだけになっています。

advanceAfterCurrentの実装は以下のようになっています。

  protected boolean advanceAfterCurrent() throws IOException {
    do { // repeat until minimum nr of matchers
      currentDoc = scorerDocQueue.topDoc();
      currentScore = scorerDocQueue.topScore();
      nrMatchers = 1;
      do { // Until all subscorers are after currentDoc
        if (!scorerDocQueue.topNextAndAdjustElsePop()) {
          if (scorerDocQueue.size() == 0) {
            break; // nothing more to advance, check for last match.
          }
        }
        if (scorerDocQueue.topDoc() != currentDoc) {
          break; // All remaining subscorers are after currentDoc.
        }
        currentScore += scorerDocQueue.topScore();
        nrMatchers++;
      } while (true);
      
      if (nrMatchers >= minimumNrMatchers) {
        return true;
      } else if (scorerDocQueue.size() < minimumNrMatchers) {
        return false;
      }
    } while (true);
  }

ここでtopNextAndAdjustElsePopというのはpriorityQueueの先頭、すなわちidの最も小さいScorerの文章番号を進めて、priorityQueueの制約条件を維持します。もしScorerの次の文章が存在しない場合、priorityQueueからの除去も行います。

Scorerは他にも全てのScorerにマッチする文章のみ返すConjunctionScorer,Scorer A,BのうちAにはマッチするがBにはマッチしない文章のみ返すReqExclScorer, これらの組み合わせによりBooleanQueryを実現するBooleanScorer2, 通常の転置インデックスに近い動きをするTermScorerなどがあります。

実際類似検索を行うときには複数のTermScorerを閾値1のDisjunctionSumScorerを使って列挙する形になります。