信息检索笔记-词典及容错式检索
本文将介绍当查询中出现拼写错误时的鲁棒性处理技术。并给出可能的查询结果。
词典的数据结构
第一章我们知道，倒排表包括两个部分。一个是词典，另一个是倒排记录表。我们查询的时候首先要通过索引词典的词，然后再通过词的指针找到倒排表的地址，取出相应的倒排记录表。
前面，我们已经知道了倒排记录表可以通过链表或者可变数组实现。那么词典可以通过哪些数据结构实现呢？我们可以通过hash表实现，hash表的缺点在于，如果hash空间增大，我们需要把已存在的记录重新hash一遍，可扩展性太弱；B树实现，很容易满足前缀搜索的要求；个人觉得trie树也是不错的选择，专门用来实现字典的树。反正就是为了加快对字典的检索速度。下面画个示意图。
通配符查询
用户有时候对单词的不确定性，可能会输入一些通配符操作。例如，ab*表示以ab开头的任意单词，这种表示前缀式；还以可能是“*ab”表示以ab结尾的单词，这种表示后缀式；还有可能是ab*cd，这种比较麻烦。
为了处理这三种查询，我们有这样的解决办法。
（1）B树解决方案
字符串前缀搜索一直是B树的优点，而字符串后缀搜索，我们可以采用反向B树，那么对于这种ab*cd，那么我就可以通过B树和反向B树的结合，最后取一个交集。
（2）轮排索引解决方案
我们对一个单词建立轮排索引。假如有hello，我们建立下列轮排单词表。
那么对于通配符操作，我们怎样用这个方案去解决呢。对于"m*n"我们首先通过选择将“*”旋转到末尾，下一步就是在轮排索引中查找该字符串，实际上等价于查找该字符串旋转后的结果。同样的对于fi*mo*er类似的查询，我们通过不同的旋转得到不同的词项，然后找到其倒排表。详细处理如下：
轮排索引的缺点很显然：词典集合太大。
（3）k-gram解决方案
举个例子，对于一个单词castle，它的3-gram包括：$ca、cas、ast、stl和tl$。（在开始和结尾处添加$）。
在k-gram中，其词典由词汇表中所有单词的k-gram形式组成。最后与操作一下，注意下图引入了一个后过滤的过程（剔除一些不满足条件的单词吧）。
拼写校正问题
用户可能存在错误输入，这时，我们需要对用户的输入给出一些校正的提示方案。具体方法如下：
（1）基于编辑距离的校正
在字典中找出编辑距离最近的单词，当然如果单词本身输入是对的，那肯定是单词本身被找出来。这里注意编辑距离的求法，采用动态规划：http://blog.csdn.net/lsjseu/article/details/12193027。从键盘的设置来考虑，我们还可以考虑给一些字母加些权重。例如：在键盘上把“a”敲成“s”的可能性大于，把“a”敲成“u”，因为a和s靠得很近，这样我们就可以在求字符串编辑距离的时候，给定不同的权重。
同时，求字符串是个庞大的工程，因为我们要同字典的每个单词进行求编辑距离。这是我们就可以通过给定一些额外的条件来减少匹配单词的个数，比如我们假设首字母肯定要对。
（2）k-gram的校正方法
我们可以利用k-gram索引来匹配那些单词具有公共的k-gram。例如，“bo”，则abord和border两个单词都含有这个2-gram，所以我们同时返回这两个。
那么到底谁是对的，我们可以通过提取各种用户的搜索日志，来确定谁输入的次数多，我们最终返回给用户频率多的。
（3）上下文敏感的拼写技术
对于查询“flew form Beijing”，这个查询，“from”被写成“from”，此时我们如果就单个词的来矫正的话，没法弄，因为form本身也是对的。所以此时我们要通过单词的前后单词，然后结合用户的搜索日志给出提示结果。
（4）基于发音技术的校正
