词典搜索的数据结构

• 哈希表
  弊端：查询词项稍有变化，哈希函数会生成截然不同的结果，故难以处理词项存在轻微变形的情况(如前缀式查询)
• 搜索树
  1、二叉树
  
  2、B树
  采用B树，允许内部节点的子树数目在某个固定区间内变化，减少重新对树进行平衡化处理的开销。

通配符查询

根据通配符*在字符串中出现的位置，有以下处理策略。

• 尾通配符查询(trailing wildcard query)

  基于搜索树的字典结构能很方便处理尾通配符查询

• 首通配符查询(leading wildcard query)

  引入词典的反向B树结构，即将原来B树中的每个从根到叶子路径所代表的的词项全部反过来写。如词项lemon，在反向B树中的路径是root-n-o-m-e-l。

• 单通配符的一般通配符查询

同时使用B树和反向B树，如se*mon,通过B树返回前缀se的词项集合W，再通过反向B树来返回所有后缀为mon的词项集合R。然后对W和R求交集。

一般的通配符查询

策略：将通配符查询q表示成布尔查询Q，在特定的倒排索引上进行处理，逐一判断Q对应的词项集合的每一个元素是否满足q的需求，剔除不满足的。最后得到q对应的词项，再去查普通倒排索引。

轮排索引

引入$$，用于标识词项结束。例，将词项hello，扩展成hello $，对扩展词项的每个旋转结果都构造一个指针来指向原始词项。

处理查询的方式，例：
查询mn，将查询进行旋转让出现在字符串末尾，即得到n$m*。在轮排索引中查找该字符串，返回轮排索引中对应的词项集合，然后通过穷举法检查该集合中每个元素，过滤掉一些不满足查询的词项，再利用剩下的词项去查普通倒排索引。

轮排索引缺点：词典会变得非常大

支持通配符查询的k-gram索引

在k-gram索引结构中，词典由词汇表中所有词汇的所有k-gram构成，每个倒排记录表由包含k-gram的词项组成

拼写校正

拼写校正的基本原则(1)在其可能的正确拼写中，选择距离"最近"的一个。(2)当两个正确拼写查询邻近度相等时，选择最常见的那个(可通过统计各词项在文档集中出现的次数来获得)。

词项独立(isolated-term)的校正

在词项独立的校正方法中，不管查询中包含多少个查询词项，每次只对单个查询词项进行校正。
缺点：很难检测到查询flew form Heathrow中实际包含一个错误的词项form（正确形式应为from）

编辑距离

编辑距离：给定两个字符串s1和s2，两者的编辑距离为将s1转换成s2的最小编辑操作数。

编辑操作包括：(1)将字符插入字符串(2)从字符串中删除一个字符(3)将字符串中的一个字符替换成另一个字符。这些操作的编辑距离也称Levenshtein距离

编辑距离的推广：允许不同编辑操作具有不同的权重

编辑距离的解决思路:动态规划

拼写校正中的k-gram索引

通过线性扫描给出查询q的所有k-gram的倒排记录表，并立即合并倒排记录表(只需待匹配词项包含查询q中某个固定数目的k-gram即可)。

• Jaccard系数 - 更精确的重叠度计算方法
  

其中A,B分别是查询q、词汇表词项的k-gram集合。

上下文敏感(context-sensitive)的校正

• 简单的实现方法
  即使每个单词拼写都是对的，仍要对每个单词找到可能的拼写正确词，然后尝试对短语中的每个词进行替换。
  穷举过程中开销会很大。

• 启发式方法
  在对词进行替换时，只保留文档集合或者查询日志中高频组合结果。

基于语音的校正技术

针对用户输入与目标词项发音相似的查询，尤其适用于人名查找。

基本思路：对每个词项，进行一个语音哈希操作，发音相似的词项都被映射为同一值

• soundex算法
  (1)将所有词项转变为四字符的简化形式
  (2)对查询词项进行相同的操作
  (3)对查询进行soundex匹配
• 四字符编码的常用方式
  (1)保留词项的首字母
  (2)将后续所有的A、E、I、O、U、H、W、Y等字母转换为0
  (3)其他字母转换规则如下：将B、F、P、V转换成1； 将C、G、J、K、Q、S、X、Z转换成2; 将D、T转换为3；将L转换为4； 将M和N转换成5 ；将R转换为6
  (4)将连续出现的两个同一字符转换为一个字符
  (5)在结果字符串中剔除0，并在结果字符尾部补足0，返回前四个字符，该字符由一个字母和三个数字组成。

缺点:发音体系不同则无法使用。