/* * 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. */ using System; using IndexReader = Lucene.Net.Index.IndexReader; using Term = Lucene.Net.Index.Term; namespace Lucene.Net.Search { /// <summary>Subclass of FilteredTermEnum for enumerating all terms that are similiar /// 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. /// </summary> 00030 public sealed class FuzzyTermEnum : 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 const int TYPICAL_LONGEST_WORD_IN_INDEX = 19; /* Allows us save time required to create a new array * everytime similarity is called. */ private int[][] d; private float similarity; private bool endEnum = false; private Term searchTerm = null; private System.String field; private System.String text; private System.String prefix; private float minimumSimilarity; private float scale_factor; private int[] maxDistances = new int[TYPICAL_LONGEST_WORD_IN_INDEX]; /// <summary> 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. /// /// </summary> /// <param name="reader"> /// </param> /// <param name="term"> /// </param> /// <throws> IOException </throws> /// <seealso cref="FuzzyTermEnum(IndexReader, Term, float, int)"> /// </seealso> 00069 public FuzzyTermEnum(IndexReader reader, Term term) : this(reader, term, FuzzyQuery.defaultMinSimilarity, FuzzyQuery.defaultPrefixLength) { } /// <summary> 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. /// /// </summary> /// <param name="reader"> /// </param> /// <param name="term"> /// </param> /// <param name="minSimilarity"> /// </param> /// <throws> IOException </throws> /// <seealso cref="FuzzyTermEnum(IndexReader, Term, float, int)"> /// </seealso> 00088 public FuzzyTermEnum(IndexReader reader, Term term, float minSimilarity) : this(reader, term, minSimilarity, FuzzyQuery.defaultPrefixLength) { } /// <summary> 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. /// /// </summary> /// <param name="reader">Delivers terms. /// </param> /// <param name="term">Pattern term. /// </param> /// <param name="minSimilarity">Minimum required similarity for terms from the reader. Default value is 0.5f. /// </param> /// <param name="prefixLength">Length of required common prefix. Default value is 0. /// </param> /// <throws> IOException </throws> 00109 public FuzzyTermEnum(IndexReader reader, Term term, float minSimilarity, int prefixLength) : base() { if (minSimilarity >= 1.0f) throw new System.ArgumentException("minimumSimilarity cannot be greater than or equal to 1"); else if (minSimilarity < 0.0f) throw new System.ArgumentException("minimumSimilarity cannot be less than 0"); if (prefixLength < 0) throw new System.ArgumentException("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. int fullSearchTermLength = searchTerm.Text().Length; int realPrefixLength = prefixLength > fullSearchTermLength?fullSearchTermLength:prefixLength; this.text = searchTerm.Text().Substring(realPrefixLength); this.prefix = searchTerm.Text().Substring(0, (realPrefixLength) - (0)); InitializeMaxDistances(); this.d = InitDistanceArray(); SetEnum(reader.Terms(new Term(searchTerm.Field(), prefix))); } /// <summary> The termCompare method in FuzzyTermEnum uses Levenshtein distance to /// calculate the distance between the given term and the comparing term. /// </summary> 00141 protected internal override bool TermCompare(Term term) { if (field == term.Field() && term.Text().StartsWith(prefix)) { System.String target = term.Text().Substring(prefix.Length); this.similarity = Similarity(target); return (similarity > minimumSimilarity); } endEnum = true; return false; } 00153 public override float Difference() { return (float) ((similarity - minimumSimilarity) * scale_factor); } 00158 public override bool EndEnum() { return endEnum; } /// <summary>*************************** /// Compute Levenshtein distance /// **************************** /// </summary> /// <summary> Finds and returns the smallest of three integers </summary> 00169 private static int min(int a, int b, int c) { int t = (a < b) ? a : b; return (t < c) ? t : c; } private int[][] InitDistanceArray() { int[][] tmpArray = new int[this.text.Length + 1][]; for (int i = 0; i < this.text.Length + 1; i++) { tmpArray[i] = new int[TYPICAL_LONGEST_WORD_IN_INDEX]; } return tmpArray; } /// <summary> <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 /// mimimum 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 comparision. 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 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. /// </summary> /// <param name="target">the target word or phrase /// </param> /// <returns> 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 /// </returns> 00223 private float Similarity(System.String target) { lock (this) { int m = target.Length; 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); } int maxDistance = GetMaxDistance(m); if (maxDistance < System.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 (d[0].Length <= m) { GrowDistanceArray(m); } // init matrix d for (int i = 0; i <= n; i++) d[i][0] = i; for (int j = 0; j <= m; j++) d[0][j] = j; // start computing edit distance for (int i = 1; i <= n; i++) { int bestPossibleEditDistance = m; char s_i = text[i - 1]; for (int j = 1; j <= m; j++) { if (s_i != target[j - 1]) { d[i][j] = min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]) + 1; } else { d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1]); } bestPossibleEditDistance = System.Math.Min(bestPossibleEditDistance, d[i][j]); } //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 (i > 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; } } // 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) d[n][m] / (float) (prefix.Length + System.Math.Min(n, m))); } } /// <summary> Grow the second dimension of the array, so that we can calculate the /// Levenshtein difference. /// </summary> 00309 private void GrowDistanceArray(int m) { for (int i = 0; i < d.Length; i++) { d[i] = new int[m + 1]; } } /// <summary> 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. /// </summary> /// <param name="m">the length of the "other value" /// </param> /// <returns> the maximum levenshtein distance that we care about /// </returns> 00325 private int GetMaxDistance(int m) { return (m < maxDistances.Length)?maxDistances[m]:CalculateMaxDistance(m); } private void InitializeMaxDistances() { for (int i = 0; i < maxDistances.Length; i++) { maxDistances[i] = CalculateMaxDistance(i); } } private int CalculateMaxDistance(int m) { return (int) ((1 - minimumSimilarity) * (System.Math.Min(text.Length, m) + prefix.Length)); } 00343 public override void Close() { base.Close(); //call super.close() and let the garbage collector do its work. } } }

Generated by Doxygen 1.6.0 Back to index