lucene-java-3.5.0/lucene/src/java/org/apache/lucene/search/FuzzyTermEnum.java

   1 package org.apache.lucene.search;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 import java.io.IOException;
  21
  22 import org.apache.lucene.index.IndexReader;
  23 import org.apache.lucene.index.Term;
  24
  25 /** Subclass of FilteredTermEnum for enumerating all terms that are similar
  26  * to the specified filter term.
  27  *
  28  * <p>Term enumerations are always ordered by Term.compareTo().  Each term in
  29  * the enumeration is greater than all that precede it.
  30  */
  31 public final class FuzzyTermEnum extends FilteredTermEnum {
  32
  33   /* Allows us save time required to create a new array
  34    * every time similarity is called.
  35    */
  36   private int[] p;
  37   private int[] d;
  38
  39   private float similarity;
  40   private boolean endEnum = false;
  41
  42   private Term searchTerm = null;
  43   private final String field;
  44   private final char[] text;
  45   private final String prefix;
  46
  47   private final float minimumSimilarity;
  48   private final float scale_factor;
  49
  50   /**
  51    * Creates a FuzzyTermEnum with an empty prefix and a minSimilarity of 0.5f.
  52    * <p>
  53    * After calling the constructor the enumeration is already pointing to the first
  54    * valid term if such a term exists.
  55    *
  56    * @param reader
  57    * @param term
  58    * @throws IOException
  59    * @see #FuzzyTermEnum(IndexReader, Term, float, int)
  60    */
  61   public FuzzyTermEnum(IndexReader reader, Term term) throws IOException {
  62     this(reader, term, FuzzyQuery.defaultMinSimilarity, FuzzyQuery.defaultPrefixLength);
  63   }
  64
  65   /**
  66    * Creates a FuzzyTermEnum with an empty prefix.
  67    * <p>
  68    * After calling the constructor the enumeration is already pointing to the first
  69    * valid term if such a term exists.
  70    *
  71    * @param reader
  72    * @param term
  73    * @param minSimilarity
  74    * @throws IOException
  75    * @see #FuzzyTermEnum(IndexReader, Term, float, int)
  76    */
  77   public FuzzyTermEnum(IndexReader reader, Term term, float minSimilarity) throws IOException {
  78     this(reader, term, minSimilarity, FuzzyQuery.defaultPrefixLength);
  79   }
  80
  81   /**
  82    * Constructor for enumeration of all terms from specified <code>reader</code> which share a prefix of
  83    * length <code>prefixLength</code> with <code>term</code> and which have a fuzzy similarity &gt;
  84    * <code>minSimilarity</code>.
  85    * <p>
  86    * After calling the constructor the enumeration is already pointing to the first
  87    * valid term if such a term exists.
  88    *
  89    * @param reader Delivers terms.
  90    * @param term Pattern term.
  91    * @param minSimilarity Minimum required similarity for terms from the reader. Default value is 0.5f.
  92    * @param prefixLength Length of required common prefix. Default value is 0.
  93    * @throws IOException
  94    */
  95   public FuzzyTermEnum(IndexReader reader, Term term, final float minSimilarity, final int prefixLength) throws IOException {
  96     super();
  97
  98     if (minSimilarity >= 1.0f)
  99       throw new IllegalArgumentException("minimumSimilarity cannot be greater than or equal to 1");
 100     else if (minSimilarity < 0.0f)
 101       throw new IllegalArgumentException("minimumSimilarity cannot be less than 0");
 102     if(prefixLength < 0)
 103       throw new IllegalArgumentException("prefixLength cannot be less than 0");
 104
 105     this.minimumSimilarity = minSimilarity;
 106     this.scale_factor = 1.0f / (1.0f - minimumSimilarity);
 107     this.searchTerm = term;
 108     this.field = searchTerm.field();
 109
 110     //The prefix could be longer than the word.
 111     //It's kind of silly though.  It means we must match the entire word.
 112     final int fullSearchTermLength = searchTerm.text().length();
 113     final int realPrefixLength = prefixLength > fullSearchTermLength ? fullSearchTermLength : prefixLength;
 114
 115     this.text = searchTerm.text().substring(realPrefixLength).toCharArray();
 116     this.prefix = searchTerm.text().substring(0, realPrefixLength);
 117
 118     this.p = new int[this.text.length+1];
 119     this.d = new int[this.text.length+1];
 120
 121     setEnum(reader.terms(new Term(searchTerm.field(), prefix)));
 122   }
 123
 124   /**
 125    * The termCompare method in FuzzyTermEnum uses Levenshtein distance to
 126    * calculate the distance between the given term and the comparing term.
 127    */
 128   @Override
 129   protected final boolean termCompare(Term term) {
 130     if (field == term.field() && term.text().startsWith(prefix)) {
 131         final String target = term.text().substring(prefix.length());
 132         this.similarity = similarity(target);
 133         return (similarity > minimumSimilarity);
 134     }
 135     endEnum = true;
 136     return false;
 137   }
 138
 139   /** {@inheritDoc} */
 140   @Override
 141   public final float difference() {
 142     return (similarity - minimumSimilarity) * scale_factor;
 143   }
 144
 145   /** {@inheritDoc} */
 146   @Override
 147   public final boolean endEnum() {
 148     return endEnum;
 149   }
 150
 151   /******************************
 152    * Compute Levenshtein distance
 153    ******************************/
 154
 155   /**
 156    * <p>Similarity returns a number that is 1.0f or less (including negative numbers)
 157    * based on how similar the Term is compared to a target term.  It returns
 158    * exactly 0.0f when
 159    * <pre>
 160    *    editDistance &gt; maximumEditDistance</pre>
 161    * Otherwise it returns:
 162    * <pre>
 163    *    1 - (editDistance / length)</pre>
 164    * where length is the length of the shortest term (text or target) including a
 165    * prefix that are identical and editDistance is the Levenshtein distance for
 166    * the two words.</p>
 167    *
 168    * <p>Embedded within this algorithm is a fail-fast Levenshtein distance
 169    * algorithm.  The fail-fast algorithm differs from the standard Levenshtein
 170    * distance algorithm in that it is aborted if it is discovered that the
 171    * minimum distance between the words is greater than some threshold.
 172    *
 173    * <p>To calculate the maximum distance threshold we use the following formula:
 174    * <pre>
 175    *     (1 - minimumSimilarity) * length</pre>
 176    * where length is the shortest term including any prefix that is not part of the
 177    * similarity comparison.  This formula was derived by solving for what maximum value
 178    * of distance returns false for the following statements:
 179    * <pre>
 180    *   similarity = 1 - ((float)distance / (float) (prefixLength + Math.min(textlen, targetlen)));
 181    *   return (similarity > minimumSimilarity);</pre>
 182    * where distance is the Levenshtein distance for the two words.
 183    * </p>
 184    * <p>Levenshtein distance (also known as edit distance) is a measure of similarity
 185    * between two strings where the distance is measured as the number of character
 186    * deletions, insertions or substitutions required to transform one string to
 187    * the other string.
 188    * @param target the target word or phrase
 189    * @return the similarity,  0.0 or less indicates that it matches less than the required
 190    * threshold and 1.0 indicates that the text and target are identical
 191    */
 192   private float similarity(final String target) {
 193     final int m = target.length();
 194     final int n = text.length;
 195     if (n == 0)  {
 196       //we don't have anything to compare.  That means if we just add
 197       //the letters for m we get the new word
 198       return prefix.length() == 0 ? 0.0f : 1.0f - ((float) m / prefix.length());
 199     }
 200     if (m == 0) {
 201       return prefix.length() == 0 ? 0.0f : 1.0f - ((float) n / prefix.length());
 202     }
 203
 204     final int maxDistance = calculateMaxDistance(m);
 205
 206     if (maxDistance < Math.abs(m-n)) {
 207       //just adding the characters of m to n or vice-versa results in
 208       //too many edits
 209       //for example "pre" length is 3 and "prefixes" length is 8.  We can see that
 210       //given this optimal circumstance, the edit distance cannot be less than 5.
 211       //which is 8-3 or more precisely Math.abs(3-8).
 212       //if our maximum edit distance is 4, then we can discard this word
 213       //without looking at it.
 214       return 0.0f;
 215     }
 216
 217     // init matrix d
 218     for (int i = 0; i<=n; ++i) {
 219       p[i] = i;
 220     }
 221
 222     // start computing edit distance
 223     for (int j = 1; j<=m; ++j) { // iterates through target
 224       int bestPossibleEditDistance = m;
 225       final char t_j = target.charAt(j-1); // jth character of t
 226       d[0] = j;
 227
 228       for (int i=1; i<=n; ++i) { // iterates through text
 229         // minimum of cell to the left+1, to the top+1, diagonally left and up +(0|1)
 230         if (t_j != text[i-1]) {
 231           d[i] = Math.min(Math.min(d[i-1], p[i]),  p[i-1]) + 1;
 232                 } else {
 233           d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]);
 234                 }
 235         bestPossibleEditDistance = Math.min(bestPossibleEditDistance, d[i]);
 236       }
 237
 238       //After calculating row i, the best possible edit distance
 239       //can be found by found by finding the smallest value in a given column.
 240       //If the bestPossibleEditDistance is greater than the max distance, abort.
 241
 242       if (j > maxDistance && bestPossibleEditDistance > maxDistance) {  //equal is okay, but not greater
 243         //the closest the target can be to the text is just too far away.
 244         //this target is leaving the party early.
 245         return 0.0f;
 246       }
 247
 248       // copy current distance counts to 'previous row' distance counts: swap p and d
 249       int _d[] = p;
 250       p = d;
 251       d = _d;
 252     }
 253
 254     // our last action in the above loop was to switch d and p, so p now
 255     // actually has the most recent cost counts
 256
 257     // this will return less than 0.0 when the edit distance is
 258     // greater than the number of characters in the shorter word.
 259     // but this was the formula that was previously used in FuzzyTermEnum,
 260     // so it has not been changed (even though minimumSimilarity must be
 261     // greater than 0.0)
 262     return 1.0f - ((float)p[n] / (float) (prefix.length() + Math.min(n, m)));
 263   }
 264
 265   /**
 266    * The max Distance is the maximum Levenshtein distance for the text
 267    * compared to some other value that results in score that is
 268    * better than the minimum similarity.
 269    * @param m the length of the "other value"
 270    * @return the maximum levenshtein distance that we care about
 271    */
 272   private int calculateMaxDistance(int m) {
 273     return (int) ((1-minimumSimilarity) * (Math.min(text.length, m) + prefix.length()));
 274   }
 275
 276   /** {@inheritDoc} */
 277   @Override
 278   public void close() throws IOException {
 279     p = d = null;
 280     searchTerm = null;
 281     super.close();  //call super.close() and let the garbage collector do its work.
 282   }
 283
 284 }