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