You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ro...@apache.org on 2015/06/15 11:01:51 UTC

svn commit: r1685517 - in /lucene/dev/branches/branch_5x: ./ lucene/ lucene/core/ lucene/core/src/java/org/apache/lucene/search/spans/ lucene/core/src/test/org/apache/lucene/search/spans/

Author: romseygeek
Date: Mon Jun 15 09:01:51 2015
New Revision: 1685517

URL: http://svn.apache.org/r1685517
Log:
LUCENE-6537: NearSpansOrdered should be lazy

Removed:
    lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansPayloadOrdered.java
Modified:
    lucene/dev/branches/branch_5x/   (props changed)
    lucene/dev/branches/branch_5x/lucene/   (props changed)
    lucene/dev/branches/branch_5x/lucene/CHANGES.txt   (contents, props changed)
    lucene/dev/branches/branch_5x/lucene/core/   (props changed)
    lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java
    lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java
    lucene/dev/branches/branch_5x/lucene/core/src/test/org/apache/lucene/search/spans/TestNearSpansOrdered.java

Modified: lucene/dev/branches/branch_5x/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/CHANGES.txt?rev=1685517&r1=1685516&r2=1685517&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_5x/lucene/CHANGES.txt Mon Jun 15 09:01:51 2015
@@ -100,6 +100,13 @@ Changes in Runtime Behavior
 * LUCENE-6538: Also include java.vm.version and java.runtime.version
   in per-segment diagnostics (Robert Muir, Mike McCandless)
 
+* LUCENE-6537: NearSpansOrdered no longer tries to minimize its
+  Span matches.  This means that the matching algorithm is entirely
+  lazy.  All spans returned by the previous implementation are still 
+  reported, but matching documents may now also return additional 
+  spans that were previously discarded in preference to shorter 
+  overlapping ones. (Alan Woodward, Adrien Grand, Paul Elschot)
+
 Build
 
 * LUCENE-6518: Don't report false thread leaks from IBM J9

Modified: lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java?rev=1685517&r1=1685516&r2=1685517&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java (original)
+++ lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/NearSpansOrdered.java Mon Jun 15 09:01:51 2015
@@ -18,13 +18,13 @@ package org.apache.lucene.search.spans;
  */
 
 import java.io.IOException;
+import java.util.ArrayList;
 import java.util.List;
 import java.util.Collection;
 
-/** A Spans that is formed from the ordered subspans of a SpanNearQuery
- * where the subspans do not overlap and have a maximum slop between them,
- * and that does not need to collect payloads.
- * To also collect payloads, see {@link NearSpansPayloadOrdered}.
+/**
+ * A Spans that is formed from the ordered subspans of a SpanNearQuery
+ * where the subspans do not overlap and have a maximum slop between them.
  * <p>
  * The formed spans only contains minimum slop matches.<br>
  * The matching slop is computed from the distance(s) between
@@ -41,15 +41,14 @@ import java.util.Collection;
  * <pre>t1 t2 .. t3      </pre>
  * <pre>      t1 .. t2 t3</pre>
  *
- *
  * Expert:
  * Only public for subclassing.  Most implementations should not need this class
  */
 public class NearSpansOrdered extends NearSpans {
 
-  protected int matchDoc = -1;
   protected int matchStart = -1;
   protected int matchEnd = -1;
+  protected int matchWidth = -1;
 
   public NearSpansOrdered(SpanNearQuery query, List<Spans> subSpans) throws IOException {
     super(query, subSpans);
@@ -58,20 +57,22 @@ public class NearSpansOrdered extends Ne
 
   @Override
   boolean twoPhaseCurrentDocMatches() throws IOException {
-    subSpansToFirstStartPosition();
-    while (true) {
-      if (! stretchToOrder()) {
-        return false;
-      }
-      if (shrinkToAfterShortestMatch()) {
-        atFirstInCurrentDoc = true;
-        return true;
+    assert unpositioned();
+    oneExhaustedInCurrentDoc = false;
+    while (subSpans[0].nextStartPosition() != NO_MORE_POSITIONS && !oneExhaustedInCurrentDoc) {
+      if (stretchToOrder() && matchWidth <= allowedSlop) {
+        return atFirstInCurrentDoc = true;
       }
-      // not a match, after shortest ordered spans
-      if (oneExhaustedInCurrentDoc) {
+    }
+    return false;
+  }
+
+  private boolean unpositioned() {
+    for (Spans span : subSpans) {
+      if (span.startPosition() != -1)
         return false;
-      }
     }
+    return true;
   }
 
   @Override
@@ -80,42 +81,27 @@ public class NearSpansOrdered extends Ne
       atFirstInCurrentDoc = false;
       return matchStart;
     }
-    while (true) {
-      if (oneExhaustedInCurrentDoc) {
-        matchStart = NO_MORE_POSITIONS;
-        matchEnd = NO_MORE_POSITIONS;
-        return NO_MORE_POSITIONS;
-      }
-      if (! stretchToOrder()) {
-        matchStart = NO_MORE_POSITIONS;
-        matchEnd = NO_MORE_POSITIONS;
-        return NO_MORE_POSITIONS;
-      }
-      if (shrinkToAfterShortestMatch()) { // may also leave oneExhaustedInCurrentDoc
+    oneExhaustedInCurrentDoc = false;
+    while (subSpans[0].nextStartPosition() != NO_MORE_POSITIONS && !oneExhaustedInCurrentDoc) {
+      if (stretchToOrder() && matchWidth <= allowedSlop) {
         return matchStart;
       }
-      // after shortest ordered spans, or oneExhaustedInCurrentDoc
-    }
-  }
-
-  private void subSpansToFirstStartPosition() throws IOException {
-    for (Spans spans : subSpans) {
-      assert spans.startPosition() == -1 : "spans="+spans;
-      spans.nextStartPosition();
-      assert spans.startPosition() != NO_MORE_POSITIONS;
     }
-    oneExhaustedInCurrentDoc = false;
+    return matchStart = matchEnd = NO_MORE_POSITIONS;
   }
 
-  /** Order the subSpans within the same document by using nextStartPosition on all subSpans
+  /**
+   * Order the subSpans within the same document by using nextStartPosition on all subSpans
    * after the first as little as necessary.
    * Return true when the subSpans could be ordered in this way,
    * otherwise at least one is exhausted in the current doc.
    */
   private boolean stretchToOrder() throws IOException {
     Spans prevSpans = subSpans[0];
+    matchStart = prevSpans.startPosition();
     assert prevSpans.startPosition() != NO_MORE_POSITIONS : "prevSpans no start position "+prevSpans;
     assert prevSpans.endPosition() != NO_MORE_POSITIONS;
+    matchWidth = 0;
     for (int i = 1; i < subSpans.length; i++) {
       Spans spans = subSpans[i];
       assert spans.startPosition() != NO_MORE_POSITIONS;
@@ -123,62 +109,17 @@ public class NearSpansOrdered extends Ne
 
       while (prevSpans.endPosition() > spans.startPosition()) { // while overlapping spans
         if (spans.nextStartPosition() == NO_MORE_POSITIONS) {
+          oneExhaustedInCurrentDoc = true;
           return false;
         }
       }
+      matchWidth += (spans.startPosition() - prevSpans.endPosition());
       prevSpans = spans;
     }
+    matchEnd = subSpans[subSpans.length - 1].endPosition();
     return true; // all subSpans ordered and non overlapping
   }
 
-  /** The subSpans are ordered in the same doc, so there is a possible match.
-   * Compute the slop while making the match as short as possible by using nextStartPosition
-   * on all subSpans, except the last one, in reverse order.
-   */
-  protected boolean shrinkToAfterShortestMatch() throws IOException {
-    Spans lastSubSpans = subSpans[subSpans.length - 1];
-    matchStart = lastSubSpans.startPosition();
-    matchEnd = lastSubSpans.endPosition();
-
-    int matchSlop = 0;
-    int lastStart = matchStart;
-    for (int i = subSpans.length - 2; i >= 0; i--) {
-      Spans prevSpans = subSpans[i];
-
-      int prevStart = prevSpans.startPosition();
-      int prevEnd = prevSpans.endPosition();
-      while (true) { // prevSpans nextStartPosition until after (lastStart, lastEnd)
-        if (prevSpans.nextStartPosition() == NO_MORE_POSITIONS) {
-          oneExhaustedInCurrentDoc = true;
-          break; // Check remaining subSpans for match.
-        }
-        int ppStart = prevSpans.startPosition();
-        int ppEnd = prevSpans.endPosition();
-        if (ppEnd > lastStart) { // if overlapping spans
-          break; // Check remaining subSpans.
-        }
-        // prevSpans still before (lastStart, lastEnd)
-        prevStart = ppStart;
-        prevEnd = ppEnd;
-      }
-
-      assert prevStart <= matchStart;
-      if (matchStart > prevEnd) { // Only non overlapping spans add to slop.
-        matchSlop += (matchStart - prevEnd);
-      }
-
-      /* Do not break on (matchSlop > allowedSlop) here to make sure
-       * that on return the first subSpans has nextStartPosition called.
-       */
-      matchStart = prevStart;
-      lastStart = prevStart;
-    }
-
-    boolean match = matchSlop <= allowedSlop;
-
-    return match; // ordered and allowed slop
-  }
-
   @Override
   public int startPosition() {
     return atFirstInCurrentDoc ? -1 : matchStart;
@@ -191,11 +132,20 @@ public class NearSpansOrdered extends Ne
 
   @Override
   public Collection<byte[]> getPayload() throws IOException {
-    return null;
+    List<byte[]> payloads = new ArrayList<>();
+    for (Spans spans : subSpans) {
+      if (spans.isPayloadAvailable())
+        payloads.addAll(spans.getPayload());
+    }
+    return payloads;
   }
 
   @Override
-  public boolean isPayloadAvailable() {
+  public boolean isPayloadAvailable() throws IOException {
+    for (Spans spans : subSpans) {
+      if (spans.isPayloadAvailable())
+        return true;
+    }
     return false;
   }
 
@@ -203,5 +153,6 @@ public class NearSpansOrdered extends Ne
   public String toString() {
     return "NearSpansOrdered("+query.toString()+")@"+docID()+": "+startPosition()+" - "+endPosition();
   }
+
 }
 

Modified: lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java?rev=1685517&r1=1685516&r2=1685517&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java (original)
+++ lucene/dev/branches/branch_5x/lucene/core/src/java/org/apache/lucene/search/spans/SpanNearQuery.java Mon Jun 15 09:01:51 2015
@@ -17,15 +17,8 @@ package org.apache.lucene.search.spans;
  * limitations under the License.
  */
 
-import java.io.IOException;
-import java.util.List;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.lucene.index.LeafReaderContext;
 import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.LeafReaderContext;
 import org.apache.lucene.index.Term;
 import org.apache.lucene.index.TermContext;
 import org.apache.lucene.index.Terms;
@@ -33,6 +26,13 @@ import org.apache.lucene.search.Query;
 import org.apache.lucene.util.Bits;
 import org.apache.lucene.util.ToStringUtils;
 
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
 /** Matches spans which are near one another.  One can specify <i>slop</i>, the
  * maximum number of intervening unmatched positions, as well as whether
  * matches are required to be in-order.
@@ -131,14 +131,12 @@ public class SpanNearQuery extends SpanQ
     }
 
     Terms terms = context.reader().terms(field);
-    if (terms == null) {
+    if (terms == null)
       return null; // field does not exist
-    }
-    
+
     // all NearSpans require at least two subSpans
-    return (! inOrder) ? new NearSpansUnordered(this, subSpans)
-          : collectPayloads && terms.hasPayloads() ? new NearSpansPayloadOrdered(this, subSpans)
-          : new NearSpansOrdered(this, subSpans);
+    return (!inOrder) ? new NearSpansUnordered(this, subSpans) : new NearSpansOrdered(this, subSpans);
+
   }
 
   @Override

Modified: lucene/dev/branches/branch_5x/lucene/core/src/test/org/apache/lucene/search/spans/TestNearSpansOrdered.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_5x/lucene/core/src/test/org/apache/lucene/search/spans/TestNearSpansOrdered.java?rev=1685517&r1=1685516&r2=1685517&view=diff
==============================================================================
--- lucene/dev/branches/branch_5x/lucene/core/src/test/org/apache/lucene/search/spans/TestNearSpansOrdered.java (original)
+++ lucene/dev/branches/branch_5x/lucene/core/src/test/org/apache/lucene/search/spans/TestNearSpansOrdered.java Mon Jun 15 09:01:51 2015
@@ -68,7 +68,8 @@ public class TestNearSpansOrdered extend
     "w1 w2 w3 w4 w5",
     "w1 w3 w2 w3 zz",
     "w1 xx w2 yy w3",
-    "w1 w3 xx w2 yy w3 zz"
+    "w1 w3 xx w2 yy w3 zz",
+    "t1 t2 t2 t1"
   };
 
   protected SpanNearQuery makeQuery(String s1, String s2, String s3,
@@ -208,8 +209,38 @@ public class TestNearSpansOrdered extend
     SpanNearQuery q = makeOverlappedQuery("w3", "w4", true, "w5", true);
     CheckHits.checkHits(random(), q, FIELD, searcher, new int[] {0});
   }
-  
-  
+
+  public void testOrderedSpanIteration() throws Exception {
+    SpanNearQuery q = new SpanNearQuery(new SpanQuery[]{
+        new SpanOrQuery(new SpanTermQuery(new Term(FIELD, "w1")), new SpanTermQuery(new Term(FIELD, "w2"))),
+        new SpanTermQuery(new Term(FIELD, "w4"))
+    }, 10, true);
+    Spans spans = MultiSpansWrapper.wrap(reader, q);
+    assertNext(spans,0,0,4);
+    assertNext(spans,0,1,4);
+    assertFinished(spans);
+  }
+
+  public void testOrderedSpanIterationSameTerms1() throws Exception {
+    SpanNearQuery q = new SpanNearQuery(new SpanQuery[]{
+        new SpanTermQuery(new Term(FIELD, "t1")), new SpanTermQuery(new Term(FIELD, "t2"))
+    }, 1, true);
+    Spans spans = MultiSpansWrapper.wrap(reader, q);
+    assertNext(spans,4,0,2);
+    assertFinished(spans);
+  }
+
+  public void testOrderedSpanIterationSameTerms2() throws Exception {
+    SpanNearQuery q = new SpanNearQuery(new SpanQuery[]{
+        new SpanTermQuery(new Term(FIELD, "t2")), new SpanTermQuery(new Term(FIELD, "t1"))
+    }, 1, true);
+    Spans spans = MultiSpansWrapper.wrap(reader, q);
+    assertNext(spans,4,1,4);
+    assertNext(spans,4,2,4);
+    assertFinished(spans);
+  }
+
+
   /**
    * not a direct test of NearSpans, but a demonstration of how/when
    * this causes problems