Lucene.Net  3.0.3
Lucene.Net is a port of the Lucene search engine library, written in C# and targeted at .NET runtime users.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Pages
DisjunctionMaxScorer.cs
Go to the documentation of this file.
1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 using System;
19 
20 namespace Lucene.Net.Search
21 {
22 
23  /// <summary> The Scorer for DisjunctionMaxQuery's. The union of all documents generated by the the subquery scorers
24  /// is generated in document number order. The score for each document is the maximum of the scores computed
25  /// by the subquery scorers that generate that document, plus tieBreakerMultiplier times the sum of the scores
26  /// for the other subqueries that generate the document.
27  /// </summary>
29  {
30 
31  /* The scorers for subqueries that have remaining docs, kept as a min heap by number of next doc. */
32  private Scorer[] subScorers;
33  private int numScorers;
34  /* Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result. */
35  private float tieBreakerMultiplier;
36  private int doc = - 1;
37 
38  /// <summary> Creates a new instance of DisjunctionMaxScorer
39  ///
40  /// </summary>
41  /// <param name="tieBreakerMultiplier">Multiplier applied to non-maximum-scoring subqueries for a
42  /// document as they are summed into the result.
43  /// </param>
44  /// <param name="similarity">-- not used since our definition involves neither coord nor terms
45  /// directly
46  /// </param>
47  /// <param name="subScorers">The sub scorers this Scorer should iterate on
48  /// </param>
49  /// <param name="numScorers">The actual number of scorers to iterate on. Note that the array's
50  /// length may be larger than the actual number of scorers.
51  /// </param>
52  public DisjunctionMaxScorer(float tieBreakerMultiplier, Similarity similarity, Scorer[] subScorers, int numScorers):base(similarity)
53  {
54 
55  this.tieBreakerMultiplier = tieBreakerMultiplier;
56  // The passed subScorers array includes only scorers which have documents
57  // (DisjunctionMaxQuery takes care of that), and their nextDoc() was already
58  // called.
59  this.subScorers = subScorers;
60  this.numScorers = numScorers;
61 
62  Heapify();
63  }
64 
65  public override int NextDoc()
66  {
67  if (numScorers == 0)
68  return doc = NO_MORE_DOCS;
69  while (subScorers[0].DocID() == doc)
70  {
71  if (subScorers[0].NextDoc() != NO_MORE_DOCS)
72  {
73  HeapAdjust(0);
74  }
75  else
76  {
77  HeapRemoveRoot();
78  if (numScorers == 0)
79  {
80  return doc = NO_MORE_DOCS;
81  }
82  }
83  }
84 
85  return doc = subScorers[0].DocID();
86  }
87 
88  public override int DocID()
89  {
90  return doc;
91  }
92 
93  /// <summary>Determine the current document score. Initially invalid, until <see cref="NextDoc()" /> is called the first time.</summary>
94  /// <returns> the score of the current generated document
95  /// </returns>
96  public override float Score()
97  {
98  int doc = subScorers[0].DocID();
99  float[] sum = new float[]{subScorers[0].Score()}, max = new float[]{sum[0]};
100  int size = numScorers;
101  ScoreAll(1, size, doc, sum, max);
102  ScoreAll(2, size, doc, sum, max);
103  return max[0] + (sum[0] - max[0]) * tieBreakerMultiplier;
104  }
105 
106  // Recursively iterate all subScorers that generated last doc computing sum and max
107  private void ScoreAll(int root, int size, int doc, float[] sum, float[] max)
108  {
109  if (root < size && subScorers[root].DocID() == doc)
110  {
111  float sub = subScorers[root].Score();
112  sum[0] += sub;
113  max[0] = System.Math.Max(max[0], sub);
114  ScoreAll((root << 1) + 1, size, doc, sum, max);
115  ScoreAll((root << 1) + 2, size, doc, sum, max);
116  }
117  }
118 
119  public override int Advance(int target)
120  {
121  if (numScorers == 0)
122  return doc = NO_MORE_DOCS;
123  while (subScorers[0].DocID() < target)
124  {
125  if (subScorers[0].Advance(target) != NO_MORE_DOCS)
126  {
127  HeapAdjust(0);
128  }
129  else
130  {
131  HeapRemoveRoot();
132  if (numScorers == 0)
133  {
134  return doc = NO_MORE_DOCS;
135  }
136  }
137  }
138  return doc = subScorers[0].DocID();
139  }
140 
141  // Organize subScorers into a min heap with scorers generating the earliest document on top.
142  private void Heapify()
143  {
144  for (int i = (numScorers >> 1) - 1; i >= 0; i--)
145  {
146  HeapAdjust(i);
147  }
148  }
149 
150  /* The subtree of subScorers at root is a min heap except possibly for its root element.
151  * Bubble the root down as required to make the subtree a heap.
152  */
153  private void HeapAdjust(int root)
154  {
155  Scorer scorer = subScorers[root];
156  int doc = scorer.DocID();
157  int i = root;
158  while (i <= (numScorers >> 1) - 1)
159  {
160  int lchild = (i << 1) + 1;
161  Scorer lscorer = subScorers[lchild];
162  int ldoc = lscorer.DocID();
163  int rdoc = System.Int32.MaxValue, rchild = (i << 1) + 2;
164  Scorer rscorer = null;
165  if (rchild < numScorers)
166  {
167  rscorer = subScorers[rchild];
168  rdoc = rscorer.DocID();
169  }
170  if (ldoc < doc)
171  {
172  if (rdoc < ldoc)
173  {
174  subScorers[i] = rscorer;
175  subScorers[rchild] = scorer;
176  i = rchild;
177  }
178  else
179  {
180  subScorers[i] = lscorer;
181  subScorers[lchild] = scorer;
182  i = lchild;
183  }
184  }
185  else if (rdoc < doc)
186  {
187  subScorers[i] = rscorer;
188  subScorers[rchild] = scorer;
189  i = rchild;
190  }
191  else
192  {
193  return ;
194  }
195  }
196  }
197 
198  // Remove the root Scorer from subScorers and re-establish it as a heap
199  private void HeapRemoveRoot()
200  {
201  if (numScorers == 1)
202  {
203  subScorers[0] = null;
204  numScorers = 0;
205  }
206  else
207  {
208  subScorers[0] = subScorers[numScorers - 1];
209  subScorers[numScorers - 1] = null;
210  --numScorers;
211  HeapAdjust(0);
212  }
213  }
214  }
215 }