manual/aspell.html/Aspell-Suggestion-Strategy.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
   2 <html>
   3 <!-- This is the user's manual for Aspell
   4
   5 GNU Aspell is a spell checker designed to eventually replace Ispell.
   6 It can either be used as a library or as an independent spell checker.
   7
   8 Copyright © 2000-2019 Kevin Atkinson.
   9
  10 Permission is granted to copy, distribute and/or modify this document
  11 under the terms of the GNU Free Documentation License, Version 1.1 or
  12 any later version published by the Free Software Foundation; with no
  13 Invariant Sections, no Front-Cover Texts and no Back-Cover Texts.  A
  14 copy of the license is included in the section entitled "GNU Free
  15 Documentation License". -->
  16 <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
  17 <head>
  18 <title>GNU Aspell 0.60.7: Aspell Suggestion Strategy</title>
  19
  20 <meta name="description" content="Aspell 0.60.7 spell checker user&rsquo;s manual.">
  21 <meta name="keywords" content="GNU Aspell 0.60.7: Aspell Suggestion Strategy">
  22 <meta name="resource-type" content="document">
  23 <meta name="distribution" content="global">
  24 <meta name="Generator" content="makeinfo">
  25 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  26 <link href="index.html#Top" rel="start" title="Top">
  27 <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
  28 <link href="Implementation-Notes.html#Implementation-Notes" rel="up" title="Implementation Notes">
  29 <link href="Notes-on-8_002dbit-Characters.html#Notes-on-8_002dbit-Characters" rel="next" title="Notes on 8-bit Characters">
  30 <link href="Implementation-Notes.html#Implementation-Notes" rel="prev" title="Implementation Notes">
  31 <style type="text/css">
  32 <!--
  33 a.summary-letter {text-decoration: none}
  34 blockquote.smallquotation {font-size: smaller}
  35 div.display {margin-left: 3.2em}
  36 div.example {margin-left: 3.2em}
  37 div.indentedblock {margin-left: 3.2em}
  38 div.lisp {margin-left: 3.2em}
  39 div.smalldisplay {margin-left: 3.2em}
  40 div.smallexample {margin-left: 3.2em}
  41 div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
  42 div.smalllisp {margin-left: 3.2em}
  43 kbd {font-style:oblique}
  44 pre.display {font-family: inherit}
  45 pre.format {font-family: inherit}
  46 pre.menu-comment {font-family: serif}
  47 pre.menu-preformatted {font-family: serif}
  48 pre.smalldisplay {font-family: inherit; font-size: smaller}
  49 pre.smallexample {font-size: smaller}
  50 pre.smallformat {font-family: inherit; font-size: smaller}
  51 pre.smalllisp {font-size: smaller}
  52 span.nocodebreak {white-space:nowrap}
  53 span.nolinebreak {white-space:nowrap}
  54 span.roman {font-family:serif; font-weight:normal}
  55 span.sansserif {font-family:sans-serif; font-weight:normal}
  56 ul.no-bullet {list-style: none}
  57 -->
  58 </style>
  59
  60
  61 </head>
  62
  63 <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
  64 <a name="Aspell-Suggestion-Strategy"></a>
  65 <div class="header">
  66 <p>
  67 Next: <a href="Notes-on-8_002dbit-Characters.html#Notes-on-8_002dbit-Characters" accesskey="n" rel="next">Notes on 8-bit Characters</a>, Up: <a href="Implementation-Notes.html#Implementation-Notes" accesskey="u" rel="up">Implementation Notes</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>]</p>
  68 </div>
  69 <hr>
  70 <a name="Aspell-Suggestion-Strategy-1"></a>
  71 <h3 class="appendixsec">A.1 Aspell Suggestion Strategy</h3>
  72
  73 <p>The magic behind my spell checker comes from merging Lawrence Philips
  74 excellent metaphone algorithm and Ispell&rsquo;s near miss strategy which is
  75 inserting a space or hyphen, interchanging two adjacent letters,
  76 changing one letter, deleting a letter, or adding a letter.
  77 </p>
  78 <p>The process goes something like this.
  79 </p>
  80 <ol>
  81 <li> Convert the misspelled word to its soundslike equivalent (its
  82 metaphone for English words).
  83
  84 </li><li> Find all words that have a soundslike within one or two edit distances
  85 from the original word&rsquo;s soundslike.  The edit distance is the total
  86 number of deletions, insertions, exchanges, or adjacent swaps needed
  87 to make one string equivalent to the other.  When set to only look for
  88 soundslikes within one edit distance it tries all possible soundslike
  89 combinations and checks if each one is in the dictionary.  When set to
  90 find all soundslike within two edit distances it scans through the
  91 entire dictionary and quickly scores each soundslike.  The scoring is
  92 quick because it will give up if the two soundslikes are more than two
  93 edit distances apart.
  94
  95 </li><li> Find misspelled words that have a correctly spelled replacement by the
  96 same criteria of step number 2 and 3.  That is the misspelled word in
  97 the word pair (such as &ldquo;teh -&gt; the&rdquo;) would appear in the suggestions
  98 list as if it was a correct spelling.
  99
 100 </li><li> Score the result list and return the words with the lowest score.  The
 101 score is roughly the weighed average of the weighed edit distance of
 102 the word to the misspelled word and the soundslike equivalent of the
 103 two words.  The weighted edit distance is like the edit distance
 104 except that the various edits have weights attached to them.
 105
 106 </li><li> Replace the misspelled words that have correctly spelled replacements
 107 with their replacements and remove any duplicates that might arise
 108 because of this.
 109 </li></ol>
 110
 111 <p>Please note that the soundslike equivalent is a rough approximation of
 112 how the words sounds.  It is not the phoneme of the word by any means.
 113 For more details about exactly how each step is performed please see
 114 the file <samp>suggest.cc</samp>.  For more information on the metaphone
 115 algorithm please see the data file <samp>english_phonet.dat</samp>.
 116 </p>
 117 <hr>
 118 <div class="header">
 119 <p>
 120 Next: <a href="Notes-on-8_002dbit-Characters.html#Notes-on-8_002dbit-Characters" accesskey="n" rel="next">Notes on 8-bit Characters</a>, Up: <a href="Implementation-Notes.html#Implementation-Notes" accesskey="u" rel="up">Implementation Notes</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>]</p>
 121 </div>
 122
 123
 124
 125 </body>
 126 </html>