beagled/Lucene.Net/Search/FuzzyTermEnum.cs

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