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/09/24 21:56:06 UTC

svn commit: r1389543 - in /lucene/dev/branches/lucene3842/lucene: core/src/java/org/apache/lucene/analysis/ core/src/test/org/apache/lucene/analysis/ suggest/src/java/org/apache/lucene/search/suggest/analyzing/ suggest/src/test/org/apache/lucene/search...

Author: mikemccand
Date: Mon Sep 24 19:56:06 2012
New Revision: 1389543

URL: http://svn.apache.org/viewvc?rev=1389543&view=rev
Log:
LUCENE-3842: clean up nocommits; sometimes don't preserve_sep in random test; fix dup bug

Modified:
    lucene/dev/branches/lucene3842/lucene/core/src/java/org/apache/lucene/analysis/TokenStreamToAutomaton.java
    lucene/dev/branches/lucene3842/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java
    lucene/dev/branches/lucene3842/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionLookup.java
    lucene/dev/branches/lucene3842/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionTest.java

Modified: lucene/dev/branches/lucene3842/lucene/core/src/java/org/apache/lucene/analysis/TokenStreamToAutomaton.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3842/lucene/core/src/java/org/apache/lucene/analysis/TokenStreamToAutomaton.java?rev=1389543&r1=1389542&r2=1389543&view=diff
==============================================================================
--- lucene/dev/branches/lucene3842/lucene/core/src/java/org/apache/lucene/analysis/TokenStreamToAutomaton.java (original)
+++ lucene/dev/branches/lucene3842/lucene/core/src/java/org/apache/lucene/analysis/TokenStreamToAutomaton.java Mon Sep 24 19:56:06 2012
@@ -21,8 +21,6 @@ import java.io.FileOutputStream;
 import java.io.IOException;
 import java.io.OutputStreamWriter;
 import java.io.Writer;
-import java.util.HashMap;
-import java.util.Map;
 
 import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
 import org.apache.lucene.analysis.tokenattributes.PositionLengthAttribute;
@@ -167,7 +165,7 @@ public class TokenStreamToAutomaton {
   }
 
   // for debugging!
-  // nocommit comment out again
+  /*
   private static void toDot(Automaton a) throws IOException {
     final String s = a.toDot();
     Writer w = new OutputStreamWriter(new FileOutputStream("/tmp/out.dot"));
@@ -175,6 +173,7 @@ public class TokenStreamToAutomaton {
     w.close();
     System.out.println("TEST: saved to /tmp/out.dot");
   }
+  */
 
   // nocommit test syn over N deleted stop words
 

Modified: lucene/dev/branches/lucene3842/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3842/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java?rev=1389543&r1=1389542&r2=1389543&view=diff
==============================================================================
--- lucene/dev/branches/lucene3842/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java (original)
+++ lucene/dev/branches/lucene3842/lucene/core/src/test/org/apache/lucene/analysis/TestGraphTokenizers.java Mon Sep 24 19:56:06 2012
@@ -422,7 +422,7 @@ public class TestGraphTokenizers extends
   }
 
   // for debugging!
-  // nocommit comment out
+  /*
   private static void toDot(Automaton a) throws IOException {
     final String s = a.toDot();
     Writer w = new OutputStreamWriter(new FileOutputStream("/x/tmp3/out.dot"));
@@ -430,6 +430,7 @@ public class TestGraphTokenizers extends
     w.close();
     System.out.println("TEST: saved to /x/tmp3/out.dot");
   }
+  */
 
   private static final Automaton SEP_A = BasicAutomata.makeChar(TokenStreamToAutomaton.POS_SEP);
   private static final Automaton HOLE_A = BasicAutomata.makeChar(TokenStreamToAutomaton.HOLE);

Modified: lucene/dev/branches/lucene3842/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionLookup.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3842/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionLookup.java?rev=1389543&r1=1389542&r2=1389543&view=diff
==============================================================================
--- lucene/dev/branches/lucene3842/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionLookup.java (original)
+++ lucene/dev/branches/lucene3842/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionLookup.java Mon Sep 24 19:56:06 2012
@@ -23,17 +23,14 @@ import java.io.InputStream;
 import java.io.OutputStream;
 import java.io.StringReader;
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.Comparator;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 
 import org.apache.lucene.analysis.Analyzer;
-import org.apache.lucene.analysis.TokenFilter;
 import org.apache.lucene.analysis.TokenStream;
 import org.apache.lucene.analysis.TokenStreamToAutomaton;
-import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
-import org.apache.lucene.analysis.tokenattributes.TermToBytesRefAttribute;
 import org.apache.lucene.search.spell.TermFreqIterator;
 import org.apache.lucene.search.suggest.Lookup;
 import org.apache.lucene.search.suggest.fst.Sort;
@@ -278,8 +275,6 @@ public class AnalyzingCompletionLookup e
     Sort.ByteSequencesReader reader = null;
     BytesRef scratch = new BytesRef();
 
-    BytesRef separator = new BytesRef(new byte[] { (byte)TokenStreamToAutomaton.POS_SEP });
-
     TokenStreamToAutomaton ts2a = new EscapingTokenStreamToAutomaton();
 
     // analyzed sequence + 0(byte) + weight(int) + surface + analyzedLength(short) 
@@ -386,7 +381,7 @@ public class AnalyzingCompletionLookup e
           dedup = 0;
           previous.copyBytes(analyzed);
         }
-        
+
         analyzed.grow(analyzed.length+2);
         // NOTE: must be byte 0 so we sort before whatever
         // is next
@@ -395,7 +390,7 @@ public class AnalyzingCompletionLookup e
         analyzed.length += 2;
 
         Util.toIntsRef(analyzed, scratchInts);
-        //System.out.println("ADD: " + analyzed);
+        //System.out.println("ADD: " + analyzed + " -> " + surface.utf8ToString());
         builder.add(scratchInts, outputs.newPair(cost, BytesRef.deepCopyOf(surface)));
       }
       fst = builder.finish();
@@ -438,9 +433,8 @@ public class AnalyzingCompletionLookup e
   @Override
   public List<LookupResult> lookup(final CharSequence key, boolean onlyMorePopular, int num) {
     assert num > 0;
-    Arc<Pair<Long,BytesRef>> arc = new Arc<Pair<Long,BytesRef>>();
 
-    // System.out.println("lookup num=" + num);
+    //System.out.println("lookup key=" + key + " num=" + num);
 
     try {
 
@@ -466,8 +460,7 @@ public class AnalyzingCompletionLookup e
       final List<FSTUtil.Path<Pair<Long,BytesRef>>> prefixPaths;
       prefixPaths = FSTUtil.intersectPrefixPaths(automaton, fst);
 
-      //System.out.println("  prefixPaths: " +
-      //prefixPaths.size());
+      //System.out.println("  prefixPaths: " + prefixPaths.size());
 
       BytesReader bytesReader = fst.getBytesReader(0);
 
@@ -533,16 +526,22 @@ public class AnalyzingCompletionLookup e
         }
       }
 
-      // nocommit hmm w/ a graph ... aren't we going to
-      // produce dup surface form suggestions ...?  do we
-      // need to dedup by surface form?
-
       Util.TopNSearcher<Pair<Long,BytesRef>> searcher;
       searcher = new Util.TopNSearcher<Pair<Long,BytesRef>>(fst,
                                                             num - results.size(),
                                                             weightComparator) {
+        private final Set<BytesRef> seen = new HashSet<BytesRef>();
+
         @Override
         protected boolean acceptResult(IntsRef input, Pair<Long,BytesRef> output) {
+          
+          // Dedup: when the input analyzes to a graph we
+          // can get duplicate surface forms:
+          if (seen.contains(output.output2)) {
+            return false;
+          }
+          seen.add(output.output2);
+          
           if (!exactFirst) {
             return true;
           } else {

Modified: lucene/dev/branches/lucene3842/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3842/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionTest.java?rev=1389543&r1=1389542&r2=1389543&view=diff
==============================================================================
--- lucene/dev/branches/lucene3842/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionTest.java (original)
+++ lucene/dev/branches/lucene3842/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/AnalyzingCompletionTest.java Mon Sep 24 19:56:06 2012
@@ -24,9 +24,9 @@ import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
+import java.util.HashSet;
 import java.util.List;
-import java.util.Map;
-import java.util.TreeMap;
+import java.util.Set;
 import java.util.TreeSet;
 
 import org.apache.lucene.analysis.Analyzer;
@@ -135,11 +135,10 @@ public class AnalyzingCompletionTest ext
 
     AnalyzingCompletionLookup suggester = new AnalyzingCompletionLookup(new MockAnalyzer(random()), options, 256, -1);
     suggester.build(new TermFreqArrayIterator(keys));
-    // nocommit if i change this to "ab " ... the test fails
-    // now but really it should pass???  problem is
-    // analyzers typically strip trailing space?  really we
-    // need a SEP token appear instead...?  hmm actually i
-    // think we need to look @ posIncAtt after .end()?
+    // TODO: would be nice if "ab " would allow the test to
+    // pass, and more generally if the analyzer can know
+    // that the user's current query has ended at a word, 
+    // but, analyzers don't produce SEP tokens!
     List<LookupResult> r = suggester.lookup(_TestUtil.stringToCharSequence("ab c", random()), false, 2);
     assertEquals(2, r.size());
 
@@ -149,6 +148,71 @@ public class AnalyzingCompletionTest ext
     assertEquals("abcd", r.get(0).key.toString());
   }
 
+  public void testGraphDups() throws Exception {
+
+    final Analyzer analyzer = new Analyzer() {
+      @Override
+      protected TokenStreamComponents createComponents(String fieldName, Reader reader) {
+        Tokenizer tokenizer = new MockTokenizer(reader, MockTokenizer.SIMPLE, true);
+        
+        return new TokenStreamComponents(tokenizer) {
+          int tokenStreamCounter = 0;
+          final TokenStream[] tokenStreams = new TokenStream[] {
+            new CannedTokenStream(new Token[] {
+                token("wifi",1,1),
+                token("hotspot",0,2),
+                token("network",1,1),
+                token("is",1,1),
+                token("slow",1,1)
+              }),
+            new CannedTokenStream(new Token[] {
+                token("wi",1,1),
+                token("hotspot",0,3),
+                token("fi",1,1),
+                token("network",1,1),
+                token("is",1,1),
+                token("fast",1,1)
+
+              }),
+            new CannedTokenStream(new Token[] {
+                token("wifi",1,1),
+                token("hotspot",0,2),
+                token("network",1,1)
+              }),
+          };
+
+          @Override
+          public TokenStream getTokenStream() {
+            TokenStream result = tokenStreams[tokenStreamCounter];
+            tokenStreamCounter++;
+            return result;
+          }
+         
+          @Override
+          protected void setReader(final Reader reader) throws IOException {
+          }
+        };
+      }
+    };
+
+    TermFreq keys[] = new TermFreq[] {
+        new TermFreq("wifi network is slow", 50),
+        new TermFreq("wi fi network is fast", 10),
+    };
+    //AnalyzingCompletionLookup suggester = new AnalyzingCompletionLookup(analyzer, AnalyzingCompletionLookup.EXACT_FIRST, 256, -1);
+    AnalyzingCompletionLookup suggester = new AnalyzingCompletionLookup(analyzer);
+    suggester.build(new TermFreqArrayIterator(keys));
+    List<LookupResult> results = suggester.lookup("wifi network", false, 10);
+    if (VERBOSE) {
+      System.out.println("Results: " + results);
+    }
+    assertEquals(2, results.size());
+    assertEquals("wifi network is slow", results.get(0).key);
+    assertEquals(50, results.get(0).value);
+    assertEquals("wi fi network is fast", results.get(1).key);
+    assertEquals(10, results.get(1).value);
+  }
+
   public void testInputPathRequired() throws Exception {
 
     //  SynonymMap.Builder b = new SynonymMap.Builder(false);
@@ -164,8 +228,6 @@ public class AnalyzingCompletionTest ext
       protected TokenStreamComponents createComponents(String fieldName, Reader reader) {
         Tokenizer tokenizer = new MockTokenizer(reader, MockTokenizer.SIMPLE, true);
         
-        // TokenStream stream = new SynonymFilter(tokenizer, map, true);
-        // return new TokenStreamComponents(tokenizer, new RemoveDuplicatesTokenFilter(stream));
         return new TokenStreamComponents(tokenizer) {
           int tokenStreamCounter = 0;
           final TokenStream[] tokenStreams = new TokenStream[] {
@@ -220,6 +282,7 @@ public class AnalyzingCompletionTest ext
     return new BinaryToken(term);
   }
 
+  /*
   private void printTokens(final Analyzer analyzer, String input) throws IOException {
     System.out.println("Tokens for " + input);
     TokenStream ts = analyzer.tokenStream("", new StringReader(input));
@@ -234,7 +297,8 @@ public class AnalyzingCompletionTest ext
     }
     ts.end();
     ts.close();
-  }  
+  } 
+  */ 
 
   private final Analyzer getUnusualAnalyzer() {
     return new Analyzer() {
@@ -345,52 +409,139 @@ public class AnalyzingCompletionTest ext
     }
   }
   
+  // Holds surface form seperately:
+  private static class TermFreq2 implements Comparable<TermFreq2> {
+    public final String surfaceForm;
+    public final String analyzedForm;
+    public final long weight;
+
+    public TermFreq2(String surfaceForm, String analyzedForm, long weight) {
+      this.surfaceForm = surfaceForm;
+      this.analyzedForm = analyzedForm;
+      this.weight = weight;
+    }
+
+    @Override
+    public int compareTo(TermFreq2 other) {
+      int cmp = analyzedForm.compareTo(other.analyzedForm);
+      if (cmp != 0) {
+        return cmp;
+      } else if (weight > other.weight) {
+        return -1;
+      } else if (weight < other.weight) {
+        return 1;
+      } else {
+        assert false;
+        return 0;
+      }
+    }
+  }
+
   public void testRandom() throws Exception {
     int numWords = atLeast(1000);
     
-    final TreeMap<String,Long> slowCompletor = new TreeMap<String,Long>();
+    final List<TermFreq2> slowCompletor = new ArrayList<TermFreq2>();
     final TreeSet<String> allPrefixes = new TreeSet<String>();
+    final Set<String> seen = new HashSet<String>();
     
     TermFreq[] keys = new TermFreq[numWords];
+
+    boolean preserveSep = random().nextBoolean();
+
+    if (VERBOSE) {
+      System.out.println("TEST: " + numWords + " words; preserveSep=" + preserveSep);
+    }
     
     for (int i = 0; i < numWords; i++) {
-      String s;
-      while (true) {
-        // TODO: would be nice to fix this slowCompletor/comparator to
-        // use full range, but we might lose some coverage too...
-        s = _TestUtil.randomSimpleString(random());
-        if (!slowCompletor.containsKey(s)) {
+      int numTokens = _TestUtil.nextInt(random(), 1, 4);
+      String key;
+      String keyNoSep;
+      while(true) {
+        key = "";
+        keyNoSep = "";
+        for(int token=0;token < numTokens;token++) {
+          String s;
+          while (true) {
+            // TODO: would be nice to fix this slowCompletor/comparator to
+            // use full range, but we might lose some coverage too...
+            s = _TestUtil.randomSimpleString(random());
+            if (s.length() > 0) {
+              if (token > 0) {
+                key += " ";
+              }
+              key += s;
+              keyNoSep += s;
+              break;
+            }
+          }
+        }
+
+        // Don't add same surface form more than once:
+        if (!seen.contains(key)) {
+          seen.add(key);
           break;
         }
       }
-      
-      for (int j = 1; j < s.length(); j++) {
-        allPrefixes.add(s.substring(0, j));
+
+      for (int j = 1; j < key.length(); j++) {
+        allPrefixes.add(key.substring(0, j));
       }
       // we can probably do Integer.MAX_VALUE here, but why worry.
       int weight = random().nextInt(1<<24);
-      slowCompletor.put(s, (long)weight);
-      keys[i] = new TermFreq(s, weight);
+      keys[i] = new TermFreq(key, weight);
+      slowCompletor.add(new TermFreq2(key, preserveSep ? key : keyNoSep, weight));
     }
 
-    // nocommit also test NOT preserving seps/holes
-    // nocommit why no failure if we DON'T preserve seps/holes...?
-    AnalyzingCompletionLookup suggester = new AnalyzingCompletionLookup(new MockAnalyzer(random(), MockTokenizer.KEYWORD, false),
-                                                                        AnalyzingCompletionLookup.PRESERVE_SEP, 256, -1);
+    if (VERBOSE) {
+      // Don't just sort original list, to avoid VERBOSE
+      // altering the test:
+      List<TermFreq2> sorted = new ArrayList<TermFreq2>(slowCompletor);
+      Collections.sort(sorted);
+      for(TermFreq2 ent : sorted) {
+        System.out.println("  surface='" + ent.surfaceForm + " analyzed='" + ent.analyzedForm + "' weight=" + ent.weight);
+      }
+    }
+
+    // nocommit also test NOT preserving holes
+    AnalyzingCompletionLookup suggester = new AnalyzingCompletionLookup(new MockAnalyzer(random(), MockTokenizer.WHITESPACE, false),
+                                                                        preserveSep ? AnalyzingCompletionLookup.PRESERVE_SEP : 0, 256, -1);
     suggester.build(new TermFreqArrayIterator(keys));
     
     for (String prefix : allPrefixes) {
-    
+
+      if (VERBOSE) {
+        System.out.println("TEST: prefix=" + prefix);
+      }
+
+      if (preserveSep && prefix.endsWith(" ")) {
+        // TODO: would be great if we didn't have to skip
+        // these cases ... but we can't handle them today
+        // because tokenizers don't/can't output SEP tokens,
+        // or indicate that a token has finished w/o a new
+        // token starting...
+        if (VERBOSE) {
+          System.out.println("  skip...");
+        }
+        continue;
+      }
+
       final int topN = _TestUtil.nextInt(random(), 1, 10);
       List<LookupResult> r = suggester.lookup(_TestUtil.stringToCharSequence(prefix, random()), false, topN);
 
-      // 2. go thru whole treemap (slowCompletor) and check its actually the best suggestion
-      final List<LookupResult> matches = new ArrayList<LookupResult>();
+      // 2. go thru whole set to find suggestions:
+      List<LookupResult> matches = new ArrayList<LookupResult>();
+
+      String key;
+      if (!preserveSep) {
+        key = prefix.replaceAll(" ", "");
+      } else {
+        key = prefix;
+      }
 
       // TODO: could be faster... but its slowCompletor for a reason
-      for (Map.Entry<String,Long> e : slowCompletor.entrySet()) {
-        if (e.getKey().startsWith(prefix)) {
-          matches.add(new LookupResult(e.getKey(), e.getValue().longValue()));
+      for (TermFreq2 e : slowCompletor) {
+        if (e.analyzedForm.startsWith(key)) {
+          matches.add(new LookupResult(e.surfaceForm, e.weight));
         }
       }
 
@@ -406,7 +557,19 @@ public class AnalyzingCompletionTest ext
         }
       });
       if (matches.size() > topN) {
-        matches.subList(topN, matches.size()).clear();
+        matches = matches.subList(0, topN);
+      }
+
+      if (VERBOSE) {
+        System.out.println("  expected:");
+        for(LookupResult lr : matches) {
+          System.out.println("    key=" + lr.key + " weight=" + lr.value);
+        }
+
+        System.out.println("  actual:");
+        for(LookupResult lr : r) {
+          System.out.println("    key=" + lr.key + " weight=" + lr.value);
+        }
       }
 
       assertEquals(matches.size(), r.size());
@@ -419,8 +582,6 @@ public class AnalyzingCompletionTest ext
     }
   }
 
-  // nocommit need random full binary test
-
   public void testStolenBytes() throws Exception {
     
     final Analyzer analyzer = new Analyzer() {
@@ -481,7 +642,6 @@ public class AnalyzingCompletionTest ext
     assertEquals(50, results.get(0).value);
   }
 
-  // nocommit test that dups are preserved by weight:
   public void testMaxSurfaceFormsPerAnalyzedForm() throws Exception {
 
     AnalyzingCompletionLookup suggester = new AnalyzingCompletionLookup(new MockAnalyzer(random()), 0, 2, -1);