1. 概述

此 spellfix1 虚拟表 可用于搜索大型词汇表以查找近似匹配。例如，spellfix1 可用于建议拼错单词的更正。或者，它可以与 FTS4 一起使用，以使用可能拼错的单词进行全文搜索。

spellfix1 虚拟表的实现位于 SQLite 源代码树的杂项扩展文件夹中，特别是在 ext/misc/spellfix1.c 文件中。spellfix1 虚拟表未包含在 SQLite 合并 中，也不属于任何标准 SQLite 版本的一部分。它是一个 可加载扩展。

加载 spellfix1 扩展后，可以像这样创建 spellfix1 虚拟表的实例

CREATE VIRTUAL TABLE demo USING spellfix1;

"spellfix1" 一词是 spellfix 模块的名称，必须按所示输入。 "demo" 一词是您将创建的虚拟表的名称，可以根据您的应用程序的需要进行更改。虚拟表最初为空。为了使虚拟表有用，您需要用您的词汇表填充它。假设您在名为 "big_vocabulary" 的表中有一列单词。然后执行以下操作

INSERT INTO demo(word) SELECT word FROM big_vocabulary;

如果您打算将此虚拟表与 FTS4 表配合使用（用于搜索词的拼写更正），那么您可能需要使用 fts4aux 表提取词汇表

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

您还可以为虚拟表提供每个单词的“排名”。“排名”是对单词出现频率的估计。数字越大，表示单词越常用。如果您在填充表格时省略了排名，则假定排名为 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

这是从模式到单词的编辑距离或莱文斯坦距离。

langid

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

score

分数是排名和距离的组合。其理念是分数越低越好。虚拟表尝试查找得分最低的单词，并且默认情况下（除非被 ORDER BY 覆盖），返回结果的顺序是得分递增的顺序。

matchlen

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

phonehash

此列显示用于限制搜索的音韵散列前缀。对于任何给定的查询，此列对所有行都应该相同。此信息可用于诊断目的，通常不认为它在实际应用程序中很有用。

top

(隐藏) 对于任何查询，此值在所有行上都相同。它是一个整数，表示将输出的最大行数。实际输出的行数可能小于此数字，但绝不会大于此数字。top 的默认值为 20，但可以在每次查询中通过在查询的 WHERE 子句中包含形式为 “top=N” 的项来更改。

scope

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

srchcnt

(隐藏) 对于任何查询，此值在所有行上都相同。此值是一个整数，表示使用编辑距离算法检查的单词数，以找到最终显示的最佳匹配结果。此值仅用于诊断目的。

soundslike

(隐藏) 插入词汇表条目时，可以将此字段设置为与单词发音匹配的拼写。有关详细信息，请参见下面的“处理不寻常和难以拼写的单词”部分。

command

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

4. 算法

spellfix1 虚拟表创建一个名为 "%_vocab" 的单一影子表（其中 % 将被虚拟表的名称替换；例如，对于 “demo” 虚拟表，它是 “demo_vocab”）。影子表包含以下列

id

唯一 ID (INTEGER PRIMARY KEY)

rank

单词的排名。

langid

此条目的语言 ID。

word

词汇表单词的原始 UTF8 文本

k1

单词转写为小写 ASCII。有一个标准映射表，用于将非 ASCII 字符映射为 ASCII。例如： "æ" -> "ae"，"þ" -> "th"，"ß" -> "ss"，"á" -> "a"，... 辅助函数 spellfix1_translit(X) 将执行非 ASCII 到 ASCII 的映射。内置的 lower(X) 函数将转换为小写。因此： k1 = lower(spellfix1_translit(word))。如果单词已经是全部小写 ASCII，则 k1 列将包含 NULL。这减少了 %_vocab 表的存储要求，并有助于 spellfix 运行得更快。因此，最好使用小写 ASCII 词汇表填充尽可能多的 spellfix 表。

k2

此字段保存从 coalesce(k1,word) 派生的音韵代码。具有相似音调的字母映射到相同的符号。例如，所有元音和元音簇都变为单个符号 “A”。字母 “p”、”b”、”f” 和 “v” 都变为 “B”。所有鼻音都表示为 “N”。等等。映射基于在 Soundex、Metaphone 和其他长期存在的音韵匹配系统中发现的想法。此密钥可以通过 spellfix1_phonehash(X) 函数生成。因此： k2 = spellfix1_phonehash(coalesce(k1,word))

还有一个用于计算模式和单词之间的瓦格纳编辑距离或莱文斯坦距离的函数。此函数公开为 spellfix1_editdist(X,Y)。编辑距离函数返回将 X 转换为 Y 的“成本”。一些转换比其他转换更昂贵。例如，将一个元音更改为另一个元音相对便宜，就像将一个辅音加倍或省略一个双辅音的第二个字符一样。其他转换或更昂贵。其理念是，编辑距离函数对相似的单词返回较低的成本，对相差较远的单词返回较高的成本。在此实现中，任何单个字符编辑（删除、插入或替换）的最大成本为 100，而某些编辑的成本较低（例如，将元音转换）。

比较的“得分”是模式和单词之间的编辑距离，向下调整为单词排名的以 2 为底的对数。例如，距离为 100 但排名为 1000 的匹配将具有 122 的得分（= 100 - log2(1000) + 32），而距离为 100 但排名为 1 的匹配将具有 131 的得分（100 - log2(1) + 32）。（注意：常数 32 加到每个分数中，以防止在编辑距离为零的情况下分数变为负数。）这样，常用的单词会获得略微更低的成本，这会使它们倾向于出现在替代拼写列表的顶部。

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

假设要进行拼写校正的词语是 X。为了限制搜索空间，X 将使用等效于以下内容的转换转换为 k2 类密钥

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

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

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

仅搜索词汇表中具有匹配 langid 的术语。因此，同一表格可以包含来自多种语言的条目，并且只会使用请求的语言。默认 langid 为 0。

5. 可配置编辑距离

内置的 Wagner 编辑距离函数（具有固定权重）可以替换为 editdist3() 编辑距离函数（具有应用程序定义的权重并支持 Unicode），方法是在创建虚拟表时将“edit_cost_table=TABLENAME”参数指定给 spellfix1 模块。例如

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

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

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

只要每个条目都有不同的 soundslike 值，就可以为同一个词添加多个条目。请注意，如果未指定 soundslike 值，则 soundslike 默认为词本身。

以下是可能需要添加额外的 soundslike 条目的情况。具体条目将取决于应用程序和目标语言。

• 以“ps”开头的单词中的无声“p”：psalm、psyche
• 以“pn”开头的单词中的无声“p”：pneumonia、pneumatic
• 以“pt”开头的单词中的无声“p”：pterodactyl、ptolemaic
• 以“dj”开头的单词中的无声“d”：djinn、Djikarta
• 以“kn”开头的单词中的无声“k”：knight、Knuthson
• 以“gn”开头的单词中的无声“g”：gnarly、gnome、gnat
• 以“Mac”和“Mc”开头的苏格兰姓氏
• 斯拉夫语中的“Tch”音：Tchaikovsky vs. Chaykovsky
• 西班牙语中发音为“h”的字母“j”：LaJolla
• 以“wr”和“r”开头的单词：write vs. rite
• 各种有问题的单词，如“debt”、“tsetse”、“Nguyen”、“Van Nuyes”。

7. 辅助函数

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

editdist3(P,W)
editdist3(P,W,L)
editdist3(T)

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

spellfix1_editdist(P,W)

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

spellfix1_phonehash(X)

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

spellfix1_scriptcode(X)

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

• 215 - 拉丁语
• 220 - 西里尔字母
• 200 - 希腊语

在将来的版本中可能会添加额外的语言代码。

spellfix1_translit(X)

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

8. editdist3 函数

editdist3 算法是一个函数，它计算两个输入字符串之间的最小编辑距离（也称为 Levenshtein 距离）。editdist3 算法是 spellfix1 默认编辑距离函数的可配置替代方案。editdist3 的功能包括

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

• 应用程序可以提供一个包含插入、删除和替换成本的表格。

• 成本表中可以列出多字符插入、删除和替换。

9. editdist3 成本表

要对 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	含义
''	'?'	默认插入成本
'?'	''	默认删除成本
'?'	'?'	默认替换成本

如果上面显示的任何特殊情况条目被省略，则插入和删除使用 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()”SQL 函数直接测试 editdist3。editdist3() SQL 函数有 3 种形式

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

第一种形式从名为“TABLENAME”的表中加载编辑距离系数。任何先前的系数将被丢弃。因此，在使用权重进行实验并且权重表发生更改时，只需重新运行 editdist3() 的单参数形式以重新加载修改后的系数。请注意，editdist3() SQL 函数使用的编辑距离权重独立于 spellfix1 虚拟表使用的权重。

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

此页面最后修改于 2023-10-10 17:29:48 UTC