lucene-java-3.5.0/lucene/src/java/org/apache/lucene/search/DisjunctionMaxScorer.java

   1 package org.apache.lucene.search;
   2
   3 /**
   4  * Copyright 2004 The Apache Software Foundation
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19 import java.io.IOException;
  20
  21 /**
  22  * The Scorer for DisjunctionMaxQuery.  The union of all documents generated by the the subquery scorers
  23  * is generated in document number order.  The score for each document is the maximum of the scores computed
  24  * by the subquery scorers that generate that document, plus tieBreakerMultiplier times the sum of the scores
  25  * for the other subqueries that generate the document.
  26  */
  27 class DisjunctionMaxScorer extends Scorer {
  28
  29   /* The scorers for subqueries that have remaining docs, kept as a min heap by number of next doc. */
  30   private final Scorer[] subScorers;
  31   private int numScorers;
  32   /* Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result. */
  33   private final float tieBreakerMultiplier;
  34   private int doc = -1;
  35
  36   /* Used when scoring currently matching doc. */
  37   private float scoreSum;
  38   private float scoreMax;
  39
  40   /**
  41    * Creates a new instance of DisjunctionMaxScorer
  42    *
  43    * @param weight
  44    *          The Weight to be used.
  45    * @param tieBreakerMultiplier
  46    *          Multiplier applied to non-maximum-scoring subqueries for a
  47    *          document as they are summed into the result.
  48    * @param similarity
  49    *          -- not used since our definition involves neither coord nor terms
  50    *          directly
  51    * @param subScorers
  52    *          The sub scorers this Scorer should iterate on
  53    * @param numScorers
  54    *          The actual number of scorers to iterate on. Note that the array's
  55    *          length may be larger than the actual number of scorers.
  56    */
  57   public DisjunctionMaxScorer(Weight weight, float tieBreakerMultiplier,
  58       Similarity similarity, Scorer[] subScorers, int numScorers) throws IOException {
  59     super(similarity, weight);
  60     this.tieBreakerMultiplier = tieBreakerMultiplier;
  61     // The passed subScorers array includes only scorers which have documents
  62     // (DisjunctionMaxQuery takes care of that), and their nextDoc() was already
  63     // called.
  64     this.subScorers = subScorers;
  65     this.numScorers = numScorers;
  66
  67     heapify();
  68   }
  69
  70   @Override
  71   public int nextDoc() throws IOException {
  72     if (numScorers == 0) return doc = NO_MORE_DOCS;
  73     while (subScorers[0].docID() == doc) {
  74       if (subScorers[0].nextDoc() != NO_MORE_DOCS) {
  75         heapAdjust(0);
  76       } else {
  77         heapRemoveRoot();
  78         if (numScorers == 0) {
  79           return doc = NO_MORE_DOCS;
  80         }
  81       }
  82     }
  83
  84     return doc = subScorers[0].docID();
  85   }
  86
  87   @Override
  88   public int docID() {
  89     return doc;
  90   }
  91
  92   /** Determine the current document score.  Initially invalid, until {@link #nextDoc()} is called the first time.
  93    * @return the score of the current generated document
  94    */
  95   @Override
  96   public float score() throws IOException {
  97     int doc = subScorers[0].docID();
  98     scoreSum = scoreMax = subScorers[0].score();
  99     int size = numScorers;
 100     scoreAll(1, size, doc);
 101     scoreAll(2, size, doc);
 102     return scoreMax + (scoreSum - scoreMax) * tieBreakerMultiplier;
 103   }
 104
 105   // Recursively iterate all subScorers that generated last doc computing sum and max
 106   private void scoreAll(int root, int size, int doc) throws IOException {
 107     if (root < size && subScorers[root].docID() == doc) {
 108       float sub = subScorers[root].score();
 109       scoreSum += sub;
 110       scoreMax = Math.max(scoreMax, sub);
 111       scoreAll((root<<1)+1, size, doc);
 112       scoreAll((root<<1)+2, size, doc);
 113     }
 114   }
 115
 116   @Override
 117   public int advance(int target) throws IOException {
 118     if (numScorers == 0) return doc = NO_MORE_DOCS;
 119     while (subScorers[0].docID() < target) {
 120       if (subScorers[0].advance(target) != NO_MORE_DOCS) {
 121         heapAdjust(0);
 122       } else {
 123         heapRemoveRoot();
 124         if (numScorers == 0) {
 125           return doc = NO_MORE_DOCS;
 126         }
 127       }
 128     }
 129     return doc = subScorers[0].docID();
 130   }
 131
 132   // Organize subScorers into a min heap with scorers generating the earliest document on top.
 133   private void heapify() {
 134     for (int i = (numScorers >> 1) - 1; i >= 0; i--) {
 135       heapAdjust(i);
 136     }
 137   }
 138
 139   /* The subtree of subScorers at root is a min heap except possibly for its root element.
 140    * Bubble the root down as required to make the subtree a heap.
 141    */
 142   private void heapAdjust(int root) {
 143     Scorer scorer = subScorers[root];
 144     int doc = scorer.docID();
 145     int i = root;
 146     while (i <= (numScorers >> 1) - 1) {
 147       int lchild = (i << 1) + 1;
 148       Scorer lscorer = subScorers[lchild];
 149       int ldoc = lscorer.docID();
 150       int rdoc = Integer.MAX_VALUE, rchild = (i << 1) + 2;
 151       Scorer rscorer = null;
 152       if (rchild < numScorers) {
 153         rscorer = subScorers[rchild];
 154         rdoc = rscorer.docID();
 155       }
 156       if (ldoc < doc) {
 157         if (rdoc < ldoc) {
 158           subScorers[i] = rscorer;
 159           subScorers[rchild] = scorer;
 160           i = rchild;
 161         } else {
 162           subScorers[i] = lscorer;
 163           subScorers[lchild] = scorer;
 164           i = lchild;
 165         }
 166       } else if (rdoc < doc) {
 167         subScorers[i] = rscorer;
 168         subScorers[rchild] = scorer;
 169         i = rchild;
 170       } else {
 171         return;
 172       }
 173     }
 174   }
 175
 176   // Remove the root Scorer from subScorers and re-establish it as a heap
 177   private void heapRemoveRoot() {
 178     if (numScorers == 1) {
 179       subScorers[0] = null;
 180       numScorers = 0;
 181     } else {
 182       subScorers[0] = subScorers[numScorers - 1];
 183       subScorers[numScorers - 1] = null;
 184       --numScorers;
 185       heapAdjust(0);
 186     }
 187   }
 188
 189 }