| 1 |
<!DOCTYPE html> |
| 2 |
<html><head> |
| 3 |
<meta name="viewport" content="width=device-width, initial-scale=1.0"> |
| 4 |
<meta http-equiv="content-type" content="text/html; charset=UTF-8"> |
| 5 |
<link href="sqlite.css" rel="stylesheet"> |
| 6 |
<title>The Spellfix1 Virtual Table</title> |
| 7 |
<!-- path= --> |
| 8 |
</head> |
| 9 |
<body> |
| 10 |
<div class=nosearch> |
| 11 |
<a href="index.html"> |
| 12 |
<img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0"> |
| 13 |
</a> |
| 14 |
<div><!-- IE hack to prevent disappearing logo --></div> |
| 15 |
<div class="tagline desktoponly"> |
| 16 |
Small. Fast. Reliable.<br>Choose any three. |
| 17 |
</div> |
| 18 |
<div class="menu mainmenu"> |
| 19 |
<ul> |
| 20 |
<li><a href="index.html">Home</a> |
| 21 |
<li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a> |
| 22 |
<li class='wideonly'><a href='about.html'>About</a> |
| 23 |
<li class='desktoponly'><a href="docs.html">Documentation</a> |
| 24 |
<li class='desktoponly'><a href="download.html">Download</a> |
| 25 |
<li class='wideonly'><a href='copyright.html'>License</a> |
| 26 |
<li class='desktoponly'><a href="support.html">Support</a> |
| 27 |
<li class='desktoponly'><a href="prosupport.html">Purchase</a> |
| 28 |
<li class='search' id='search_menubutton'> |
| 29 |
<a href="javascript:void(0)" onclick='toggle_search()'>Search</a> |
| 30 |
</ul> |
| 31 |
</div> |
| 32 |
<div class="menu submenu" id="submenu"> |
| 33 |
<ul> |
| 34 |
<li><a href='about.html'>About</a> |
| 35 |
<li><a href='docs.html'>Documentation</a> |
| 36 |
<li><a href='download.html'>Download</a> |
| 37 |
<li><a href='support.html'>Support</a> |
| 38 |
<li><a href='prosupport.html'>Purchase</a> |
| 39 |
</ul> |
| 40 |
</div> |
| 41 |
<div class="searchmenu" id="searchmenu"> |
| 42 |
<form method="GET" action="search"> |
| 43 |
<select name="s" id="searchtype"> |
| 44 |
<option value="d">Search Documentation</option> |
| 45 |
<option value="c">Search Changelog</option> |
| 46 |
</select> |
| 47 |
<input type="text" name="q" id="searchbox" value=""> |
| 48 |
<input type="submit" value="Go"> |
| 49 |
</form> |
| 50 |
</div> |
| 51 |
</div> |
| 52 |
<script> |
| 53 |
function toggle_div(nm) { |
| 54 |
var w = document.getElementById(nm); |
| 55 |
if( w.style.display=="block" ){ |
| 56 |
w.style.display = "none"; |
| 57 |
}else{ |
| 58 |
w.style.display = "block"; |
| 59 |
} |
| 60 |
} |
| 61 |
function toggle_search() { |
| 62 |
var w = document.getElementById("searchmenu"); |
| 63 |
if( w.style.display=="block" ){ |
| 64 |
w.style.display = "none"; |
| 65 |
} else { |
| 66 |
w.style.display = "block"; |
| 67 |
setTimeout(function(){ |
| 68 |
document.getElementById("searchbox").focus() |
| 69 |
}, 30); |
| 70 |
} |
| 71 |
} |
| 72 |
function div_off(nm){document.getElementById(nm).style.display="none";} |
| 73 |
window.onbeforeunload = function(e){div_off("submenu");} |
| 74 |
/* Disable the Search feature if we are not operating from CGI, since */ |
| 75 |
/* Search is accomplished using CGI and will not work without it. */ |
| 76 |
if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){ |
| 77 |
document.getElementById("search_menubutton").style.display = "none"; |
| 78 |
} |
| 79 |
/* Used by the Hide/Show button beside syntax diagrams, to toggle the */ |
| 80 |
function hideorshow(btn,obj){ |
| 81 |
var x = document.getElementById(obj); |
| 82 |
var b = document.getElementById(btn); |
| 83 |
if( x.style.display!='none' ){ |
| 84 |
x.style.display = 'none'; |
| 85 |
b.innerHTML='show'; |
| 86 |
}else{ |
| 87 |
x.style.display = ''; |
| 88 |
b.innerHTML='hide'; |
| 89 |
} |
| 90 |
return false; |
| 91 |
} |
| 92 |
var antiRobot = 0; |
| 93 |
function antiRobotGo(){ |
| 94 |
if( antiRobot!=3 ) return; |
| 95 |
antiRobot = 7; |
| 96 |
var j = document.getElementById("mtimelink"); |
| 97 |
if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href"); |
| 98 |
} |
| 99 |
function antiRobotDefense(){ |
| 100 |
document.body.onmousedown=function(){ |
| 101 |
antiRobot |= 2; |
| 102 |
antiRobotGo(); |
| 103 |
document.body.onmousedown=null; |
| 104 |
} |
| 105 |
document.body.onmousemove=function(){ |
| 106 |
antiRobot |= 2; |
| 107 |
antiRobotGo(); |
| 108 |
document.body.onmousemove=null; |
| 109 |
} |
| 110 |
setTimeout(function(){ |
| 111 |
antiRobot |= 1; |
| 112 |
antiRobotGo(); |
| 113 |
}, 100) |
| 114 |
antiRobotGo(); |
| 115 |
} |
| 116 |
antiRobotDefense(); |
| 117 |
</script> |
| 118 |
<div class=fancy> |
| 119 |
<div class=nosearch> |
| 120 |
<div class="fancy_title"> |
| 121 |
The Spellfix1 Virtual Table |
| 122 |
</div> |
| 123 |
<details class="fancy_toc"> |
| 124 |
<summary>Table Of Contents</summary> |
| 125 |
<div id="toc_sub"><div class="fancy-toc1"><a href="#overview">1. Overview</a></div> |
| 126 |
<div class="fancy-toc1"><a href="#search_refinements">2. Search Refinements</a></div> |
| 127 |
<div class="fancy-toc1"><a href="#virtual_table_details">3. Virtual Table Details</a></div> |
| 128 |
<div class="fancy-toc1"><a href="#algorithm">4. Algorithm</a></div> |
| 129 |
<div class="fancy-toc1"><a href="#configurable_edit_distance">5. Configurable Edit Distance</a></div> |
| 130 |
<div class="fancy-toc1"><a href="#dealing_with_unusual_and_difficult_spellings">6. Dealing With Unusual And Difficult Spellings</a></div> |
| 131 |
<div class="fancy-toc1"><a href="#auxiliary_functions">7. Auxiliary Functions</a></div> |
| 132 |
<div class="fancy-toc1"><a href="#the_editdist3_function">8. The editdist3 function</a></div> |
| 133 |
<div class="fancy-toc1"><a href="#the_editdist3_cost_table">9. The editdist3 COST table</a></div> |
| 134 |
<div class="fancy-toc1"><a href="#experimenting_with_the_editcost3_function">10. Experimenting with the editcost3() function</a></div> |
| 135 |
</div> |
| 136 |
</details> |
| 137 |
</div> |
| 138 |
|
| 139 |
|
| 140 |
|
| 141 |
|
| 142 |
<h1 id="overview"><span>1. </span>Overview</h1> |
| 143 |
|
| 144 |
<p>This spellfix1 <a href="vtab.html">virtual table</a> can be used to search |
| 145 |
a large vocabulary for close matches. For example, spellfix1 |
| 146 |
can be used to suggest corrections to misspelled words. Or, |
| 147 |
it could be used with <a href="fts3.html#fts4">FTS4</a> to do full-text search using potentially |
| 148 |
misspelled words. |
| 149 |
|
| 150 |
</p><p>The implementation for the spellfix1 virtual table is held in the |
| 151 |
SQLite source tree in the miscellaneous extensions folder and in |
| 152 |
particular in the file |
| 153 |
<a href="https://sqlite.org/src/finfo?name=ext/misc/spellfix.c">ext/misc/spellfix1.c</a>. |
| 154 |
The spellfix1 virtual table is not included in the SQLite <a href="amalgamation.html">amalgamation</a> |
| 155 |
and is not a part of any standard SQLite build. It is a <a href="loadext.html">loadable extension</a>. |
| 156 |
|
| 157 |
</p><p>Once the spellfix1 extension is loaded, an instance of the spellfix1 |
| 158 |
virtual table is created like this: |
| 159 |
|
| 160 |
</p><blockquote><pre> |
| 161 |
CREATE VIRTUAL TABLE demo USING spellfix1; |
| 162 |
</pre></blockquote> |
| 163 |
|
| 164 |
<p>The "spellfix1" term is the name of the spellfix module and must be |
| 165 |
entered as shown. The "demo" term is the |
| 166 |
name of the virtual table you will be creating and can be altered |
| 167 |
to suit the needs of your application. The virtual table is initially |
| 168 |
empty. In order for the virtual table to be useful, you will need to |
| 169 |
populate it with your vocabulary. Suppose you |
| 170 |
have a list of words in a table named "big_vocabulary". Then do this: |
| 171 |
|
| 172 |
</p><blockquote><pre> |
| 173 |
INSERT INTO demo(word) SELECT word FROM big_vocabulary; |
| 174 |
</pre></blockquote> |
| 175 |
|
| 176 |
<p>If you intend to use this virtual table in cooperation with an <a href="fts3.html#fts4">FTS4</a> |
| 177 |
table (for spelling correction of search terms) then you might extract |
| 178 |
the vocabulary using an <a href="fts3.html#fts4aux">fts4aux</a> table: |
| 179 |
|
| 180 |
</p><blockquote><pre> |
| 181 |
INSERT INTO demo(word) SELECT term FROM search_aux WHERE col='*'; |
| 182 |
</pre></blockquote> |
| 183 |
|
| 184 |
<p>You can also provide the virtual table with a "rank" for each word. |
| 185 |
The "rank" is an estimate of how common the word is. Larger numbers |
| 186 |
mean the word is more common. If you omit the rank when populating |
| 187 |
the table, then a rank of 1 is assumed. But if you have rank |
| 188 |
information, you can supply it and the virtual table will show a |
| 189 |
slight preference for selecting more commonly used terms. To |
| 190 |
populate the rank from an fts4aux table "search_aux" do something |
| 191 |
like this: |
| 192 |
|
| 193 |
</p><blockquote><pre> |
| 194 |
INSERT INTO demo(word,rank) |
| 195 |
SELECT term, documents FROM search_aux WHERE col='*'; |
| 196 |
</pre></blockquote> |
| 197 |
|
| 198 |
<p>To query the virtual table, include a MATCH operator in the WHERE |
| 199 |
clause. For example: |
| 200 |
|
| 201 |
</p><blockquote><pre> |
| 202 |
SELECT word FROM demo WHERE word MATCH 'kennasaw'; |
| 203 |
</pre></blockquote> |
| 204 |
|
| 205 |
<p>Using a dataset of American place names (derived from |
| 206 |
<a href="http://geonames.usgs.gov/domestic/download_data.htm">http://geonames.usgs.gov/domestic/download_data.htm</a>) the query above |
| 207 |
returns 20 results beginning with: |
| 208 |
|
| 209 |
</p><blockquote><pre> |
| 210 |
kennesaw |
| 211 |
kenosha |
| 212 |
kenesaw |
| 213 |
kenaga |
| 214 |
keanak |
| 215 |
</pre></blockquote> |
| 216 |
|
| 217 |
<p>If you append the character '*' to the end of the pattern, then |
| 218 |
a prefix search is performed. For example: |
| 219 |
|
| 220 |
</p><blockquote><pre> |
| 221 |
SELECT word FROM demo WHERE word MATCH 'kennes*'; |
| 222 |
</pre></blockquote> |
| 223 |
|
| 224 |
<p>Yields 20 results beginning with: |
| 225 |
|
| 226 |
</p><blockquote><pre> |
| 227 |
kennesaw |
| 228 |
kennestone |
| 229 |
kenneson |
| 230 |
kenneys |
| 231 |
keanes |
| 232 |
keenes |
| 233 |
</pre></blockquote> |
| 234 |
|
| 235 |
<h1 id="search_refinements"><span>2. </span>Search Refinements</h1> |
| 236 |
|
| 237 |
<p>By default, the spellfix1 table returns no more than 20 results. |
| 238 |
(It might return less than 20 if there were fewer good matches.) |
| 239 |
You can change the upper bound on the number of returned rows by |
| 240 |
adding a "top=N" term to the WHERE clause of your query, where N |
| 241 |
is the new maximum. For example, to see the 5 best matches: |
| 242 |
|
| 243 |
</p><blockquote><pre> |
| 244 |
SELECT word FROM demo WHERE word MATCH 'kennes*' AND top=5; |
| 245 |
</pre></blockquote> |
| 246 |
|
| 247 |
<p>Each entry in the spellfix1 virtual table is associated with |
| 248 |
a particular language, identified by the integer "langid" column. |
| 249 |
The default langid is 0 and if no other actions are taken, the |
| 250 |
entire vocabulary is a part of the 0 language. But if your application |
| 251 |
needs to operate in multiple languages, then you can specify different |
| 252 |
vocabulary items for each language by specifying the langid field |
| 253 |
when populating the table. For example: |
| 254 |
|
| 255 |
</p><blockquote><pre> |
| 256 |
INSERT INTO demo(word,langid) SELECT word, 0 FROM en_vocabulary; |
| 257 |
INSERT INTO demo(word,langid) SELECT word, 1 FROM de_vocabulary; |
| 258 |
INSERT INTO demo(word,langid) SELECT word, 2 FROM fr_vocabulary; |
| 259 |
INSERT INTO demo(word,langid) SELECT word, 3 FROM ru_vocabulary; |
| 260 |
INSERT INTO demo(word,langid) SELECT word, 4 FROM cn_vocabulary; |
| 261 |
</pre></blockquote> |
| 262 |
|
| 263 |
<p>After the virtual table has been populated with items from multiple |
| 264 |
languages, specify the language of interest using a "langid=N" term |
| 265 |
in the WHERE clause of the query: |
| 266 |
|
| 267 |
</p><blockquote><pre> |
| 268 |
SELECT word FROM demo WHERE word MATCH 'hildes*' AND langid=1; |
| 269 |
</pre></blockquote> |
| 270 |
|
| 271 |
<p>Note that if you do not include the "langid=N" term in the WHERE clause, |
| 272 |
the search will be against language 0 (English in the example above.) |
| 273 |
All spellfix1 searches are against a single language id. There is no |
| 274 |
way to search all languages at once. |
| 275 |
|
| 276 |
|
| 277 |
</p><h1 id="virtual_table_details"><span>3. </span>Virtual Table Details</h1> |
| 278 |
|
| 279 |
<p>Each row in the spellfix1 virtual table has a unique rowid |
| 280 |
with seven columns plus five extra hidden columns. |
| 281 |
The columns are as follows: |
| 282 |
|
| 283 |
</p><dl> |
| 284 |
<dt><p><b>rowid</b></p></dt><dd> |
| 285 |
A unique integer number associated with each |
| 286 |
vocabulary item in the table. This can be used |
| 287 |
as a foreign key on other tables in the database. |
| 288 |
|
| 289 |
</dd><dt><p><b>word</b></p></dt><dd> |
| 290 |
The text of the word that matches the pattern. |
| 291 |
Both word and pattern can contain unicode characters |
| 292 |
and can be mixed case. |
| 293 |
|
| 294 |
</dd><dt><p><b>rank</b></p></dt><dd> |
| 295 |
This is the rank of the word, as specified in the |
| 296 |
original INSERT statement. |
| 297 |
|
| 298 |
|
| 299 |
</dd><dt><p><b>distance</b></p></dt><dd> |
| 300 |
This is an edit distance or Levenshtein distance going |
| 301 |
from the pattern to the word. |
| 302 |
|
| 303 |
</dd><dt><p><b>langid</b></p></dt><dd> |
| 304 |
This is the language-id of the word. All queries are |
| 305 |
against a single language-id, which defaults to 0. |
| 306 |
For any given query this value is the same on all rows. |
| 307 |
|
| 308 |
</dd><dt><p><b>score</b></p></dt><dd> |
| 309 |
The score is a combination of rank and distance. The |
| 310 |
idea is that a lower score is better. The virtual table |
| 311 |
attempts to find words with the lowest score and |
| 312 |
by default (unless overridden by ORDER BY) returns |
| 313 |
results in order of increasing score. |
| 314 |
|
| 315 |
</dd><dt><p><b>matchlen</b></p></dt><dd> |
| 316 |
In a prefix search, the matchlen is the number of characters in |
| 317 |
the string that match against the prefix. For a non-prefix search, |
| 318 |
this is the same as length(word). |
| 319 |
|
| 320 |
</dd><dt><p><b>phonehash</b></p></dt><dd> |
| 321 |
This column shows the phonetic hash prefix that was used to restrict |
| 322 |
the search. For any given query, this column should be the same for |
| 323 |
every row. This information is available for diagnostic purposes and |
| 324 |
is not normally considered useful in real applications. |
| 325 |
|
| 326 |
</dd><dt><p><b>top</b></p></dt><dd> |
| 327 |
(HIDDEN) For any query, this value is the same on all |
| 328 |
rows. It is an integer which is the maximum number of |
| 329 |
rows that will be output. The actual number of rows |
| 330 |
output might be less than this number, but it will never |
| 331 |
be greater. The default value for top is 20, but that |
| 332 |
can be changed for each query by including a term of |
| 333 |
the form "top=N" in the WHERE clause of the query. |
| 334 |
|
| 335 |
</dd><dt><p><b>scope</b></p></dt><dd> |
| 336 |
(HIDDEN) For any query, this value is the same on all |
| 337 |
rows. The scope is a measure of how widely the virtual |
| 338 |
table looks for matching words. Smaller values of |
| 339 |
scope cause a broader search. The scope is normally |
| 340 |
chosen automatically and is capped at 4. Applications |
| 341 |
can change the scope by including a term of the form |
| 342 |
"scope=N" in the WHERE clause of the query. Increasing |
| 343 |
the scope will make the query run faster, but will reduce |
| 344 |
the possible corrections. |
| 345 |
|
| 346 |
</dd><dt><p><b>srchcnt</b></p></dt><dd> |
| 347 |
(HIDDEN) For any query, this value is the same on all |
| 348 |
rows. This value is an integer which is the number of |
| 349 |
words examined using the edit-distance algorithm to |
| 350 |
find the top matches that are ultimately displayed. This |
| 351 |
value is for diagnostic use only. |
| 352 |
|
| 353 |
</dd><dt><p><b>soundslike</b></p></dt><dd> |
| 354 |
(HIDDEN) When inserting vocabulary entries, this field |
| 355 |
can be set to a spelling that matches what the word |
| 356 |
sounds like. See the DEALING WITH UNUSUAL AND DIFFICULT |
| 357 |
SPELLINGS section below for details. |
| 358 |
|
| 359 |
</dd><dt><p><b>command</b></p></dt><dd> |
| 360 |
(HIDDEN) The value of the "command" column is always NULL. However, |
| 361 |
applications can insert special strings into the "command" column in order |
| 362 |
to provoke certain behaviors in the spellfix1 virtual table. |
| 363 |
For example, inserting the string 'reset' into the "command" column |
| 364 |
will cause the virtual table to reread its edit distance weights |
| 365 |
(if there are any). |
| 366 |
</dd></dl> |
| 367 |
|
| 368 |
<h1 id="algorithm"><span>4. </span>Algorithm</h1> |
| 369 |
|
| 370 |
<p>The spellfix1 virtual table creates a single |
| 371 |
shadow table named "%_vocab" (where the % is replaced by the name of |
| 372 |
the virtual table; Ex: "demo_vocab" for the "demo" virtual table). |
| 373 |
the shadow table contains the following columns: |
| 374 |
|
| 375 |
</p><dl> |
| 376 |
<dt><p><b>id</b></p></dt><dd> |
| 377 |
The unique id (INTEGER PRIMARY KEY) |
| 378 |
|
| 379 |
</dd><dt><p><b>rank</b></p></dt><dd> |
| 380 |
The rank of word. |
| 381 |
|
| 382 |
</dd><dt><p><b>langid</b></p></dt><dd> |
| 383 |
The language id for this entry. |
| 384 |
|
| 385 |
</dd><dt><p><b>word</b></p></dt><dd> |
| 386 |
The original UTF8 text of the vocabulary word |
| 387 |
|
| 388 |
</dd><dt><p><b>k1</b></p></dt><dd> |
| 389 |
The word transliterated into lower-case ASCII. |
| 390 |
There is a standard table of mappings from non-ASCII |
| 391 |
characters into ASCII. Examples: "æ" -> "ae", |
| 392 |
"þ" -> "th", "ß" -> "ss", "á" -> "a", ... The |
| 393 |
accessory function spellfix1_translit(X) will do |
| 394 |
the non-ASCII to ASCII mapping. The built-in lower(X) |
| 395 |
function will convert to lower-case. Thus: |
| 396 |
k1 = lower(spellfix1_translit(word)). |
| 397 |
|
| 398 |
If the word is already all lower-case ASCII, then the k1 column |
| 399 |
will contain a NULL. This reduces the storage requirements for |
| 400 |
the %_vocab table and helps spellfix to run a little faster. |
| 401 |
Therefore, it is advantageous to populate as much of the spellfix |
| 402 |
table as possible using lower-case ASCII vocabulary. |
| 403 |
|
| 404 |
</dd><dt><p><b>k2</b></p></dt><dd> |
| 405 |
This field holds a phonetic code derived from coalesce(k1,word). |
| 406 |
Letters that have similar sounds are mapped into the same symbol. |
| 407 |
For example, all vowels and vowel clusters become the |
| 408 |
single symbol "A". And the letters "p", "b", "f", and |
| 409 |
"v" all become "B". All nasal sounds are represented |
| 410 |
as "N". And so forth. The mapping is based on |
| 411 |
ideas found in Soundex, Metaphone, and other |
| 412 |
long-standing phonetic matching systems. This key can |
| 413 |
be generated by the function spellfix1_phonehash(X). |
| 414 |
Hence: k2 = spellfix1_phonehash(coalesce(k1,word)) |
| 415 |
</dd></dl> |
| 416 |
|
| 417 |
<p>There is also a function for computing the Wagner edit distance or the |
| 418 |
Levenshtein distance between a pattern and a word. This function |
| 419 |
is exposed as spellfix1_editdist(X,Y). The edit distance function |
| 420 |
returns the "cost" of converting X into Y. Some transformations |
| 421 |
cost more than others. Changing one vowel into a different vowel, |
| 422 |
for example is relatively cheap, as is doubling a constant, or |
| 423 |
omitting the second character of a double-constant. Other transformations |
| 424 |
are more expensive. The idea is that the edit distance function returns |
| 425 |
a low cost for words that are similar and a higher cost for words |
| 426 |
that are further apart. In this implementation, the maximum cost |
| 427 |
of any single-character edit (delete, insert, or substitute) is 100, |
| 428 |
with lower costs for some edits (such as transforming vowels). |
| 429 |
|
| 430 |
</p><p>The "score" for a comparison is the edit distance between the pattern |
| 431 |
and the word, adjusted down by the base-2 logarithm of the word rank. |
| 432 |
For example, a match with distance 100 but rank 1000 would have a |
| 433 |
score of 122 (= 100 - log2(1000) + 32) whereas a match with distance |
| 434 |
100 with a rank of 1 would have a score of 131 (100 - log2(1) + 32). |
| 435 |
(NB: The constant 32 is added to each score to keep it from going |
| 436 |
negative in case the edit distance is zero.) In this way, frequently |
| 437 |
used words get a slightly lower cost which tends to move them toward |
| 438 |
the top of the list of alternative spellings. |
| 439 |
|
| 440 |
</p><p>A straightforward implementation of a spelling corrector would be |
| 441 |
to compare the search term against every word in the vocabulary |
| 442 |
and select the 20 with the lowest scores. However, there will |
| 443 |
typically be hundreds of thousands or millions of words in the |
| 444 |
vocabulary, and so this approach is not fast enough. |
| 445 |
|
| 446 |
</p><p>Suppose the term that is being spell-corrected is X. To limit |
| 447 |
the search space, X is converted to a k2-like key using the |
| 448 |
equivalent of: |
| 449 |
|
| 450 |
</p><blockquote><pre> |
| 451 |
key = spellfix1_phonehash(lower(spellfix1_translit(X))) |
| 452 |
</pre></blockquote> |
| 453 |
|
| 454 |
<p>This key is then limited to "scope" characters. The default scope |
| 455 |
value is 4, but an alternative scope can be specified using the |
| 456 |
"scope=N" term in the WHERE clause. After the key has been truncated, |
| 457 |
the edit distance is run against every term in the vocabulary that |
| 458 |
has a k2 value that begins with the abbreviated key. |
| 459 |
|
| 460 |
</p><p>For example, suppose the input word is "Paskagula". The phonetic |
| 461 |
key is "BACACALA" which is then truncated to 4 characters "BACA". |
| 462 |
The edit distance is then run on the 4980 entries (out of |
| 463 |
272,597 entries total) of the vocabulary whose k2 values begin with |
| 464 |
BACA, yielding "Pascagoula" as the best match. |
| 465 |
|
| 466 |
</p><p>Only terms of the vocabulary with a matching langid are searched. |
| 467 |
Hence, the same table can contain entries from multiple languages |
| 468 |
and only the requested language will be used. The default langid |
| 469 |
is 0. |
| 470 |
|
| 471 |
<a name="configeditdist"></a> |
| 472 |
|
| 473 |
</p><h1 id="configurable_edit_distance"><span>5. </span>Configurable Edit Distance</h1> |
| 474 |
|
| 475 |
<p>The built-in Wagner edit-distance function with fixed weights can be |
| 476 |
replaced by the <a href="spellfix1.html#editdist3">editdist3()</a> edit-distance function |
| 477 |
with application-defined weights and support for unicode, by specifying |
| 478 |
the "edit_cost_table=<i>TABLENAME</i>" parameter to the spellfix1 module |
| 479 |
when the virtual table is created. |
| 480 |
For example: |
| 481 |
|
| 482 |
</p><blockquote><pre> |
| 483 |
CREATE VIRTUAL TABLE demo2 USING spellfix1(edit_cost_table=APPCOST); |
| 484 |
</pre></blockquote> |
| 485 |
|
| 486 |
<p>The <a href="spellfix1.html#editdist3">editdist3()</a> edit-distance function can also be selected or |
| 487 |
deselected at run-time by inserting an appropriate string into the |
| 488 |
"command" column of the virtual table:</p> |
| 489 |
|
| 490 |
<blockquote><pre> |
| 491 |
INSERT INTO demo2(command) VALUES('edit_cost_table=APPCOST'); |
| 492 |
</pre></blockquote> |
| 493 |
|
| 494 |
|
| 495 |
<p>In the examples above, the APPCOST table would be interrogated to find |
| 496 |
the edit distance coefficients. It is the presence of the "edit_cost_table=" |
| 497 |
parameter to the spellfix1 module name that causes editdist3() to be used |
| 498 |
in place of the built-in edit distance function. If APPCOST is an empty |
| 499 |
string, then the built-in Wagner edit-distance function is used. |
| 500 |
|
| 501 |
</p><p>The edit distance coefficients are normally read from the APPCOST table |
| 502 |
once and thereafter stored in memory. Hence, run-time changes to the |
| 503 |
APPCOST table will not normally affect the edit distance results. |
| 504 |
However, inserting the special string 'reset' into the "command" column of the |
| 505 |
virtual table causes the edit distance coefficients to reread the |
| 506 |
APPCOST table. Hence, applications should run a SQL statement similar |
| 507 |
to the following when changes to the APPCOST table occur: |
| 508 |
|
| 509 |
</p><blockquote> |
| 510 |
INSERT INTO demo2(command) VALUES("reset"); |
| 511 |
</blockquote> |
| 512 |
|
| 513 |
<h1 id="dealing_with_unusual_and_difficult_spellings"><span>6. </span>Dealing With Unusual And Difficult Spellings</h1> |
| 514 |
|
| 515 |
<p>The algorithm above works quite well for most cases, but there are |
| 516 |
exceptions. These exceptions can be dealt with by making additional |
| 517 |
entries in the virtual table using the "soundslike" column. |
| 518 |
|
| 519 |
</p><p>For example, many words of Greek origin begin with letters "ps" where |
| 520 |
the "p" is silent. Ex: psalm, pseudonym, psoriasis, psyche. In |
| 521 |
another example, many Scottish surnames can be spelled with an |
| 522 |
initial "Mac" or "Mc". Thus, "MacKay" and "McKay" are both pronounced |
| 523 |
the same. |
| 524 |
|
| 525 |
</p><p>Accommodation can be made for words that are not spelled as they |
| 526 |
sound by making additional entries into the virtual table for the |
| 527 |
same word, but adding an alternative spelling in the "soundslike" |
| 528 |
column. For example, the canonical entry for "psalm" would be this: |
| 529 |
|
| 530 |
</p><blockquote><pre> |
| 531 |
INSERT INTO demo(word) VALUES('psalm'); |
| 532 |
</pre></blockquote> |
| 533 |
|
| 534 |
<p>To enhance the ability to correct the spelling of "salm" into |
| 535 |
"psalm", make an addition entry like this: |
| 536 |
|
| 537 |
</p><blockquote><pre> |
| 538 |
INSERT INTO demo(word,soundslike) VALUES('psalm','salm'); |
| 539 |
</pre></blockquote> |
| 540 |
|
| 541 |
<p>It is ok to make multiple entries for the same word as long as |
| 542 |
each entry has a different soundslike value. Note that if no |
| 543 |
soundslike value is specified, the soundslike defaults to the word |
| 544 |
itself. |
| 545 |
|
| 546 |
</p><p>Listed below are some cases where it might make sense to add additional |
| 547 |
soundslike entries. The specific entries will depend on the application |
| 548 |
and the target language. |
| 549 |
|
| 550 |
</p><ul> |
| 551 |
<li>Silent "p" in words beginning with "ps": psalm, psyche |
| 552 |
</li><li>Silent "p" in words beginning with "pn": pneumonia, pneumatic |
| 553 |
</li><li>Silent "p" in words beginning with "pt": pterodactyl, ptolemaic |
| 554 |
</li><li>Silent "d" in words beginning with "dj": djinn, Djikarta |
| 555 |
</li><li>Silent "k" in words beginning with "kn": knight, Knuthson |
| 556 |
</li><li>Silent "g" in words beginning with "gn": gnarly, gnome, gnat |
| 557 |
</li><li>"Mac" versus "Mc" beginning Scottish surnames |
| 558 |
</li><li>"Tch" sounds in Slavic words: Tchaikovsky vs. Chaykovsky |
| 559 |
</li><li>The letter "j" pronounced like "h" in Spanish: LaJolla |
| 560 |
</li><li>Words beginning with "wr" versus "r": write vs. rite |
| 561 |
</li><li>Miscellaneous problem words such as "debt", "tsetse", |
| 562 |
"Nguyen", "Van Nuyes". |
| 563 |
</li></ul> |
| 564 |
|
| 565 |
<h1 id="auxiliary_functions"><span>7. </span>Auxiliary Functions</h1> |
| 566 |
|
| 567 |
<p>The source code module that implements the spellfix1 virtual table also |
| 568 |
implements several SQL functions that might be useful to applications |
| 569 |
that employ spellfix1 or for testing or diagnostic work while developing |
| 570 |
applications that use spellfix1. The following auxiliary functions are |
| 571 |
available: |
| 572 |
|
| 573 |
</p><dl> |
| 574 |
<dt><p><b>editdist3(P,W)<br>editdist3(P,W,L)<br>editdist3(T)</b></p></dt><dd> |
| 575 |
These routines provide direct access to the version of the Wagner |
| 576 |
edit-distance function that allows for application-defined weights |
| 577 |
on edit operations. The first two forms of this function compare |
| 578 |
pattern P against word W and return the edit distance. In the first |
| 579 |
function, the langid is assumed to be 0 and in the second, the |
| 580 |
langid is given by the L parameter. The third form of this function |
| 581 |
reloads edit distance coefficients from the table named by T. |
| 582 |
|
| 583 |
</dd><dt><p><b>spellfix1_editdist(P,W)</b></p></dt><dd> |
| 584 |
This routine provides access to the built-in Wagner edit-distance |
| 585 |
function that uses default, fixed costs. The value returned is |
| 586 |
the edit distance needed to transform W into P. |
| 587 |
|
| 588 |
</dd><dt><p><b>spellfix1_phonehash(X)</b></p></dt><dd> |
| 589 |
This routine constructs a phonetic hash of the pure ascii input word X |
| 590 |
and returns that hash. This routine is used internally by spellfix1 in |
| 591 |
order to transform the K1 column of the shadow table into the K2 |
| 592 |
column. |
| 593 |
|
| 594 |
</dd><dt><p><b>spellfix1_scriptcode(X)</b></p></dt><dd> |
| 595 |
Given an input string X, this routine attempts to determine the dominant |
| 596 |
script of that input and returns the ISO-15924 numeric code for that |
| 597 |
script. The current implementation understands the following scripts: |
| 598 |
<ul> |
| 599 |
<li> 215 - Latin |
| 600 |
</li><li> 220 - Cyrillic |
| 601 |
</li><li> 200 - Greek |
| 602 |
</li></ul> |
| 603 |
Additional language codes might be added in future releases. |
| 604 |
|
| 605 |
</dd><dt><p><b>spellfix1_translit(X)</b></p></dt><dd> |
| 606 |
This routine transliterates unicode text into pure ascii, returning |
| 607 |
the pure ascii representation of the input text X. This is the function |
| 608 |
that is used internally to transform vocabulary words into the K1 |
| 609 |
column of the shadow table. |
| 610 |
|
| 611 |
</dd></dl> |
| 612 |
|
| 613 |
<a name="editdist3"></a> |
| 614 |
|
| 615 |
<h1 id="the_editdist3_function"><span>8. </span>The editdist3 function</h1> |
| 616 |
|
| 617 |
<p>The editdist3 algorithm is a function that computes the minimum edit |
| 618 |
distance (a.k.a. the Levenshtein distance) between two input strings. |
| 619 |
The editdist3 algorithm is a configurable alternative to the default |
| 620 |
edit distance function of spellfix1. |
| 621 |
Features of editdist3 include: |
| 622 |
|
| 623 |
</p><ul> |
| 624 |
<li><p>It works with unicode (UTF8) text. |
| 625 |
|
| 626 |
</p></li><li><p>A table of insertion, deletion, and substitution costs can be |
| 627 |
provided by the application. |
| 628 |
|
| 629 |
</p></li><li><p>Multi-character insertions, deletions, and substitutions can be |
| 630 |
enumerated in the cost table. |
| 631 |
</p></li></ul> |
| 632 |
|
| 633 |
<h1 id="the_editdist3_cost_table"><span>9. </span>The editdist3 COST table</h1> |
| 634 |
|
| 635 |
<p>To program the costs of editdist3, create a table such as the following: |
| 636 |
|
| 637 |
</p><blockquote><pre> |
| 638 |
CREATE TABLE editcost( |
| 639 |
iLang INT, -- The language ID |
| 640 |
cFrom TEXT, -- Convert text from this |
| 641 |
cTo TEXT, -- Convert text into this |
| 642 |
iCost INT -- The cost of doing the conversion |
| 643 |
); |
| 644 |
</pre></blockquote> |
| 645 |
|
| 646 |
<p>The cost table can be named anything you want - it does not have to be |
| 647 |
called "editcost". And the table can contain additional columns. |
| 648 |
The only requirement is that the |
| 649 |
table must contain the four columns shown above, with exactly the names shown. |
| 650 |
|
| 651 |
</p><p>The iLang column is a non-negative integer that identifies a set of costs |
| 652 |
appropriate for a particular language. The editdist3 function will only use |
| 653 |
a single iLang value for any given edit-distance computation. The default |
| 654 |
value is 0. It is recommended that applications that only need to use a |
| 655 |
single language always use iLang==0 for all entries. |
| 656 |
|
| 657 |
</p><p>The iCost column is the numeric cost of transforming cFrom into cTo. This |
| 658 |
value should be a non-negative integer, and should probably be less than 100. |
| 659 |
The default single-character insertion and deletion costs are 100 and the |
| 660 |
default single-character to single-character substitution cost is 150. A |
| 661 |
cost of 10000 or more is considered "infinite" and causes the rule to be |
| 662 |
ignored. |
| 663 |
|
| 664 |
</p><p>The cFrom and cTo columns show edit transformation strings. Either or both |
| 665 |
columns may contain more than one character. Or either column (but not both) |
| 666 |
may hold an empty string. When cFrom is empty, that is the cost of inserting |
| 667 |
cTo. When cTo is empty, that is the cost of deleting cFrom. |
| 668 |
|
| 669 |
</p><p>In the spellfix1 algorithm, cFrom is the text as the user entered it and |
| 670 |
cTo is the correctly spelled text as it exists in the database. The goal |
| 671 |
of the editdist3 algorithm is to determine how close the user-entered text is |
| 672 |
to the dictionary text. |
| 673 |
|
| 674 |
</p><p>There are three special-case entries in the cost table: |
| 675 |
|
| 676 |
</p><table border="1" align="center"> |
| 677 |
<tr><th>cFrom</th><th>cTo</th><th>Meaning</th></tr> |
| 678 |
<tr><td>''</td><td>'?'</td><td>The default insertion cost</td></tr> |
| 679 |
<tr><td>'?'</td><td>''</td><td>The default deletion cost</td></tr> |
| 680 |
<tr><td>'?'</td><td>'?'</td><td>The default substitution cost</td></tr> |
| 681 |
</table> |
| 682 |
|
| 683 |
<p>If any of the special-case entries shown above are omitted, then the |
| 684 |
value of 100 is used for insertion and deletion and 150 is used for |
| 685 |
substitution. To disable the default insertion, deletion, and/or substitution |
| 686 |
set their respective cost to 10000 or more. |
| 687 |
|
| 688 |
</p><p>Other entries in the cost table show specific transforms for particular |
| 689 |
characters. |
| 690 |
The cost of specific transforms should be less than the default costs, or else |
| 691 |
the default costs will take precedence and the specific transforms will never |
| 692 |
be used. |
| 693 |
|
| 694 |
</p><p>Some example, cost table entries: |
| 695 |
|
| 696 |
</p><blockquote><pre> |
| 697 |
INSERT INTO editcost(iLang, cFrom, cTo, iCost) |
| 698 |
VALUES(0, 'a', 'ä', 5); |
| 699 |
</pre></blockquote> |
| 700 |
|
| 701 |
<p>The rule above says that the letter "a" in user input can be matched against |
| 702 |
the letter "ä" in the dictionary with a penalty of 5. |
| 703 |
|
| 704 |
</p><blockquote><pre> |
| 705 |
INSERT INTO editcost(iLang, cFrom, cTo, iCost) |
| 706 |
VALUES(0, 'ss', 'ß', 8); |
| 707 |
</pre></blockquote> |
| 708 |
|
| 709 |
<p>The number of characters in cFrom and cTo do not need to be the same. The |
| 710 |
rule above says that "ss" on user input will match "ß" with a penalty of 8. |
| 711 |
|
| 712 |
</p><h1 id="experimenting_with_the_editcost3_function"><span>10. </span>Experimenting with the editcost3() function</h1> |
| 713 |
|
| 714 |
<p>The spellfix1 virtual table |
| 715 |
uses editdist3 if the "edit_cost_table=TABLE" option |
| 716 |
is specified as an argument when the spellfix1 virtual table is created. |
| 717 |
But editdist3 can also be tested directly using the built-in "editdist3()" |
| 718 |
SQL function. The editdist3() SQL function has 3 forms: |
| 719 |
|
| 720 |
</p><ol> |
| 721 |
<li> editdist3('TABLENAME'); |
| 722 |
</li><li> editdist3('string1', 'string2'); |
| 723 |
</li><li> editdist3('string1', 'string2', langid); |
| 724 |
</li></ol> |
| 725 |
|
| 726 |
<p>The first form loads the edit distance coefficients from a table called |
| 727 |
'TABLENAME'. Any prior coefficients are discarded. So when experimenting |
| 728 |
with weights and the weight table changes, simply rerun the single-argument |
| 729 |
form of editdist3() to reload revised coefficients. Note that the |
| 730 |
edit distance |
| 731 |
weights used by the editdist3() SQL function are independent from the |
| 732 |
weights used by the spellfix1 virtual table. |
| 733 |
|
| 734 |
</p><p>The second and third forms return the computed edit distance between strings |
| 735 |
'string1' and "string2'. In the second form, a language id of 0 is used. |
| 736 |
The language id is specified in the third form. |
| 737 |
</p><p align="center"><small><i>This page was last updated on 2025-07-12 15:11:36Z </small></i></p> |
| 738 |
|