研究生课程：现代信息检索-第4讲 通配查询与拼写矫正

《现代信息检索》课程笔记：第4讲 通配查询与拼写矫正

第4讲 通配查询与拼写矫正

词典

词典是指存储词项词汇表的数据结构：作用：存储词项以及定位词项

词项词汇表指的是具体数据，而词典指的是数据结构

采用定长数组的词典结构对每个词项需要存储文档频率和指向倒排记录表的指针

词项定位（查词典）：在词典中查找给定关键字

用于词项定位的数据结构：主要是哈希表和树

有些IR系统用哈希表，有些系统用树结构

采用哈希表或树的准则：

• 词项数目是否固定（词项数目是否持续增长）（固定采用哈希表更好，因为快，但是动态更新的代价比较高）
• 词项的相对访问频率如何
• 词项的数目有多少

哈希函数：输入词项，输出正整数（通常是地址）

• 每个词项通过哈希函数映射成一个整数
• 尽可能避免冲突
• 查询处理时： 对查询词项进行哈希，如果有冲突，则解决冲突，最后在定长数组中定位
• 优点：
  • 在哈希表中的定位速度快于树中的定位速度
  • 查询时间是常数
• 缺点：
  • 无法处理词项的微小变形
  • 不支持前缀搜索
  • 如果词汇表不断增大，需要定期对所有词项重新哈希

树

树可以支持前缀查找(相当于对词典再建一层索引)

最简单的树结构：二叉树，搜索速度略低于哈希表方式，时间复杂度为, 其中是词汇表大小，即所有词项的数目

且仅仅对平衡树成立，使二叉树重新保持平衡开销很大

B-树：每个内部节点的子节点数目在之间，其中为合适的正整数

通配查询

通配查询：包含通配符的查询

mon*: 找出所有包含以mon开头的词项的文档

如果采用B-树词典结构，那么实现起来非常容易，只需要返回区间mon ≤ t < moo上的词项t

*mon: 找出所有包含以mon结尾的词项的文档

将所有的词项倒转过来，然后基于它们建一棵附加的树，返回区间nom ≤ t < non上的词项t

词项中间的*号处理：mnchen

• 在B-树中分别查找满足m*和 *nchen的词项集合，然后求交集（开销很大）

轮排索引：（主要思想：让星号出现在词汇的末尾）

• 将每个通配查询旋转，使*出现在末尾
• 将每个旋转后的结果存放在词典中，即B-树中

轮排索引的查找过程：

• 将查询进行旋转，将通配符旋转到右部
• 同以往一样查找B-树，得到匹配的所有词项，将这些词项对应的倒排记录表取出

相对于通常的B-树，轮排索引(轮排树)的空间要大4倍以上 (经验值)

k-gram索引：枚举一个词项中所有连读的k个字符构成k-gram

• 构建一个倒排索引，此时词典部分是所有的k-gram，倒排记录表部分是包含某个k-gram的所有词项
• 相当于对词项再构建一个倒排索引（二级索引）
• 比轮排索引空间开销要小
• 但是可能返回一些伪正例，需要进行后过滤

k-gram存在两个倒排索引：

• 词典-文档的倒排索引基于词项返回文档
• k-gram索引用于查找词项，即基于查询所包含的k-gram来查找所有的词项

k-gram索引 vs. 轮排索引

• k-gram索引的空间消耗小
• 轮排索引不需要进行后过滤

拼写矫正

涉及的任务：拼写错误检测和拼写错误矫正（并不是先后的关系）

错误种类：非词汇错误（纠正的时候不需要考虑上下文）和真实词汇错误（纠正的时候需要考虑上下文）

两个主要用途

• 纠正待索引文档
• 纠正用户的查询

非词汇拼写错误检测：词典中不存在的词均视为错误

• 一般来说，词典越大越好
• Web很大，但是充满了拼写错误，因此并不是一个很好的词典

非词汇拼写错误矫正：

• 产生候选：与错误书写的单词相似的真实词汇
• 选择最好的候选词：最短加权编辑距离和最高噪声通道概率
• 候选集：找到发音相似的候选词、找到拼写相似的候选词、将 w 也包括在候选集里

词独立法：

• 词典中不存在的词均视为错误
• 只检查每个单词本身的拼写错误
• 但是如果某个单词拼写错误后变成另外一个单词，则无法查出

采用拼写噪声通道模型：通过贝叶斯定理求解：

正确拼写为，错误拼写为，则

可以通过文档进行估计

• 拼写相近的词：Damerau-Levenshtein编辑距离（插入、删除、替换、两个相邻字母的替换）
  • 80% 的拼写错误到正确拼写的编辑距离 = 1，几乎所有拼写错误到正确拼写的编辑距离 <= 2

产生候选词的方法：

1. 遍历词典，计算每一个词的编辑距离
2. 生成所有编辑距离 ≤ k (例如, k = 1 或 2)的词，然后与词典取交集
3. 建立一个字符k-gram索引，从词典中找到共享最多k-grams的词项（例如，基于Jaccard系数计算）
4. 使用Levenshtein 有限状态转换机快速计算
5. 预先计算一个词项到可能的 正确词项/拼写错误的映射表

语言模型

若有包含个词条的大文本语料，则，是词频。（一元先验概率）

通道模型概率-计算错误概率：混淆“矩阵”（计算一个字符变为另一个字符的概率如何）

• 混淆矩阵构建也可以考虑键盘的邻近型

然后可以计算噪声通道模型

计算的过程中可以添加加一概率平滑：上述混淆矩阵的例子很难避免某种操作样本数为0，要避免这种概率为0的情况

真实词汇错误的纠正通常需要考虑上下文

上下文敏感法：

• 纠错时要考虑周围的单词
• 产生候选：与错误书写的单词相似的真实词汇
  • 找到发音相似的候选词
  • 找到拼写相似的候选词
  • 选择最好的候选词：最短加权编辑距离、最高噪声通道概率

真实词汇拼写矫正的噪声通道：二元语言模型，将一元模型与二元模型插值

• 给定句子，为每个词产生一个候选词集合，最后选择序列使得概率最大

通道模型的改进：

• 为概率增加一个权重
• 允许更丰富的编辑操作
• 将发音融入到通道模型中
• 将设备融入到通道模型中