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

   1 package org.apache.lucene.search;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import java.io.IOException;
  21 import java.util.ArrayList;
  22
  23 final class SloppyPhraseScorer extends PhraseScorer {
  24     private int slop;
  25   private boolean checkedRepeats; // flag to only check in first candidate doc in case there are no repeats
  26   private boolean hasRepeats; // flag indicating that there are repeats (already checked in first candidate doc)
  27   private PhraseQueue pq; // for advancing min position
  28   private PhrasePositions[] nrPps; // non repeating pps ordered by their query offset
  29
  30     SloppyPhraseScorer(Weight weight, PhraseQuery.PostingsAndFreq[] postings, Similarity similarity,
  31                        int slop, byte[] norms) {
  32         super(weight, postings, similarity, norms);
  33         this.slop = slop;
  34     }
  35
  36     /**
  37      * Score a candidate doc for all slop-valid position-combinations (matches)
  38      * encountered while traversing/hopping the PhrasePositions.
  39      * <br> The score contribution of a match depends on the distance:
  40      * <br> - highest score for distance=0 (exact match).
  41      * <br> - score gets lower as distance gets higher.
  42      * <br>Example: for query "a b"~2, a document "x a b a y" can be scored twice:
  43      * once for "a b" (distance=0), and once for "b a" (distance=2).
  44      * <br>Possibly not all valid combinations are encountered, because for efficiency
  45      * we always propagate the least PhrasePosition. This allows to base on
  46      * PriorityQueue and move forward faster.
  47      * As result, for example, document "a b c b a"
  48      * would score differently for queries "a b c"~4 and "c b a"~4, although
  49      * they really are equivalent.
  50      * Similarly, for doc "a b c b a f g", query "c b"~2
  51      * would get same score as "g f"~2, although "c b"~2 could be matched twice.
  52      * We may want to fix this in the future (currently not, for performance reasons).
  53      */
  54     @Override
  55   protected float phraseFreq() throws IOException {
  56     int end = initPhrasePositions();
  57     //printPositions(System.err, "INIT DONE:");
  58     if (end==Integer.MIN_VALUE) {
  59       return 0.0f;
  60     }
  61
  62     float freq = 0.0f;
  63     PhrasePositions pp = pq.pop();
  64     int matchLength = end - pp.position;
  65     int next = pq.size()>0 ? pq.top().position : pp.position;
  66     //printQueue(System.err, pp, "Bef Loop: next="+next+" mlen="+end+"-"+pp.position+"="+matchLength);
  67     while (pp.nextPosition() && (end=advanceRepeats(pp, end)) != Integer.MIN_VALUE)  {
  68       if (pp.position > next) {
  69         //printQueue(System.err, pp, "A: >next="+next+" matchLength="+matchLength);
  70         if (matchLength <= slop) {
  71           freq += getSimilarity().sloppyFreq(matchLength); // score match
  72         }
  73         pq.add(pp);
  74         pp = pq.pop();
  75         next = pq.size()>0 ? pq.top().position : pp.position;
  76         matchLength = end - pp.position;
  77         //printQueue(System.err, pp, "B: >next="+next+" matchLength="+matchLength);
  78       } else {
  79         int matchLength2 = end - pp.position;
  80         //printQueue(System.err, pp, "C: mlen2<mlen: next="+next+" matchLength="+matchLength+" matchLength2="+matchLength2);
  81         if (matchLength2 < matchLength) {
  82           matchLength = matchLength2;
  83         }
  84       }
  85     }
  86     if (matchLength <= slop) {
  87       freq += getSimilarity().sloppyFreq(matchLength); // score match
  88     }
  89     return freq;
  90   }
  91
  92   /**
  93    * Advance repeating pps of an input (non-repeating) pp.
  94    * Return a modified 'end' in case pp or its repeats exceeds original 'end'.
  95    * "Dirty" trick: when there are repeats, modifies pp's position to that of
  96    * least repeater of pp (needed when due to holes repeaters' positions are "back").
  97    */
  98   private int advanceRepeats(PhrasePositions pp, int end) throws IOException {
  99     int repeatsEnd = end;
 100     if (pp.position > repeatsEnd) {
 101       repeatsEnd = pp.position;
 102     }
 103     if (!hasRepeats) {
 104       return repeatsEnd;
 105     }
 106     int tpPos = tpPos(pp);
 107     for (PhrasePositions pp2=pp.nextRepeating; pp2!=null; pp2=pp2.nextRepeating) {
 108       while (tpPos(pp2) <= tpPos) {
 109         if (!pp2.nextPosition()) {
 110           return Integer.MIN_VALUE;
 111         }
 112       }
 113       tpPos = tpPos(pp2);
 114       if (pp2.position > repeatsEnd) {
 115         repeatsEnd = pp2.position;
 116       }
 117       // "dirty" trick: with holes, given a pp, its repeating pp2 might have smaller position.
 118       // so in order to have the right "start" in matchLength computation we fake pp.position.
 119       // this relies on pp.nextPosition() not using pp.position.
 120       if (pp2.position < pp.position) {
 121         pp.position = pp2.position;
 122       }
 123     }
 124     return repeatsEnd;
 125   }
 126
 127   /**
 128    * Initialize PhrasePositions in place.
 129    * There is a one time initialization for this scorer (taking place at the first doc that matches all terms):
 130    * <ul>
 131    *  <li>Detect groups of repeating pps: those with same tpPos (tpPos==position in the doc) but different offsets in query.
 132    *  <li>For each such group:
 133    *  <ul>
 134    *   <li>form an inner linked list of the repeating ones.
 135    *   <li>propagate all group members but first so that they land on different tpPos().
 136    *  </ul>
 137    *  <li>Mark whether there are repetitions at all, so that scoring queries with no repetitions has no overhead due to this computation.
 138    *  <li>Insert to pq only non repeating PPs, or PPs that are the first in a repeating group.
 139    * </ul>
 140    * Examples:
 141    * <ol>
 142    *  <li>no repetitions: <b>"ho my"~2</b>
 143    *  <li>repetitions: <b>"ho my my"~2</b>
 144    *  <li>repetitions: <b>"my ho my"~2</b>
 145    * </ol>
 146    * @return end (max position), or Integer.MIN_VALUE if any term ran out (i.e. done)
 147    */
 148   private int initPhrasePositions() throws IOException {
 149     int end = Integer.MIN_VALUE;
 150
 151     // no repeats at all (most common case is also the simplest one)
 152     if (checkedRepeats && !hasRepeats) {
 153       // build queue from list
 154       pq.clear();
 155       for (PhrasePositions pp=min,prev=null; prev!=max; pp=(prev=pp).next) {  // iterate cyclic list: done once handled max
 156         pp.firstPosition();
 157         if (pp.position > end) {
 158           end = pp.position;
 159         }
 160         pq.add(pp);         // build pq from list
 161       }
 162       return end;
 163     }
 164
 165     //printPositions(System.err, "Init: 1: Bef position");
 166
 167     // position the pp's
 168     for (PhrasePositions pp=min,prev=null; prev!=max; pp=(prev=pp).next) {  // iterate cyclic list: done once handled max
 169       pp.firstPosition();
 170     }
 171
 172     //printPositions(System.err, "Init: 2: Aft position");
 173
 174     // one time initialization for this scorer (done only for the first candidate doc)
 175     if (!checkedRepeats) {
 176       checkedRepeats = true;
 177       ArrayList<PhrasePositions> ppsA = new ArrayList<PhrasePositions>();
 178       PhrasePositions dummyPP = new PhrasePositions(null, -1, -1);
 179       // check for repeats
 180       for (PhrasePositions pp=min,prev=null; prev!=max; pp=(prev=pp).next) {  // iterate cyclic list: done once handled max
 181         if (pp.nextRepeating != null) {
 182           continue; // a repetition of an earlier pp
 183         }
 184         ppsA.add(pp);
 185         int tpPos = tpPos(pp);
 186         for (PhrasePositions prevB=pp, pp2=pp.next; pp2!= min; pp2=pp2.next) {
 187           if (
 188               pp2.nextRepeating != null  // already detected as a repetition of an earlier pp
 189               || pp.offset == pp2.offset // not a repetition: the two PPs are originally in same offset in the query!
 190               || tpPos(pp2) != tpPos) {  // not a repetition
 191             continue;
 192           }
 193           // a repetition
 194           hasRepeats = true;
 195           prevB.nextRepeating = pp2;  // add pp2 to the repeats linked list
 196           pp2.nextRepeating = dummyPP; // allows not to handle the last pp in a sub-list
 197           prevB = pp2;
 198         }
 199       }
 200       if (hasRepeats) {
 201         // clean dummy markers
 202         for (PhrasePositions pp=min,prev=null; prev!=max; pp=(prev=pp).next) {  // iterate cyclic list: done once handled max
 203           if (pp.nextRepeating == dummyPP) {
 204             pp.nextRepeating = null;
 205           }
 206         }
 207       }
 208       nrPps = ppsA.toArray(new PhrasePositions[0]);
 209       pq = new PhraseQueue(nrPps.length);
 210     }
 211
 212     //printPositions(System.err, "Init: 3: Aft check-repeats");
 213
 214     // with repeats must advance some repeating pp's so they all start with differing tp's
 215     if (hasRepeats) {
 216       for (PhrasePositions pp: nrPps) {
 217         if ((end=advanceRepeats(pp, end)) == Integer.MIN_VALUE) {
 218           return Integer.MIN_VALUE; // ran out of a term -- done (no valid matches in current doc)
 219         }
 220       }
 221     }
 222
 223     //printPositions(System.err, "Init: 4: Aft advance-repeats");
 224
 225     // build queue from non repeating pps
 226     pq.clear();
 227     for (PhrasePositions pp: nrPps) {
 228       if (pp.position > end) {
 229         end = pp.position;
 230       }
 231       pq.add(pp);
 232     }
 233
 234     return end;
 235   }
 236
 237   /** Actual position in doc of a PhrasePosition, relies on that position = tpPos - offset) */
 238   private final int tpPos(PhrasePositions pp) {
 239     return pp.position + pp.offset;
 240   }
 241
 242 //  private void printPositions(PrintStream ps, String title) {
 243 //    ps.println();
 244 //    ps.println("---- "+title);
 245 //    int k = 0;
 246 //    if (nrPps!=null) {
 247 //      for (PhrasePositions pp: nrPps) {
 248 //        ps.println("  " + k++ + "  " + pp);
 249 //      }
 250 //    } else {
 251 //      for (PhrasePositions pp=min; 0==k || pp!=min; pp = pp.next) {
 252 //        ps.println("  " + k++ + "  " + pp);
 253 //      }
 254 //    }
 255 //  }
 256
 257 //  private void printQueue(PrintStream ps, PhrasePositions ext, String title) {
 258 //    ps.println();
 259 //    ps.println("---- "+title);
 260 //    ps.println("EXT: "+ext);
 261 //    PhrasePositions[] t = new PhrasePositions[pq.size()];
 262 //    if (pq.size()>0) {
 263 //      t[0] = pq.pop();
 264 //      ps.println("  " + 0 + "  " + t[0]);
 265 //      for (int i=1; i<t.length; i++) {
 266 //        t[i] = pq.pop();
 267 //        assert t[i-1].position <= t[i].position : "PQ is out of order: "+(i-1)+"::"+t[i-1]+" "+i+"::"+t[i];
 268 //        ps.println("  " + i + "  " + t[i]);
 269 //      }
 270 //      // add them back
 271 //      for (int i=t.length-1; i>=0; i--) {
 272 //        pq.add(t[i]);
 273 //      }
 274 //    }
 275 //  }
 276 }