<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" />
<title>Xapian Spelling Correction</title>
<style type="text/css">
/*
:Author: David Goodger (goodger@python.org)
:Id: $Id: html4css1.css 5196 2007-06-03 20:25:28Z wiemann $
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left {
clear: left }
img.align-right {
clear: right }
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font-family: serif ;
font-size: 100% }
pre.literal-block, pre.doctest-block {
margin-left: 2em ;
margin-right: 2em }
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
</head>
<body>
<div class="document" id="xapian-spelling-correction">
<h1 class="title">Xapian Spelling Correction</h1>
<!-- Copyright (C) 2007,2008,2009,2010 Olly Betts -->
<div class="contents topic" id="table-of-contents">
<p class="topic-title first">Table of contents</p>
<ul class="simple">
<li><a class="reference internal" href="#introduction" id="id1">Introduction</a></li>
<li><a class="reference internal" href="#indexing" id="id2">Indexing</a><ul>
<li><a class="reference internal" href="#static-spelling-data" id="id3">Static spelling data</a></li>
<li><a class="reference internal" href="#dynamic-spelling-data" id="id4">Dynamic spelling data</a></li>
</ul>
</li>
<li><a class="reference internal" href="#searching" id="id5">Searching</a><ul>
<li><a class="reference internal" href="#queryparser-integration" id="id6">QueryParser Integration</a></li>
</ul>
</li>
<li><a class="reference internal" href="#omega" id="id7">Omega</a></li>
<li><a class="reference internal" href="#algorithm" id="id8">Algorithm</a><ul>
<li><a class="reference internal" href="#unicode-support" id="id9">Unicode Support</a></li>
</ul>
</li>
<li><a class="reference internal" href="#current-limitations" id="id10">Current Limitations</a><ul>
<li><a class="reference internal" href="#exactness" id="id11">Exactness</a></li>
<li><a class="reference internal" href="#backend-support" id="id12">Backend Support</a></li>
<li><a class="reference internal" href="#prefixed-terms" id="id13">Prefixed Terms</a></li>
<li><a class="reference internal" href="#queryparser-changed-word-locations" id="id14">QueryParser changed word locations</a></li>
</ul>
</li>
<li><a class="reference internal" href="#references" id="id15">References</a></li>
</ul>
</div>
<div class="section" id="introduction">
<h1><a class="toc-backref" href="#id1">Introduction</a></h1>
<p>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.</p>
</div>
<div class="section" id="indexing">
<h1><a class="toc-backref" href="#id2">Indexing</a></h1>
<p>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.</p>
<div class="section" id="static-spelling-data">
<h2><a class="toc-backref" href="#id3">Static spelling data</a></h2>
<p>If <tt class="docutils literal"><span class="pre">db</span></tt> is a Xapian::WritableDatabase, you can add to the spelling dictionary
using:</p>
<pre class="literal-block">
db.add_spelling(word, frequency_inc);
</pre>
<p>The <tt class="docutils literal"><span class="pre">frequency_inc</span></tt> parameter is optional, and defaults to 1.</p>
<p>And the corresponding way to remove from the spelling dictionary is:</p>
<pre class="literal-block">
db.remove_spelling(word, frequency_dec);
</pre>
<p>The <tt class="docutils literal"><span class="pre">frequency_dec</span></tt> 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
removed.</p>
</div>
<div class="section" id="dynamic-spelling-data">
<h2><a class="toc-backref" href="#id4">Dynamic spelling data</a></h2>
<p><tt class="docutils literal"><span class="pre">Xapian::TermGenerator</span></tt> can be configured to automatically add words from
indexed documents to the spelling dictionary:</p>
<pre class="literal-block">
Xapian::TermGenerator indexer;
indexer.set_database(db);
indexer.set_flags(indexer.FLAG_SPELLING);
</pre>
<p>Note that you must call the <tt class="docutils literal"><span class="pre">set_database()</span></tt> method as well as setting
<tt class="docutils literal"><span class="pre">FLAG_SPELLING</span></tt> so that Xapian knows where to add the spelling dictionary
entries.</p>
<p>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.</p>
<p>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 <tt class="docutils literal"><span class="pre">remove_spelling()</span></tt> for each word.</p>
</div>
</div>
<div class="section" id="searching">
<h1><a class="toc-backref" href="#id5">Searching</a></h1>
<div class="section" id="queryparser-integration">
<h2><a class="toc-backref" href="#id6">QueryParser Integration</a></h2>
<p>If FLAG_SPELLING_CORRECTION is passed to QueryParser::parse_query() and
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.</p>
<p>If a correction is found, then a modified version of the query string will be
generated which can be obtained by calling
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
QueryParser::parse_query() on it.</p>
</div>
</div>
<div class="section" id="omega">
<h1><a class="toc-backref" href="#id7">Omega</a></h1>
<p>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
<a class="reference external" href="http://xapian.org/docs/omega/">Omega documentation</a> for more details.</p>
</div>
<div class="section" id="algorithm">
<h1><a class="toc-backref" href="#id8">Algorithm</a></h1>
<p>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>").</p>
<p>This technique alone would missing many single-edit errors in two and three
character words, so we handle these specially as follows:</p>
<p>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>".</p>
<p>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>".</p>
<p>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.</p>
<p>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.</p>
<p>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 of this too,
it's essentially arbitrary which is chosen.</p>
<p>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.</p>
<p>The maximum edit distance to consider can be specified as an optional parameter
to 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 high.</p>
<div class="section" id="unicode-support">
<h2><a class="toc-backref" href="#id9">Unicode Support</a></h2>
<p>Trigrams are generated at the byte level, but the edit distance calculation
currently works with Unicode characters, so get_spelling_suggestion() should
suggest suitable spelling corrections respecting the specified (or default)
edit distance threshold.</p>
</div>
</div>
<div class="section" id="current-limitations">
<h1><a class="toc-backref" href="#id10">Current Limitations</a></h1>
<div class="section" id="exactness">
<h2><a class="toc-backref" href="#id11">Exactness</a></h2>
<p>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.</p>
</div>
<div class="section" id="backend-support">
<h2><a class="toc-backref" href="#id12">Backend Support</a></h2>
<p>Currently spelling correction is supported for chert, flint, and brass
databases. It works with a single database or multiple databases (use
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.</p>
</div>
<div class="section" id="prefixed-terms">
<h2><a class="toc-backref" href="#id13">Prefixed Terms</a></h2>
<p>Currently spelling correction ignores prefixed terms.</p>
</div>
<div class="section" id="queryparser-changed-word-locations">
<h2><a class="toc-backref" href="#id14">QueryParser changed word locations</a></h2>
<p>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.</p>
</div>
</div>
<div class="section" id="references">
<h1><a class="toc-backref" href="#id15">References</a></h1>
<p>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. It's available online at:
<a class="reference external" href="http://berghel.net/publications/asm/asm.php">http://berghel.net/publications/asm/asm.php</a></p>
</div>
</div>
</body>
</html>
