ext/misc/editdist3.wiki

<title>The editdist3 algorithm</title>

The editdist3 algorithm is a function that computes the minimum edit distance
(a.k.a. the Levenshtein distance) between two input strings.  Features of
editdist3 include:

   *   It works with unicode (UTF8) text.

   *   A table of insertion, deletion, and substitution costs can be 
       provided by the application.

   *   Multi-character insertsions, deletions, and substitutions can be
       enumerated in the cost table.

<h2>The COST table</h2>

To program the costs of editdist3, create a table such as the following:

<blockquote><pre>
CREATE TABLE editcost(
  iLang INT,   -- The language ID
  cFrom TEXT,  -- Convert text from this
  cTo   TEXT,  -- Convert text into this
  iCost INT    -- The cost of doing the conversionnn
);
</pre></blockquote>

The cost table can be named anything you want - it does not have to be called
"editcost".  And the table can contain additional columns.  However, it the
table must contain the four columns show above, with exactly the names shown.

The iLang column is a non-negative integer that identifies a set of costs
appropriate for a particular language.  The editdist3 function will only use
a single iLang value for any given edit-distance computation.  The default
value is 0.  It is recommended that applications that only need to use a
single langauge always use iLang==0 for all entries.

The iCost column is the numeric cost of transforming cFrom into cTo.  This
value should be a non-negative integer, and should probably be less than 100.
The default single-character insertion and deletion costs are 100 and the
default single-character to single-character substitution cost is 150.  A
cost of 10000 or more is considered "infinite" and causes the rule to be
ignored.

The cFrom and cTo columns show edit transformation strings.  Either or both
columns may contain more than one character.  Or either column (but not both)
may hold an empty string.  When cFrom is empty, that is the cost of inserting
cTo.  When cTo is empty, that is the cost of deleting cFrom.

In the spellfix1 algorithm, cFrom is the text as the user entered it and
cTo is the correctly spelled text as it exists in the database.  The goal
of the editdist3 algorithm is to determine how close the user-entered text is
to the dictionary text.

There are three special-case entries in the cost table:

<table border=1>
<tr><th>cFrom</th><th>cTo</th><th>Meaning</th></tr>
<tr><td>''</td><td>'?'</td><td>The default insertion cost</td></tr>
<tr><td>'?'</td><td>''</td><td>The default deletion cost</td></tr>
<tr><td>'?'</td><td>'?'</td><td>The default substitution cost</td></tr>
</table>

If any of the special-case entries shows above are omitted, then the
value of 100 is used for insertion and deletion and 150 is used for
substitution.  To disable the default insertion, deletion, and/or substitution
set their respective cost to 10000 or more.

Other entries in the cost table specific transforms for particular characters.
The cost of specific transforms should be less than the default costs, or else
the default costs will take precedence and the specific transforms will never 
be used.

Some example, cost table entries:

<blockquote><pre>
INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'a', 'ä', 5);
</pre></blockquote>

The rule above says that the letter "a" in user input can be matched against
the letter "ä" in the dictionary with a penalty of 5.

<blockquote><pre>
INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'ss', 'ß', 8);
</pre></blockquote>

The number of characters in cFrom and cTo do not need to be the same.  The
rule above says that "ss" on user input will match "ß" with a penalty of 8.

<h2>Experimenting with the editcost3() function</h2>

The [./spellfix1.wiki | spellfix1 virtual table]
uses editdist3 if the "edit_cost_table=TABLE" option
is specified as an argument when the spellfix1 virtual table is created.  
But editdist3 can also be tested directly using the built-in "editdist3()"
SQL function.  The editdist3() SQL function has 3 forms:

  1.  editdist3('TABLENAME');
  2.  editdist3('string1', 'string2');
  3.  editdist3('string1', 'string2', langid);

The first form loads the edit distance coefficients from a table called
'TABLENAME'.  Any prior coefficients are discarded.  So when experimenting
with weights and the weight table changes, simply rerun the single-argument
form of editdist3() to reload revised coefficients.  Note that the 
edit distance
weights used by the editdist3() SQL function are independent from the
weights used by the spellfix1 virtual table.

The second and third forms return the computed edit distance between strings
'string1' and "string2'.  In the second form, an language id of 0 is used.
The language id is specified in the third form.