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/23 14:30:22 UTC

svn commit: r1401272 - in /lucene/dev/branches/lucene3846/lucene/suggest/src: java/org/apache/lucene/search/suggest/analyzing/ test/org/apache/lucene/search/suggest/analyzing/

Author: mikemccand
Date: Tue Oct 23 12:30:21 2012
New Revision: 1401272

URL: http://svn.apache.org/viewvc?rev=1401272&view=rev
Log:
LUCENE-3846: add comments, javadocs; remove dead code

Modified:
    lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java
    lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FSTUtil.java
    lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FuzzySuggester.java
    lucene/dev/branches/lucene3846/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/FuzzySuggesterTest.java

Modified: lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java?rev=1401272&r1=1401271&r2=1401272&view=diff
==============================================================================
--- lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java (original)
+++ lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/AnalyzingSuggester.java Tue Oct 23 12:30:21 2012
@@ -31,6 +31,7 @@ import java.util.Set;
 import org.apache.lucene.analysis.Analyzer;
 import org.apache.lucene.analysis.TokenStream;
 import org.apache.lucene.analysis.TokenStreamToAutomaton;
+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;
@@ -676,7 +677,12 @@ public class AnalyzingSuggester extends 
   };
   
   /**
-   * Returns a new {@link PathIntersector}  
+   * Returns a new {@link PathIntersector}.
+   *
+   * <p>NOTE: The labels on the transitions incoming
+   * automaton are bytes returned by the {@link
+   * TokenStream}'s {@link TermToBytesRefAttribute}, which
+   * are typically UTF8 encoded.
    */
   protected PathIntersector getPathIntersector(Automaton automaton, FST<Pair<Long,BytesRef>> fst) {
     return new PathIntersector(automaton, fst);

Modified: lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FSTUtil.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FSTUtil.java?rev=1401272&r1=1401271&r2=1401272&view=diff
==============================================================================
--- lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FSTUtil.java (original)
+++ lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FSTUtil.java Tue Oct 23 12:30:21 2012
@@ -22,7 +22,6 @@ import java.util.List;
 import java.io.IOException;
 
 import org.apache.lucene.util.IntsRef;
-import org.apache.lucene.util.UnicodeUtil;
 import org.apache.lucene.util.automaton.Automaton;
 import org.apache.lucene.util.automaton.State;
 import org.apache.lucene.util.automaton.Transition;
@@ -106,11 +105,13 @@ public class FSTUtil {
                 .add(path.output, nextArc.output), newInput));
           }
         } else {
-          // TODO:
-          // if we accept the entire range possible in the FST (ie. 0 to 256)
+          // TODO: if this transition's TO state is accepting, and
+          // it accepts the entire range possible in the FST (ie. 0 to 255),
           // we can simply use the prefix as the accepted state instead of
-          // looking up all the
-          // ranges and terminate early here?
+          // looking up all the ranges and terminate early
+          // here.  This just shifts the work from one queue
+          // (this one) to another (the completion search
+          // done in AnalyzingSuggester).
           FST.Arc<T> nextArc = Util.readCeilArc(min, fst, path.fstNode,
               scratchArc, fstReader);
           while (nextArc != null && nextArc.label <= max) {

Modified: lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FuzzySuggester.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FuzzySuggester.java?rev=1401272&r1=1401271&r2=1401272&view=diff
==============================================================================
--- lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FuzzySuggester.java (original)
+++ lucene/dev/branches/lucene3846/lucene/suggest/src/java/org/apache/lucene/search/suggest/analyzing/FuzzySuggester.java Tue Oct 23 12:30:21 2012
@@ -21,6 +21,8 @@ import java.util.List;
 import java.util.Set;
 
 import org.apache.lucene.analysis.Analyzer;
+import org.apache.lucene.analysis.TokenStream;
+import org.apache.lucene.analysis.tokenattributes.TermToBytesRefAttribute; // javadocs
 import org.apache.lucene.search.suggest.analyzing.FSTUtil.Path;
 import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.IntsRef;
@@ -41,7 +43,12 @@ import org.apache.lucene.util.fst.PairOu
  * At most, this query will match terms up to
  * {@value org.apache.lucene.util.automaton.LevenshteinAutomata#MAXIMUM_SUPPORTED_DISTANCE}
  * edits. Higher distances (especially with transpositions enabled), are not
- * supported.
+ * supported.  Note that the fuzzy distance is byte-by-byte
+ * as returned by the {@link TokenStream}'s {@link
+ * TermToBytesRefAttribute}, usually UTF8.  By default
+ * the first 2 (@link #DEFAULT_MIN_PREFIX) bytes must match,
+ * and by default we allow up to 1 (@link
+ * #DEFAULT_MAX_EDITS} edit.
  * <p>
  * Note: complex query analyzers can have a significant impact on the lookup
  * performance. It's recommended to not use analyzers that drop or inject terms
@@ -131,15 +138,13 @@ public final class FuzzySuggester extend
     this.minPrefix = minPrefix;
   }
   
-  
-
   @Override
   protected PathIntersector getPathIntersector(Automaton automaton,
       FST<Pair<Long,BytesRef>> fst) {
     return new FuzzyPathIntersector(automaton, fst);
   }
 
-  final Automaton toLevenshteinAutomata(Automaton automaton) {
+  Automaton toLevenshteinAutomata(Automaton automaton) {
     final Set<IntsRef> ref = SpecialOperations.getFiniteStrings(automaton, -1);
     Automaton subs[] = new Automaton[ref.size()];
     int upto = 0;

Modified: lucene/dev/branches/lucene3846/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/FuzzySuggesterTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3846/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/FuzzySuggesterTest.java?rev=1401272&r1=1401271&r2=1401272&view=diff
==============================================================================
--- lucene/dev/branches/lucene3846/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/FuzzySuggesterTest.java (original)
+++ lucene/dev/branches/lucene3846/lucene/suggest/src/test/org/apache/lucene/search/suggest/analyzing/FuzzySuggesterTest.java Tue Oct 23 12:30:21 2012
@@ -29,7 +29,6 @@ import java.util.Set;
 import java.util.TreeSet;
 
 import org.apache.lucene.analysis.Analyzer;
-import org.apache.lucene.analysis.CannedBinaryTokenStream.BinaryToken;
 import org.apache.lucene.analysis.CannedTokenStream;
 import org.apache.lucene.analysis.MockAnalyzer;
 import org.apache.lucene.analysis.MockTokenFilter;
@@ -49,9 +48,6 @@ import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.LuceneTestCase;
 import org.apache.lucene.util._TestUtil;
 import org.apache.lucene.util.automaton.Automaton;
-import org.apache.lucene.util.automaton.BasicAutomata;
-import org.apache.lucene.util.automaton.BasicOperations;
-import org.apache.lucene.util.automaton.LevenshteinAutomata;
 import org.apache.lucene.util.automaton.State;
 import org.apache.lucene.util.fst.Util;
 
@@ -74,8 +70,6 @@ public class FuzzySuggesterTest extends 
       assertEquals("foo bar boo far", results.get(0).key.toString());
       assertEquals(12, results.get(0).value, 0.01F);  
     }
-    
-    
   }
   
   /** this is basically the WFST test ported to KeywordAnalyzer. so it acts the same */
@@ -335,10 +329,6 @@ public class FuzzySuggesterTest extends 
     return t;
   }
 
-  private static BinaryToken token(BytesRef term) {
-    return new BinaryToken(term);
-  }
-
   /*
   private void printTokens(final Analyzer analyzer, String input) throws IOException {
     System.out.println("Tokens for " + input);
@@ -800,40 +790,48 @@ public class FuzzySuggesterTest extends 
     assertEquals(50, results.get(1).value);
   }
   
-  private static String addRandomEdit(String string, int prefixLenght) {
-    char[] charArray = string.toCharArray();
+  private static String addRandomEdit(String string, int prefixLength) {
+    char[] input = string.toCharArray();
     StringBuilder builder = new StringBuilder();
-    for (int i = 0; i < charArray.length; i++) {
-      if (i >= prefixLenght && random().nextBoolean() && i < charArray.length-1) {
-        switch(random().nextInt(3)){
+    for (int i = 0; i < input.length; i++) {
+      if (i >= prefixLength && random().nextBoolean() && i < input.length-1) {
+        switch(random().nextInt(3)) {
           case 2:
-            for (int j = i+1; j < charArray.length; j++) {
-              builder.append(charArray[j]);  
+            // Delete input[i]
+            for (int j = i+1; j < input.length; j++) {
+              builder.append(input[j]);  
             }
             return builder.toString();
           case 1:
-            if (i+1<charArray.length) {
-              builder.append(charArray[i+1]);
-              builder.append(charArray[i++]);
+            // Insert input[i+1] twice
+            if (i+1<input.length) {
+              builder.append(input[i+1]);
+              builder.append(input[i++]);
               i++;
             }
-            for (int j = i; j < charArray.length; j++) {
-              builder.append(charArray[j]);
+            for (int j = i; j < input.length; j++) {
+              builder.append(input[j]);
             }
             return builder.toString();
           case 0:
+            // Insert random byte.
+            // NOTE: can only use ascii here so that, in
+            // UTF8 byte space it's still a single
+            // insertion:
             int x = random().nextInt(128);
             builder.append((char) x);
-            for (int j = i; j < charArray.length; j++) {
-              builder.append(charArray[j]);  
+            for (int j = i; j < input.length; j++) {
+              builder.append(input[j]);  
             }
             return builder.toString();
-           
+
+          // nocommit need transposition too?
         }
       }
-      builder.append(charArray[i]);
-      
+
+      builder.append(input[i]);
     }
+
     return builder.toString();
   }
 }