Documentation Source Text

<title>The spellfix1 virtual table</title>
<tcl>
hd_keywords {spellfix1}</tcl>
<h1 align='center'>The Spellfix1 Virtual Table</h1>

<p>This spellfix1 [virtual table] can be used to search
a large vocabulary for close matches.  For example, spellfix1
can be used to suggest corrections to misspelled words.  Or,
it could be used with [FTS4] to do full-text search using potentially
misspelled words.

<p>The implementation for the spellfix1 virtual table is held in the
canonical SQLite source tree in the file src/test_spellfix1.c.  The


spellfix1 virtual table is not included in the SQLite [amalgamation]
and is not a part of any standard SQLite build.  Applications that
want to make use of spellfix1 should obtain a copy of the src/test_spellfix1.c
source file and compile it as a shared library or DLL.  Then use the
[sqlite3_load_extension()] interface at run-time to load this extension
into the application.

<p>Once the extension is loaded, an instance of the spellfix1 virtual table
is created like this:

<blockquote><pre>
CREATE VIRTUAL TABLE demo USING spellfix1;
</pre></blockquote>

<p>The "spellfix1" term is the name of this module and must be entered as
shown.  The "demo" term is the
name of the virtual table you will be creating and can be altered
to suit the needs of your application.  The virtual table is initially
empty.  In order for the virtual table to be useful, you will need to
populate it with your vocabulary.  Suppose you
have a list of words in a table named "big_vocabulary".  Then do this:

<blockquote><pre>
INSERT INTO demo(word) SELECT word FROM big_vocabulary;
</pre></blockquote>

<p>If you intend to use this virtual table in cooperation with an FTS4
table (for spelling correctly of search terms) then you might extract
the vocabulary using an fts3aux table:

<blockquote><pre>
INSERT INTO demo(word) SELECT term FROM search_aux WHERE col='*';
</pre></blockquote>

<p>You can also provide the virtual table with a "rank" for each word.
The "rank" is an estimate of how common the word is.  Larger numbers

the search will be against language 0 (English in the example above.)
All spellfix1 searches are against a single language id.  There is no
way to search all languages at once.
 

<h2>Virtual Table Details</h2>


<p>The virtual table actually has a unique rowid with seven columns plus five
extra hidden columns.  The columns are as follows:

<blockquote><dl>
<dt><p><b>rowid</b><dd>
A unique integer number associated with each
vocabulary item in the table.  This can be used
as a foreign key on other tables in the database.

SPELLINGS section below for details.

<dt><p><b>command</b><dd>
(HIDDEN)  The value of the "command" column is always NULL.  However,
applications can insert special strings into the "command" column in order
to provoke certain behaviors in the spellfix1 virtual table.
For example, inserting the string 'reset' into the "command" column
will cause the virtual table will reread its edit distance weights
(if there are any).
</dl></blockquote>

<h2>Algorithm</h2>

<p>The spellfix1 virtual table creates a single
shadow table named "%_vocab" (where the % is replaced by the name of

Levenshtein distance between a pattern and a word.  This function
is exposed as spellfix1_editdist(X,Y).  The edit distance function
returns the "cost" of converting X into Y.  Some transformations
cost more than others.  Changing one vowel into a different vowel,
for example is relatively cheap, as is doubling a constant, or
omitting the second character of a double-constant.  Other transformations
or more expensive.  The idea is that the edit distance function returns
a low cost of words that are similar and a higher cost for words
that are further apart.  In this implementation, the maximum cost
of any single-character edit (delete, insert, or substitute) is 100,
with lower costs for some edits (such as transforming vowels).

<p>The "score" for a comparison is the edit distance between the pattern
and the word, adjusted down by the base-2 logarithm of the word rank.
For example, a match with distance 100 but rank 1000 would have a

<p>The source code module that implements the spellfix1 virtual table also
implements several SQL functions that might be useful to applications
that employ spellfix1 or for testing or diagnostic work while developing
applications that use spellfix1.  The following auxiliary functions are
available:

<blockquote><dl>
<dt><p><b>editdist3(P,W)<br>editdist2(P,W,L)<br>editdist3(T)</b><dd>
These routines provide direct access to the version of the Wagner
edit-distance function that allows for application-defined weights
on edit operations.  The first two forms of this function compare
pattern P against word W and return the edit distance.  In the first
function, the langid is assumed to be 0 and in the second, the
langid is given by the L parameter.  The third form of this function
reloads edit distance coefficients from the table named by T.