Adding "Did You Mean" to the Simple Search

Next we'll extend the search to prompt with "did you mean" suggestions for misspelled search terms in the query. Let's go through this step by step in the following subsections.

Generating a Spell Index

The first step is to generate an index from the original index that includes the letter n-grams for each word in the original index. I shall refer to this index as the spell index. With the help of the Lucene Spell Checker, this is very easy:

package org.tiling.didyoumean;

import java.io.IOException;


import org.apache.lucene.index.IndexReader;
import org.apache.lucene.search.spell.Dictionary;
import org.apache.lucene.search.spell.LuceneDictionary;
import org.apache.lucene.search.spell.SpellChecker;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FSDirectory;

public class DidYouMeanIndexer {
    private static final String DEFAULT_FIELD = "contents";

    private static final String FIELD_OPTION = "f";
    private static final String ORIGINAL_INDEX_OPTION = "i";
    private static final String SPELL_INDEX_OPTION = "o";

    public void createSpellIndex(String field,
            Directory originalIndexDirectory,
            Directory spellIndexDirectory) throws IOException {

        IndexReader indexReader = null;
        try {
            indexReader = IndexReader.open(originalIndexDirectory);
            Dictionary dictionary = new LuceneDictionary(indexReader, field);
            SpellChecker spellChecker = new SpellChecker(spellIndexDirectory);
            spellChecker.indexDictionnary(dictionary);
        } finally {
            if (indexReader != null) {
                indexReader.close();
            }
        }
    }


}

  

The Dictionary interface specifies a single method:

public Iterator getWordsIterator();

that returns an iterator over the words in the dictionary. Here we use a LuceneDictionary object to read each word in the given field from the original index. We then create a SpellChecker, giving it a new index location to which to write the n-grams as it indexes the dictionary.

To create the spell index, you can instantiate a new DidYouMeanIndexer and invoke the createSpellIndex() method from your code. Alternatively, you can run DidYouMeanIndexer from the command line (the main() method is not shown in the above listing).

The "Did You Mean" Search Engine

Next, let's turn back to our SearchEngine interface and look at the implementation of DidYouMeanSearchEngine. This implementation looks for query suggestions when the search results have low relevance.

package org.tiling.didyoumean;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import org.apache.lucene.queryParser.ParseException;
import org.apache.lucene.search.Hits;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.store.Directory;

public class DidYouMeanSearchEngine implements SearchEngine {

    private String defaultField;
    private String nameField;
    private Directory originalIndexDirectory;
    private int maxHits;
    private int minimumHits;
    private float minimumScore;
    private DidYouMeanParser didYouMeanParser;

    public DidYouMeanSearchEngine(String defaultField, String nameField,
            Directory originalIndexDirectory,
            int maxHits, int minimumHits, float minimumScore,
            DidYouMeanParser didYouMeanParser) {

        this.defaultField = defaultField;
        this.nameField = nameField;
        this.originalIndexDirectory = originalIndexDirectory;
        this.maxHits = maxHits;
        this.minimumHits = minimumHits;
        this.minimumScore = minimumScore;
        this.didYouMeanParser = didYouMeanParser;
    }

    public SearchResult search(String queryString) throws IOException, ParseException {
        long startTime = System.currentTimeMillis();
        IndexSearcher is = null;
        try {
            is = new IndexSearcher(originalIndexDirectory);
            Query query = didYouMeanParser.parse(queryString);
            Hits hits = is.search(query);

            String suggestedQueryString = null;
            if (hits.length() < minimumHits || hits.score(0) < minimumScore) {
                Query didYouMean = didYouMeanParser.suggest(queryString);
                if (didYouMean != null) {
                    suggestedQueryString = didYouMean.toString(defaultField);
                }
            }

            long endTime = System.currentTimeMillis();
            return new SearchResult(extractHits(hits), hits.length(),
                    endTime - startTime, queryString, suggestedQueryString);
        } finally {
            if (is != null) {
                is.close();
            }
        }
    }

    private List extractHits(Hits hits) throws IOException {
        List hitList = new ArrayList();
        for (int i = 0, count = 0; i < hits.length() && count++ < maxHits; i++) {
            hitList.add(hits.doc(i).getField(nameField).stringValue());
        }
        return hitList;
    }

}

  

The "Did You Mean" Parser

The key difference between the DidYouMeanSearchEngine class and the SimpleSearchEngine class is the introduction of the DidYouMeanParser interface. The DidYouMeanParser interface encapsulates a strategy both for parsing query strings and for suggesting spelling corrections for query strings:

package org.tiling.didyoumean;

import org.apache.lucene.queryParser.ParseException;
import org.apache.lucene.search.Query;

public interface DidYouMeanParser {
    public Query parse(String queryString) throws ParseException;
    public Query suggest(String queryString) throws ParseException;
}

  

The DidYouMeanSearchEngine only asks the DidYouMeanParser for a suggested query if the number of hits returned falls below a minimum threshold (the minimumHits property), or if the relevance of the top hit falls below a minimum threshold (the minimumScore property). Of course, you may choose to implement your own criteria for when to make a "did you mean" suggestion, but this rule is simple and effective.

The first implementation of DidYouMeanParser is straightforward:

package org.tiling.didyoumean;

import java.io.IOException;

import org.apache.lucene.index.Term;
import org.apache.lucene.queryParser.ParseException;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.search.spell.SpellChecker;
import org.apache.lucene.store.Directory;

public class SimpleDidYouMeanParser implements DidYouMeanParser {

    private String defaultField;
    private Directory spellIndexDirectory;

    public SimpleDidYouMeanParser(String defaultField, Directory spellIndexDirectory) {
        this.defaultField = defaultField;
        this.spellIndexDirectory = spellIndexDirectory;
    }

    public Query parse(String queryString) {
        return new TermQuery(new Term(defaultField, queryString));
    }

    public Query suggest(String queryString) throws ParseException {
        try {
            SpellChecker spellChecker = new SpellChecker(spellIndexDirectory);
            if (spellChecker.exist(queryString)) {
                return null;
            }
            String[] similarWords = spellChecker.suggestSimilar(queryString, 1);
            if (similarWords.length == 0) {
                return null;
            }
            return new TermQuery(new Term(defaultField, similarWords[0]));
        } catch (IOException e) {
            throw new ParseException(e.getMessage());
        }
    }

}

  

The parse() method simply constructs a new TermQuery from the query. (This means that SimpleDidYouMeanParser only works with single-word queries, a deficiency we shall remedy later.) The suggest() implementation is more interesting. Just as when we created the spell index earlier, we construct a new SpellChecker with the index location for the spell index. This time, however, we just read from the index. First we check if the query word is in the index--if it is, we assume that it is correctly spelled, and make no suggestion by returning null. If instead the query word is not in the index, then we ask the spell checker for a single suggestion, by invoking the suggestSimilar() method. Of course, it may happen that no words are similar enough to the input, so we return null again. But if a suggestion is found, then it is returned as a new TermQuery.

Whew! Let's see it in action after everything has been wired up using Spring. Figure 2 is a screenshot for the misspelled query "lettice."

Figure 2. Suggesting a sensible alternative query

How It Works

There's a lot going on in the suggestSimilar() method of SpellChecker, so let's follow it through with an example. Take the correctly spelled word "lettuce," which appears in the Beatrix Potter texts I've used for this article. In the original index, where each Lucene document corresponds to a text, "lettuce" appears in two Lucene documents in the contents field. On the other hand, the spell index contains a whole Lucene document for every distinct word in the original index. Each document has a number of fields, as shown here with the values for the document representing the word "lettuce."

Notice how both trigrams and 4-grams are indexed. In fact, precisely which n-grams are indexed depends on the size of the word. For very short words, unigrams and bigrams are indexed, whereas for longer words, trigrams and 4-grams are indexed.

The suggestSimilar() method forms a Lucene query to search the spell index for candidate suggestions. For the misspelling "lettice" the query is as follows (split over two lines to make it easier to read):

start3:let^2.0 end3:ice gram3:let gram3:ett gram3:tti gram3:tic gram3:ice
start4:lett^2.0 end4:tice gram4:lett gram4:etti gram4:ttic gram4:tice
  

The start n-grams are given more weight than the other n-grams in the word; here, they are boosted by a factor of two, signified by the ^2.0 notation. Another reason to index the start and end n-grams separately is because they are positional, unlike the other n-grams. For example, the words "eat" and "ate" have the same set of unigrams and bigrams (gram1:e gram1:a gram1:t gram2:ea gram2:at), so they need the start and end fields to distinguish them (start1:e end1:t start2:ea end2:at for "eat," and start1:a end1:e start2:at end2:te for "ate").