词典与容错检索

约 3125 字大约 10 分钟

2026-02-03

词典的搜索结构

主要有两种，哈希表和搜索树哈希（Hashing）和搜索树（Search trees）在字典查找中的应用及其优缺点：

哈希：
- 在一些搜索引擎中用于字典查找。将词汇项（键）哈希到一个足够大的整数空间，使哈希冲突不太可能发生；若发生冲突则通过辅助结构解决。
- 查询时，对每个查询词分别哈希并跟随指针到相应文档列表，需处理哈希冲突逻辑。
- 存在问题：难以找到查询词的细微变体（如重音和非重音版本），无法执行前缀查找（如查找以“automat”开头的所有词）；在词汇量不断增长的场景（如网络）中，为当前需求设计的哈希函数可能几年后就不够用。
搜索树：
- 克服了哈希的许多问题，例如可以枚举所有以特定前缀开头的词汇项。
- 最著名的搜索树是二叉树，每个内部节点有两个子节点。搜索从根节点开始，每个内部节点进行一个二分测试，根据测试结果向该节点下方的两个子树之一继续搜索。
- 高效搜索（比较次数为 O(logM)）的关键在于树保持平衡，即任何节点下的两个子树的术语数量要么相等，要么相差 1。主要问题是重新平衡，当向二叉搜索树中插入或删除术语时，需要重新平衡以保持平衡特性。

常用于字典的搜索树是 B 树 —— 一种搜索树，其中每个内部节点的子节点数量落在区间 [a,b]内，a与 b为合适的正整数。

模糊搜索

在模糊搜索中，*通配符的位置决定了我们的检索策略。

后缀与前导通配符查询
- 后缀通配符查询（如 mon*） *只在字符串末尾出现时，可以直接利用搜索树处理：从根节点依次沿 m → o → n遍历，就能枚举出字典中所有以 mon为前缀的词项集合 W，再通过标准倒排索引批量检索包含这些词项的文档。
- 前导通配符查询（如 *mon）当 *出现在开头，正向搜索不再适用。我们可以构建反向 B 树：把词项反向书写（例如 lemon变成 n o m e l），树的路径就对应反向词。这样，从根节点沿 n → o → m向下走，就能枚举出所有以 mon为后缀的词项集合 R。
处理中间带 *的通配符查询更进一步，结合普通 B 树（regular B-tree）与反向 B 树（reverse B-tree），我们还能处理只含单个 * 的更一般情况，例如 se*mon。思路如下：
1. 前缀匹配：用普通 B 树找出所有以 se为前缀的词项集合 W。
2. 后缀匹配：用反向 B 树找出所有以 mon为后缀的词项集合 R。
3. 交集筛选：取 W ∩ R，得到既以 se开头又以 mon结尾的词项。
4. 文档检索：利用标准倒排索引检索包含这些词项的文档。只需两棵 B 树——普通与反向——就能灵活应对单星号通配符的各种位置，显著提升搜索的表达能力。

通用模糊查询

我们现在研究两种用于处理一般通配符查询的技术。这两种技术共享一个通用策略：把给定的通配符查询 $q_w$ 表示为一个在特殊构造的索引上进行的布尔查询 Q，使得 Q的答案集合是匹配 $q_w$ 的词项集合的一个超集。然后，我们将 Q的每个答案词项与 $q_w$ 逐一比对，剔除那些不匹配 $q_w$ 的词项。此时我们就得到了真正匹配 $q_w$ 的词项集合，并可转而使用标准倒排索引来检索文档。

好的，我会把置换词索引（Permuterm Index）和k-gram 索引的核心原理、流程、优缺点以及一个简单示例，整理成适合博客发布的总结，并与前面的搜索树通配符处理方法形成体系化讲解。

置换词索引（Permuterm Index）

核心思想

为每个词项末尾添加一个特殊标记 $（表示词结束），例如 hello → hello$。
对该字符串做所有可能的循环移位（rotations），每个移位都指向原始词项。
这样，无论 * 出现在词的开头、中间还是结尾，都可以通过旋转查询把它变成 “* 在末尾” 的形式，再用搜索树做前缀匹配。

示例
词项：hello → hello$
循环移位集合：

hello$
ello$h
llo$he
lo$hel
o$hell
$hello

这些移位在索引中都指向 hello。

查询示例

查询 m*n → 旋转成 n$m* → 在索引中查找得到 man、moron 等。
查询 fi*mo*er → 旋转成 er$fi* → 找到候选词后逐一检查是否包含 mo，过滤掉 filibuster，保留 fishmonger。

优点

能处理任意位置的单个 * 通配符查询。

缺点

索引体积大：每个词要存所有循环移位，英语词典空间可能增加近 10 倍。

k-gram 索引

核心思想

k-gram 是长度为 k 的字符序列，例如 3-gram 就是连续的 3 个字符。
为词项生成所有 k-gram（并在首尾加 $ 标记边界），建立从 k-gram 到包含它的词项的倒排列表。
查询时把通配符拆成多个 k-gram，用布尔查询（AND）在 k-gram 索引中找候选词，再做后过滤剔除不符合原查询的词。

示例
词项：castle
3-gram 集合：$ca, cas, ast, stl, tle, le$
在索引中，cas → castle、case 等词。

查询示例

查询 re*ve → 转成布尔查询 $re AND ve$ → 在 3-gram 索引中找到 relive、remove、retrieve。
查询 red* → 布尔查询 $re AND red → 可能匹配到 retired（含两个 3-gram 但不满足 red*），需要后过滤去掉它。

优点

支持任意位置通配符，不必生成大量循环移位，空间相对可控。

缺点

需要额外的后过滤步骤，查询处理更复杂；布尔组合的通配符查询会增加计算量。

小结对比

方法	原理	适用场景	优点	缺点
搜索树（普通/反向 B 树）	前缀/后缀匹配 + 集合交集	单 `*` 在开头、中间、结尾	实现直观，速度快	只能处理单 `*` 且需两棵树配合
置换词索引	循环移位 + 前缀匹配	单 `*` 任意位置	支持任意位置通配符	索引体积大（约 10 倍）
k-gram 索引	k-gram 倒排 + 布尔 AND + 后过滤	单/多 `*` 任意位置	空间较置换词小，灵活	需后过滤，查询步骤多

拼写纠错

1. k‑gram 索引用于拼写纠正

为进一步缩小需要计算编辑距离的词汇范围，可以借助 k‑gram 索引（第 3.2.2 节）快速检索与查询词 $q$ 编辑距离较低的候选词。

基本思想
检索与查询词共享 许多公共 k‑gram 的词汇项。
对“许多公共 k‑gram”给出合理定义后，检索过程相当于对查询串 $q$ 的所有 k‑gram 的倒排列表做一次线性扫描。
示例（2‑gram / bigram）
图 3.7 展示查询 bord 的三个 bigram 的部分倒排记录：
```
[bo] → aboard → about → boardroom → border
[or] → border → lord → morbid → sordid
[rd] → aboard → ardent → boardroom → border
```
若要求候选词至少包含其中两个 bigram，一次扫描倒排表即可枚举出 aboard、boardroom、border 等词。
初步方法的缺陷
仅要求匹配固定数量的 k‑gram 会引入不合理候选，例如 boardroom 明显不是 bord 的合理拼写纠正。

2. 基于 Jaccard 系数的 k‑gram 重叠度量

为了在枚举阶段过滤掉不相关词，需要更精细的 重叠度量方法。

Jaccard 系数定义
给定两个集合 $A$ 、 $B$ ：
$J(A,B) = \frac{|A \cap B|}{|A \cup B|}$
这里 $A$ = 查询 $q$ 的 k‑gram 集合， $B$ = 某词汇项 $t$ 的 k‑gram 集合。
线性扫描适配
扫描倒排列表时，对每个词汇项 $t$ 实时计算 $J(q, t)$ ，若超过预设阈值则保留，否则跳过。
关键优化
计算 Jaccard 并不需要完整的 $t$ 的 k‑gram 列表，只需：
1. $q$ 的 k‑gram 集合（扫描时已知）
2. $t$ 的 k‑gram 总数（可预计算并存储在倒排项中）
  例：q = bord 与 t = bordroom 匹配 2 个 bigram，bord 有 3 个 bigram，bordroom 有 8 个 bigram：
$J = \frac{2}{8 + 3 - 2} = \frac{2}{9}$
可替换度量
除 Jaccard 外，也可采用其他支持倒排扫描时高效计算的重叠度量。

3. 拼写纠错的实用流程

有实证支持的三步法：

候选生成
利用 k‑gram 索引 枚举一组可能是查询词 $q$ 潜在纠正项的词汇项集合。
编辑距离计算
计算 $q$ 与候选集中每个词的编辑距离（Levenshtein 距离）。
最佳纠正选取
从候选集中挑选与 $q$ 编辑距离最小的词作为最终纠正结果。

语音纠错

在容错检索（tolerant retrieval）的众多方法中，Phonetic correction（语音纠错）专门用于处理因发音相近而产生的拼写错误。它的应用场景尤其集中在人名搜索——很多时候用户输入的查询在读音上与目标词一致，只是拼写不同。

核心思路是为每个词生成一个 phonetic hash（语音哈希），让发音相似的词映射到同一个哈希值。这一思想最早来自 20 世纪初国际警察部门的需求——他们需要在不同国家拼写各异的通缉犯姓名之间建立匹配。因此，该方法更多用于纠正专有名词（proper nouns）里的语音拼写错误。

实现语音哈希的算法通常被统称为 Soundex algorithms（Soundex 算法）。最初的 Soundex 算法存在多个变体，基本构建方案如下：

将每个待索引的词转换为 4 字符简化形式，并基于这些简化形式建立倒排索引（，称为 soundex index。
对查询词执行同样的转换。
当查询需要Soundex 匹配时，就在 soundex index 中进行搜索。

不同 Soundex 算法的差异主要体现在“词 → 4 字符形式”的转换规则上。常见的一种转换结果是4 字符代码：首字符为字母，后三位为 0–9 的数字。

Soundex 算法步骤与示例

Soundex 算法的具体流程可以拆解为以下步骤：

保留术语的首字母。
将以下字母全部替换为 ‘0’：
A, E, I, O, U, H, W, Y
按以下映射将字母转为数字：
- B, F, P, V → 1
- C, G, J, K, Q, S, X, Z → 2
- D, T → 3
- L → 4
- M, N → 5
- R → 6
反复删除连续相同数字对中的一个。
去掉结果字符串中的所有 0，尾部补零至四位长度，返回前四位——即一个字母加三位数字。

举例：

Hermann → H655
当输入查询（例如 herman）时，先计算其 Soundex 代码，再从 soundex index 中检索所有与该代码匹配的词汇项，然后在标准的 inverted index（倒排索引）上执行最终查询。

算法背后的观察与局限

Soundex 的设计基于两个关键观察：

在转录姓名时，元音被视为可互换。
发音相似的辅音，会被归入同一等价类，例如 D 和 T。
这让相关姓名常常拥有相同的 Soundex 代码。

虽然这些规则在很多场景（尤其是欧洲语言）下有效，但它本质上是依赖书写系统。例如中文姓名的 Wade-Giles（威妥玛拼音）与汉语拼音转写：

Soundex 能部分处理两者的差异，比如将 Wade-Giles 的 hs 与 Pinyin 的 x 都映射为 2。
但在另一些情况下会失效，比如 Wade-Giles 的 j 与 Pinyin 的 r 会得到不同的映射结果。

这意味着，跨语言或跨书写系统的语音匹配，仅靠 Soundex 可能无法完全覆盖所有情况，需要结合其他方法或定制规则来提升效果。