检索的改进技术 哈工大信息检索研究室 2007.

Presentation on theme: "检索的改进技术 哈工大信息检索研究室 2007."— Presentation transcript:

1 检索的改进技术 哈工大信息检索研究室 2007

2 这一部分将讲述 文本处理的方法 基于倒排索引和基于签名档的检索 问题的扩展和相关反馈方法

3 文本处理 ——term处理

4 信息检索系统的体系结构 用户界面 文本 用户 需求 文本处理 用户 数据库 提问处理 建索引 反馈 管理 搜索 提问 索引 文本 数据库
逻辑视图 用户 反馈 提问处理 建索引 数据库 管理 倒排文档 搜索 提问 索引 文本 数据库 排序后 的文档 检出的文档 排序

5 文本表示 文本可以表示为 简单的表示 (如：单个词项) 效果好 一个字符串 词的集合 语言单元 (例如：名词、短语)
以往的一些研究显示：基于短语的索引不如基于词的索引 短语可能太特殊了

6 文本处理主要方法 分词（中文），断词（英文） 异文合并 繁简转换 形态还原 提取词干 其他

7 断词 句点是英文中引起断词歧义最多的符号，也是最难处理的一个符号，如：
The experiments led by Dr. Alan achieved a precision of 90.7%. 解决方案：规则+词表 撇号主要用于构成英文的动词缩写式和名词所有格，如：I'm，won't，children's，parents’ 解决方案：整体标注（Brown语料），分开（Penn Treebank） 连字符可以用来构成合成词，用连字符构成的合成词有两类： 一类已经固定成词，如： ，co-operate； 另一类是根据特定用法或语言环境生成的词，如four-year， ，All-In-One 解决方案：主要通过词表解决

8 分词 中文检索系统主要有两种检索方案： 基于字的检索按单字建立索引，需要在检索时进行逻辑运算； 基于词的检索按词建立索引，检索时直接命中。
基于词的方法具有检索速度快、准确率高的优点，目前的中文检索系统多数都支持基于词的检索。 最大匹配法的分词实现很简单，并且可以满足一些对分词准确率要求不高的检索系统，该方法在早期的分词系统中被广泛使用

9 异文合并 英文的异文合并主要体现在提取词干及形态还原 中文的异文合并主要体现在繁简转化

10 特点 克服词形的变化，把所有同根词转变为单一形式 优点: 缺点：
RECOGNIZE, RECOGNISE, RECOGNIZED, RECOGNIZATION 优点: 减少不同term的数量 识别相似的词 改进了检索性能，但不采用语言分析的方法 缺点： 正确率显然达不到100% 不正确的stemming算法可能改变词的含义 需要避免过分的截断 MEDICAL和MEDIA被识别为MED*，并被认为是意义相近的，这就错了 10

11 英文异文合并(Conflation)方法
异文合并方法 自动 (Stemmers) 手工 后继变化数 Successor Variety 删除词缀 查表 N-gram 最长匹配 简单删除

12 异文合并方法之一：查表 创建一个term和stem的对应表 表可以被索引起来，以便加快查找速度 创建这样的表很困难 存储空间的开销较大
engineering engineer engineered engineer engineer engineer

13 异文合并方法之二：词缀删除 词缀删除算法将term的前缀和/或后缀删除，留下词干
大多数算法删除后缀，例如：-SES, -ATION, -ING等等 最长匹配 从词中删除最长匹配的后缀: computability --> comput singing --> sing 避免: ability ->NULL, sing->s 迭代式最长匹配 重复最长匹配的过程： WILLINGNESS --> 删除NESS --> 删除ING

14 上下文有关和上下文无关 上下文无关 上下文有关 需要控制许多例外规则 根据后缀表删除后缀(或基于规则集) 考虑词的其它性质，例如：
happily  happi  happy 定义一个上下文敏感的转换规则：如果一个词根以i结尾，i前面是p，那么将i转换为y 需要控制许多例外规则 从TABLE中删除-ABLE不行，从GAS中删除-S也不行 有时需要删除“双写字母” FORGETTING  FORGET

15 Porter算法 (1980) 每一步有一组上下文无关或有关的规则用来删除后缀，或者将其转换为其它形式 问题：
上下文无关规则：sses  ss, ies  i, s  NULL 上下文有关规则： (*v*) : ed  NULL, ing  NULL (*v*)的含义是：词根必须包含一个元音 plastered  plaster bled  bled 删除词缀后，剩下的词干里没有元音 问题： 需要大量的语言知识来定义规则 由于人类语言的复杂性，规则无法覆盖全部情况 规则依赖于语言

16 异文合并方法之三：后继变化数 基于对文本集合的统计分析 后继变化数的定义： 考虑英文词典
给定一个足够大的语料库, 可以通过统计的方法获得词干 这种方法是自动的，和语言关联性不大的 后继变化数的定义： 语料库中跟在某个字符串后的不同字符的数 考虑英文词典 pr? -> 后继变化数是多少？ pro? -> ? pr 和 pro 谁更像一个词根? 直觉：如果一个字符串的后继变化数值很低，则可能是一个词根

17 后继变化数的例子 Corpus ABLE, APE BEATABLE FIXABLE READ READABLE READING READS
RED ROPE, RIPE

18 利用后继变化数信息切分词 尖峰和高地 切出来的词必须完整 通过后继变化数的cut off值识别边界 当后继变化数>=阈值时，进行切分
考虑阈值 = 2 R|E|AD|ABLE 尖峰和高地 在后继变化数比前后都大，出现尖峰的位置切开 READ|ABLE 切出来的词必须完整 如：READ

19 繁简转换 一种语言，两种写法 战后中国进行了语言文字改革，其结果是数以千计的汉字被大大地简化了(总表1986)。以简化形式书写的中文称作简体中文(SC) 台湾．香港以及大多数海外华人仍沿用传统的复杂形式，称作繁体中文(TC)

20 汉字简繁转换 从简体中文到繁体中文（或繁体中文到简体中文）的自动转换过程，被称作C2C（汉字简繁）转换，这一转换可以按照下面简要描述的三个递增的级别来实现 码对转换：转换的失败率很高 字对转换：被转化的是有意义的语言单位，特别是多字词 词对转换：这种汉字简繁转换不是按照拼写，而是按照语义进行的。例如，简体中的“信息”转换成繁体语义对应词时，就变成了“资讯”

21 其它term处理 词性标注 词义消歧 停用词表 采用HMM的算法 参加下页词性标记表 采用贝叶斯等算法 《同义词词林》，参见后文
没有固定的标准 英文：the, a, and, …… 中文：的，了，和， ……

22 词性标注表 普通名词：n 时间名词：nt 方位名词：nd 处所名词：nl 人名：nh 地名：ns 团体、机构、组织的专名：ni
其它专名：nz 动词：v 形容词：a 区别词：b 副词：d 数词：m 量词：q 代词；r 介词：p 连词：c 叹词：e 拟声词：o 助词：u 前接成分：h 后接成分：k 习用语：i 简称：j 语素字：g 非语素字：x 标点：wp 字符串：ws

23 文本处理 ——文本的特性

24 文本词频分布 大规模文档集，不同词的频率是怎样分布的？ 极少的词是非常常见的 大多数词很少出现
英文中最常用的两个词是： “the”, “of”，他们的出现频率占全部英文词的10% 大多数词很少出现 语料库中的一半词只出现一次 称为“heavy tailed”分布, 因为大多数的概率值都是 “tail”

25 文本的特点 有些词在文本中出现的频率非常高，而且对文本所携带的信息基本不产生影响
例如英文中的“a，the，of”，中文的“的，了，着”，字符串“http”、“.com”以及各种标点符号等，这样的词称为停用词(stop words)。 文本经过词法分析之后，停用词通常被过滤掉，不参加文件的索引。 在检索的时候，用户的查询中如果含有停用词，检索系统同样也将其过滤掉

26 样本词频数据(from B. Croft, UMass)

27 Zipf’s Law

28 Zipf(齐普夫)’s定律 Rank (r): 在按词频(f )降序排列的词表中所处的位置. Zipf (1949) “发现” :
如果rank为r的词的概率为pr，N 是所有词出现的次数:

29 Brown语料库验证Zipf定律 k = 100,000

30 Zipf定律对IR的影响 好消息: 坏消息: 停用词在文本中占的比重很大，排除停用词可以极大地节省索引文件的磁盘空间
有的检索系统中，这种空间的节省甚至能达到40%以上，目前的检索系统，基本都使用过滤停用词的策略 坏消息: 对大多数词来说，进行词汇之间的相关分析并不容易，因为它们出现的比较少

31 词表增长 随着语料库的增长，词表以什么样的速度相应地增长 这决定了随着语料库规模的增长，倒排文件需要怎样增长
由于专名的存在，词表实际上没有上限

32 Heaps’ Law V 是词表大小，n 是语料库的长度（词数） 典型的常数: K  10100
  0.40.6 (approx. square-root)

33 Heaps’ 定律

34 选择分辨力强的索引项 分辨力是一个词作为特征将它所在的文档 与其它文档区别开来的能力 按词频降序排列 无意义的 无意义的 高频词 低频词
有意义的分辨力最强 按词频降序排列

35 索引项的分辨力 好的索引项能够将文档尽可能地离散开 例如：在一个关于“计算机科学”的文档集合中 X 原始文档空间： 添加了不好的索引项：
添加了好的索引项： system, database 添加了不好的索引项： system, computer 原始文档空间： system

36 索引项分辨力举例 a就不是一个好的索引项，因为各个文档都包含a r可以使d1和d2 靠近，并使它们远离 d3和d4

37 索引项分辨力的计算 好的索引空间能够使文档集中各文档对之间的相似度的总和尽可能小 N个文档之间的平均相似度为：
假如Q 和 Qj 是加入term j之前和之后的平均相似度，这term j的分辨力为

38 索引项分辨力（图示） 加一个索引项就加了一维空间，这将使包含该索引项的文档和不包含该索引项的文档拉开距离 T1 T3 T2

39 文本质心 dvj 的计算开销太大 折中方案: 需要针对每个term，计算文档对的相似度 文档更新后，需要重新计算
找到文档空间的质心(centroid) C = (c1, c2, …, ct), Q是每个文档和质心之间的相似度 需要针对每个term，计算 N(N-1)/2 个文档对的相似度

40 索引与检索 ——倒排文档

41 信息检索系统的体系结构 用户界面 文本 用户 需求 文本处理 用户 数据库 提问处理 建索引 反馈 管理 搜索 提问 索引 文本 数据库
逻辑视图 用户 反馈 提问处理 建索引 数据库 管理 倒排文档 搜索 提问 索引 文本 数据库 排序后 的文档 检出的文档 排序

42 建立索引的目的 对文档或文档集合建立索引，以加快检索速度 倒排文档（或倒排索引）是一种最常用的索引机制
倒排文档的索引对象是文档或文档集合中的单词等。例如，有些书往往在最后提供的索引（单词—页码列表对），就可以看成是一种倒排索引

43 在关系数据库上建索引 这种想法也被应用于数据库技术中，即对数据库中需要经常进行检索的域建立索引结构，进行快速的查询。
索引结构: hashing, B+-tree 可以索引全部记录，在全部记录上进行搜索 精确地快速地查找 地址 姓名 姓名索引 查询式: 姓名 = “张三” 张三 哈尔滨工业大学

44 对文档进行索引 索引结构: hashing, B+-trees, tries. 可以进行部分匹配: ’%comput% ’
文档索引 D1 D2 D3 computer D1, 23, 97, 104 D3, 43 graphics D2, 5 D3, 44 “computer”在D1中出现的位置 索引结构: hashing, B+-trees, tries. 可以进行部分匹配: ’%comput% ’ 可以进行短语搜索:查找包含“computer graphics”的文档

45 倒排文档组成 倒排文档一般由两部分组成：词汇表（vocabulary）和记录表（posting list）
词汇表是文本或文本集合中所包含的所有不同单词的集合。 对于词汇表中的每一个单词，其在文本中出现的位置或者其出现的文本编号构成一个列表，所有这些列表的集合就称为记录表

46 一般的倒排索引 索引文件可以用任何文件结构来实现 索引文件中的词项是文档集合中的词表 附加信息 例如：词位置，出现次数
architecture computer database retrieval ... D1, a1 D1, a2 D1, a3 索引项/ 词表 索引/ 索引文件/ 索引数据库 Postings 列表 Q = term1, term2, term3, ... 附加信息 例如：词位置，出现次数 索引文件可以用任何文件结构来实现 索引文件中的词项是文档集合中的词表

47 例子 文本 词汇表 Posting list 倒排文件 技术 教材 检索 信息 … 15, … 8, … 6, 12, … 5, … … 1
3 4 5 6 7 8 9 10 11 12 13 14 15 16 这 是 一本 关于 信息 检索 的 教材 。 介绍 了 基本 技术 … 词汇表 Posting list 倒排文件 技术 教材 检索 信息 … 15, … 8, … 6, 12, … 5, … …

48 以文本为记录表 记录表既可以存储文本中单词的编号位置，也可以指向单词首字母的字符位置，还可以是其所在的文本编号，下图是一个以文本为记录表的情况

49 距离约束：需要位置信息为记录表 常常需要知道邻接条件，例如： 需求扩展: “database” 后面紧跟着“systems”
“database”和“architecture”在同一个句子里 需求扩展: 倒排索引中保存着关键词在文档中的位置，文档的组成单元(标题, 小标题, 句子分割标记等) 检索算法和位置信息相关联，并需检查文档的组成单元

50 以位置信息为记录表 保存倒排表中的位置信息: 文档D350 第8句 保存句子位置: D345, 25 D348, 37 D350, 8
database file systems ... D345, 25 D348, 37 D350, 8 D123, 5 D128, 25 database file systems ... D345, 2,3,5 D348, 37,5,9 D350, 8,12,1 D123, 5,4,3 D128, 25,1,12 D345, 2,3,6 文档D350 第8段，第12句 第1个词 保存段落、句子和词的位置：

51 以权重信息为记录表 可保存出现频率，以便支持基于统计的检索:
database file systems ... D345, 10 D348, 20 D350, 1 D123, 82 D128, 8 D345, 12 在D345中 “systems” 比 “database” 重要1.2倍 Postings中的第二个单元可以是该term的权重 (例如, 可以被归一化在0和1之间) ，或者是该term的出现频率

52 同义词扩展词汇表 同义词对于提高召回率很有意义 同义词可以通过指针指向同一个postings list. ... D345, 2,3,5
database databases systems D345, 2,3,5 D348, 37,5,9 D350, 8,12,1 D123, 5,4,3 D128, 25,1,12 D345, 2,3,6 dataset

53 建立索引的过程 识别文档中的词 删除停用词(stop words) 提取词干(stemming) 用索引项的标号代替词干(stems)
统计词干的数量(tf) (可选) 对低频词项使用同义词词典(thesaurus) (可选) 对高频词项构成短语 计算所有单个词项、短语和语义类的权重

54 建立索引的过程 – 举例 输入文本 删除stopwords Stemming 转换为索引编号 计算tf 计算词项的权值 (依赖于使用的模型)
The analysis of 25 indexing algorithms has not produced consistent retrieval performance. The best indexing technique for retrieving documents is not known 删除stopwords analysis indexing algorithms produced consistent retrieval performance best indexing technique retrieving documents known Stemming analysis index algorithm produc consistent retriev perform best index technique retriev document known 转换为索引编号 计算tf 计算词项的权值 (依赖于使用的模型)

55 检索过程 给定query 对query进行stemming，算法与对文档的处理相同 用索引编号代替stems
计算所有query terms的权重 形成query向量（对VSM模型而言） 计算query向量和文档向量之间的相似度 返回排序后的文档集合

56 倒排索引上的布尔检索 一个布尔检索包含n个用布尔操作连接的词项 ，例如：“computer AND news AND NOT newsgroup” 可以用括号来调整逻辑运算次序 每个term从倒排索引中返回一个postings list 如果term不在任何文档中出现，则postings list为空 检索结果根据逻辑关系相结合： AND: 集合做交运算 OR: 集合做并运算 NOT: 集合做差运算 A B A and B

57 倒排索引上的布尔检索 标准的优化技术应用： 显然是：“病毒”和“蠕虫”
从最短的posting list开始做“与”操作，保证中间结果越小越好 “网络” AND “病毒” AND “蠕虫” 从哪个词项开始做交运算呢？ 显然是：“病毒”和“蠕虫”

58 倒排索引的优点 快速索引 (长query需要更多时间) 灵活性: 不同类型的信息都可以存储在postings list中
如果存储了足够多的信息，则可以支持复杂的检索操作 例如：如果记录了词在文档中的准确位置，就可以支持短语检索，或模糊检索

59 倒排索引的缺点 很大的存储开销 更新、插入和删除都需要很高的维护开销，倒排索引相对静态的环境(很少插入和更新)中使用比较好
50% - 150% - 300% 更新、插入和删除都需要很高的维护开销，倒排索引相对静态的环境(很少插入和更新)中使用比较好 处理开销随着布尔操作的增加而增长 由于postings越来越多(例如引入同义词)，导致索引检索的代价越来越大，需要对位置进行很多处理(例如短语匹配)

60 倒排文档中研究的问题 倒排文档的压缩 倒排文档的删除 倒排文档的插入

61 倒排文档的压缩 索引和postings的压缩问题 分配给文档ID和词位置的字节数 16 bits不够，32 bits又浪费空间
类似视频压缩中仅记录本帧和上一帧的差异 database D345, 25, 34, 98, 120 D348, 37, 71, 85 345, 25, 9, 64, 22 3, 37, 34, 14 Word positions

62 变长整数描述变化 对于有些常用词，例如“的”，文本编号的相对变化多数是1，如果仍然使用16位编码，显然浪费了太多的空间
而另外一方面，根据Zipf定律，对于某些词，有可能仅存在于少数的文本之中，而这些文本编号的相对变化也很有可能超过65,536，即216。这时，如果仍然使用16位整数表示，就会溢出 一般使用变长整数来表示这种相对变化。其基本原理就是使用较少的位数表示较小的整数，而较大的整数，则需要使用较多的位数表示

63 压缩技术带来的负面影响 在搜索时必须花些时间对压缩的数据进行解码
在维护时，特别是进行删除操作时，由于某些文档被删除，所以不得不对剩余的文档编号进行重新编码 但是压缩技术仍然是利大于弊的

64 倒排索引的插入开销 一个文档插入时最坏的情况: 对于posting表中的每个更新操作:
当文档包含n个词，并且每个词都不重复，插入时需要更新n个posting表 对于posting表中的每个更新操作: 如果postings表没有排序，新的posting项可以被追加到表的末端，更新操作很快，但是检索无序的posting表很慢 如果posting表示排序了的，那么插入一个新的posting项需要很大的开销 新文档: D349 包含 “database” D349, 10 database D345, 25 D348, 37 D350, 8 database D345, 25 D348, 37 D349, 10 D350, 8

65 倒排索引的插入开销 插入的开销依赖于更新的频度，对索引的即时性的要求，以及系统的工作负荷能力
对于图书馆应用来说，插入操作不是问题，对新闻和互联网方面的应用而言，就是一个问题 当我们设计一个新的插入操作时，我们必须考虑: 主存和临时存储器中可利用的空间大小 索引的批量和在线更新 快速插入的方法 批更新：为新的更新和插入生成一个空索引，然后把它融合到主索引表中

66 倒排文档更新：删除和插入 倒排文档更新就是一个删除操作，后面跟着一个插入操作
为了支持删除操作，需要维护一个前向索引(forward index)来记录文档中包含的词 Doc ID word1, word2, …. 找到将要被删除的文档ID 从前向索引中获得该文档中包含的词 根据该文档中的词定位倒排索引中的posting项，并在这些posting项中将该文档ID删除 删除开销很大; 为了降低删除开销，可以： 维护一个表，表中存放要删除的文档ID号（先不在倒排表上实施） 在检索过程中，忽略那些被登记在表中的文档ID 周期性地对倒排文件进行更新

67 通过排序进行批插入 收集所有将被插入索引中的新文档 从每个文档中提取term，并准备一个批倒排文件:
Doc id Term paper report novel … … 1 … human 2 human novel paper report … … 2 1 … 排序 human 2,1 novel 1,2 paper 1,1 report 合并 在此记录频率，词的位置也可以记录 批倒排文件被插入到主倒排文件中 – 批插入为什么会快呢？因为一个词可能出现在多个文档中！

68 在批插入中提高速度 从倒排文件中检索出一个postings表，插入若干posting项，该表再放回倒排文件中
批倒排文件相当小，因此创建它并不难 批不能太小，否则很少会出现多个文件包含一个词的情况 批不能太大，否则批的生成本身开销也很大 采用批更新将使对新文档的检索被延迟 批更新实时性差 到目前为止，我们假定postings lists被存放在单一的顺序文件中，从更新的角度看，这可能不是一个好的方法

69 快速倒排算法 大量文档的倒排操作 需要快速倒排算法提高速度 批的大小 批的大小受到主存的限制，因为需要对倒排文件进行排序

70 快速倒排算法 最终的倒排文件 1 2 3 4 5 1, 3, 4 2, 4 11 5, 11 7 12, 14 12 12, 13 13, 14 分裂 加载 file 1 加载 file 2 加载 file 3 1 2 3 4 2, 4 1, 2, 5 2, 3 插入 Doc id Word IDs 1 2 3 4 5 3, 5, 12, 14 1, 3, 4, 11, 12 2, 4, 5, 12, 13 1, 5, 11, 12, 14 3, 7, 13, 14 以前的方法需要对23个项进行排序 5 7 11 1, 3, 4 2, 4 插入 12 13 14 1, 2, 3, 4 3, 5 1, 4, 5 插入 分裂为三个相同大小的文件 词ID总是被追加到后边 每一部分有已知的大小，可以预先分配存储空间

71 后缀数组

72 后缀数组 在倒排文档中，文本被看作是由单词组成的序列
在某些应用中，如基因数据库，不存在词的概念。如果使用基于词的倒排文档进行索引，很可能造成漏检 后缀数组 ：可以将文本看作是一个长的字符串，文本中的每个位置都被认为是文本的一个后缀，即一个从当前文本位置到文本末尾的字符串。 索引的位置可以是每个字符的位置、单词的位置或者汉字的位置等。

73 后缀数组的构造 原始文本，按字的顺序位置索引 文本中的部分后缀，按位置索引 相同的部分后缀，按字典序索引 这是… 是一… 信息… 检索…
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 … 这 是 一 本 关 于 信 息 检 索 的 教 材 。 介 绍 了 基 技 术 原始文本，按字的顺序位置索引 文本中的部分后缀，按位置索引 相同的部分后缀，按字典序索引 2 12 16 22 34 44 … 这是… 是一… 信息… 检索… 教材… 技术… 44 16 34 22 2 12 … 技术… 检索… 教材… 是一… 信息… 这是…

74 后缀数组的使用 在使用后缀数组进行检索的时候，将每个查询同样截取前n个字节，并于索引中进行查找 如果没有找到，则表明不包含所需查询
如果查找成功，则需要在相应的文本位置上，进行进一步的字符串比较，以确定文本中是否包含查询

75 例子: 查找“信息检索” 如果输入的查询未“信息过滤”，则原文中的12号位置不能找到“信息过滤”字符串，则查找失败
首先截取前4个字节“信息” 在后缀数组中查找到了位置12 在原文中的12号位置，找到了“信息检索”字符串，则查找成功 如果输入的查询未“信息过滤”，则原文中的12号位置不能找到“信息过滤”字符串，则查找失败 更一般的例子，如果输入的查询为“数据库”，在索引结构中不能找到“数据”，则查找直接失败返回

76 后缀数组的分析 对于需要大数据量的检索问题，后缀数组并不适用 因为构造出的后缀数组需要占用大量的空间，通常是原文本的1.7倍
和倒排文档相比，后缀数组里面储存了较多的重复信息 后缀数组的大部分功能可以通过倒排文档来实现，例如可以倒排索引文本中的二字串或者三字串，从而提高召回率

77 索引与检索 ——签名（Signature）文件
77

78 使用签名 用Karp-Rabin方法进行模式匹配 abcdefgh = ? cde 想法：比较字符串的压缩表示更有效
定长的Hash码 = ? cde 定长的Hash码 想法：比较字符串的压缩表示更有效 这种表示称为signatures 78

79 free text information retrieval
词的签名 一个词的签名是一个位向量 由F位组成，其中m位置1 free text information retrieval 文本串: Words hash(word signatures) free text information retrieval F = 12 m = 4

80 词的签名生成 词signature： Word word signature free 001 000 110 010
将 ‘free’ 转换为ASCII值，然后转换为32位整数i（每个字符8位） 例如：free = (hex) F位全置0 srandom(i) 初始化随机种子 j=0 while j < m do p = random(); 生成32位随机数 p = p mod F 映射到0和F-1之间 if (signature(p) == 0) { 确保m位置1 signature(p) = 1 j++ } done

81 free text information retrieval
块的签名生成 一个文档 (长串)被划分为固定大小的块 假设一个块包含两个连续的词 重叠(superimposed)编码(掩码) 块中所有词的签名按位进行“或”操作 Block 2 Block 1 free text information retrieval 文本串: block signatures Words Word signatures free text information retrieval

82 顺序的签名文件 最直接的方法就是按顺序存放签名文件 F bits 001 010 111 011 101 000 111 111 N 块
Signature文件 指针 文件 文档文件 N 块 F bits

83 用签名文件进行检索 给定一个q, 产生一个查询式的签名 Sq 匹配条件：Sq  Sb = Sq
如果一个块在q的signature取1的位置上也取1，则该块被返回 例如： query signature block block Block 1:  = Block 2:   块1匹配成功，块2匹配失败

84 误检（False Drop） 但是… 如果一个query 签名和一个 block 签名匹配成功, 就一定能够确保是一次正确的匹配吗?
假设query为free query signature block block block 1和 block 2均匹配成功，被返回，然而在block 2中并未出现free 此时，Block 2 称为误检（false drop）. false drops的原因 主要原因：不同词的签名重叠 次要原因：hash冲突(两个不同的词具有相同的signature), 如果F足够大，hash冲突的可能性很低 bits from ‘retrieval’ signature bits from ‘information’ signature

85 误检（False Drop）概率 误检概率: 一个文本块根据其signature看包含某个term，但事实上并不包含的概率
太多位置1 False drop概率上升，极端情况，所有位都是1，将匹配任何query 置1的位太少, 过滤能力下降 没有充分利用signature提供的空间 最优的情况是1和0的数量相等 直觉的解释：当n/2被置1后，可能匹配的情况最多 例如：假设signature是4位，则其中2位置1时可能匹配的模式是6个，最多 C41=4, C42=6, C43=4

86 作为过滤器的签名文件 Signature文件可以剔出那些不包含query terms的文档
可以将通过signature过滤器的文本和查询式直接比对，从而避免False Drops = 过滤出的文本 匹配的文本 Query signature Signature文件 文档

87 存储开销 存储开销决定于被散列到一个signature中的词数
M = nF M: 需要的存储位; n: block数 F: 每个signature的位数 关键问题: 对于一个包含了给定词数的文档，生成多少signature比较合适? 如果更多的词散列到一个signature中，则存储的开销将降低，而false drop的概率将升高

88 设计时的决策 对signature file的需求 能够负担的存储开销 能够忍受的false drop概率 需要确定的参数:
每个词多少位 优化设计: Fd = 2 -m m = F ln2/D Fd - false drop概率 m – 置1的位数 F – signature的长度 D – 一个块中的词数

89 优点 Signature文件小而可控 由于文件组织简单，因此维护费用小(更新和删除) Signatures容易生成，插入费用低
重叠编码适合多属性检索 Signature文件在倒排文件和全文扫描之间做了空间和时间的平衡 适合中等大小的数据库和查询频率较低的系统 可应用于过滤系统

90 缺点 和倒排文件相比，搜索速度慢 (尽管比全文扫描快). 对于顺序文件, 所有的签名都必须被比较 去除False drops需要昂贵的开销
因为所有被匹配的签名必须通过模式匹配来确认 在签名中，很难对频率和权值信息进行编码 其它query函数，例如分离条件、同义词、通配符, 邻近操作都很难使用

91 顺序检索

92 顺序检索技术 前面介绍的文本搜索技术需要事先建立索引，然后执行快速的查询 但是，在某些应用中，这种建立索引的方法并不适用
在签名文件的候选块确认过程中，就需要在块中查找某一查询是否真正存在； 在文本过滤技术，一般文本仅需要查询一次，这就没有建立索引； 在搜索引擎中结果后处理中，需要对搜索结果中包含的查询关键词进行加亮显示，也需要用到文本搜索技术。 顺序检索技术，也具有很广阔的应用场合。快速的顺序检索是非常必要的

93 全文扫描(Full Text Scanning)
不维护索引表 直接在文本上进行搜索 需要模式匹配和逻辑组合来处理布尔条件 This is a long article on HIT Query: article AND HIT HIT article AND hit pattern matcher

94 全文扫描 优点: 不在索引方面花费时空开销 适用于文本频繁产生和更新的动态环境 在原始文本上完成搜索任务
理论上，文本中的任何信息都可以被找到 (例如, 不需要no 停用词和Stemming操作) <h1>HIT</h1><p>…</p><p>…computer…</p> 查询: “computer” 出现在以“HIT” 为标题的某个章的第二段里 <h1>HIT</h1> <p>*computer*</p> logic hit pattern matcher hit, doc#, loc, etc. 缺点: 搜索速度慢，但对于小文档集合来说是可以接受的。 (例如个人文档集合)

95 模式匹配算法 基本的文本扫描操作： 单模式的字符串匹配技术 字符串搜索
给定一个单独的关键词p(搜索串)和一个输入串 s, 如果p 是s 的子串就回答yes，否则回答no 单模式的字符串匹配技术 Brute Force串匹配算法 快速串匹配算法 KMP算法 BM算法

96 模式匹配 ——BF算法

97 Brute Force算法(1) 搜索串 (模式): p1p2…pm 文本串: s1s2…sn (通常 n >> m)
将模式和m个字符的字串sksk+1…sk+m-1进行匹配，k从1到n - m +1. 模式要么和子串匹配，要么找到一个位置发现二者不匹配 p1 … pi … pm s1… sk … sj… sk+m-1 ...

98 Brute Force算法(2) begin end travel information travel information
j := 1 while i  m and j  n do if pi = sj then begin i := i +1; j := j +1 end else begin j := j - i + 2; i :=1 end if i > m then return “yes else return “no” end 此循环可以更早地 终止: j  n - m + 1 最多 n  m 次 i=1 j=9 travel information informing 模板 向右移动 i=1 j=8 i=7 j=14 travel information informing

99 Brute Force算法—性能 在模式的末尾 发现不匹配 在模式的开头 发现不匹配

100 模式匹配 ——KMP

101 KMP(Knuth-Morris-Pratt) 匹配算法
Brute force算法较慢，因为它和每一个m个字符的字串都要比较，其实是不必要的。 位置 文本 a b d a d e f g 模式 a b d f a b d f Brute force: 移动一个字符 a b d f 聪明的做法：移动三个字符 在位置4出现不匹配的现象，Brute force算法只移动了一位 由于前三个位置(a b d)都匹配成功了，移动一个位置不可能找到“a”，因为它已经被识别为 “b” 在文本的前缀被匹配成功后，你已经对文本串有了一些了解

102 KMP算法——基本思想 充分利用在一次失败匹配过程中获得的知识，避免重复比较已经知道的字符 关于文本的知识: a b d ?
位置： 文本串 a b d a d e f g 模式 a b d f 关于文本的知识: a b d ? 需要在文本串中找到另一个 “a” 我已经知道 “a”不可能出现在下两个字符中, 因此可以向右移动三个字符 需要实现对模板(pattern)中的字符进行分析

103 KMP算法 – 基本思想 a b d f .. x x x x .. =  如果模板向右移动一个位置，它能够匹配成功吗？
通过检查模板的前缀a b d，就能知道肯定无法匹配，因为如果x和 b匹配成功，就不可能和a匹配成功 要点是：我们能够通过预先对模式的分析获得知识： 如果 ( 在模式的位置1或2匹配失败 ) 则移动1个位置 如果 ( 在模式的位置3匹配失败 ) 则移动2个位置 如果 (在模式的位置4匹配失败) 则移动3个位置

104 KMP匹配算法 – 举例 S: b a b c b a b c a b c a a b c a 第1个字符不匹配，向右移动1次
P: a b c a b c a c a b a b c a b c a c a b 3个字符后发现不匹配， 在已经匹配成功的部分(abc)没有重复字串 将P中的第1个字符与S中不匹配的字符对齐 a b c a b c a c a b 子串abcabca匹配成功; 其中最长的重复部分是abca; 将P向右移动3个位置， 和重复部分对齐 P: a b c a b c a c a b 第1个字符不匹配，向右移动1次 a b c a b c a c a b a b c a b c a c a b

105 KMP – 一般原则 A B A B x C D y 模式 文本 从匹配成功的子模式中找出“能够相互匹配的最长的前缀和后缀”
1 j j+1 文本 C D y i i+j i+j+1 从匹配成功的子模式中找出“能够相互匹配的最长的前缀和后缀” 通过对模式的分析，我们知道A=B，在匹配过程中知道A=C, B=D; 移动模式，让A和D对齐，从位置i+j+1处开始匹配 如果当前不匹配的位置记为j，重复字串的长度为k，则跳过的字符个数为j-k-1 如果在模式 [1..j]中没有重复模式, 则可以直接移动 j个字符 有重复子模式的模式需要更多的时间去匹配，例如：aaaaaab

106 KMP算法 – Shift表 匹配失败时，决定移动多少个位置 因为 abcababcac 所以，找不到“重复子串”

107 KMP算法 – 性能 Shift表可以在O(m) 的时间复杂度下，通过对关键词的分析而获得 KMP算法花费 O(m+n)的时间来解决此问题
对每个模板字符，需要计算当匹配实效发生时应该跳过几个字符 KMP算法花费 O(m+n)的时间来解决此问题

108 模式匹配 ——Boyer-Moore

109 Boyer-Moore算法 在理论上和实践上，BM都比KMP更快，它跳过了输入串中对匹配不可能有贡献的点 BM基本想法: 从右到左匹配输入串
比较 pm 和 sm 如果sm 不在关键词中出现，那么从s的前m个字符中任何一个字符开始的字符串都不可能和p相比配 可以因此安全地向右滑动m个字符，从而避免m-1词不必要的匹配。

110 如果有两个E，应该和最右边的E对齐，不能移动得太快
BM算法 -- D1 Shift S: B A N A N A ^ C R E A M P: C R E A M P: C R E A M P: C R E A M N(sm) 和M(pm)不匹配，且N不在P中出现; 向右移动 m=5 个位置, D1= 5 E和M不匹配，E (sm) 在p中出现; 移动P使之相互对齐，D1= 2 如果有两个E，应该和最右边的E对齐，不能移动得太快

111 D1 Shift表 如果模式的长度为 p 并且字母表的大小为q (对小写字母来说q=26), 我们需要pq的 D1 shift表  1
最右不匹配的 字母位置编号  1 2 3 4 5 M 1 2 3 4  A 1 2 3   : 字母表 – {C, R, E, A, M} E 1 2  模式P=CREAM R 1  2 3 C  1 2 3 4

112 BM算法 -- D2 Shift p的尾部已经和s的某些子串相匹配，但再向左一位就不匹配了，此时使用D2 Shift
S: b a b c b a d c a b c a a b c a P: a b c a b d a c a b 仅基于 D1, 移动一个字符 a b c a b d a c a b a b c a b d a c a b 仅基于D2, 移动5个字符 问题: 如果 cab 不在模式中重复出现，怎么办？ 如果应用D1 , 只能移动一个字符 和KMP相似, 我们可以知道已经匹配成功的模式后缀cab在模式的前面已经出现过, 因此移动1个字符肯定无法匹配成功 我们应该移动模式，用前面已经出现的模式和S中相应的文本对齐 D2 = 5

113 D2 Shift 的实现 如果在 p[i]处不匹配，令： len = m - i
找到最大的 j 使p [ j .. ( j + len - 1) ] = p [ (i+1) .. m ] 则：shift2[i] = i – j + 1 P: a b c a b d a c a b i j

114 D1 和 D2 的对比 考虑如下字符串 D1 = 7, 因为不匹配的字符 d 不在剩余的模式中出现 如果基于重复子模式来考虑，则D2 = 5
S: b a b c b a d c a b c a a b c a P: a b c a b c a c a b a b c a b c a c a b D1 = 7 a b c a b c a c a b D2 = 5 D1 = 7, 因为不匹配的字符 d 不在剩余的模式中出现 如果基于重复子模式来考虑，则D2 = 5 我们需要同时计算出 D1 和 D2 ，并使用最大的shift

115 BM算法 – 扩展的 D1 Shift BM算法使用两个shift中最大的shift来决定最终移动的位数
如果应用 D1 shift, shift 可以扩展到任意P的头和尾匹配的地方。 input: b a b c b a d c a b c a a b c a keyword: a b c a b c a c a b a b c a b c a c a b D2 5 D1 = 7 Extended D1 shift

116 扩展 D1 Shift算法 a b c a b c a c a b a b c a b c a c a b 在 p[i]处不匹配 len=3
If mismatch at p[i] and D1 is used len = m – i if p[ 1 .. len ] = p[ i+1 .. m ] then D1 unchanged else find j such that p[1 .. j ] = p[ m-j+1 .. m ] D1 = D1 + len - j longest prefix in p[1..len] that matches the suffix of p[m-len+1..m]

117 BM算法 – 小结 算法维护两个shift 表 (D1 和 D2 shift): 对于每一次匹配失效，从两张表中找出最长的shift应用
在D2-shift中, bring a different character to the position in the text that caused the mismatch 扩展的D1-shift

118 BM算法 – 性能 当模式中重复部分很少时，效率最高 (类似KMP) 需要比较的字符数比输入字符串的长度n要小

119 算法选择: 启发式 这里介绍了一组经典的文本搜索算法，文献中还有更多的介绍
如果关键词的长度很小(1-3 characters), 可以使用Brute Force算法 如果字母表很大，KMP算法是一个合适的选择 否则，特别是对于长文本来说, BM 是最佳选择(重复模式)

120 模式匹配 ——Karp-Rabin

121 Karp-Rabin算法 Karp-Rabin算法使用一个hash函数来降低将关键词和每一个m字符的字串相对比的开销 Ip
travel information informing pattern p text string s hash(s) Ip = hash(p) Is

122 Karp-Rabin算法（1） h 是一个hash函数，将 m个字符的字符串影射为一个整数
如果h(p1p2…pm)  h(sksk+1…sk+m-1 )，那么我们可以确信p1p2…pm 不可能和sksk+1…sk+m-1 相互匹配 如果h(p1p2…pm) = h(sksk+1…sk+m-1 ), 那么我们必须继续将 p1p2…pm 和sksk+1…sk+m-1.. 在字符级逐个匹配，从而保证没有误匹配发生 s2 (冲突) s1 Is Ip 模式 hash =?

123 Karp-Rabin算法 (2) Hash函数将 m 个字符的比较降低为单个整数的比较, 但是需要一个快速的散列函数
Karp和Rabin建议使用函数h(x) = x mod q ，q 是一个适当大的质数 对 m 个字符的字符串 sksk+1…sk+m-1, 计算 xk = sk bm-1 + sk+1 bm-2 + … + sk+m-1 xk+1 = (xk - sk bm-1)b + sk+m string = abcde ascii(a) = 97 m = 4 hash(“abcd”) = (97* * * *20 ) % q = 1466 % q hash(“bcde”) = (98* * * *20 ) % q = 1481 % q ascii(e) hash(“bcde”) = [ ( *23) * ] % q 如果模式的hash值和文本的hash值每次都匹配，这是最坏的情况，时间复杂度为 O(mn) ，几乎不可能出现 期望的时间复杂度是： O(m+n)

124 有效的模式匹配是否有用？ 认为没有用的观点: 认为有用的观点
如果文本存储在磁盘上，全文扫描需要将文件读入主存，并执行模式匹配: 读盘操作决定了时间开销 倒排文档不需要模式匹配 认为有用的观点 文本可以在主存中被缓存 (例如：今天的新闻) 即时使用倒排文件，模式匹配仍然有用: high-lighting matched parts 如果倒排文件不包括词的位置，就需要利用模式匹配技术确认词的位置 信息推送: 大量的用户profiles (patterns/keywords) 被用来匹配少量的新到的文本 (e.g., s)

125 Query处理 ——相关反馈 125

126 信息检索系统的体系结构 用户界面 文本 用户 需求 文本处理 用户 数据库 提问处理 建索引 反馈 管理 搜索 提问 索引 文本 数据库
逻辑视图 用户 反馈 提问处理 建索引 数据库 管理 倒排文档 搜索 提问 索引 文本 数据库 排序后 的文档 检出的文档 排序 126

127 文档检索 检索出来 的文档 相关反馈 索引 查询规范化 形式语言 检索 文档表示 文档 用户的信息需求

128 相关反馈(Relevance Feedback)
手工的query再生成很难控制 相关文档和不相关文档的特征不明显 文档特征很难被转化为正确的query形式 相关反馈 : 根据用户对文档的相关性评估产生新的查询

129 Query修改过程 F G F: 从用户那里接受相关性评估，输出相关文档和不相关文档 G: 实现相关反馈公式 检索 过程 相关评估
重新形成的 query Q’ 排序输出 相关和不相关 的文档 原始Q 检索 过程 F G F: 从用户那里接受相关性评估，输出相关文档和不相关文档 G: 实现相关反馈公式

130 相关反馈的作用 x 原始query 重新形成的query 相关文档 x 不相关文档 根据原始的query 检索出5篇文档

131 Query修改的基本思路 出现在相关文档中的terms被添加到原始的query向量中, 或者这些term的权重在创建新的query时有某种程度的增长 出现在不相关文档中的terms被从原始query中删除，或者这些term的权重某种程度地降低

132 理想情况 理想情况：query terms只 出现在相关文档中! t3贡献的分值 t2贡献的分值 Q = t1, t2, t3
N documents 分值 initial 处理query term后 相关 不相关 分值 Rel docs Nonrel docs 分值 理想情况：query terms只 出现在相关文档中!

133 一般情况 Q = t1, t2, t3 一般来说，一个term可能在相关文档和不相关文档中都出现
分值 t1贡献的分值 t2贡献的分值 t3贡献的分值 一般来说，一个term可能在相关文档和不相关文档中都出现 问题是：是否应该在query中包含它，如果包含，怎样打分

134 优化的Query 根据已知的相关文档集DR和不相关文档集DN , 令 tik 表示词项 k 在文档i中的权重, 词项 k在两个集合中的平均权重分别为： 和 在优化后的query Qopt中词项 k 的权值定义为： 考虑不同的情况: 如果tk 仅出现在相关文档中, 它的权值非常高 如果tk 仅出现在不相关文档中, 它的权值就小，甚至为副 如果tk 在两类文档中都出现, 它的权值介于中间

135 Query修改 将用户提示的相关文档集DR’ 和不相关文档集DN’作为对DR 和DN 的估计,重复地修改query达到优化的目的
Q 是初始的query, , 和 是一个合适的常数 Q, Q’,Di均为加权向量

136 举例 T1 T2 T3 T4 T5 Q = ( 5, 0, 3, 0, 1) D1 = ( 2, 1, 2, 0, 0) D2 = ( 1, 0, 0, 0, 2) Q:初始query D1: 相关文档 D2:不相关文档  = 1,  = 1/2,  = 1/4 假设: S(Q,D1) = (52)+(0  1)+(3  2)+(0  0)+(1  0) = 16 S(Q’,D1)=(5.75  2)+(0.5  1)+(4  2)+(0  0)+(0.5  0)=20 S(Q,D2) = (51)+(0  0)+(3  0)+(0  0)+(1  2) = 7 S(Q’,D2)=(5.75  1)+(0.5  0)+(4  0)+(0  0)+(0.5  2)=6.75

137 向量空间模型中的反馈与查询重构 用Cr表示文整个档集中所有相关文档的集合，|Cr|表示Cr中文档的数量，用N表示整个文档集合，dj表示单一文档j 我们的目标就是希望寻找到 这样我们可以把用来区分相关文档和不相关文档的最佳查询向量定义为

138 向量空间模型中的反馈与查询重构 如果直接使用这个公式来确定最佳查询，显然会遇到很大麻烦，因为Cr是一个未知量，而任何对Cr的理想估计都会带来一定的误差 Rocchio利用迭代求精的方法来解决这个问题 Di表示第i次检索所返回的文档中，用户标明为相关文档的集合。 Dn,i表示第i次检索所返回的文档中，不相关文档的集合。 |Di|和|Dn,i|分别表示Di和Dn,i中的文档数量

139 向量空间模型中的反馈与查询重构 首先定义一个初始的查询向量q1，提交给检索系统 然后根据返回的检索结果，通过用户的选择，确定D1和Dn,1
重复执行以上步骤，直到获得理想的检索结果为止 从原始查询q1开始，每一个新产生出的查询都使用户更加靠近相关文档集合的质心，同时更加远离不相关文档集合的质心

140 需要确定的参数 如何确定, 和 ? 相关文档提供的信息比不相关文档更大，因此应比值更大 在DR’ and DN’使用多少文档？
只考虑相关文档 – 正模型 只考虑不相关文档 – 负模型 同等/不同的权值 – 混合模型 相关文档提供的信息比不相关文档更大，因此应比值更大 在DR’ and DN’使用多少文档？ 使用全部相关文档和不相关文档 使用全部相关文档和高rank值的不相关文档

141 相关反馈的作用 理想状态：相关和不相关 的文档可以很清楚地分开 相关文档 x 不相关文档 原始query 修正后的query
OK: 相关文档 仍然形成一个“簇” 糟糕的情况: 相关文档和 不相关文档混在一起

142 Query 分裂 当相关文档集R‘ (或不相关文档集) 没有形成“簇”, 反馈机制无效
当R‘ 形成多个“簇”, 如果能发现这些簇, 为每一个簇构成一个新的query，则上面的公式仍然可以使用 x 相关文档 不相关文档 原始query 修正后的query

143 文档空间的修改 不修改用户的query, 可以根据用户的反馈修改文档空间 (例如：索引项和文档的权值)
思路：使相关文档向量和query的距离拉近，不相关文档向量和query的距离拉远

144 修改文档空间的例子 相关文档 不相关文档 query 相关文档的修正 相关和不相关文档的修改

145 文档的修改 对相关文档的修改 对不相关文档的修改恰好相反 被认为是相关的文档在文档空间中一定要和Q更近
将一个不在文档中出现的query term 乘以系数a后加入文档中 已在文档中的query term 权值乘以系数b，提高权值 不在query中出现的document term乘以 -，降低权值. 使文档向量和query越接近，这些文档向量之间也越接近 对不相关文档的修改恰好相反 在query中出现的词权重下降 不在query中出现的词权重上升

146 Query处理 ——查询扩展

147 基于词典的查询扩展 将查询中的词项 t扩展为词典中的同义词和相关词 扩展词的权重应低于原始查询词 一般将提高召回率.
可能大幅度降低准确率, 特别是对于有歧义的词

148 同义词词林 《同义词词林》 梅家驹、竺一鸣、高蕴琦、殷鸿翔，上海辞书出版社1983 (第一版) ，1996年 (第二版) 架构 12大类，94中类，1428小类，3925个词群 12大类 A人，B物，C时间和空间，D抽象事物 E特征，F动作，G心理活动，H活动 I现象与状态，J关联，K助语，L敬语 举例： “苹果” Bh07，“香蕉” Bh07，“西红柿” Bh06，……

149 词典的使用：例子 五个词的term-term相关矩阵A, B, C, D, and E. 假设根据阈值将相似度转化为二值的
A B C D E A B C D E

150 使用词典的例子 q = 根据原始query不能找出仅包含E的文档，但新的query可以 q’ =
通过增加相关词来扩展query，相关term的权值系数为0.5 A=4 B=2 C=1 D=1 E=0 q = Add B=2 Add A=1,D=1 Add E =0.5 Add B=0.5, E=0.5 Add nothing A=5 B=4.5 C=1 D=2 E=1 q’ = 根据原始query不能找出仅包含E的文档，但新的query可以

151 本章小结 文本的表示方法 倒排文件，后缀数组和签名档的建立及检索 字符串匹配技术 问题的扩展和相关反馈方法