Table of contents
- Spelling Correction
- Current Limitations
Xapian provides functionality which can suggest corrections for misspelled words in queries, or in other situations where it might be useful. The suggestions can be generated dynamically from the data that has been indexed, so the correction facility isn’t tied to particular languages, and can suggest proper nouns or specialist technical terms.
The spelling dictionary can be built with words from indexed text, or by adding words from a static word list, or a combination of the two.
db is a
xapian.WritableDatabase, you can add to the spelling
frequency_inc parameter is optional, and defaults to 1.
And the corresponding way to remove from the spelling dictionary is:
frequency_dec parameter is optional and defaults to 1. If you try to
decrement the frequency of a word by more than its current value, it’s just
xapian.TermGenerator can be configured to automatically add
words from indexed documents to the spelling dictionary:
Xapian::TermGenerator indexer; indexer.set_database(db); indexer.set_flags(indexer.FLAG_SPELLING);
Note that you must call the
method as well as setting
that Xapian knows where to add the spelling dictionary entries.
If a document is removed or replaced, any spelling dictionary entries that were added when it was originally indexed won’t be automatically removed. This might seem like a flaw, but in practice it rarely causes problems, and spellings in documents which were in the database, or in older versions of documents, are still interesting. You can think of this as using the history of the document collection as a source of spelling data.
If you really want these entries removed, you can run through the termlist of
each document you are about to remove or replace (if you indexed terms
unstemmed) and call
xapian.TermGenerator.remove_spelling() for each
If you aren’t using the
xapian.QueryParser, or for other reasons you
need direct access to spelling corrections, you can get a suggestion for a
single word using
will return the best matching word in the spelling dictionary.
There’s an optional second parameter which controls the maximum edit distance it will consider; see details of the algorithm for more information.
xapian.QueryParser.FLAG_SPELLING_CORRECTION is passed to
xapian.QueryParser.set_database() has been called, the QueryParser
will look for corrections for words in the query. In Xapian 1.2.2 and earlier,
it only did this for terms which aren’t found in the database.
If a correction is found, then a modified version of the query string will be
generated which can be obtained by calling
xapian.QueryParser.get_corrected_query_string(). However, the
original query string will still be parsed, since you’ll often want to ask the
user “Did you mean: […] ?” - if you want to automatically use the corrected
form, just call
xapian.QueryParser.parse_query() on it.
As of Omega 1.1.1, omindex and scriptindex support indexing spelling correction data and omega supports suggesting corrected spellings at search time. See the Omega documentation for more details.
A list of candidate words is generated by matching trigrams (groups of 3 adjacent characters) in the candidates against those in the misspelled word. As well as groups of adjacent characters, “starts” and “ends” are generated with the first two and last two characters respectively (e.g. “FISH” generates: “<start>FI”, “FIS”, “ISH”, and “SH<end>”).
This technique alone would missing many single-edit errors in two and three character words, so we handle these specially as follows:
For a three character word (e.g. “ABC”), we generate trigrams for the two transposed forms too (“BAC” and “ACB”), in addition to “<start>AB”, “ABC”, and “BC<end>”.
For a two character word (e.g. “AB”), we generate the special start and end trigrams for the reversed form (i.e. “BA”), so the trigrams are “<start>AB”, “AB<end>”, “<start>BA”, and “BA<end>”.
And for two, three, and four character words, we generate “bookend” bigrams consisting of the prefix ‘B’ followed by the first and last letters. This allows us to handle transposition of the middle two characters of a four letter word, substitution or deletion of the middle character of a three letter word, or insertion in the middle of a two letter word.
Note that we don’t attempt to suggest corrections for single character words at all, since the suggestions are unlikely to be of good quality (we’d always suggest the same correction for a given database, probably “a” for English). We also don’t currently attempt to suggest substitution corrections for two character words, though this would perhaps be useful in some cases.
Those candidates with the better trigram matches are compared to the misspelled word by calculating the “edit distance” - that’s the smallest number of operations required to turn one word into another. The allowed operations are: insert a character; delete a character; change a character to another; transpose two adjacent characters. The candidate with the smallest edit distance is found, and if more than one word has the smallest edit distance, that which occurs the most times is chosen. If there’s a tie on this too, it’s essentially arbitrary which is chosen.
If the word passed in is in the spelling dictionary, then a candidate will still be returned if one is found with the same or greater frequency.
The maximum edit distance to consider can be specified as an optional parameter
xapian.Database.get_spelling_suggestion(). If not specified, the
default is 2, which generally does a good job. 3 is also a reasonable choice in
many cases. For most uses, 1 is probably too low, and 4 or more probably too
Because Xapian only tests the edit distance for terms which match well (or at all!) on trigrams, it may not always suggest the same answer that would be found if all possible words were checked using the edit distance algorithm. However, the best answer will usually be found, and an exhaustive search would be prohibitively expensive for many uses.
Currently spelling correction is supported for chert and glass databases. It
works with a single database or multiple databases (use
xapian.Database.add_database() as usual). We’ve no plans to support
it for the InMemory backend, but we do intend to support it for the remote
backend in the future.
The QueryParser doesn’t currently report the locations of changed words in the query string, so it’s a bit fiddly to mark up the altered words specially in HTML output, for example.
Only a single possible correction can currently be returned. It would be nice to be able to get a ranked list.
If you’re adding spelling data using
spelling data from deleted (or updated) documents doesn’t automatically get
removed from the spelling dictionary when documents are deleted. This is
usually not a problem, can be if the topic area covered by a database moves
significantly with time.
The algorithm used to calculate the edit distance is based on that described in the paper “An extension of Ukkonen’s enhanced dynamic programming ASM algorithm” by Hal Berghel, University of Arkansas, and David Roach, Acxiom Corporation.