You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2012/10/12 17:07:24 UTC
svn commit: r1397606 - in /lucene/dev/trunk/lucene:
core/src/java/org/apache/lucene/util/fst/
suggest/src/java/org/apache/lucene/search/suggest/analyzing/
suggest/src/test/org/apache/lucene/search/suggest/analyzing/
Author: mikemccand
Date: Fri Oct 12 15:07:23 2012
New Revision: 1397606
URL: http://svn.apache.org/viewvc?rev=1397606&view=rev
Log:
LUCENE-4480: handle insert into empty queue correctly
Modified:
lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java
lucene/dev/trunk/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggesterTest.java
Modified: lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/fst/Util.java?rev=1397606&r1=1397605&r2=1397606&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/fst/Util.java (original)
+++ lucene/dev/trunk/lucene/core/src/java/org/apache/lucene/util/fst/Util.java Fri Oct 12 15:07:23 2012
@@ -271,9 +271,6 @@ public final class Util {
final Comparator<T> comparator;
- // Set once the queue has filled:
- FSTPath<T> bottom = null;
-
TreeSet<FSTPath<T>> queue = null;
public TopNSearcher(FST<T> fst, int topN, Comparator<T> comparator) {
@@ -291,9 +288,10 @@ public final class Util {
assert queue != null;
T cost = fst.outputs.add(path.cost, path.arc.output);
- //System.out.println(" addIfCompetitive bottom=" + bottom + " queue.size()=" + queue.size());
+ //System.out.println(" addIfCompetitive queue.size()=" + queue.size() + " path=" + path + " + label=" + path.arc.label);
- if (bottom != null) {
+ if (queue.size() == topN) {
+ FSTPath<T> bottom = queue.last();
int comp = comparator.compare(cost, bottom.cost);
if (comp > 0) {
// Doesn't compete
@@ -323,24 +321,11 @@ public final class Util {
newInput.length = path.input.length+1;
final FSTPath<T> newPath = new FSTPath<T>(cost, path.arc, comparator, newInput);
- // this is pointless right? we do it above already:
- //newPath.input.grow(path.input.length+1);
- //System.arraycopy(path.input.ints, 0, newPath.input.ints, 0, path.input.length);
- //newPath.input.ints[path.input.length] = path.arc.label;
- //newPath.input.length = path.input.length+1;
-
- //System.out.println(" add path=" + newPath);
queue.add(newPath);
- if (bottom != null) {
- final FSTPath<T> removed = queue.pollLast();
- assert removed == bottom;
- bottom = queue.last();
- //System.out.println(" now re-set bottom: " + bottom + " queue=" + queue);
- } else if (queue.size() == topN) {
- // Queue just filled up:
- bottom = queue.last();
- //System.out.println(" now set bottom: " + bottom);
- }
+
+ if (queue.size() == topN+1) {
+ queue.pollLast();
+ }
}
/** Adds all leaving arcs, including 'finished' arc, if
@@ -387,7 +372,7 @@ public final class Util {
// For each top N path:
while (results.size() < topN) {
- //System.out.println("\nfind next path");
+ //System.out.println("\nfind next path: queue.size=" + queue.size());
FSTPath<T> path;
Modified: lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java?rev=1397606&r1=1397605&r2=1397606&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java (original)
+++ lucene/dev/trunk/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java Fri Oct 12 15:07:23 2012
@@ -533,9 +533,6 @@ public class AnalyzingSuggester extends
if (exactFirst) {
- Util.TopNSearcher<Pair<Long,BytesRef>> searcher;
- searcher = new Util.TopNSearcher<Pair<Long,BytesRef>>(fst, num, weightComparator);
-
int count = 0;
for (FSTUtil.Path<Pair<Long,BytesRef>> path : prefixPaths) {
if (fst.findTargetArc(END_BYTE, path.fstNode, scratchArc, bytesReader) != null) {
@@ -545,6 +542,9 @@ public class AnalyzingSuggester extends
}
}
+ // Searcher just to find the single exact only
+ // match, if present:
+ Util.TopNSearcher<Pair<Long,BytesRef>> searcher;
searcher = new Util.TopNSearcher<Pair<Long,BytesRef>>(fst, count * maxSurfaceFormsPerAnalyzedForm, weightComparator);
// NOTE: we could almost get away with only using
Modified: lucene/dev/trunk/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggesterTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggesterTest.java?rev=1397606&r1=1397605&r2=1397606&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggesterTest.java (original)
+++ lucene/dev/trunk/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggesterTest.java Fri Oct 12 15:07:23 2012
@@ -789,4 +789,18 @@ public class AnalyzingSuggesterTest exte
assertEquals("a ", results.get(1).key);
assertEquals(50, results.get(1).value);
}
+
+ public void testQueueExhaustion() throws Exception {
+ Analyzer a = new MockAnalyzer(random());
+ AnalyzingSuggester suggester = new AnalyzingSuggester(a, a, AnalyzingSuggester.EXACT_FIRST, 256, -1);
+
+ suggester.build(new TermFreqArrayIterator(new TermFreq[] {
+ new TermFreq("a", 2),
+ new TermFreq("a b c", 3),
+ new TermFreq("a c a", 1),
+ new TermFreq("a c b", 1),
+ }));
+
+ List<LookupResult> results = suggester.lookup("a", false, 4);
+ }
}