"Fossies" - the Fresh Open Source Software Archive

Member "xapian-core-1.4.14/docs/spelling.html" (23 Nov 2019, 19019 Bytes) of package /linux/www/xapian-core-1.4.14.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) HTML source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 <?xml version="1.0" encoding="utf-8" ?>
    2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
    3 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    4 <head>
    5 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    6 <meta name="generator" content="Docutils 0.15.2: http://docutils.sourceforge.net/" />
    7 <title>Xapian Spelling Correction</title>
    8 <style type="text/css">
    9 
   10 /*
   11 :Author: David Goodger (goodger@python.org)
   12 :Id: $Id: html4css1.css 7952 2016-07-26 18:15:59Z milde $
   13 :Copyright: This stylesheet has been placed in the public domain.
   14 
   15 Default cascading style sheet for the HTML output of Docutils.
   16 
   17 See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
   18 customize this style sheet.
   19 */
   20 
   21 /* used to remove borders from tables and images */
   22 .borderless, table.borderless td, table.borderless th {
   23   border: 0 }
   24 
   25 table.borderless td, table.borderless th {
   26   /* Override padding for "table.docutils td" with "! important".
   27      The right padding separates the table cells. */
   28   padding: 0 0.5em 0 0 ! important }
   29 
   30 .first {
   31   /* Override more specific margin styles with "! important". */
   32   margin-top: 0 ! important }
   33 
   34 .last, .with-subtitle {
   35   margin-bottom: 0 ! important }
   36 
   37 .hidden {
   38   display: none }
   39 
   40 .subscript {
   41   vertical-align: sub;
   42   font-size: smaller }
   43 
   44 .superscript {
   45   vertical-align: super;
   46   font-size: smaller }
   47 
   48 a.toc-backref {
   49   text-decoration: none ;
   50   color: black }
   51 
   52 blockquote.epigraph {
   53   margin: 2em 5em ; }
   54 
   55 dl.docutils dd {
   56   margin-bottom: 0.5em }
   57 
   58 object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
   59   overflow: hidden;
   60 }
   61 
   62 /* Uncomment (and remove this text!) to get bold-faced definition list terms
   63 dl.docutils dt {
   64   font-weight: bold }
   65 */
   66 
   67 div.abstract {
   68   margin: 2em 5em }
   69 
   70 div.abstract p.topic-title {
   71   font-weight: bold ;
   72   text-align: center }
   73 
   74 div.admonition, div.attention, div.caution, div.danger, div.error,
   75 div.hint, div.important, div.note, div.tip, div.warning {
   76   margin: 2em ;
   77   border: medium outset ;
   78   padding: 1em }
   79 
   80 div.admonition p.admonition-title, div.hint p.admonition-title,
   81 div.important p.admonition-title, div.note p.admonition-title,
   82 div.tip p.admonition-title {
   83   font-weight: bold ;
   84   font-family: sans-serif }
   85 
   86 div.attention p.admonition-title, div.caution p.admonition-title,
   87 div.danger p.admonition-title, div.error p.admonition-title,
   88 div.warning p.admonition-title, .code .error {
   89   color: red ;
   90   font-weight: bold ;
   91   font-family: sans-serif }
   92 
   93 /* Uncomment (and remove this text!) to get reduced vertical space in
   94    compound paragraphs.
   95 div.compound .compound-first, div.compound .compound-middle {
   96   margin-bottom: 0.5em }
   97 
   98 div.compound .compound-last, div.compound .compound-middle {
   99   margin-top: 0.5em }
  100 */
  101 
  102 div.dedication {
  103   margin: 2em 5em ;
  104   text-align: center ;
  105   font-style: italic }
  106 
  107 div.dedication p.topic-title {
  108   font-weight: bold ;
  109   font-style: normal }
  110 
  111 div.figure {
  112   margin-left: 2em ;
  113   margin-right: 2em }
  114 
  115 div.footer, div.header {
  116   clear: both;
  117   font-size: smaller }
  118 
  119 div.line-block {
  120   display: block ;
  121   margin-top: 1em ;
  122   margin-bottom: 1em }
  123 
  124 div.line-block div.line-block {
  125   margin-top: 0 ;
  126   margin-bottom: 0 ;
  127   margin-left: 1.5em }
  128 
  129 div.sidebar {
  130   margin: 0 0 0.5em 1em ;
  131   border: medium outset ;
  132   padding: 1em ;
  133   background-color: #ffffee ;
  134   width: 40% ;
  135   float: right ;
  136   clear: right }
  137 
  138 div.sidebar p.rubric {
  139   font-family: sans-serif ;
  140   font-size: medium }
  141 
  142 div.system-messages {
  143   margin: 5em }
  144 
  145 div.system-messages h1 {
  146   color: red }
  147 
  148 div.system-message {
  149   border: medium outset ;
  150   padding: 1em }
  151 
  152 div.system-message p.system-message-title {
  153   color: red ;
  154   font-weight: bold }
  155 
  156 div.topic {
  157   margin: 2em }
  158 
  159 h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
  160 h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
  161   margin-top: 0.4em }
  162 
  163 h1.title {
  164   text-align: center }
  165 
  166 h2.subtitle {
  167   text-align: center }
  168 
  169 hr.docutils {
  170   width: 75% }
  171 
  172 img.align-left, .figure.align-left, object.align-left, table.align-left {
  173   clear: left ;
  174   float: left ;
  175   margin-right: 1em }
  176 
  177 img.align-right, .figure.align-right, object.align-right, table.align-right {
  178   clear: right ;
  179   float: right ;
  180   margin-left: 1em }
  181 
  182 img.align-center, .figure.align-center, object.align-center {
  183   display: block;
  184   margin-left: auto;
  185   margin-right: auto;
  186 }
  187 
  188 table.align-center {
  189   margin-left: auto;
  190   margin-right: auto;
  191 }
  192 
  193 .align-left {
  194   text-align: left }
  195 
  196 .align-center {
  197   clear: both ;
  198   text-align: center }
  199 
  200 .align-right {
  201   text-align: right }
  202 
  203 /* reset inner alignment in figures */
  204 div.align-right {
  205   text-align: inherit }
  206 
  207 /* div.align-center * { */
  208 /*   text-align: left } */
  209 
  210 .align-top    {
  211   vertical-align: top }
  212 
  213 .align-middle {
  214   vertical-align: middle }
  215 
  216 .align-bottom {
  217   vertical-align: bottom }
  218 
  219 ol.simple, ul.simple {
  220   margin-bottom: 1em }
  221 
  222 ol.arabic {
  223   list-style: decimal }
  224 
  225 ol.loweralpha {
  226   list-style: lower-alpha }
  227 
  228 ol.upperalpha {
  229   list-style: upper-alpha }
  230 
  231 ol.lowerroman {
  232   list-style: lower-roman }
  233 
  234 ol.upperroman {
  235   list-style: upper-roman }
  236 
  237 p.attribution {
  238   text-align: right ;
  239   margin-left: 50% }
  240 
  241 p.caption {
  242   font-style: italic }
  243 
  244 p.credits {
  245   font-style: italic ;
  246   font-size: smaller }
  247 
  248 p.label {
  249   white-space: nowrap }
  250 
  251 p.rubric {
  252   font-weight: bold ;
  253   font-size: larger ;
  254   color: maroon ;
  255   text-align: center }
  256 
  257 p.sidebar-title {
  258   font-family: sans-serif ;
  259   font-weight: bold ;
  260   font-size: larger }
  261 
  262 p.sidebar-subtitle {
  263   font-family: sans-serif ;
  264   font-weight: bold }
  265 
  266 p.topic-title {
  267   font-weight: bold }
  268 
  269 pre.address {
  270   margin-bottom: 0 ;
  271   margin-top: 0 ;
  272   font: inherit }
  273 
  274 pre.literal-block, pre.doctest-block, pre.math, pre.code {
  275   margin-left: 2em ;
  276   margin-right: 2em }
  277 
  278 pre.code .ln { color: grey; } /* line numbers */
  279 pre.code, code { background-color: #eeeeee }
  280 pre.code .comment, code .comment { color: #5C6576 }
  281 pre.code .keyword, code .keyword { color: #3B0D06; font-weight: bold }
  282 pre.code .literal.string, code .literal.string { color: #0C5404 }
  283 pre.code .name.builtin, code .name.builtin { color: #352B84 }
  284 pre.code .deleted, code .deleted { background-color: #DEB0A1}
  285 pre.code .inserted, code .inserted { background-color: #A3D289}
  286 
  287 span.classifier {
  288   font-family: sans-serif ;
  289   font-style: oblique }
  290 
  291 span.classifier-delimiter {
  292   font-family: sans-serif ;
  293   font-weight: bold }
  294 
  295 span.interpreted {
  296   font-family: sans-serif }
  297 
  298 span.option {
  299   white-space: nowrap }
  300 
  301 span.pre {
  302   white-space: pre }
  303 
  304 span.problematic {
  305   color: red }
  306 
  307 span.section-subtitle {
  308   /* font-size relative to parent (h1..h6 element) */
  309   font-size: 80% }
  310 
  311 table.citation {
  312   border-left: solid 1px gray;
  313   margin-left: 1px }
  314 
  315 table.docinfo {
  316   margin: 2em 4em }
  317 
  318 table.docutils {
  319   margin-top: 0.5em ;
  320   margin-bottom: 0.5em }
  321 
  322 table.footnote {
  323   border-left: solid 1px black;
  324   margin-left: 1px }
  325 
  326 table.docutils td, table.docutils th,
  327 table.docinfo td, table.docinfo th {
  328   padding-left: 0.5em ;
  329   padding-right: 0.5em ;
  330   vertical-align: top }
  331 
  332 table.docutils th.field-name, table.docinfo th.docinfo-name {
  333   font-weight: bold ;
  334   text-align: left ;
  335   white-space: nowrap ;
  336   padding-left: 0 }
  337 
  338 /* "booktabs" style (no vertical lines) */
  339 table.docutils.booktabs {
  340   border: 0px;
  341   border-top: 2px solid;
  342   border-bottom: 2px solid;
  343   border-collapse: collapse;
  344 }
  345 table.docutils.booktabs * {
  346   border: 0px;
  347 }
  348 table.docutils.booktabs th {
  349   border-bottom: thin solid;
  350   text-align: left;
  351 }
  352 
  353 h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
  354 h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
  355   font-size: 100% }
  356 
  357 ul.auto-toc {
  358   list-style-type: none }
  359 
  360 </style>
  361 </head>
  362 <body>
  363 <div class="document" id="xapian-spelling-correction">
  364 <h1 class="title">Xapian Spelling Correction</h1>
  365 
  366 <!-- Copyright (C) 2007,2008,2009,2010,2011 Olly Betts -->
  367 <div class="contents topic" id="table-of-contents">
  368 <p class="topic-title first">Table of contents</p>
  369 <ul class="simple">
  370 <li><a class="reference internal" href="#introduction" id="id1">Introduction</a></li>
  371 <li><a class="reference internal" href="#indexing" id="id2">Indexing</a><ul>
  372 <li><a class="reference internal" href="#static-spelling-data" id="id3">Static spelling data</a></li>
  373 <li><a class="reference internal" href="#dynamic-spelling-data" id="id4">Dynamic spelling data</a></li>
  374 </ul>
  375 </li>
  376 <li><a class="reference internal" href="#searching" id="id5">Searching</a><ul>
  377 <li><a class="reference internal" href="#queryparser-integration" id="id6">QueryParser Integration</a></li>
  378 </ul>
  379 </li>
  380 <li><a class="reference internal" href="#omega" id="id7">Omega</a></li>
  381 <li><a class="reference internal" href="#algorithm" id="id8">Algorithm</a><ul>
  382 <li><a class="reference internal" href="#unicode-support" id="id9">Unicode Support</a></li>
  383 </ul>
  384 </li>
  385 <li><a class="reference internal" href="#current-limitations" id="id10">Current Limitations</a><ul>
  386 <li><a class="reference internal" href="#exactness" id="id11">Exactness</a></li>
  387 <li><a class="reference internal" href="#backend-support" id="id12">Backend Support</a></li>
  388 <li><a class="reference internal" href="#prefixed-terms" id="id13">Prefixed Terms</a></li>
  389 <li><a class="reference internal" href="#queryparser-changed-word-locations" id="id14">QueryParser changed word locations</a></li>
  390 </ul>
  391 </li>
  392 <li><a class="reference internal" href="#references" id="id15">References</a></li>
  393 </ul>
  394 </div>
  395 <div class="section" id="introduction">
  396 <h1><a class="toc-backref" href="#id1">Introduction</a></h1>
  397 <p>Xapian provides functionality which can suggest corrections for misspelled
  398 words in queries, or in other situations where it might be useful.  The
  399 suggestions can be generated dynamically from the data that has been indexed,
  400 so the correction facility isn't tied to particular languages, and can suggest
  401 proper nouns or specialist technical terms.</p>
  402 </div>
  403 <div class="section" id="indexing">
  404 <h1><a class="toc-backref" href="#id2">Indexing</a></h1>
  405 <p>The spelling dictionary can be built with words from indexed text, or by adding
  406 words from a static word list, or a combination of the two.</p>
  407 <div class="section" id="static-spelling-data">
  408 <h2><a class="toc-backref" href="#id3">Static spelling data</a></h2>
  409 <p>If <tt class="docutils literal">db</tt> is a Xapian::WritableDatabase, you can add to the spelling dictionary
  410 using:</p>
  411 <pre class="literal-block">
  412 db.add_spelling(word, frequency_inc);
  413 </pre>
  414 <p>The <tt class="docutils literal">frequency_inc</tt> parameter is optional, and defaults to 1.</p>
  415 <p>And the corresponding way to remove from the spelling dictionary is:</p>
  416 <pre class="literal-block">
  417 db.remove_spelling(word, frequency_dec);
  418 </pre>
  419 <p>The <tt class="docutils literal">frequency_dec</tt> parameter is optional and defaults to 1.  If you try to
  420 decrement the frequency of a word by more than its current value, it's just
  421 removed.</p>
  422 </div>
  423 <div class="section" id="dynamic-spelling-data">
  424 <h2><a class="toc-backref" href="#id4">Dynamic spelling data</a></h2>
  425 <p><tt class="docutils literal"><span class="pre">Xapian::TermGenerator</span></tt> can be configured to automatically add words from
  426 indexed documents to the spelling dictionary:</p>
  427 <pre class="literal-block">
  428 Xapian::TermGenerator indexer;
  429 indexer.set_database(db);
  430 indexer.set_flags(indexer.FLAG_SPELLING);
  431 </pre>
  432 <p>Note that you must call the <tt class="docutils literal">set_database()</tt> method as well as setting
  433 <tt class="docutils literal">FLAG_SPELLING</tt> so that Xapian knows where to add the spelling dictionary
  434 entries.</p>
  435 <p>If a document is removed or replaced, any spelling dictionary entries that
  436 were added when it was originally indexed won't be automatically removed.
  437 This might seem like a flaw, but in practice it rarely causes problems, and
  438 spellings in documents which were in the database, or in older versions of
  439 documents, are still interesting.  You can think of this as using the history
  440 of the document collection as a source of spelling data.</p>
  441 <p>If you really want these entries removed, you can run through the termlist of
  442 each document you are about to remove or replace (if you indexed terms
  443 unstemmed) and call <tt class="docutils literal">remove_spelling()</tt> for each word.</p>
  444 </div>
  445 </div>
  446 <div class="section" id="searching">
  447 <h1><a class="toc-backref" href="#id5">Searching</a></h1>
  448 <div class="section" id="queryparser-integration">
  449 <h2><a class="toc-backref" href="#id6">QueryParser Integration</a></h2>
  450 <p>If FLAG_SPELLING_CORRECTION is passed to QueryParser::parse_query() and
  451 QueryParser::set_database() has been called, the QueryParser will look for
  452 corrections for words in the query.  In Xapian 1.2.2 and earlier, it only
  453 did this for terms which aren't found in the database.</p>
  454 <p>If a correction is found, then a modified version of the query string will be
  455 generated which can be obtained by calling
  456 QueryParser::get_corrected_query_string().  However, the original query string
  457 will still be parsed, since you'll often want to ask the user &quot;Did you mean:
  458 [...] ?&quot; - if you want to automatically use the corrected form, just call
  459 QueryParser::parse_query() on it.</p>
  460 </div>
  461 </div>
  462 <div class="section" id="omega">
  463 <h1><a class="toc-backref" href="#id7">Omega</a></h1>
  464 <p>As of Omega 1.1.1, omindex and scriptindex support indexing spelling correction
  465 data and omega supports suggesting corrected spellings at search time.  See the
  466 <a class="reference external" href="https://xapian.org/docs/omega/">Omega documentation</a> for more details.</p>
  467 </div>
  468 <div class="section" id="algorithm">
  469 <h1><a class="toc-backref" href="#id8">Algorithm</a></h1>
  470 <p>A list of candidate words is generated by matching trigrams (groups of 3
  471 adjacent characters) in the candidates against those in the misspelled
  472 word.  As well as groups of adjacent characters, &quot;starts&quot; and &quot;ends&quot;
  473 are generated with the first two and last two characters respectively
  474 (e.g. &quot;FISH&quot; generates: &quot;&lt;start&gt;FI&quot;, &quot;FIS&quot;, &quot;ISH&quot;, and &quot;SH&lt;end&gt;&quot;).</p>
  475 <p>This technique alone would missing many single-edit errors in two and three
  476 character words, so we handle these specially as follows:</p>
  477 <p>For a three character word (e.g. &quot;ABC&quot;), we generate trigrams for the two
  478 transposed forms too (&quot;BAC&quot; and &quot;ACB&quot;), in addition to &quot;&lt;start&gt;AB&quot;, &quot;ABC&quot;,
  479 and &quot;BC&lt;end&gt;&quot;.</p>
  480 <p>For a two character word (e.g. &quot;AB&quot;), we generate the special start and end
  481 trigrams for the reversed form (i.e. &quot;BA&quot;), so the trigrams are &quot;&lt;start&gt;AB&quot;,
  482 &quot;AB&lt;end&gt;&quot;, &quot;&lt;start&gt;BA&quot;, and &quot;BA&lt;end&gt;&quot;.</p>
  483 <p>And for two, three, and four character words, we generate &quot;bookend&quot; bigrams
  484 consisting of the prefix 'B' followed by the first and last letters.  This
  485 allows us to handle transposition of the middle two characters of a four
  486 letter word, substitution or deletion of the middle character of a three
  487 letter word, or insertion in the middle of a two letter word.</p>
  488 <p>Note that we don't attempt to suggest corrections for single character words
  489 at all, since the suggestions are unlikely to be of good quality (we'd always
  490 suggest the same correction for a given database, probably &quot;a&quot; for English).
  491 We also don't currently attempt to suggest substitution corrections for two
  492 character words, though this would perhaps be useful in some cases.</p>
  493 <p>Those candidates with the better trigram matches are compared to the misspelled
  494 word by calculating the &quot;edit distance&quot; - that's the smallest number of
  495 operations required to turn one word into another.  The allowed operations
  496 are: insert a character; delete a character; change a character to another;
  497 transpose two adjacent characters.  The candidate with the smallest edit
  498 distance is found, and if more than one word has the smallest edit distance,
  499 that which occurs the most times is chosen.  If there's a tie of this too,
  500 it's essentially arbitrary which is chosen.</p>
  501 <p>If the word passed in is in the spelling dictionary, then a candidate will
  502 still be returned if one is found with the same or greater frequency.</p>
  503 <p>The maximum edit distance to consider can be specified as an optional parameter
  504 to Xapian::Database::get_spelling_suggestion().  If not specified, the default
  505 is 2, which generally does a good job.  3 is also a reasonable choice in many
  506 cases.  For most uses, 1 is probably too low, and 4 or more probably too high.</p>
  507 <div class="section" id="unicode-support">
  508 <h2><a class="toc-backref" href="#id9">Unicode Support</a></h2>
  509 <p>Trigrams are generated at the byte level, but the edit distance calculation
  510 currently works with Unicode characters, so get_spelling_suggestion() should
  511 suggest suitable spelling corrections respecting the specified (or default)
  512 edit distance threshold.</p>
  513 </div>
  514 </div>
  515 <div class="section" id="current-limitations">
  516 <h1><a class="toc-backref" href="#id10">Current Limitations</a></h1>
  517 <div class="section" id="exactness">
  518 <h2><a class="toc-backref" href="#id11">Exactness</a></h2>
  519 <p>Because Xapian only tests the edit distance for terms which match
  520 well (or at all!) on trigrams, it may not always suggest the same answer that
  521 would be found if all possible words were checked using the edit distance
  522 algorithm.  However, the best answer will usually be found, and an exhaustive
  523 search would be prohibitively expensive for many uses.</p>
  524 </div>
  525 <div class="section" id="backend-support">
  526 <h2><a class="toc-backref" href="#id12">Backend Support</a></h2>
  527 <p>Currently spelling correction is supported by glass and chert
  528 databases.  It works with a single database or multiple databases (use
  529 Database::add_database() as usual).  We've no plans to support it for the
  530 InMemory backend, but we do intend to support it for
  531 the remote backend in the future.</p>
  532 </div>
  533 <div class="section" id="prefixed-terms">
  534 <h2><a class="toc-backref" href="#id13">Prefixed Terms</a></h2>
  535 <p>Currently spelling correction ignores prefixed terms.</p>
  536 </div>
  537 <div class="section" id="queryparser-changed-word-locations">
  538 <h2><a class="toc-backref" href="#id14">QueryParser changed word locations</a></h2>
  539 <p>The QueryParser doesn't currently report the locations of changed words in
  540 the query string, so it's a bit fiddly to mark up the altered words specially
  541 in HTML output, for example.</p>
  542 </div>
  543 </div>
  544 <div class="section" id="references">
  545 <h1><a class="toc-backref" href="#id15">References</a></h1>
  546 <p>The algorithm used to calculate the edit distance is based on that described in
  547 the paper &quot;An extension of Ukkonen's enhanced dynamic programming ASM
  548 algorithm&quot; by Hal Berghel, University of Arkansas, and David Roach, Acxiom
  549 Corporation.  It's available online at:
  550 <a class="reference external" href="http://berghel.net/publications/asm/asm.php">http://berghel.net/publications/asm/asm.php</a></p>
  551 </div>
  552 </div>
  553 </body>
  554 </html>