xapian-core/docs/spelling.rst

   1
   2 .. Copyright (C) 2007,2008,2009,2010,2011 Olly Betts
   3
   4 ==========================
   5 Xapian Spelling Correction
   6 ==========================
   7
   8 .. contents:: Table of contents
   9
  10 Introduction
  11 ============
  12
  13 Xapian provides functionality which can suggest corrections for misspelled
  14 words in queries, or in other situations where it might be useful.  The
  15 suggestions can be generated dynamically from the data that has been indexed,
  16 so the correction facility isn't tied to particular languages, and can suggest
  17 proper nouns or specialist technical terms.
  18
  19 Indexing
  20 ========
  21
  22 The spelling dictionary can be built with words from indexed text, or by adding
  23 words from a static word list, or a combination of the two.
  24
  25 Static spelling data
  26 --------------------
  27
  28 If ``db`` is a Xapian::WritableDatabase, you can add to the spelling dictionary
  29 using::
  30
  31     db.add_spelling(word, frequency_inc);
  32
  33 The ``frequency_inc`` parameter is optional, and defaults to 1.
  34
  35 And the corresponding way to remove from the spelling dictionary is::
  36
  37     db.remove_spelling(word, frequency_dec);
  38
  39 The ``frequency_dec`` parameter is optional and defaults to 1.  If you try to
  40 decrement the frequency of a word by more than its current value, it's just
  41 removed.
  42
  43 Dynamic spelling data
  44 ---------------------
  45
  46 ``Xapian::TermGenerator`` can be configured to automatically add words from
  47 indexed documents to the spelling dictionary::
  48
  49     Xapian::TermGenerator indexer;
  50     indexer.set_database(db);
  51     indexer.set_flags(indexer.FLAG_SPELLING);
  52
  53 Note that you must call the ``set_database()`` method as well as setting
  54 ``FLAG_SPELLING`` so that Xapian knows where to add the spelling dictionary
  55 entries.
  56
  57 If a document is removed or replaced, any spelling dictionary entries that
  58 were added when it was originally indexed won't be automatically removed.
  59 This might seem like a flaw, but in practice it rarely causes problems, and
  60 spellings in documents which were in the database, or in older versions of
  61 documents, are still interesting.  You can think of this as using the history
  62 of the document collection as a source of spelling data.
  63
  64 If you really want these entries removed, you can run through the termlist of
  65 each document you are about to remove or replace (if you indexed terms
  66 unstemmed) and call ``remove_spelling()`` for each word.
  67
  68 Searching
  69 =========
  70
  71 QueryParser Integration
  72 -----------------------
  73
  74 If FLAG_SPELLING_CORRECTION is passed to QueryParser::parse_query() and
  75 QueryParser::set_database() has been called, the QueryParser will look for
  76 corrections for words in the query.  In Xapian 1.2.2 and earlier, it only
  77 did this for terms which aren't found in the database.
  78
  79 If a correction is found, then a modified version of the query string will be
  80 generated which can be obtained by calling
  81 QueryParser::get_corrected_query_string().  However, the original query string
  82 will still be parsed, since you'll often want to ask the user "Did you mean:
  83 [...] ?" - if you want to automatically use the corrected form, just call
  84 QueryParser::parse_query() on it.
  85
  86 Omega
  87 =====
  88
  89 As of Omega 1.1.1, omindex and scriptindex support indexing spelling correction
  90 data and omega supports suggesting corrected spellings at search time.  See the
  91 `Omega documentation <https://xapian.org/docs/omega/>`_ for more details.
  92
  93 Algorithm
  94 =========
  95
  96 A list of candidate words is generated by matching trigrams (groups of 3
  97 adjacent characters) in the candidates against those in the misspelled
  98 word.  As well as groups of adjacent characters, "starts" and "ends"
  99 are generated with the first two and last two characters respectively
 100 (e.g. "FISH" generates: "<start>FI", "FIS", "ISH", and "SH<end>").
 101
 102 This technique alone would missing many single-edit errors in two and three
 103 character words, so we handle these specially as follows:
 104
 105 For a three character word (e.g. "ABC"), we generate trigrams for the two
 106 transposed forms too ("BAC" and "ACB"), in addition to "<start>AB", "ABC",
 107 and "BC<end>".
 108
 109 For a two character word (e.g. "AB"), we generate the special start and end
 110 trigrams for the reversed form (i.e. "BA"), so the trigrams are "<start>AB",
 111 "AB<end>", "<start>BA", and "BA<end>".
 112
 113 And for two, three, and four character words, we generate "bookend" bigrams
 114 consisting of the prefix 'B' followed by the first and last letters.  This
 115 allows us to handle transposition of the middle two characters of a four
 116 letter word, substitution or deletion of the middle character of a three
 117 letter word, or insertion in the middle of a two letter word.
 118
 119 Note that we don't attempt to suggest corrections for single character words
 120 at all, since the suggestions are unlikely to be of good quality (we'd always
 121 suggest the same correction for a given database, probably "a" for English).
 122 We also don't currently attempt to suggest substitution corrections for two
 123 character words, though this would perhaps be useful in some cases.
 124
 125 Those candidates with the better trigram matches are compared to the misspelled
 126 word by calculating the "edit distance" - that's the smallest number of
 127 operations required to turn one word into another.  The allowed operations
 128 are: insert a character; delete a character; change a character to another;
 129 transpose two adjacent characters.  The candidate with the smallest edit
 130 distance is found, and if more than one word has the smallest edit distance,
 131 that which occurs the most times is chosen.  If there's a tie of this too,
 132 it's essentially arbitrary which is chosen.
 133
 134 If the word passed in is in the spelling dictionary, then a candidate will
 135 still be returned if one is found with the same or greater frequency.
 136
 137 The maximum edit distance to consider can be specified as an optional parameter
 138 to Xapian::Database::get_spelling_suggestion().  If not specified, the default
 139 is 2, which generally does a good job.  3 is also a reasonable choice in many
 140 cases.  For most uses, 1 is probably too low, and 4 or more probably too high.
 141
 142 Unicode Support
 143 ---------------
 144
 145 Trigrams are generated at the byte level, but the edit distance calculation
 146 currently works with Unicode characters, so get_spelling_suggestion() should
 147 suggest suitable spelling corrections respecting the specified (or default)
 148 edit distance threshold.
 149
 150 Current Limitations
 151 ===================
 152
 153 Exactness
 154 ---------
 155
 156 Because Xapian only tests the edit distance for terms which match
 157 well (or at all!) on trigrams, it may not always suggest the same answer that
 158 would be found if all possible words were checked using the edit distance
 159 algorithm.  However, the best answer will usually be found, and an exhaustive
 160 search would be prohibitively expensive for many uses.
 161
 162 Backend Support
 163 ---------------
 164
 165 Currently spelling correction is supported by glass and chert
 166 databases.  It works with a single database or multiple databases (use
 167 Database::add_database() as usual).  We've no plans to support it for the
 168 InMemory backend, but we do intend to support it for
 169 the remote backend in the future.
 170
 171 Prefixed Terms
 172 --------------
 173
 174 Currently spelling correction ignores prefixed terms.
 175
 176 QueryParser changed word locations
 177 ----------------------------------
 178
 179 The QueryParser doesn't currently report the locations of changed words in
 180 the query string, so it's a bit fiddly to mark up the altered words specially
 181 in HTML output, for example.
 182
 183 References
 184 ==========
 185
 186 The algorithm used to calculate the edit distance is based on that described in
 187 the paper "An extension of Ukkonen's enhanced dynamic programming ASM
 188 algorithm" by Hal Berghel, University of Arkansas, and David Roach, Acxiom
 189 Corporation.  It's available online at:
 190 http://berghel.net/publications/asm/asm.php