lucene-java-3.5.0/lucene/src/java/org/apache/lucene/search/FuzzyQuery.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 org.apache.lucene.index.IndexReader;
  21 import org.apache.lucene.index.Term;
  22 import org.apache.lucene.util.ToStringUtils;
  23
  24 import java.io.IOException;
  25
  26 /** Implements the fuzzy search query. The similarity measurement
  27  * is based on the Levenshtein (edit distance) algorithm.
  28  *
  29  * <p><em>Warning:</em> this query is not very scalable with its default prefix
  30  * length of 0 - in this case, *every* term will be enumerated and
  31  * cause an edit score calculation.
  32  *
  33  * <p>This query uses {@link MultiTermQuery.TopTermsScoringBooleanQueryRewrite}
  34  * as default. So terms will be collected and scored according to their
  35  * edit distance. Only the top terms are used for building the {@link BooleanQuery}.
  36  * It is not recommended to change the rewrite mode for fuzzy queries.
  37  */
  38 public class FuzzyQuery extends MultiTermQuery {
  39
  40   public final static float defaultMinSimilarity = 0.5f;
  41   public final static int defaultPrefixLength = 0;
  42   public final static int defaultMaxExpansions = Integer.MAX_VALUE;
  43
  44   private float minimumSimilarity;
  45   private int prefixLength;
  46   private boolean termLongEnough = false;
  47
  48   protected Term term;
  49
  50   /**
  51    * Create a new FuzzyQuery that will match terms with a similarity
  52    * of at least <code>minimumSimilarity</code> to <code>term</code>.
  53    * If a <code>prefixLength</code> &gt; 0 is specified, a common prefix
  54    * of that length is also required.
  55    *
  56    * @param term the term to search for
  57    * @param minimumSimilarity a value between 0 and 1 to set the required similarity
  58    *  between the query term and the matching terms. For example, for a
  59    *  <code>minimumSimilarity</code> of <code>0.5</code> a term of the same length
  60    *  as the query term is considered similar to the query term if the edit distance
  61    *  between both terms is less than <code>length(term)*0.5</code>
  62    * @param prefixLength length of common (non-fuzzy) prefix
  63    * @param maxExpansions the maximum number of terms to match. If this number is
  64    *  greater than {@link BooleanQuery#getMaxClauseCount} when the query is rewritten,
  65    *  then the maxClauseCount will be used instead.
  66    * @throws IllegalArgumentException if minimumSimilarity is &gt;= 1 or &lt; 0
  67    * or if prefixLength &lt; 0
  68    */
  69   public FuzzyQuery(Term term, float minimumSimilarity, int prefixLength,
  70       int maxExpansions) {
  71     this.term = term;
  72
  73     if (minimumSimilarity >= 1.0f)
  74       throw new IllegalArgumentException("minimumSimilarity >= 1");
  75     else if (minimumSimilarity < 0.0f)
  76       throw new IllegalArgumentException("minimumSimilarity < 0");
  77     if (prefixLength < 0)
  78       throw new IllegalArgumentException("prefixLength < 0");
  79     if (maxExpansions < 0)
  80       throw new IllegalArgumentException("maxExpansions < 0");
  81
  82     setRewriteMethod(new MultiTermQuery.TopTermsScoringBooleanQueryRewrite(maxExpansions));
  83
  84     if (term.text().length() > 1.0f / (1.0f - minimumSimilarity)) {
  85       this.termLongEnough = true;
  86     }
  87
  88     this.minimumSimilarity = minimumSimilarity;
  89     this.prefixLength = prefixLength;
  90   }
  91
  92   /**
  93    * Calls {@link #FuzzyQuery(Term, float) FuzzyQuery(term, minimumSimilarity, prefixLength, Integer.MAX_VALUE)}.
  94    */
  95   public FuzzyQuery(Term term, float minimumSimilarity, int prefixLength) {
  96     this(term, minimumSimilarity, prefixLength, defaultMaxExpansions);
  97   }
  98
  99   /**
 100    * Calls {@link #FuzzyQuery(Term, float) FuzzyQuery(term, minimumSimilarity, 0, Integer.MAX_VALUE)}.
 101    */
 102   public FuzzyQuery(Term term, float minimumSimilarity) {
 103     this(term, minimumSimilarity, defaultPrefixLength, defaultMaxExpansions);
 104   }
 105
 106   /**
 107    * Calls {@link #FuzzyQuery(Term, float) FuzzyQuery(term, 0.5f, 0, Integer.MAX_VALUE)}.
 108    */
 109   public FuzzyQuery(Term term) {
 110     this(term, defaultMinSimilarity, defaultPrefixLength, defaultMaxExpansions);
 111   }
 112
 113   /**
 114    * Returns the minimum similarity that is required for this query to match.
 115    * @return float value between 0.0 and 1.0
 116    */
 117   public float getMinSimilarity() {
 118     return minimumSimilarity;
 119   }
 120
 121   /**
 122    * Returns the non-fuzzy prefix length. This is the number of characters at the start
 123    * of a term that must be identical (not fuzzy) to the query term if the query
 124    * is to match that term.
 125    */
 126   public int getPrefixLength() {
 127     return prefixLength;
 128   }
 129
 130   @Override
 131   protected FilteredTermEnum getEnum(IndexReader reader) throws IOException {
 132     if (!termLongEnough) {  // can only match if it's exact
 133       return new SingleTermEnum(reader, term);
 134     }
 135     return new FuzzyTermEnum(reader, getTerm(), minimumSimilarity, prefixLength);
 136   }
 137
 138   /**
 139    * Returns the pattern term.
 140    */
 141   public Term getTerm() {
 142     return term;
 143   }
 144
 145   @Override
 146   public String toString(String field) {
 147     final StringBuilder buffer = new StringBuilder();
 148     if (!term.field().equals(field)) {
 149         buffer.append(term.field());
 150         buffer.append(":");
 151     }
 152     buffer.append(term.text());
 153     buffer.append('~');
 154     buffer.append(Float.toString(minimumSimilarity));
 155     buffer.append(ToStringUtils.boost(getBoost()));
 156     return buffer.toString();
 157   }
 158
 159   @Override
 160   public int hashCode() {
 161     final int prime = 31;
 162     int result = super.hashCode();
 163     result = prime * result + Float.floatToIntBits(minimumSimilarity);
 164     result = prime * result + prefixLength;
 165     result = prime * result + ((term == null) ? 0 : term.hashCode());
 166     return result;
 167   }
 168
 169   @Override
 170   public boolean equals(Object obj) {
 171     if (this == obj)
 172       return true;
 173     if (!super.equals(obj))
 174       return false;
 175     if (getClass() != obj.getClass())
 176       return false;
 177     FuzzyQuery other = (FuzzyQuery) obj;
 178     if (Float.floatToIntBits(minimumSimilarity) != Float
 179         .floatToIntBits(other.minimumSimilarity))
 180       return false;
 181     if (prefixLength != other.prefixLength)
 182       return false;
 183     if (term == null) {
 184       if (other.term != null)
 185         return false;
 186     } else if (!term.equals(other.term))
 187       return false;
 188     return true;
 189   }
 190
 191
 192 }