通配符查询？
mon*: 找出所有包含以 mon开头的词项的文档
如果采用B-树词典结构，那么实现起来非常容易，只需要返回区间mon ≤ t < moo上的词项t
*mon: 找出所有包含以mon结尾的词项的文档
将所有的词项倒转过来，然后基于它们建一棵附加的树
返回区间nom ≤ t < non上的词项t
例子: m*nchen
在B-树中分别查找满足m*和 *nchen的词项集合，然后求交集
这种做法开销很大
另外一种方法: 轮排(permuterm) 索引
对于hello，轮排索引中已经存储了 hello$, ello$h, llo$he, lo$hel, o$hell和$hello字符串
查询处理
输入查询为 X，则在轮排索引中寻找 X$字符串即可
输入查询为 X*，则寻找以$X开始的字符串
输入查询为 *X，则寻找以X$开始的字符串
输入查询为 *X*，则寻找X开始的字符串即可，比如查询为*ello*，则只需要查到ello开头的串即可(上面是ello$h)，因为在轮排索引中，ello右部一定包含一个$，不论$是否处于尾部，该串均能满足查询*X*
输入查询为 X*Y, 则寻找Y$X开始的字符串，比如通配查询为 hel*o, 那么相当于要寻找o$hel开始的字符串
相对于通常的B-树，轮排索引(轮排树)的空间要大4倍以上 (经验值)
k-gram索引？
比轮排索引空间开销要小
枚举一个词项中所有连读的k个字符构成k-gram 。
2-gram称为二元组(bigram)
3-gram称为三元组(trigram)
例子: April is the cruelest month
2-gram: $a ap pr ri il l$ $i is s$ $t th he e$ $c cr ru ue el le es st t$ $m mo on nt h$
同前面一样，$ 是一个特殊字符，表示单词开始或结束
k-gram索引可能会返回很多伪正例，需要做过滤处理。
编辑距离？
拼写校正中的k-gram索引
略。
上下文敏感的拼写校正？
略。
基于发音的校正技术（Soundex算法）
保留词项的首字母
将后续所有的A、E、I、O、U、H、W及Y等字母转换为0。
按照如下方式将字母转换成数字：
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，并在结果字符串尾部补足0，然后返回前四个字符，该字符由1个字母加上3个数字组成。
References:
[1] Christopher D.Manning, Hinrich Schütze, Prabhakar Raghavan, 王斌[译]. 信息检索导论[M]. 北京:人民邮电出版社, 2016.
[2] 王斌,信息检索导论讲义,lecture3-tolerant-retrieval,2017
@qingdujun
2017-12-9 北京 怀柔