The Spellfix1 Virtual Table

1.概述

2.搜索优化

3.虚拟表格细节

4.算法

5.可配置的编辑距离

6.处理不寻常和困难的拼写

7.辅助函数

8. editdist3函数

9. editdist3 COST表

10.试用editcost3()函数

1.概述

这个 spellfix1 虚拟表可以用来搜索大量的词汇来进行近似匹配。例如，可以使用 spellfix1 来为错误的单词建议更正。或者，它可以与FTS4一起使用，以使用可能拼写错误的单词进行全文搜索。

spellfix1 虚拟表的实现保存在杂项扩展文件夹中的 SQLite 源代码树中，特别是在文件ext/misc/spellfix1.c中。spellfix1 虚拟表不包含在 SQLite 合并中，也不是任何标准 SQLite 构建的一部分。这是一个可装载的扩展。

一旦加载了 spellfix1 扩展，就会像这样创建 spellfix1 虚拟表的一个实例：

CREATE VIRTUAL TABLE demo USING spellfix1;

“spellfix1”术语是spellfix模块的名称，必须如图所示输入。“演示”术语是您要创建的虚拟表的名称，可以根据您的应用程序的需要进行更改。虚拟表最初是空的。为了使虚拟表有用，您需要使用词汇表填充它。假设你有一个名为“big_vocabulary”的表中的单词列表。然后这样做：

INSERT INTO demo(word) SELECT word FROM big_vocabulary;

如果您打算将这个虚拟表与FTS4表（用于搜索词的拼写纠正）配合使用，那么您可以使用 fts4aux 表提取词汇表：

INSERT INTO demo(word) SELECT term FROM search_aux WHERE col='*';

您还可以为每个单词提供“rank”的虚拟表。“rank”是对这个词有多普遍的估计。数字越大意味着这个词越常见。如果在填充表格时省略了排名，则假定等级为1。但是如果你有排名信息，你可以提供它，虚拟表将显示一个轻微的偏好选择更常用的术语。要从fts4aux表“search_aux”填充等级，请执行如下操作：

INSERT INTO demo(word,rank)
   SELECT term, documents FROM search_aux WHERE col='*';

要查询虚拟表，请在 WHERE 子句中包含 MATCH 运算符。例如：

SELECT word FROM demo WHERE word MATCH 'kennasaw';

使用美国地名的数据集（来自http://geonames.usgs.gov/domestic/download_data.htm），上面的查询返回20个结果，开始于：

kennesaw
kenosha
kenesaw
kenaga
keanak

如果将字符'*'追加到模式的末尾，则执行前缀搜索。例如：

SELECT word FROM demo WHERE word MATCH 'kennes*';

产生20个结果开始于：

kennesaw
kennestone
kenneson
kenneys
keanes
keenes

2.搜索优化

默认情况下，spellfix1 表返回不超过20个结果。（如果匹配次数较少，则返回值可能小于20.）可以通过向查询的WHERE子句添加“top = N”项来更改返回行数的上限，其中N是新的最大值。例如，要查看5个最佳匹配项：

SELECT word FROM demo WHERE word MATCH 'kennes*' AND top=5;

spellfix1 虚拟表中的每个条目都与特定语言相关联，由整数“langid”列标识。默认的langid是0，如果没有采取其他操作，整个词汇表就是0语言的一部分。但是，如果您的应用程序需要以多种语言操作，那么您可以在填充表格时通过指定langid字段来为每种语言指定不同的词汇项。例如：

INSERT INTO demo(word,langid) SELECT word, 0 FROM en_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 1 FROM de_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 2 FROM fr_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 3 FROM ru_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 4 FROM cn_vocabulary;

使用多种语言的项填充虚拟表后，请在查询的WHERE子句中使用“langid = N”项来指定感兴趣的语言：

SELECT word FROM demo WHERE word MATCH 'hildes*' AND langid=1;

请注意，如果您在WHERE子句中未包含“langid = N”项，则搜索将针对语言0（上述示例中的英语）。所有spellfix1搜索都针对单一语言ID。无法一次搜索所有语言。

3.虚拟表格细节

spellfix1 虚拟表中的每一行都有一个唯一的 rowid，包含七列和五个额外的隐藏列。专栏如下：

rowid

与表格中每个词汇项目相关的唯一整数。这可以用作数据库中其他表的外键。

word

与模式匹配的单词的文本。单词和模式都可以包含unicode字符，并且可以混合使用。

rank

这是在原始 INSERT 语句中指定的单词的级别。

distance

这是从模式到单词的编辑距离或 Levenshtein 距离。

langid

这是该词的语言标识。所有查询都是针对单个语言标识，默认为0.对于任何给定的查询，此值在所有行上都是相同的。

score

评分是排名和距离的组合。这个想法是，分数越低越好。虚拟表试图找到分数最低的单词，默认情况下（除非被ORDER BY覆盖）以分数递增的顺序返回结果。

matchlen

在前缀搜索中，matchlen是字符串中与前缀匹配的字符数。对于非前缀搜索，这与length(word)相同。

phonehash

此列显示用于限制搜索的语音哈希前缀。对于任何给定的查询，该列对于每一行都应该是相同的。这些信息可用于诊断目的，通常不适用于实际应用。

top

（HIDDEN）对于任何查询，这个值在所有行上都是相同的。它是一个整数，它是将要输出的最大行数。实际输出的行数可能小于这个数字，但它永远不会更大。top的缺省值是20，但可以通过在查询的WHERE子句中包含“top = N”形式的项来更改每个查询的值。

scope

(HIDDEN)对于任何查询，这个值在所有行上都是相同的。范围是衡量虚拟表查找匹配词的程度。较小的范围值会导致更广泛的搜索。范围通常是自动选择的，并且被限制为4.应用程序可以通过在查询的WHERE子句中包含一个形式为“scope = N”的术语来更改范围。增加范围将使查询运行得更快，但会减少可能的更正。

srchcnt

(HIDDEN)对于任何查询，这个值在所有行上都是相同的。该值是一个整数，它是使用编辑距离算法检查以查找最终显示的最高匹配的单词数量。该值仅用于诊断。

soundslike

(HIDDEN)当插入词条时，可以将该字段设置为匹配单词听起来像的拼写。有关详细信息，请参阅下面的“使用不寻常和难以处理的拼写处理”部分。

command

（HIDDEN）“command”列的值始终为NULL。但是，应用程序可以在“command”列中插入特殊字符串，以激发spellfix1虚拟表中的某些行为。例如，将字符串'reset'插入到“command”列中将导致虚拟表重新读取其编辑距离权重（如果有的话）。

4. Algorithm

spellfix1虚拟表创建一个名为“％_vocab”的影子表（其中％由虚拟表的名称替换;例如：“demo”虚拟表的“demo_vocab”）。影子表包含以下列：

id

唯一的ID（INTEGER PRIMARY KEY）

rank

word的等级。

langid

此条目的语言ID。

word

词汇单词的原始UTF8文本

k1

这个词被音译成小写的ASCII。有一个从非ASCII字符到ASCII的标准映射表。例如："æ" -> "ae", "þ" -> "th", "ß" -> "ss", "á" -> "a", ... 附件功能spellfix1_translit(X)非ASCII到ASCII映射。内置的较低(X)功能将转换为小写。因此：k1 = lower(spellfix1_translit(word)）。

k2

该字段包含从k1派生的语音代码。具有类似声音的字母映射到相同的符号。例如，所有元音和元音集群变成单个符号“A”。而字母“p”，“b”，“f”和“v”全部变成“B”。所有鼻音都表示为“N”。等等。该映射基于Soundex，Metaphone和其他长期拼音匹配系统中的想法。该键可以由函数spellfix1_phonehash(X)生成。因此：k2 = spellfix1_phonehash(k1)

还有计算模式和单词之间的Wagner编辑距离或Levenshtein距离的功能。这个函数被暴露为spellfix1_editdist(X，Y)。编辑距离函数返回将X转换为Y的“cost”。一些转换比其他转换花费更多。例如，将一个元音改变成不同的元音相对便宜，例如将常数加倍或省略双常数的第二个字符。其他转换或更昂贵。这个想法是，编辑距离函数对于相似的单词返回较低的成本，对于相距较远的单词成本较高。在此实现中，任何单字符编辑（delete, insert, or substitute）的最大成本为100，而某些编辑（如变换元音）的成本较低。

用于比较的“score”是模式与单词之间的编辑距离，由单词等级的基数2对数调整。例如，距离100但等级1000的匹配将具有122的分数（= 100-log2（1000）+32），而与等级为1的距离100的匹配将具有131的分数（100-log2（ 1）+32）。（注意：在编辑距离为零的情况下，将常数32加到每个得分上以防止其变为负值）。以这种方式，经常使用的单词得到稍低的成本，这往往会将它们移动到列表的顶部替代拼写。

直接执行拼写校正的方法是将搜索词与词汇表中的每个单词进行比较，并选择最低分数的20。但是，词汇表中通常会有数十万或数百万个单词，因此这种方法速度不够快。

假设正在进行拼写纠正的术语是X.为了限制搜索空间，X被转换为类似k2的密钥，使用等价的：

   key = spellfix1_phonehash(lower(spellfix1_translit(X)))

这个键然后限制为“scope”字符。默认范围值为4，但可以使用WHERE子句中的“scope= N”项指定替代范围。在截断键后，编辑距离将针对词汇表中的每个术语运行，该术语的k2值以缩写键开头。

例如，假设输入的单词是“Paskagula”。拼音键是“BACACALA”，然后被截断为4个字符“BACA”。编辑距离然后在k2值以BACA开头的词汇的4980个条目（总计272,597个条目中）上运行，产生“Pascagoula”作为最佳匹配。

只搜索具有匹配的langid的词汇的术语。因此，同一张表可以包含来自多种语言的条目，并且只会使用所需的语言。默认的langid是0。

5. Configurable Edit Distance

具有固定权重的内置Wagner编辑距离函数可以由editdist3()编辑距离函数替换，该函数具有应用程序定义的权重并支持unicode，通过为虚拟模块指定spellfix1模块的“edit_cost_table = TABLENAME ”参数表已创建。例如：

CREATE VIRTUAL TABLE demo2 USING spellfix1(edit_cost_table=APPCOST);

editdist3()编辑距离函数也可以在运行时通过在虚拟表的“command”列中插入适当的字符串来选择或取消选择：

INSERT INTO demo2(command) VALUES('edit_cost_table=APPCOST');

在上面的例子中，APPCOST表将被询问以找到编辑距离系数。这是spellfix1模块名称的“edit_cost_table =”参数的存在，导致使用editdist3()代替内置的编辑距离函数。如果APPCOST是空字符串，则使用内置的Wagner编辑距离函数。

编辑距离系数通常在存储在存储器中后从APPCOST表中一次又一次地读取。因此，对APPCOST表的运行时更改通常不会影响编辑距离结果。但是，将特殊字符串'reset'插入虚拟表的“command”列会导致编辑距离系数重新读取APPCOST表。因此，当对APPCOST表进行更改时，应用程序应该运行类似于以下内容的SQL语句：

INSERT INTO demo2(command) VALUES("reset");

6.处理不寻常和困难的拼写

上面的算法在大多数情况下工作得很好，但也有例外。这些例外情况可以通过在虚拟表格中使用“soundslike”列添加额外条目来处理。

例如，许多希腊语词汇以字母“ps”开始，其中“p”是无声的。例如：psalm, pseudonym, psoriasis, psyche。在另一个例子中，许多苏格兰姓氏可以拼写成最初的“Mac”或“Mc”。因此，“MacKay”和“McKay”的发音都是相同的。

通过在同一单词的虚拟表格中添加更多条目，但在“soundslike”列中添加替代拼写时，可以对不拼写的单词进行住宿。例如，“psalm”的规范条目是这样的：

  INSERT INTO demo(word) VALUES('psalm');

为了增强将“salm”拼写改写为“psalm”的能力，请添加如下所示的条目：

  INSERT INTO demo(word,soundslike) VALUES('psalm','salm');

只要每个条目具有不同的声音值，就可以为同一个单词创建多个条目。请注意，如果没有指定类似于声音的值，那么声音就会默认为该单词本身。

下面列出的是某些情况下可能会添加额外的声音条目。具体条目将取决于应用程序和目标语言。

• 以 “ps” 开头的无声 “p”：psalm, psyche

• 以 “pn” 开头的无声 “p”：pneumonia, pneumatic

• 用“pt”开头的无声“p”：pterodactyl, ptolemaic

• “d” 以 “dj” 开头的单词：djinn，Djikarta

• 用 “kn” 开头的无声 “k”：Knight，Knuthson

• 用 “gn” 开头的单词中的 “g”：gnarly，gnome，gnat

• “Mac” 与 “Mc”开始的苏格兰姓氏

• “Tch” 以斯拉夫语言发声：柴可夫斯基与 Chaykovsky

• 字母 “j” 在西班牙语中显示为 “h”：LaJolla

• 以 “wr” 与 “r” 开头的词语：写作与仪式

• 其他问题词如"debt", "tsetse", "Nguyen", "Van Nuyes".

7.辅助功能

实现 spellfix1 虚拟表的源代码模块还实现了几个 SQL 函数，这些函数可能对使用 spellfix1 的应用程序或在开发使用 spellfix1 的应用程序时进行测试或诊断工作有用。以下辅助功能可用：

editdist3(P,W)

editdist3(P,W,L)

editdist3(T)

这些例程提供对 Wagner 编辑距离功能版本的直接访问，允许编辑操作中的应用程序定义权重。该功能的前两种形式将模式 P 与字 W 进行比较并返回编辑距离。在第一个函数中，lan​​gid 假定为0，而第二个中，lan​​gid 由 L 参数给出。该函数的第三种形式是从T命名表中重新加载编辑距离系数。

spellfix1_editdist(P,W)

此例程提供对使用默认固定成本的内置 Wagner 编辑距离功能的访问。返回的值是将 W 转换为 P 所需的编辑距离。

spellfix1_phonehash(X)

此例程构造纯 ASCII 输入字 X 的语音散列并返回该散列。此例程由 spellfix1 在内部使用，以便将影子表的 K1列转换为 K2列。

spellfix1_scriptcode(X)

给定一个输入字符串 X，此例程将尝试确定该输入的主导脚本，并返回该脚本的 ISO-15924 数字代码。当前的实现理解以下脚本：

• 215 - Latin

• 220 - Cyrillic

• 200 - Greek

未来版本中可能会添加其他语言代码。

spellfix1_translit(X)

此例程将 unicode 文本转换为纯 ASCII，返回输入文本 X 的纯 ASCII 表示形式。这是内部用于将词汇表转换为影子表的K1列的函数。

8. editdist3 函数

editdist3 算法是计算两个输入字符串之间的最小编辑距离（即Levenshtein距离）的函数。editdist3 算法是 spellfix1 的默认编辑距离函数的可替代选项。editdist3 的特点包括：

• 它适用于 Unicode（UTF8）文本。

• 应用程序可以提供插入，删除和替换成本表。

• 多字符插入，删除和替换可以在成本表中枚举。

9. editdist3 COST 表

要编辑 editdist3 的成本，请创建一个如下所示的表格：

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 conversion
);

费用表可以任意命名 - 它不必被称为 “editcost”。该表可以包含其他列。唯一的要求是该表必须包含上面显示的四列，并显示正确的名称。

iLang 列是一个非负整数，用于标识适用于特定语言的一组成本。对于任何给定的编辑距离计算，editdist3 函数将只使用一个 iLang 值。默认值为0.建议仅需要使用单一语言的应用程序始终对所有条目使用 iLang == 0。

iCost 列是将 cFrom 转换为 cTo 的数字代价。该值应该是一个非负整数，可能应该小于100.默认的单字符插入和删除成本为100，默认的单字符到单字符替换成本为150.成本为10000或更多被认为是“无限”，并导致规则被忽略。

cFrom 和 cTo 列显示编辑转换字符串。其中一个或两个列可能包含多个字符。或者任一列（但不是两者）可以保存一个空字符串。当 cFrom 为空时，这是插入 cTo 的成本。当 cTo 为空时，这是删除 cFrom 的成本。

在 spellfix1 算法中，cFrom 是用户输入的文本，cTo 是拼写正确的文本，因为它存在于数据库中。editdist3 算法的目标是确定用户输入的文本与字典文本的接近程度。

成本表中有三种特殊情况条目：

cFrom	cTo	Meaning
''	'?'	The default insertion cost
'?'	''	The default deletion cost
'?'	'?'	The default substitution cost

如果上面显示的任何特例条目被省略，则100的值用于插入和删除，150用于替换。要禁用默认插入，删除和/或替换，请将其各自的成本设置为10000或更高。

成本表中的其他条目特定字符转换。特定转换的成本应低于默认成本，否则默认成本将优先，并且不会使用特定的转换。

一些示例，成本表条目：

INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'a', 'ä', 5);

上面的规则表明，用户输入中的字母 “a” 可以与字典中的字母 “ä” 相匹配，罚款5。

INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'ss', 'ß', 8);

cFrom 和 cTo 中的字符数不需要相同。上面的规则说，用户输入的 “ss” 将与 “ß” 相符，罚款为8。

10.试用 editcost3（）函数

如果在创建 spellfix1 虚拟表时将 “edit_cost_table = TABLE” 选项指定为参数，则 spellfix1 虚拟表使用 editdist3。但是 editdist3 也可以直接使用内置的 “editdist3（）”SQL 函数进行测试。editdist3（）SQL函数有三种形式：

• editdist3('TABLENAME');

• editdist3('string1', 'string2');

• editdist3('string1', 'string2', langid);

第一种形式从名为 “TABLENAME” 的表格加载编辑距离系数。任何先前的系数都被丢弃。因此，当尝试使用权重和权重表更改时，只需重新运行 editdist3（）的单参数形式以重新加载修订的系数即可。请注意，editdist3（）SQL 函数使用的编辑距离权重与 spellfix1 虚拟表使用的权重无关。

第二种和第三种形式返回字符串 'string1' 和 'string2' 之间计算的编辑距离，第二种形式使用0的语言 ID，第三种形式指定语言 ID。