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 { /* 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. These are slices that * will be reused during dynamic programming hand-over-hand * style. */ private final int[] d0; private final int[] d1; 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; /** * Creates a FuzzyTermEnum with an empty prefix and a minSimilarity of 0.5f. *

* 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. *

* 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 `reader`

which share a prefix of
* length `prefixLength`

with `term`

and which have a fuzzy similarity >
* `minSimilarity`

.
*

* 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); this.prefix = searchTerm.text().substring(0, realPrefixLength); this.d0 = new int[this.text.length()+1]; this.d1 = new int[this.d0.length]; 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. */ 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; } public final float difference() { return (float)((similarity - minimumSimilarity) * scale_factor); } public final boolean endEnum() { return endEnum; } /****************************** * Compute Levenshtein distance ******************************/ /** * Finds and returns the smallest of three integers */ private static final int min(int a, int b, int c) { // removed assignments to use double ternary return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b: c); // alt form is: // if (a < b) { if (a < c) return a; else return c; } // if (b < c) return b; else return c; } /** *

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 *

* editDistance < maximumEditDistance* Otherwise it returns: *

* 1 - (editDistance / length)* 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. * *

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. * *

To calculate the maximum distance threshold we use the following formula: *

* (1 - minimumSimilarity) * length* 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: *

* similarity = 1 - ((float)distance / (float) (prefixLength + Math.min(textlen, targetlen))); * return (similarity > minimumSimilarity);* where distance is the Levenshtein distance for the two words. * *

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 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 precisesly Math.abs(3-8). //if our maximum edit distance is 4, then we can discard this word //without looking at it. return 0.0f; } int[] dLast = d0; // set locals for efficiency int[] dCurrent = d1; for (int j = 0; j <= n; j++) dCurrent[j] = j; for (int i = 0; i < m; ) { final char s_i = target.charAt(i); int[] dTemp = dLast; dLast = dCurrent; // previously: d[i-i] dCurrent = dTemp; // previously: d[i] boolean prune = (dCurrent[0] = ++i) > maxDistance; // true if d[i][0] is too large for (int j = 0; j < n; j++) { dCurrent[j+1] = (s_i == text.charAt(j)) ? min(dLast[j+1]+1, dCurrent[j]+1, dLast[j]) : min(dLast[j+1], dCurrent[j], dLast[j])+1; if (prune && dCurrent[j+1] <= maxDistance) prune = false; } // (prune==false) iff (dCurrent[j] < maxDistance) for some j if (prune) { return 0.0f; } } // 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 - dCurrent[n]/(float)(prefix.length() + Math.min(n,m)); } private int calculateMaxDistance(int m) { return (int) ((1-minimumSimilarity) * (Math.min(text.length(), m) + prefix.length())); } /* This is redundant public void close() throws IOException { super.close(); //call super.close() and let the garbage collector do its work. } */ } --------------090601080905090901080508 Content-Type: text/plain; name="FuzzyTermEnum.intermed.java" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="FuzzyTermEnum.intermed.java" package org.apache.lucene.search; /** * Copyright 2004 The Apache Software Foundation * * Licensed 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 org.apache.lucene.index.IndexReader; import org.apache.lucene.index.Term; import java.io.IOException; /** Subclass of FilteredTermEnum for enumerating all terms that are similiar * to the specified filter term. * *

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 { /* 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. These are slices that * will be reused during dynamic programming hand-over-hand * style. They get resized, if necessary, by growDistanceArrays(int). */ private int[] d0; private int[] d1; 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; /** * Creates a FuzzyTermEnum with an empty prefix and a minSimilarity of 0.5f. *

* 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. *

* 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 `reader`

which share a prefix of
* length `prefixLength`

with `term`

and which have a fuzzy similarity >
* `minSimilarity`

.
*

* 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); this.prefix = searchTerm.text().substring(0, realPrefixLength); growDistanceArrays(TYPICAL_LONGEST_WORD_IN_INDEX); 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. */ 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; } public final float difference() { return (float)((similarity - minimumSimilarity) * scale_factor); } public final boolean endEnum() { return endEnum; } /****************************** * Compute Levenshtein distance ******************************/ /** * Finds and returns the smallest of three integers */ private static final int min(int a, int b, int c) { // removed assignments to use double ternary return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b: c); // alt form is: // if (a < b) { if (a < c) return a; else return c; } // if (b < c) return b; else return c; } /** *

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 *

* editDistance < maximumEditDistance* Otherwise it returns: *

* 1 - (editDistance / length)* 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. * *

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. * *

To calculate the maximum distance threshold we use the following formula: *

* (1 - minimumSimilarity) * length* 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: *

* similarity = 1 - ((float)distance / (float) (prefixLength + Math.min(textlen, targetlen))); * return (similarity > minimumSimilarity);* where distance is the Levenshtein distance for the two words. * *

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 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 precisesly Math.abs(3-8). //if our maximum edit distance is 4, then 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 (d0.length <= m) { growDistanceArrays(m); } int[] dLast = d0; // set local vars for efficiency ~ the old d[i-1] int[] dCurrent = d1; // ~ the old d[i] for (int j = 0; j <= m; j++) dCurrent[j] = j; for (int i = 0; i < n; ) { final char s_i = text.charAt(i); int[] dTemp = dLast; dLast = dCurrent; // previously: d[i-i] dCurrent = dTemp; // previously: d[i] boolean prune = (dCurrent[0] = ++i) > maxDistance; // true if d[i][0] is too large for (int j = 0; j < m; j++) { dCurrent[j+1] = (s_i == target.charAt(j)) ? min(dLast[j+1]+1, dCurrent[j]+1, dLast[j]) : min(dLast[j+1], dCurrent[j], dLast[j])+1; if (prune && dCurrent[j+1] <= maxDistance) prune = false; } // (prune==false) iff (dCurrent[j] < maxDistance) for some j if (prune) { return 0.0f; } } // 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 - dCurrent[m]/(float)(prefix.length() + Math.min(n,m)); } /** * Grow the second dimension of the array slices, so that we can * calculate the Levenshtein difference. */ private void growDistanceArrays(int m) { d0 = new int[m+1]; d1 = new int[m+1]; } private int calculateMaxDistance(int m) { return (int) ((1-minimumSimilarity) * (Math.min(text.length(), m) + prefix.length())); } /* This is redundant public void close() throws IOException { super.close(); //call super.close() and let the garbage collector do its work. } */ } --------------090601080905090901080508 Content-Type: text/plain; charset=us-ascii --------------------------------------------------------------------- To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org For additional commands, e-mail: java-dev-help@lucene.apache.org --------------090601080905090901080508--