--- /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 java.io.StringReader;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+
+import org.apache.lucene.analysis.Analyzer;
+import org.apache.lucene.analysis.TokenStream;
+import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.index.TermEnum;
+import org.apache.lucene.util.PriorityQueue;
+
+/**
+ * Fuzzifies ALL terms provided as strings and then picks the best n differentiating terms.
+ * In effect this mixes the behaviour of FuzzyQuery and MoreLikeThis but with special consideration
+ * of fuzzy scoring factors.
+ * This generally produces good results for queries where users may provide details in a number of
+ * fields and have no knowledge of boolean query syntax and also want a degree of fuzzy matching and
+ * a fast query.
+ *
+ * For each source term the fuzzy variants are held in a BooleanQuery with no coord factor (because
+ * we are not looking for matches on multiple variants in any one doc). Additionally, a specialized
+ * TermQuery is used for variants and does not use that variant term's IDF because this would favour rarer
+ * terms eg misspellings. Instead, all variants use the same IDF ranking (the one for the source query
+ * term) and this is factored into the variant's boost. If the source query term does not exist in the
+ * index the average IDF of the variants is used.
+ */
+public class FuzzyLikeThisQuery extends Query
+{
+ static Similarity sim=new DefaultSimilarity();
+ Query rewrittenQuery=null;
+ ArrayList<FieldVals> fieldVals=new ArrayList<FieldVals>();
+ Analyzer analyzer;
+
+ ScoreTermQueue q;
+ int MAX_VARIANTS_PER_TERM=50;
+ boolean ignoreTF=false;
+ private int maxNumTerms;
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + ((analyzer == null) ? 0 : analyzer.hashCode());
+ result = prime * result
+ + ((fieldVals == null) ? 0 : fieldVals.hashCode());
+ result = prime * result + (ignoreTF ? 1231 : 1237);
+ result = prime * result + maxNumTerms;
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (getClass() != obj.getClass())
+ return false;
+ FuzzyLikeThisQuery other = (FuzzyLikeThisQuery) obj;
+ if (analyzer == null) {
+ if (other.analyzer != null)
+ return false;
+ } else if (!analyzer.equals(other.analyzer))
+ return false;
+ if (fieldVals == null) {
+ if (other.fieldVals != null)
+ return false;
+ } else if (!fieldVals.equals(other.fieldVals))
+ return false;
+ if (ignoreTF != other.ignoreTF)
+ return false;
+ if (maxNumTerms != other.maxNumTerms)
+ return false;
+ return true;
+ }
+
+
+ /**
+ *
+ * @param maxNumTerms The total number of terms clauses that will appear once rewritten as a BooleanQuery
+ * @param analyzer
+ */
+ public FuzzyLikeThisQuery(int maxNumTerms, Analyzer analyzer)
+ {
+ q=new ScoreTermQueue(maxNumTerms);
+ this.analyzer=analyzer;
+ this.maxNumTerms = maxNumTerms;
+ }
+
+ class FieldVals
+ {
+ String queryString;
+ String fieldName;
+ float minSimilarity;
+ int prefixLength;
+ public FieldVals(String name, float similarity, int length, String queryString)
+ {
+ fieldName = name;
+ minSimilarity = similarity;
+ prefixLength = length;
+ this.queryString = queryString;
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result
+ + ((fieldName == null) ? 0 : fieldName.hashCode());
+ result = prime * result + Float.floatToIntBits(minSimilarity);
+ result = prime * result + prefixLength;
+ result = prime * result
+ + ((queryString == null) ? 0 : queryString.hashCode());
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (getClass() != obj.getClass())
+ return false;
+ FieldVals other = (FieldVals) obj;
+ if (fieldName == null) {
+ if (other.fieldName != null)
+ return false;
+ } else if (!fieldName.equals(other.fieldName))
+ return false;
+ if (Float.floatToIntBits(minSimilarity) != Float
+ .floatToIntBits(other.minSimilarity))
+ return false;
+ if (prefixLength != other.prefixLength)
+ return false;
+ if (queryString == null) {
+ if (other.queryString != null)
+ return false;
+ } else if (!queryString.equals(other.queryString))
+ return false;
+ return true;
+ }
+
+
+
+ }
+
+ /**
+ * Adds user input for "fuzzification"
+ * @param queryString The string which will be parsed by the analyzer and for which fuzzy variants will be parsed
+ * @param fieldName
+ * @param minSimilarity The minimum similarity of the term variants (see FuzzyTermEnum)
+ * @param prefixLength Length of required common prefix on variant terms (see FuzzyTermEnum)
+ */
+ public void addTerms(String queryString, String fieldName,float minSimilarity, int prefixLength)
+ {
+ fieldVals.add(new FieldVals(fieldName,minSimilarity,prefixLength,queryString));
+ }
+
+
+ private void addTerms(IndexReader reader,FieldVals f) throws IOException
+ {
+ if(f.queryString==null) return;
+ TokenStream ts=analyzer.reusableTokenStream(f.fieldName,new StringReader(f.queryString));
+ CharTermAttribute termAtt = ts.addAttribute(CharTermAttribute.class);
+
+ int corpusNumDocs=reader.numDocs();
+ Term internSavingTemplateTerm =new Term(f.fieldName); //optimization to avoid constructing new Term() objects
+ HashSet<String> processedTerms=new HashSet<String>();
+ ts.reset();
+ while (ts.incrementToken())
+ {
+ String term = termAtt.toString();
+ if(!processedTerms.contains(term))
+ {
+ processedTerms.add(term);
+ ScoreTermQueue variantsQ=new ScoreTermQueue(MAX_VARIANTS_PER_TERM); //maxNum variants considered for any one term
+ float minScore=0;
+ Term startTerm=internSavingTemplateTerm.createTerm(term);
+ FuzzyTermEnum fe=new FuzzyTermEnum(reader,startTerm,f.minSimilarity,f.prefixLength);
+ TermEnum origEnum = reader.terms(startTerm);
+ int df=0;
+ if(startTerm.equals(origEnum.term()))
+ {
+ df=origEnum.docFreq(); //store the df so all variants use same idf
+ }
+ int numVariants=0;
+ int totalVariantDocFreqs=0;
+ do
+ {
+ Term possibleMatch=fe.term();
+ if(possibleMatch!=null)
+ {
+ numVariants++;
+ totalVariantDocFreqs+=fe.docFreq();
+ float score=fe.difference();
+ if(variantsQ.size() < MAX_VARIANTS_PER_TERM || score > minScore){
+ ScoreTerm st=new ScoreTerm(possibleMatch,score,startTerm);
+ variantsQ.insertWithOverflow(st);
+ minScore = variantsQ.top().score; // maintain minScore
+ }
+ }
+ }
+ while(fe.next());
+ if(numVariants>0)
+ {
+ int avgDf=totalVariantDocFreqs/numVariants;
+ if(df==0)//no direct match we can use as df for all variants
+ {
+ df=avgDf; //use avg df of all variants
+ }
+
+ // take the top variants (scored by edit distance) and reset the score
+ // to include an IDF factor then add to the global queue for ranking
+ // overall top query terms
+ int size = variantsQ.size();
+ for(int i = 0; i < size; i++)
+ {
+ ScoreTerm st = variantsQ.pop();
+ st.score=(st.score*st.score)*sim.idf(df,corpusNumDocs);
+ q.insertWithOverflow(st);
+ }
+ }
+ }
+ }
+ ts.end();
+ ts.close();
+ }
+
+ @Override
+ public Query rewrite(IndexReader reader) throws IOException
+ {
+ if(rewrittenQuery!=null)
+ {
+ return rewrittenQuery;
+ }
+ //load up the list of possible terms
+ for (Iterator<FieldVals> iter = fieldVals.iterator(); iter.hasNext();)
+ {
+ FieldVals f = iter.next();
+ addTerms(reader,f);
+ }
+ //clear the list of fields
+ fieldVals.clear();
+
+ BooleanQuery bq=new BooleanQuery();
+
+
+ //create BooleanQueries to hold the variants for each token/field pair and ensure it
+ // has no coord factor
+ //Step 1: sort the termqueries by term/field
+ HashMap<Term,ArrayList<ScoreTerm>> variantQueries=new HashMap<Term,ArrayList<ScoreTerm>>();
+ int size = q.size();
+ for(int i = 0; i < size; i++)
+ {
+ ScoreTerm st = q.pop();
+ ArrayList<ScoreTerm> l= variantQueries.get(st.fuzziedSourceTerm);
+ if(l==null)
+ {
+ l=new ArrayList<ScoreTerm>();
+ variantQueries.put(st.fuzziedSourceTerm,l);
+ }
+ l.add(st);
+ }
+ //Step 2: Organize the sorted termqueries into zero-coord scoring boolean queries
+ for (Iterator<ArrayList<ScoreTerm>> iter = variantQueries.values().iterator(); iter.hasNext();)
+ {
+ ArrayList<ScoreTerm> variants = iter.next();
+ if(variants.size()==1)
+ {
+ //optimize where only one selected variant
+ ScoreTerm st= variants.get(0);
+ TermQuery tq = new FuzzyTermQuery(st.term,ignoreTF);
+ tq.setBoost(st.score); // set the boost to a mix of IDF and score
+ bq.add(tq, BooleanClause.Occur.SHOULD);
+ }
+ else
+ {
+ BooleanQuery termVariants=new BooleanQuery(true); //disable coord and IDF for these term variants
+ for (Iterator<ScoreTerm> iterator2 = variants.iterator(); iterator2
+ .hasNext();)
+ {
+ ScoreTerm st = iterator2.next();
+ TermQuery tq = new FuzzyTermQuery(st.term,ignoreTF); // found a match
+ tq.setBoost(st.score); // set the boost using the ScoreTerm's score
+ termVariants.add(tq, BooleanClause.Occur.SHOULD); // add to query
+ }
+ bq.add(termVariants, BooleanClause.Occur.SHOULD); // add to query
+ }
+ }
+ //TODO possible alternative step 3 - organize above booleans into a new layer of field-based
+ // booleans with a minimum-should-match of NumFields-1?
+ bq.setBoost(getBoost());
+ this.rewrittenQuery=bq;
+ return bq;
+ }
+
+ //Holds info for a fuzzy term variant - initially score is set to edit distance (for ranking best
+ // term variants) then is reset with IDF for use in ranking against all other
+ // terms/fields
+ private static class ScoreTerm{
+ public Term term;
+ public float score;
+ Term fuzziedSourceTerm;
+
+ public ScoreTerm(Term term, float score, Term fuzziedSourceTerm){
+ this.term = term;
+ this.score = score;
+ this.fuzziedSourceTerm=fuzziedSourceTerm;
+ }
+ }
+
+ private static class ScoreTermQueue extends PriorityQueue<ScoreTerm> {
+ public ScoreTermQueue(int size){
+ initialize(size);
+ }
+
+ /* (non-Javadoc)
+ * @see org.apache.lucene.util.PriorityQueue#lessThan(java.lang.Object, java.lang.Object)
+ */
+ @Override
+ protected boolean lessThan(ScoreTerm termA, ScoreTerm termB) {
+ if (termA.score== termB.score)
+ return termA.term.compareTo(termB.term) > 0;
+ else
+ return termA.score < termB.score;
+ }
+
+ }
+
+ //overrides basic TermQuery to negate effects of IDF (idf is factored into boost of containing BooleanQuery)
+ private static class FuzzyTermQuery extends TermQuery
+ {
+ boolean ignoreTF;
+ public FuzzyTermQuery(Term t, boolean ignoreTF)
+ {
+ super(t);
+ this.ignoreTF=ignoreTF;
+ }
+ @Override
+ public Similarity getSimilarity(Searcher searcher)
+ {
+ Similarity result = super.getSimilarity(searcher);
+ result = new SimilarityDelegator(result) {
+
+ @Override
+ public float tf(float freq)
+ {
+ if(ignoreTF)
+ {
+ return 1; //ignore tf
+ }
+ return super.tf(freq);
+ }
+ @Override
+ public float idf(int docFreq, int numDocs)
+ {
+ //IDF is already factored into individual term boosts
+ return 1;
+ }
+ };
+ return result;
+ }
+ }
+
+
+
+ /* (non-Javadoc)
+ * @see org.apache.lucene.search.Query#toString(java.lang.String)
+ */
+ @Override
+ public String toString(String field)
+ {
+ return null;
+ }
+
+
+ public boolean isIgnoreTF()
+ {
+ return ignoreTF;
+ }
+
+
+ public void setIgnoreTF(boolean ignoreTF)
+ {
+ this.ignoreTF = ignoreTF;
+ }
+
+}
fnp / pylucene.git / blobdiff