lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dna...@apache.org
Subject cvs commit: jakarta-lucene/src/java/org/apache/lucene/search FuzzyTermEnum.java
Date Sun, 07 Nov 2004 23:27:24 GMT
dnaber      2004/11/07 15:27:24

  Modified:    src/java/org/apache/lucene/search FuzzyTermEnum.java
  Log:
  speed up Fuzzy queries 20%-50%, I only did some small whitespace and comment fixes compared
to the original patch
  PR: 31882
  Submitted by: Jonathan Hager
  
  Revision  Changes    Path
  1.10      +201 -95   jakarta-lucene/src/java/org/apache/lucene/search/FuzzyTermEnum.java
  
  Index: FuzzyTermEnum.java
  ===================================================================
  RCS file: /home/cvs/jakarta-lucene/src/java/org/apache/lucene/search/FuzzyTermEnum.java,v
  retrieving revision 1.9
  retrieving revision 1.10
  diff -u -r1.9 -r1.10
  --- FuzzyTermEnum.java	6 Oct 2004 16:19:51 -0000	1.9
  +++ FuzzyTermEnum.java	7 Nov 2004 23:27:24 -0000	1.10
  @@ -16,30 +16,44 @@
    * limitations under the License.
    */
   
  -import java.io.IOException;
   import org.apache.lucene.index.IndexReader;
   import org.apache.lucene.index.Term;
   
  -/** Subclass of FilteredTermEnum for enumerating all terms that are similiar to the specified
filter term.
  +import java.io.IOException;
   
  -  <p>Term enumerations are always ordered by Term.compareTo().  Each term in
  -  the enumeration is greater than all that precede it.  */
  +/** Subclass of FilteredTermEnum for enumerating all terms that are similiar
  + * to the specified filter term.
  + *
  + * <p>Term enumerations are always ordered by Term.compareTo().  Each term in
  + * the enumeration is greater than all that precede it.
  + */
   public final class FuzzyTermEnum extends FilteredTermEnum {
  -    float similarity;
  -    boolean endEnum = false;
   
  -    Term searchTerm = null;
  -    String field = "";
  -    String text = "";
  -    int textlen;
  -    String prefix = "";
  -    int prefixLength = 0;
  -    float minimumSimilarity;
  -    float scale_factor;
  -    
  -    
  +    /* This should be somewhere around the average long word.
  +     * If it is longer, we waste time and space. If it is shorter, we waste a
  +     * little bit of time growing the array as we encounter longer words.
  +     */
  +    private static final int TYPICAL_LONGEST_WORD_IN_INDEX = 19;
  +
  +    /* Allows us save time required to create a new array
  +     * everytime similarity is called.
  +     */
  +    private int[][] d;
  +
  +    private float similarity;
  +    private boolean endEnum = false;
  +
  +    private Term searchTerm = null;
  +    private final String field;
  +    private final String text;
  +    private final String prefix;
  +
  +    private final float minimumSimilarity;
  +    private final float scale_factor;
  +    private final int[] maxDistances = new int[TYPICAL_LONGEST_WORD_IN_INDEX];
  +
       /**
  -     * Empty prefix and minSimilarity of 0.5f are used.
  +     * Creates a FuzzyTermEnum with an empty prefix and a minSimilarity of 0.5f.
        * 
        * @param reader
        * @param term
  @@ -51,7 +65,7 @@
       }
       
       /**
  -     * This is the standard FuzzyTermEnum with an empty prefix.
  +     * Creates a FuzzyTermEnum with an empty prefix.
        * 
        * @param reader
        * @param term
  @@ -74,46 +88,43 @@
        * @param prefixLength Length of required common prefix. Default value is 0.
        * @throws IOException
        */
  -    public FuzzyTermEnum(IndexReader reader, Term term, float minSimilarity, int prefixLength)
throws IOException {
  +    public FuzzyTermEnum(IndexReader reader, Term term, final float minSimilarity, final
int prefixLength) throws IOException {
           super();
           
  -        if (minimumSimilarity >= 1.0f)
  -          throw new IllegalArgumentException("minimumSimilarity >= 1");
  -        else if (minimumSimilarity < 0.0f)
  -          throw new IllegalArgumentException("minimumSimilarity < 0");
  -        
  -        minimumSimilarity = minSimilarity;
  -        scale_factor = 1.0f / (1.0f - minimumSimilarity);
  -        searchTerm = term;
  -        field = searchTerm.field();
  -        text = searchTerm.text();
  -        textlen = text.length();
  -        
  +        if (minSimilarity >= 1.0f)
  +          throw new IllegalArgumentException("minimumSimilarity cannot be greater than
or equal to 1");
  +        else if (minSimilarity < 0.0f)
  +          throw new IllegalArgumentException("minimumSimilarity cannot be less than 0");
           if(prefixLength < 0)
  -          throw new IllegalArgumentException("prefixLength < 0");
  -        
  -        if(prefixLength > textlen)
  -          prefixLength = textlen;
  -        
  -        this.prefixLength = prefixLength;
  -        prefix = text.substring(0, prefixLength);
  -        text = text.substring(prefixLength);
  -        textlen = text.length();
  -        
  +          throw new IllegalArgumentException("prefixLength cannot be less than 0");
  +
  +        this.minimumSimilarity = minSimilarity;
  +        this.scale_factor = 1.0f / (1.0f - minimumSimilarity);
  +        this.searchTerm = term;
  +        this.field = searchTerm.field();
  +
  +        //The prefix could be longer than the word.
  +        //It's kind of silly though.  It means we must match the entire word.
  +        final int fullSearchTermLength = searchTerm.text().length();
  +        final int realPrefixLength = prefixLength > fullSearchTermLength ? fullSearchTermLength
: prefixLength;
  +
  +        this.text = searchTerm.text().substring(realPrefixLength);
  +        this.prefix = searchTerm.text().substring(0, realPrefixLength);
  +
  +        initializeMaxDistances();
  +        this.d = initDistanceArray();
  +
           setEnum(reader.terms(new Term(searchTerm.field(), prefix)));
       }
  -    
  +
       /**
  -     The termCompare method in FuzzyTermEnum uses Levenshtein distance to 
  -     calculate the distance between the given term and the comparing term. 
  +     * The termCompare method in FuzzyTermEnum uses Levenshtein distance to 
  +     * calculate the distance between the given term and the comparing term. 
        */
       protected final boolean termCompare(Term term) {
  -        String termText = term.text();
  -        if (field == term.field() && termText.startsWith(prefix)) {
  -            String target = termText.substring(prefixLength);
  -            int targetlen = target.length();
  -            int dist = editDistance(text, target, textlen, targetlen);
  -            similarity = 1 - ((float)dist / (float) (prefixLength + Math.min(textlen, targetlen)));
  +        if (field == term.field() && term.text().startsWith(prefix)) {
  +            final String target = term.text().substring(prefix.length());
  +            this.similarity = similarity(target);
               return (similarity > minimumSimilarity);
           }
           endEnum = true;
  @@ -133,62 +144,157 @@
        ******************************/
       
       /**
  -     Finds and returns the smallest of three integers 
  +     * Finds and returns the smallest of three integers 
        */
       private static final int min(int a, int b, int c) {
  -        int t = (a < b) ? a : b;
  +        final int t = (a < b) ? a : b;
           return (t < c) ? t : c;
       }
  -    
  -    /**
  -     * This static array saves us from the time required to create a new array
  -     * everytime editDistance is called.
  -     */
  -    private int e[][] = new int[1][1];
  -    
  -    /**
  -     Levenshtein distance also known as edit distance is a measure of similiarity
  -     between two strings where the distance is measured as the number of character 
  -     deletions, insertions or substitutions required to transform one string to 
  -     the other string. 
  -     <p>This method takes in four parameters; two strings and their respective 
  -     lengths to compute the Levenshtein distance between the two strings.
  -     The result is returned as an integer.
  -     */ 
  -    private final int editDistance(String s, String t, int n, int m) {
  -        if (e.length <= n || e[0].length <= m) {
  -            e = new int[Math.max(e.length, n+1)][Math.max(e[0].length, m+1)];
  -        }
  -        int d[][] = e; // matrix
  -        int i; // iterates through s
  -        int j; // iterates through t
  -        char s_i; // ith character of s
  -        
  -        if (n == 0) return m;
  -        if (m == 0) return n;
  -        
  +
  +  private final int[][] initDistanceArray(){
  +    return new int[this.text.length() + 1][TYPICAL_LONGEST_WORD_IN_INDEX];
  +  }
  +
  +  /**
  +   * <p>Similarity returns a number that is 1.0f or less (including negative numbers)
  +   * based on how similar the Term is compared to a target term.  It returns
  +   * exactly 0.0f when
  +   * <pre>
  +   *    editDistance &lt; maximumEditDistance</pre>
  +   * Otherwise it returns:
  +   * <pre>
  +   *    1 - (editDistance / length)</pre>
  +   * where length is the length of the shortest term (text or target) including a
  +   * prefix that are identical and editDistance is the Levenshtein distance for
  +   * the two words.</p>
  +   *
  +   * <p>Embedded within this algorithm is a fail-fast Levenshtein distance
  +   * algorithm.  The fail-fast algorithm differs from the standard Levenshtein
  +   * distance algorithm in that it is aborted if it is discovered that the
  +   * mimimum distance between the words is greater than some threshold.
  +   *
  +   * <p>To calculate the maximum distance threshold we use the following formula:
  +   * <pre>
  +   *     (1 - minimumSimilarity) / length</pre>
  +   * where length is the shortest term including any prefix that is not part of the
  +   * similarity comparision.  This formula was derived by solving for what maximum value
  +   * of distance returns false for the following statements:
  +   * <pre>
  +   *   similarity = 1 - ((float)distance / (float) (prefixLength + Math.min(textlen, targetlen)));
  +   *   return (similarity > minimumSimilarity);</pre>
  +   * where distance is the Levenshtein distance for the two words.
  +   * </p>
  +   * <p>Levenshtein distance (also known as edit distance) is a measure of similiarity
  +   * between two strings where the distance is measured as the number of character
  +   * deletions, insertions or substitutions required to transform one string to
  +   * the other string.
  +   * @param target the target word or phrase
  +   * @return the similarity,  0.0 or less indicates that it matches less than the required
  +   * threshold and 1.0 indicates that the text and target are identical
  +   */
  +    private synchronized final float similarity(final String target) {
  +        final int m = target.length();
  +        final int n = text.length();
  +        if (n == 0)  {
  +          //we don't have antyhing to compare.  That means if we just add
  +          //the letters for m we get the new word
  +          return prefix.length() == 0 ? 0.0f : 1.0f - ((float) m / prefix.length());
  +        }
  +        if (m == 0) {
  +          return prefix.length() == 0 ? 0.0f : 1.0f - ((float) n / prefix.length());
  +        }
  +
  +        final int maxDistance = getMaxDistance(m);
  +
  +        if (maxDistance < Math.abs(m-n)) {
  +          //just adding the characters of m to n or vice-versa results in
  +          //too many edits
  +          //for example "pre" length is 3 and "prefixes" length is 8.  We can see that
  +          //given this optimal circumstance, the edit distance cannot be less than 5.
  +          //which is 8-3 or more precisesly Math.abs(3-8).
  +          //if our maximum edit distance is 4, than we can discard this word
  +          //without looking at it.
  +          return 0.0f;
  +        }
  +
  +        //let's make sure we have enough room in our array to do the distance calculations.
  +        if (d[0].length <= m) {
  +          growDistanceArray(m);
  +        }
  +
           // init matrix d
  -        for (i = 0; i <= n; i++) d[i][0] = i;
  -        for (j = 0; j <= m; j++) d[0][j] = j;
  +        for (int i = 0; i <= n; i++) d[i][0] = i;
  +        for (int j = 0; j <= m; j++) d[0][j] = j;
           
           // start computing edit distance
  -        for (i = 1; i <= n; i++) {
  -            s_i = s.charAt(i - 1);
  -            for (j = 1; j <= m; j++) {
  -                if (s_i != t.charAt(j-1))
  +        for (int i = 1; i <= n; i++) {
  +            int bestPossibleEditDistance = m;
  +            final char s_i = text.charAt(i - 1);
  +            for (int j = 1; j <= m; j++) {
  +                if (s_i != target.charAt(j-1)) {
                       d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1])+1;
  -                else d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]);
  +                }
  +                else {
  +                  d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]);
  +                }
  +                bestPossibleEditDistance = Math.min(bestPossibleEditDistance, d[i][j]);
               }
  +
  +          //After calculating row i, the best possible edit distance
  +          //can be found by found by finding the smallest value in a given column.
  +          //If the bestPossibleEditDistance is greater than the max distance, abort.
  +
  +          if (i > maxDistance && bestPossibleEditDistance > maxDistance)
{  //equal is okay, but not greater
  +            //the closest the target can be to the text is just too far away.
  +            //this target is leaving the party early.
  +            return 0.0f;
  +          }
           }
  -        
  -        // we got the result!
  -        return d[n][m];
  +
  +        // this will return less than 0.0 when the edit distance is
  +        // greater than the number of characters in the shorter word.
  +        // but this was the formula that was previously used in FuzzyTermEnum,
  +        // so it has not been changed (even though minimumSimilarity must be
  +        // greater than 0.0)
  +        return 1.0f - ((float)d[n][m] / (float) (prefix.length() + Math.min(n, m)));
  +
       }
  -    
  +
  +  /**
  +   * Grow the second dimension of the array, so that we can calculate the
  +   * Levenshtein difference.
  +   */
  +  private void growDistanceArray(int m) {
  +    for (int i = 0; i < d.length; i++)
  +    {
  +      d[i] = new int[m+1];
  +    }
  +  }
  +
  +  /**
  +   * The max Distance is the maximum Levenshtein distance for the text
  +   * compared to some other value that results in score that is
  +   * better than the minimum similarity.
  +   * @param m the length of the "other value"
  +   * @return the maximum levenshtein distance that we care about
  +   */
  +  private final int getMaxDistance(int m) {
  +    return (m < maxDistances.length) ? maxDistances[m] : calculateMaxDistance(m);
  +  }
  +
  +  private void initializeMaxDistances() {
  +    for (int i = 0; i < maxDistances.length; i++)
  +    {
  +      maxDistances[i] = calculateMaxDistance(i);
  +    }
  +  }
  +  
  +  private int calculateMaxDistance(int m) {
  +    return (int) ((1-minimumSimilarity) * (Math.min(text.length(), m) + prefix.length()));
  +  }
  +
     public void close() throws IOException {
  -      super.close();
  -      searchTerm = null;
  -      field = null;
  -      text = null;
  +    super.close();  //call super.close() and let the garbage collector do its work.
     }
  +  
   }
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: lucene-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: lucene-dev-help@jakarta.apache.org


Mime
View raw message