--- /dev/null
+package org.apache.lucene.search;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * 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 similar
+ * 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 {
+
+ /* Allows us save time required to create a new array
+ * every time similarity is called.
+ */
+ private int[] p;
+ private int[] d;
+
+ private float similarity;
+ private boolean endEnum = false;
+
+ private Term searchTerm = null;
+ private final String field;
+ private final char[] text;
+ private final String prefix;
+
+ private final float minimumSimilarity;
+ private final float scale_factor;
+
+ /**
+ * Creates a FuzzyTermEnum with an empty prefix and a minSimilarity of 0.5f.
+ * <p>
+ * After calling the constructor the enumeration is already pointing to the first
+ * valid term if such a term exists.
+ *
+ * @param reader
+ * @param term
+ * @throws IOException
+ * @see #FuzzyTermEnum(IndexReader, Term, float, int)
+ */
+ public FuzzyTermEnum(IndexReader reader, Term term) throws IOException {
+ this(reader, term, FuzzyQuery.defaultMinSimilarity, FuzzyQuery.defaultPrefixLength);
+ }
+
+ /**
+ * Creates a FuzzyTermEnum with an empty prefix.
+ * <p>
+ * After calling the constructor the enumeration is already pointing to the first
+ * valid term if such a term exists.
+ *
+ * @param reader
+ * @param term
+ * @param minSimilarity
+ * @throws IOException
+ * @see #FuzzyTermEnum(IndexReader, Term, float, int)
+ */
+ public FuzzyTermEnum(IndexReader reader, Term term, float minSimilarity) throws IOException {
+ this(reader, term, minSimilarity, FuzzyQuery.defaultPrefixLength);
+ }
+
+ /**
+ * Constructor for enumeration of all terms from specified <code>reader</code> which share a prefix of
+ * length <code>prefixLength</code> with <code>term</code> and which have a fuzzy similarity >
+ * <code>minSimilarity</code>.
+ * <p>
+ * After calling the constructor the enumeration is already pointing to the first
+ * valid term if such a term exists.
+ *
+ * @param reader Delivers terms.
+ * @param term Pattern term.
+ * @param minSimilarity Minimum required similarity for terms from the reader. Default value is 0.5f.
+ * @param prefixLength Length of required common prefix. Default value is 0.
+ * @throws IOException
+ */
+ public FuzzyTermEnum(IndexReader reader, Term term, final float minSimilarity, final int prefixLength) throws IOException {
+ super();
+
+ 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 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).toCharArray();
+ this.prefix = searchTerm.text().substring(0, realPrefixLength);
+
+ this.p = new int[this.text.length+1];
+ this.d = new int[this.text.length+1];
+
+ 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.
+ */
+ @Override
+ protected final boolean termCompare(Term term) {
+ 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;
+ return false;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public final float difference() {
+ return (similarity - minimumSimilarity) * scale_factor;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public final boolean endEnum() {
+ return endEnum;
+ }
+
+ /******************************
+ * Compute Levenshtein distance
+ ******************************/
+
+ /**
+ * <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 > 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
+ * minimum 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 comparison. 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 similarity
+ * 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 float similarity(final String target) {
+ final int m = target.length();
+ final int n = text.length;
+ if (n == 0) {
+ //we don't have anything 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 = calculateMaxDistance(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 precisely Math.abs(3-8).
+ //if our maximum edit distance is 4, then we can discard this word
+ //without looking at it.
+ return 0.0f;
+ }
+
+ // init matrix d
+ for (int i = 0; i<=n; ++i) {
+ p[i] = i;
+ }
+
+ // start computing edit distance
+ for (int j = 1; j<=m; ++j) { // iterates through target
+ int bestPossibleEditDistance = m;
+ final char t_j = target.charAt(j-1); // jth character of t
+ d[0] = j;
+
+ for (int i=1; i<=n; ++i) { // iterates through text
+ // minimum of cell to the left+1, to the top+1, diagonally left and up +(0|1)
+ if (t_j != text[i-1]) {
+ d[i] = Math.min(Math.min(d[i-1], p[i]), p[i-1]) + 1;
+ } else {
+ d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]);
+ }
+ bestPossibleEditDistance = Math.min(bestPossibleEditDistance, d[i]);
+ }
+
+ //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 (j > 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;
+ }
+
+ // copy current distance counts to 'previous row' distance counts: swap p and d
+ int _d[] = p;
+ p = d;
+ d = _d;
+ }
+
+ // our last action in the above loop was to switch d and p, so p now
+ // actually has the most recent cost counts
+
+ // 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)p[n] / (float) (prefix.length() + Math.min(n, m)));
+ }
+
+ /**
+ * 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 int calculateMaxDistance(int m) {
+ return (int) ((1-minimumSimilarity) * (Math.min(text.length, m) + prefix.length()));
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public void close() throws IOException {
+ p = d = null;
+ searchTerm = null;
+ super.close(); //call super.close() and let the garbage collector do its work.
+ }
+
+}
fnp / pylucene.git / blobdiff