现在的位置: 首页 > 综合 > 正文

《Introduction to Information Retrieval》读书笔记(二)

2018年04月04日 ⁄ 综合 ⁄ 共 1285字 ⁄ 字号 评论关闭

词典

1.在反文档索引的过程中,词语的查找操作用到了一种经典的数据结构:词典(dictionary)。词典的实现有两种普遍的实现方法:哈希(hash)与查找树。

2.哈希已经被用在了一些搜索引擎的词典查找中:每个词语(Key)将会被散列到一个足够大的整数空间去。这样散列冲突的可能性极小;如果发生冲突,也可通过某种方法修复。在查询阶段,只需将查询词散列到该整数空间,找到对应的后缀即可。哈希方法的缺点是:如果查找词有微小的变动,它们也将会被散列到不同的整数,如resume,rèsume,另外,用哈希查询不能一次找到前缀为automat的所有词。当词库不断扩大时,一个满足现有需求的设计良好的哈希函数不一定能够满足几年后的需求。

3.查找树克服了哈希方法的诸多缺点,最广为人知的查找树是二叉查找树(Binary Search Tree),二叉树中每个中间节点有两个孩子,从根节点开始查找。由于二叉树在插入或删除某个词时需要恢复原来的性质,因而引入了B树进行改进。适用查找树的前提条件是文档中适用的字符必须有某种预定义的顺序,这和哈希方法不同,例如英文的26字母具有顺序;汉语本身并没有特定的顺序,但是现在它的字符集也采用了一套标准的顺序系统以满足在这方面的应用。

4.通配符查询(wildcard query)是查找树的一大优势:例如要查找mon*,我们沿着查找树往下,随着符号m,o,n,可以得到一个均带有前缀mon的词语集w,再在反文档索引中查找w中的每个词语,即做到了通配符查询。*mon:形如这样的前置通配符查询只需要再建立一个反向B树:在这个树中每个从根到叶子的道路对应词典中的一个反向书写的单词:例如lemon在反向B树种是n-o-m-e-l。形如s*dney的查询只需用到一半的B树和反向B树,对前置和后置通配符的查询结构求交即可。

5.搜索引擎进行拼写检查的方法有两种:edit distance 和 K-gram overlap.拼写检查的原则有两个:在众多可选的正确拼写中,选最接近的那个;在有相同接近的单词的前提下,选最常用的那个。一个比较好的想法是选择接近其它人输入最多的那个。

6.编辑距离:给定两个字符串S1和S2,它们间的edit distace指将S1装换为S2所需的最小编辑操作次数。编辑操作指:插入一个字符、删除一个字符、替换一个字符。算法用到了动态规划的思想。

7.将k-gram indexes用在拼写检查上:k-gram index:一个k-gram指一个含有k个字符的序列,k-gram index值将一个k-gram指向所有所有含有该k-gram的单词形成的后缀。用在拼写检查时,首先将原查询词(可以是词组)分成n个k-gram,然后对每个k-gram在k-gram index中查找,得到一个单词集M,对M中的每个单词,依次计算其Jaccaro coefficient,长度为l的单词含有的k-gram的个数为l-k+1;若其与查询词中的n个k-gram有m个相同,则Jaccaro系数为:m/(n+l-k+1-m),当该系数足够大时,将其作为一个备用的正确词。

抱歉!评论已关闭.