FuzzyTermEnum


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