Debian Codegraph @

www/spellfix1.html

raw
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