DisjunctionMaxScorer.cs
上传用户:zhangkuixh
上传日期:2013-09-30
资源大小:5473k
文件大小:7k
源码类别:

搜索引擎

开发平台:

C#

  1. /*
  2.  * Copyright 2005 The Apache Software Foundation
  3.  * 
  4.  * Licensed under the Apache License, Version 2.0 (the "License");
  5.  * you may not use this file except in compliance with the License.
  6.  * You may obtain a copy of the License at
  7.  * 
  8.  * http://www.apache.org/licenses/LICENSE-2.0
  9.  * 
  10.  * Unless required by applicable law or agreed to in writing, software
  11.  * distributed under the License is distributed on an "AS IS" BASIS,
  12.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13.  * See the License for the specific language governing permissions and
  14.  * limitations under the License.
  15.  */
  16. using System;
  17. namespace Lucene.Net.Search
  18. {
  19. /// <summary> The Scorer for DisjunctionMaxQuery's.  The union of all documents generated by the the subquery scorers
  20. /// is generated in document number order.  The score for each document is the maximum of the scores computed
  21. /// by the subquery scorers that generate that document, plus tieBreakerMultiplier times the sum of the scores
  22. /// for the other subqueries that generate the document.
  23. /// </summary>
  24. /// <author>  Chuck Williams
  25. /// </author>
  26. class DisjunctionMaxScorer : Scorer
  27. {
  28. /* The scorers for subqueries that have remaining docs, kept as a min heap by number of next doc. */
  29. private System.Collections.ArrayList subScorers = new System.Collections.ArrayList();
  30. /* Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result. */
  31. private float tieBreakerMultiplier;
  32. private bool more = false; // True iff there is a next document
  33. private bool firstTime = true; // True iff next() has not yet been called
  34. /// <summary>Creates a new instance of DisjunctionMaxScorer</summary>
  35. /// <param name="tieBreakerMultiplier">Multiplier applied to non-maximum-scoring subqueries for a document as they are summed into the result.
  36. /// </param>
  37. /// <param name="similarity">-- not used since our definition involves neither coord nor terms directly 
  38. /// </param>
  39. public DisjunctionMaxScorer(float tieBreakerMultiplier, Similarity similarity) : base(similarity)
  40. {
  41. this.tieBreakerMultiplier = tieBreakerMultiplier;
  42. }
  43. /// <summary>Add the scorer for a subquery</summary>
  44. /// <param name="scorer">the scorer of a subquery of our associated DisjunctionMaxQuery
  45. /// </param>
  46. public virtual void  Add(Scorer scorer)
  47. {
  48. if (scorer.Next())
  49. {
  50. // Initialize and retain only if it produces docs
  51. subScorers.Add(scorer);
  52. more = true;
  53. }
  54. }
  55. /// <summary>Generate the next document matching our associated DisjunctionMaxQuery.</summary>
  56. /// <returns> true iff there is a next document
  57. /// </returns>
  58. public override bool Next()
  59. {
  60. if (!more)
  61. return false;
  62. if (firstTime)
  63. {
  64. Heapify();
  65. firstTime = false;
  66. return true; // more would have been false if no subScorers had any docs
  67. }
  68. // Increment all generators that generated the last doc and adjust the heap.
  69. int lastdoc = ((Scorer) subScorers[0]).Doc();
  70. do 
  71. {
  72. if (((Scorer) subScorers[0]).Next())
  73. HeapAdjust(0);
  74. else
  75. {
  76. HeapRemoveRoot();
  77. if ((subScorers.Count == 0))
  78. return (more = false);
  79. }
  80. }
  81. while (((Scorer) subScorers[0]).Doc() == lastdoc);
  82. return true;
  83. }
  84. /// <summary>Determine the current document number.  Initially invalid, until {@link #Next()} is called the first time.</summary>
  85. /// <returns> the document number of the currently generated document
  86. /// </returns>
  87. public override int Doc()
  88. {
  89. return ((Scorer) subScorers[0]).Doc();
  90. }
  91. /// <summary>Determine the current document score.  Initially invalid, until {@link #Next()} is called the first time.</summary>
  92. /// <returns> the score of the current generated document
  93. /// </returns>
  94. public override float Score()
  95. {
  96. int doc = ((Scorer) subScorers[0]).Doc();
  97. float[] sum = new float[]{((Scorer) subScorers[0]).Score()}, max = new float[]{sum[0]};
  98. int size = subScorers.Count;
  99. ScoreAll(1, size, doc, sum, max);
  100. ScoreAll(2, size, doc, sum, max);
  101. return max[0] + (sum[0] - max[0]) * tieBreakerMultiplier;
  102. }
  103. // Recursively iterate all subScorers that generated last doc computing sum and max
  104. private void  ScoreAll(int root, int size, int doc, float[] sum, float[] max)
  105. {
  106. if (root < size && ((Scorer) subScorers[root]).Doc() == doc)
  107. {
  108. float sub = ((Scorer) subScorers[root]).Score();
  109. sum[0] += sub;
  110. max[0] = System.Math.Max(max[0], sub);
  111. ScoreAll((root << 1) + 1, size, doc, sum, max);
  112. ScoreAll((root << 1) + 2, size, doc, sum, max);
  113. }
  114. }
  115. /// <summary>Advance to the first document beyond the current whose number is greater than or equal to target.</summary>
  116. /// <param name="target">the minimum number of the next desired document
  117. /// </param>
  118. /// <returns> true iff there is a document to be generated whose number is at least target
  119. /// </returns>
  120. public override bool SkipTo(int target)
  121. {
  122. while (subScorers.Count > 0 && ((Scorer) subScorers[0]).Doc() < target)
  123. {
  124. if (((Scorer) subScorers[0]).SkipTo(target))
  125. HeapAdjust(0);
  126. else
  127. HeapRemoveRoot();
  128. }
  129. if ((subScorers.Count == 0))
  130. return (more = false);
  131. return true;
  132. }
  133. /// <summary>Explain a score that we computed.  UNSUPPORTED -- see explanation capability in DisjunctionMaxQuery.</summary>
  134. /// <param name="doc">the number of a document we scored
  135. /// </param>
  136. /// <returns> the Explanation for our score
  137. /// </returns>
  138. public override Explanation Explain(int doc)
  139. {
  140. throw new System.NotSupportedException();
  141. }
  142. // Organize subScorers into a min heap with scorers generating the earlest document on top.
  143. private void  Heapify()
  144. {
  145. int size = subScorers.Count;
  146. for (int i = (size >> 1) - 1; i >= 0; i--)
  147. HeapAdjust(i);
  148. }
  149. /* The subtree of subScorers at root is a min heap except possibly for its root element.
  150. * Bubble the root down as required to make the subtree a heap.
  151. */
  152. private void  HeapAdjust(int root)
  153. {
  154. Scorer scorer = (Scorer) subScorers[root];
  155. int doc = scorer.Doc();
  156. int i = root, size = subScorers.Count;
  157. while (i <= (size >> 1) - 1)
  158. {
  159. int lchild = (i << 1) + 1;
  160. Scorer lscorer = (Scorer) subScorers[lchild];
  161. int ldoc = lscorer.Doc();
  162. int rdoc = System.Int32.MaxValue, rchild = (i << 1) + 2;
  163. Scorer rscorer = null;
  164. if (rchild < size)
  165. {
  166. rscorer = (Scorer) subScorers[rchild];
  167. rdoc = rscorer.Doc();
  168. }
  169. if (ldoc < doc)
  170. {
  171. if (rdoc < ldoc)
  172. {
  173. subScorers[i] = rscorer;
  174. subScorers[rchild] = scorer;
  175. i = rchild;
  176. }
  177. else
  178. {
  179. subScorers[i] = lscorer;
  180. subScorers[lchild] = scorer;
  181. i = lchild;
  182. }
  183. }
  184. else if (rdoc < doc)
  185. {
  186. subScorers[i] = rscorer;
  187. subScorers[rchild] = scorer;
  188. i = rchild;
  189. }
  190. else
  191. return ;
  192. }
  193. }
  194. // Remove the root Scorer from subScorers and re-establish it as a heap
  195. private void  HeapRemoveRoot()
  196. {
  197. int size = subScorers.Count;
  198. if (size == 1)
  199. subScorers.RemoveAt(0);
  200. else
  201. {
  202. subScorers[0] = subScorers[size - 1];
  203. subScorers.RemoveAt(size - 1);
  204. HeapAdjust(0);
  205. }
  206. }
  207. }
  208. }