← Back to branch summary

~ubuntu-branches/ubuntu/trusty/pylucene/trusty

« back to all changes in this revision

Viewing changes to lucene-java-3.5.0/lucene/src/java/org/apache/lucene/search/FuzzyTermEnum.java

  • Committer: Package Import Robot
  • Author(s): Dmitry Nezhevenko
  • Date: 2012-04-23 16:43:55 UTC
  • mfrom: (1.1.1)
  • Revision ID: package-import@ubuntu.com-20120423164355-grqtepnwtecdjfk2
Tags: 3.5.0-1
http://bugs.debian.org/670179
http://bugs.debian.org/581198
http://bugs.debian.org/632240
http://bugs.debian.org/581197
* New maintainer (closes: 670179)
* New upstream release
* Switch to dpkg-source 3.0 (quilt) format
* Switch to machine-readable debian/copyright
* Bump debian/compat to 8, drop debian/pycompat
* Switch from cdbs to dh
* Add watch file
* Build for all supported versions of python2 (closes: 581198, 632240)
* Rename binary package to python-lucene (closes: 581197)
* Add -dbg package

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
}