信息检索——词典及容错式检索
词典及容错式检索
目录
词典的数据结构中存储了 词项词汇表，文档频率，每个倒排记录表的指针....
本章内容：
- 词典搜索的数据结构（哈希表和树）
- 通配符查询（轮排索引/k-gram索引）
- 拼写校正（编辑距离/k-gram重合度——Jaccard系数/上下文敏感/基于发音）
词典搜索的数据结构
词典的数据结构中存储了 词项词汇表，文档频率，每个倒排记录表的指针....
词项词汇表：数据
词典dictionary：储存词项词汇表的数据结构
两个问题：
- 如何在在查询时间内查询词项？
- 应该使用哪种数据结构定位？
两种选择：哈希表和树
键key:词汇表中的每个词项
哈希表
词项中的每个词项都被哈希函数映射成一个整数
优点：比树更快的查找时间
缺点：
- 如果出现一个新词，需要把所有词重新映射，成本太高
- 如果你的系统：词永远不会变化 或者很少变化，可以使用哈希表
- 无法对输错的词进行纠错
- 无法处理前缀搜索
树
优点：
- 纠错
- 前缀搜索
- 可以处理词项不断增加
缺点：慢
如果是使用树，可以纠错；哈希表无法纠错，它是固定的
二叉搜索树
- 需要平衡
- 每个结点最多两个孩子
- 出现新词，重新平衡，成本高
B树
- 子结点个数是一个区间范围
- 新词过来，不一定要重新平衡，降低成本
B+树
广泛应用于文件系统和数据库
数据结构
词典存储方式dictionary：哈希表 树
倒排表posting：链表
通配符查询*
适用于
- 对查询拼写不太确定（Sydney/Sidney 所以S*dney）
- 查询词项可能有不同拼写版本，并且要把包含这些版本的文档都找出来（color和colour）
- 查找某个词项的所有变形，这些变形可能还做了词干还原（judicial/judiciary 所以judicia*）
- 不确定外来词或者短语的正确拼写形式（Universit*Stuttgart）
首通配符查询：
Mon* :查找词项以mon开头的所有文档
容易
词项范围在mon ≤ w < moo
尾通配符查询：
*mon :查找词项以mon结尾
困难
引入反向树，范围在nom ≤ w < non.
通配符在中间：
infor*ation
通配符在中间，正向+反向B树可以解决，开销最大
轮排索引（一般的通配符查询）
- 轮排索引的问题: ≈ 四倍的原始词汇表大小
如何使用轮排索引来处理通配符查询？
用户输入关键词hello，先在最后加上hello$，查找
1.无通配符，可以在轮排词表上查找。
2.通配符在最后，hel*，也可以
3.通配符在前面，*llo，怎么找？多一个预处理步骤。 *llo
(1)先加个结束符：*llo$
(2)旋转直到*号在最后,llo$*，去倒排索引中找。
4.通配符在中间，he*o，怎么找？
(1)先加个结束符：he*o$
(2)把*号转到最后，
e*o$h
*o$he
o$he*
(3)在倒排索引中找，也可以解决。
支持通配符查询的K-gram索引（双联词索引）
$ 标识词项的开始或结束
原始的倒排索引：
among 1 6 8 9 11 13
mace 1 5 6 7 8 9
monday 1 2 3 9 10 13 15
n-gram方法 ：
原始的倒排索引不变，本来是什么样就是什么 样。
只是另外加了一张双连词索引
原始的倒排索引：
among 1 6 8 9 11 13
mace 1 5 6 7 8 9
monday 1 2 3 9 10 13 15
假设用户输入关键词：mon
(1)按2-gram拆：$m mo on，在双连词索引中，求交集，得到monday....
(2)拿着monday....，在原始的倒排索引中找文档。
先查找双连词索引：
1.$m mo on
2.moon：符合$m mo on的交集的要求，但是不符合mon*的要求。
3.还是按刚才的方法在双连词索引中得到一些符合$m mo on的词项：monday、moon...
4.进行一个过滤，把以上查找出来的词项依次判断是否是mon*，如果不是，去掉。
5.过滤后的词项再去查找倒排索引。
轮排索引与K-gram的区别
- 轮排：占的存储空间太大，不需要过淲。
- 2-gram：比较节省空间，不是扩大倒排索引，而是只加一张表。但是需要过滤。
处理通配符查询
举例：
先找出所有的pyth开头的词，n个；再找出所有的prog开头的词，m个
要找n*m个词项。
通配符：windows,linux。找某某文件。需要用通配符查询。小型IR系统
大型搜索引擎：数据量太多，没有这个功能。Google没有
拼写校正
- 用户输入关键词输错了，需要校正
- 用户发表内容（文档）中的错误单词
两条原则
- 对于一个拼写错误的查询，在其可能的正确拼写中，选择距离“最近”的那一个
- 当两个拼写查询的邻近都相近时，选择更常见的一个
两种方法
1.词项独立：fly from。输入多关键词，一个个判断是否写错。
2.上下文敏感：根据整个句子（上下文）来推断，是否用错了词。
flew from
form：真实存在 ，只是在这个句子中用错了。
1.词项独立：缺点，不考虑上下文 ，直接判断这个词是否是一个真实存在的词。
I flew form Heathrow to Narita。
如果是词项独立，是查不出来的，无法纠错的。如果上述句子，以词项独立来判断，认为是正确。
2.上下文敏感：根据整个句子推断词是否用错。
I flew form Heathrow to Narita。
用上下文敏感，是可以找出是错误的句子。
文档校正
OCR：从图片中识别出文字。
有些图片，打印版，打印机墨的问题，rn墨太多，连在一起，识别出来后变成了m。
文档校正可以应用 在OCR识别上，发现识别结果的错误，并纠正。
- 假定1：有一份正确单词列表
- 假定2：有方法计算拼错单词和正确单词的距离
- 简单的拼写校正算法：返回与拼错的单词距离最小的“正确”单词
- 例：informaton——information
- 对于正确单词列表，可以使用文档集中所有单词的词汇表
词项独立校正
方法：1.编辑距离方法
2．k-gram重合度方法
编辑距离
- 给定字符串 S1 和 S2, 编辑距离是将S1转换成S2的最小编辑操作次数
- 插入、删除、替换
例如：
- dof 与 dog 的编辑距离是1
- cat 与 act 的编辑距离是 2
- cat 与 dog 的编辑距离是3.
求snow和Oslo的编辑距离
求法：
- 左上：判断两个字母是否相同：相同：复制左上的值；不相同：左上加1
- 右上：上方元素+1
- 左下：左边元素+1
- 右下：取最小值
大格子，外面的使用的都是大格子的右下的元素。
右下元素求完后，大格子中的左上/右上/左下是没有用的。
算法中为了节省空间，只存储了大格子中的右下元素。
算法：
代码解释：
编辑距离，参数：s1和s2分别是两个词
1~4初始化二维数组
1~2初始化第1列，填了下标为0的列
3~4初始化第1行，填了下标为0的行
5~6：二重循环，行列下标从1开始。
7判断两个字母是否相同
8：如果相同，m[i-1,j-1]，m[i-1,j]+1，m[i,j-1]+1取最小值
9：如果不相同，m[i-1,j-1]+1，m[i-1,j]+1，m[i,j-1]+1取最小值
10：返回最终的结果
m[i,j]
左上：m[i-1,j-1]
右上：m[i-1,j]+1
左下：m[i,j-1]+1
求小值——右下
|s1|：s1的长度，
|s2|：s2的长度
m[4,4]写为m[|s1|,|s2|]
带权重的编辑距离
更有可能写错的，应该给予更高的权重
错误的可能性高的给予更高的权重。
更有可能写错？
用户将m打成n，或者将n打成m的可能性很大，键盘上这两个字符相邻。
用户将m打成q的可能性较小，
使用编辑距离：
用户输入查询的关键字，每次输入关键字都要计算 编辑距离？
用户输入关键字，搜索引擎先查询，如果结果数量比较多，基本上表示用户输入是正确的，不需要计算编辑距离。
不应该每次都 计算 编辑距离，如果每次都计算编辑距离，导致响应变慢了。
如果搜索引擎查询出来的结果很 少，用户写错了单 词，此时就需要计算 一下编辑距离。
k-gram重合度方法
hashtable
hasgtable，应该与整个词汇表计算编辑距离。
假设词汇表有100万个词，
hasgtable与100万个词都计算编辑距离？花费非常 多的时间 。
做法：先找到一些有可能的词1万个，将hasgtable与1万个词计算 编辑距离。
1万个词如何找出来？——n-gram，应用在很多场景下，也可以用于拼写校正。
2-gram：拆词
3-gram
november
如果是2-gram：no ov ve....er
计算 有多少重叠的。重叠的越多，说明两个词越相似
交集个数是多少？交集个数越多，说明两个词越相似。。
词与词的相似使用n-gram+jaccord系数
n-gram直接求交集个数。词有长有短，不能单纯的以交集个数来判断。
||：个数
Jaccard系数
- 一种常用的重叠方法
- 设 X 和 Y 为两个集合; Jaccard系数的计算公式
- X、Y分别是查询q,词汇表词项中的n-gram集合。
- 结果为1表示X与Y含有相同元素;结果为0表示他们是不相交的
- X 和 Y 不需要相同大小
-
在0和1之间取一个数值
- 设定一个界限来决定是否匹配
E.g., 如果Jaccard系数 > 0.8, 表示匹配
Jaccard：交集个数/并集个数，
Jaccard+n-gram可以用于判断词与词（其他地方）的相似度。
3/9=1/3
3-gram
求Jaccard和hello的相似度：Jaccard系数，如果两个词完全不同（字母都没有一样的），交集个数为0，Jaccard系数为0。
求hello和hello的相似度：
3-gram
hel,ell,llo
hel,ell,llo
Jaccard系数：3/3=1
如果两个词完全不同，Jaccard系数为0
如果两个词一模一样，Jaccard系数为1
范围：0~1，来表示两个词的相似度。
词的相似度，0.8
不可能将错误拼写的词与全词汇表（100万）都计算 编辑距离——太慢
先使用Jaccard+n-gram的方法 ，先找出一个子集（比如，1万个词），将错误拼写的词与这个子集（1万）个再去求编辑距离。
子集怎么找出来的：
lord：本身只有3个2-gram
要求找出一个子集，这个子集必须和lord匹配了两个2-gram
alone与lord，只重叠了一个2-gram，lo
border与lord，重叠了2个-gram，or/rd
border比alone与lord更相似
1.假设词汇表只有7个词，根据条件，3个2-gram匹配两个，筛选出了border/lord ，7个中只找了了2个最像的出来。
2.相同的方法 ，从100万个词汇中找出一个子集（比如1万）
3.先在词汇表中找出一些比较 相似 的词再来计算 编辑距离。
1.用户给定错误查询
2.词汇表中词太多，不可能全部与错误的单词计算 编辑距离——太慢
3.采用JAccard+n-gram的方法，先从词汇表中找出一个与错误单词比较像的子集
4.对于子集中的每个词，再来计算 编辑距离，最找编辑距离最小的，提示给用户。
拼写校正两种方法：
1.上下文无关：编辑距离只能找出上下文无关的错误的单词。可以判断出明确写错的单词。hasgtable，词典中是不存在 ，可以判断出来的。
2.上下文敏感：更智能，更难处理，能判断出来句子中有没有 使用错误的单词。
form：这是一个存在的单词，词典中有form这个词（表格，形式....）
搜索引擎：发现该短语搜索结果数太少，表示用户用错了词，输错了词。
flew form Heathrow 关键字
其中的form是使用错误。
程序只知道flew form Heathrow有问题，但不知道是其中哪一个词。
只好，把3个位置 的可能出错的位置 ，都换 成其他的比较 相似 的词。挨个再去查询，根据查询结果的多少，如果查询结果多，表明这个写法才是正确 。
搜索引擎现在都有拼写校正，返回正确的查询结果，并提示用户。
搜索出来的结果很 少，基本上很 有可能错误的词，或者是用错了词。
基于发音的校正技术
英文发音的算法——SQL Server中使用了这个算法。
Herman
H0rm0n
H06505
H655
Hermann
H06505
H655
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
我们能处理哪种查询？
-
- 基于跳表的位置倒排索引
- 通配符查询
- 拼写校正
- 发音校正
PPT3√ note10.7×