信息检索技术

1、信息检索技术1第1页，共52页，2022年，5月20日，0点54分，星期一内容提要倒排文档检索加权检索全文检索2第2页，共52页，2022年，5月20日，0点54分，星期一4.1 倒排文档检索3第3页，共52页，2022年，5月20日，0点54分，星期一信息检索系统的体系结构文本数据库数据库管理建索引索引提问处理搜索排序排序后的文档用户反馈文本处理用户界面检出的文档用户需求文本提问逻辑视图倒排文档4第4页，共52页，2022年，5月20日，0点54分，星期一建立索引的目的对文档或文档集合建立索引，以加快检索速度倒排文档（或倒排索引）是一种最常用的索引机制倒排文档的索引对象是文档或文档集合中的单

2、词等。5第5页，共52页，2022年，5月20日，0点54分，星期一在关系数据库上建索引这种想法也被应用于数据库技术中，即对数据库中需要经常进行检索的域建立索引结构，进行快速的查询。索引结构: hashing, B+-tree可以索引全部记录，在全部记录上进行搜索精确地快速地查找地址姓名姓名索引查询式:姓名 = “张三”张三哈尔滨工业大学张三6第6页，共52页，2022年，5月20日，0点54分，星期一对文档进行索引索引结构: hashing, B+-trees, tries.可以进行部分匹配: %comput% 可以进行短语搜索:查找包含“computer graphics”的文档文档索引D

3、1D2D3computerD1, 23, 97, 104D3, 43graphicsD2, 5D3, 44“computer”在D1中出现的位置7第7页，共52页，2022年，5月20日，0点54分，星期一倒排文档组成倒排文档一般由两部分组成：词汇表（vocabulary）和记录表（posting list）词汇表是文本或文本集合中所包含的所有不同单词的集合。对于词汇表中的每一个单词，其在文本中出现的位置或者其出现的文本编号构成一个列表，所有这些列表的集合就称为记录表8第8页，共52页，2022年，5月20日，0点54分，星期一一般的倒排索引索引文件可以用任何文件结构来实现索引文件中的词项是文

4、档集合中的词表architecturecomputerdatabaseretrieval.D1, a1D1, a2D1, a3索引项/词表索引/索引文件/索引数据库Postings 列表Q = term1, term2, term3, .附加信息例如：词位置，出现次数9第9页，共52页，2022年，5月20日，0点54分，星期一例子12345678910111213141516这是一本关于信息检索的教材。介绍了检索的基本技术。技术教材检索信息15, 8, 6, 12, 5, 词汇表Posting list文本倒排文件10第10页，共52页，2022年，5月20日，0点54分，星期一以文本为记录

5、表 记录表既可以存储文本中单词的编号位置，也可以指向单词首字母的字符位置，还可以是其所在的文本编号，下图是一个以文本为记录表的情况11第11页，共52页，2022年，5月20日，0点54分，星期一距离约束：需要位置信息为记录表常常需要知道邻接条件，例如：“database” 后面紧跟着“systems”例如：短语搜索 “database systems”“database”和“systems”之间不能间隔超过3个词“database”和“architecture”在同一个句子里需求扩展:倒排索引中保存着关键词在文档中的位置，文档的组成单元(标题, 小标题, 句子分割标记等)检索算法和位置信息相

6、关联，并需检查文档的组成单元12第12页，共52页，2022年，5月20日，0点54分，星期一以位置信息为记录表保存段落、句子和词的位置：databasefilesystems.D345, 25D348, 37D350, 8D123, 5D128, 25D345, 25保存倒排表中的位置信息:保存句子位置:文档D350第8句databasefilesystems.D345, 2,3,5D348, 37,5,9D350, 8,12,1D123, 5,4,3D128, 25,1,12D345, 2,3,6文档D350第8段，第12句第1个词13第13页，共52页，2022年，5月20日，0点54分

7、，星期一以权重信息为记录表可保存出现频率，以便支持基于统计的检索:databasefilesystems.D345, 10D348, 20D350, 1D123, 82D128, 8D345, 12在D345中“systems” 比“database”重要1.2倍Postings中的第二个单元可以是该term的权重 (例如, 可以被归一化在0和1之间) ，或者是该term的出现频率14第14页，共52页，2022年，5月20日，0点54分，星期一同义词扩展词汇表同义词对于提高召回率很有意义同义词可以通过指针指向同一个postings list.databasedatabasessystemsD

8、345, 2,3,5D348, 37,5,9D350, 8,12,1D123, 5,4,3D128, 25,1,12D345, 2,3,6dataset15第15页，共52页，2022年，5月20日，0点54分，星期一建立索引的过程16第16页，共52页，2022年，5月20日，0点54分，星期一建立索引的过程识别文档中的词删除停用词(stop words)提取词干(stemming)用索引项的标号代替词干(stems) 统计词干的数量(tf)(可选) 对低频词项使用同义词词典(thesaurus)(可选) 对高频词项构成短语计算所有单个词项、短语和语义类的权重17第17页，共52页，2022

9、年，5月20日，0点54分，星期一英文词根还原(Stemming)进行词根还原：stop/stops/stopping/stoppedstop好处：减少词典量；坏处：按词形查不到，词根还原还可能出现错误不进行词根还原：Stoppedsto+ppe+d好处：支持词形查询；坏处：增加词典量18第18页，共52页，2022年，5月20日，0点54分，星期一停用词消除停用词(stop words)是指那些出现频率高但是无重要意义，通常不会作为查询词出现的词，如“的”、“地”、“得”、“都”、“是”等等消除：通常是通过查表的方式去除，去除的好处-大大较少索引量，坏处-有些平时的停用词在某些上下文可能有意

10、义保留：索引空间很大19第19页，共52页，2022年，5月20日，0点54分，星期一建立索引的过程 举例输入文本The analysis of 25 indexing algorithms has not produced consistent retrieval performance. The best indexing technique for retrieving documents is not known删除stopwordsanalysis indexing algorithms produced consistent retrieval performance best i

11、ndexing technique retrieving documents knownStemminganalysis index algorithm produc consistent retriev perform best index technique retriev document known转换为索引编号123 345 110 2234 432 3565 2302 566 345 4321 3565 755 1128计算tf110 1 123 1 345 2 1 432 1 566 1 755 1 1128 1 2302 1 2344 1 3565 2 4321 1计算词项的权

12、值 (依赖于使用的模型)20第20页，共52页，2022年，5月20日，0点54分，星期一检索过程给定query对query进行stemming，算法与对文档的处理相同用索引编号代替stems计算所有query terms的权重形成query向量（对VSM模型而言）计算query向量和文档向量之间的相似度返回排序后的文档集合21第21页，共52页，2022年，5月20日，0点54分，星期一倒排索引上的布尔检索一个布尔检索包含n个用布尔操作连接的词项 ，例如：“computer AND news AND NOT newsgroup”可以用括号来调整逻辑运算次序每个term从倒排索引中返回一个po

13、stings list如果term不在任何文档中出现，则postings list为空检索结果根据逻辑关系相结合：AND: 集合做交运算OR: 集合做并运算NOT: 集合做差运算ABA and B22第22页，共52页，2022年，5月20日，0点54分，星期一倒排索引上的布尔检索查询:中国 AND 文化查找Dictionary，定位中国;读取对应的postings.查找Dictionary，定位文化;读取对应的postings.“Merge” 合并(AND)两个postings:12834248163264123581321中国文化23第23页，共52页，2022年，5月20日，0点54分，

14、星期一34128248163264123581321合并Lists的合并算法34248163264123581321中国文化28If the list lengths are x and y, the merge takes O(x+y)operations.Crucial: postings sorted by docID.24第24页，共52页，2022年，5月20日，0点54分，星期一倒排索引上的布尔检索标准的优化技术应用：从最短的posting list开始做“与”操作，保证中间结果越小越好“网络” AND “病毒” AND “蠕虫”从哪个词项开始做交运算呢？显然是：“病毒”和“蠕虫”

15、25第25页，共52页，2022年，5月20日，0点54分，星期一倒排索引的优点快速索引 (长query需要更多时间)灵活性: 不同类型的信息都可以存储在postings list中如果存储了足够多的信息，则可以支持复杂的检索操作例如：如果记录了词在文档中的准确位置，就可以支持短语检索，或模糊检索26第26页，共52页，2022年，5月20日，0点54分，星期一倒排索引的缺点很大的存储开销50% - 150% - 300%更新、插入和删除都需要很高的维护开销，倒排索引相对静态的环境(很少插入和更新)中使用比较好处理开销随着布尔操作的增加而增长由于postings越来越多(例如引入同义词)，导致

16、索引检索的代价越来越大，需要对位置进行很多处理(例如短语匹配)27第27页，共52页，2022年，5月20日，0点54分，星期一倒排文档中研究的问题倒排文档的压缩倒排文档的删除倒排文档的插入28第28页，共52页，2022年，5月20日，0点54分，星期一索引压缩理论上，(全文)索引的大小和原始文件相当，因为每个词的每次出现都必须在posting list中记录。需不需要压缩？要压缩：索引大小通常和原始文本大小相当，不压缩可能会耗费大量存储开销不压缩：硬盘很便宜，数据量不是特别大，而且不需要解压缩的消耗29第29页，共52页，2022年，5月20日，0点54分，星期一倒排索引的更新情况一：出现

17、了新的词，则需要修改词典结构，在词典中增加词条。情况二：出现了新的文档，则在相应的词条下增加posting list。情况三：某些文档不复存在，则在相应的位置进行标记，等积累到一定时期进行一次性操作。30第30页，共52页，2022年，5月20日，0点54分，星期一词汇表的组织顺序排序数组：采用字典序，查找采用二分法。空间消耗小，查找较快，但是插入删除麻烦。二叉搜索树、B树、Trie树等。Hash表：通过Hash函数直接把词映射到地址，空间消耗和Hash函数设计有关。较快，插入删除容易。31第31页，共52页，2022年，5月20日，0点54分，星期一4.2 加权检索加权检索根据每个词在检索要

18、求中的重要程度不同，分别给予一定的数值（权值）加以区别，同时利用给出的检索命中界限值（阈值，Threshold）限定检索结果的输出。加权检索是布尔逻辑检索的一种扩充，把量化思想引入定性检索中。加权检索分为标引加权和检索加权两种类型。32第32页，共52页，2022年，5月20日，0点54分，星期一4.2.1 检索词赋权检索对每一检索词给定一权值，代表其重要性。检索时，对存在的检索词的记录计算其权值总和。当权值总和大于阈值时，则认为命中。 最简单、最容易实现的加权检索系统。33第33页，共52页，2022年，5月20日，0点54分，星期一举例一个企业管理者为了改进企业管理模式，接受新的管理理念，

19、提高企业的竞争力，希望获取知识管理、竞争情报、企业文化方面的文献资料，用加权法列出的提问式如下： W = 知识管理（4）竞争情报（2）企业文化（1）表中“”表示相应检索词与文献中主题词匹配，若设定阈值为4，由上表可知，组合1至4为命中文献。34第34页，共52页，2022年，5月20日，0点54分，星期一检索词赋权检索的优缺点检索词赋权检索的优点：明确了检索词在检索中的重要程度；通过提高或降低阈值来扩大和缩小检索输出的范围；检索结果按符合检索需求的重要程度顺序排列。检索词赋权检索的缺点：加权法提问式表达不如逻辑式直观；权值的确定较为困难。35第35页，共52页，2022年，5月20日，0点54

20、分，星期一4.2.2 加权标引加权标引是指在对文献进行标引时，根据每个标引词在文献中的重要程度不同，为它们附上不同的权值，检索时通过对检索词的标引权值相加来筛选命中记录。36第36页，共52页，2022年，5月20日，0点54分，星期一加权标引在进行加权标引时，对反映文献主要内容的标引词给予高权值，反映文献次要内容的标引词给予较低的权值。词频加权检索方法应建立在对全文数据库和文摘数据库基础之上，否则词频加权将失去意义。37第37页，共52页，2022年，5月20日，0点54分，星期一简单词频加权简单词频加权检索：指检索时累计检索词在记录中出现的次数来决定记录的权值。最大缺点就是不论文章长短、词

21、频高低都采用的是统一的词频标准。38第38页，共52页，2022年，5月20日，0点54分，星期一相对词频加权检索将每一个检索词在本文中频率和在整个数据库中的频率综合考虑，进行加权检索的方法。文内频率=指定词在本文中的频次/该文本词汇总频次文外频率=指定词在本文中的频次/该词在整个数据库(所有文献)中总次数文内频率解决了短文章中词频过低的问题，文外频率解决了新词、专用词的低频问题。 39第39页，共52页，2022年，5月20日，0点54分，星期一4.2.3 标引加权的检索过程检索时给出检索词和检索阈值，对满足检索阈值的检索结果按其权值之和从大到小输出来筛选命中记录。 在实际的人工标引中尚未见

22、有加权标引的系统。在计算机自动标引的系统中，可以方便而有效的采用加权标引技术。40第40页，共52页，2022年，5月20日，0点54分，星期一标引加权检索阈值的设定在检索中，阈值有两种设置方法：为每个检索词制定一个阈值，避免了次要内容被检出；给总的检索结果指定一个阈值，保证了命中文献的综合相关度。41第41页，共52页，2022年，5月20日，0点54分，星期一4.3 全文检索技术全文检索，即检索的数据源、检索的对象、检索匹配技术、检索结果都是全文信息的检索。全文检索有两种实现方式：对全文编索引；不对全文进行任何加工处理，只是从前至后的逐字匹配。42第42页，共52页，2022年，5月20日

23、，0点54分，星期一4.3.1 全文检索的技术指标（1）索引膨胀系数索引的膨胀系数是指针对全文所建的索引文件大小与全文文件大小之比。索引膨胀系数 =索引文件的大小/全文数据库的大小全文索引需要以最小的标引单位作为索引主键字，英语一般为单词，中文则为单汉字。（2）检索速度 43第43页，共52页，2022年，5月20日，0点54分，星期一4.3.2 全文检索的实现全文检索的实现通常用检索词对全文产生的词（字）索引文档的匹配。西文的全文检索多数采用位置检索技术，这样可以提高全文检索的查准率。位置检索分为四种级别：记录级检索、字段或段落级检索或自然句级检索、词位置检索。 44第44页，共52页，20

24、22年，5月20日，0点54分，星期一词位置级检索（1）词位置顺序相邻（W）检索时要求（W）两边的词在原文中不能有其他单词，并且次序不能颠倒。例如：？select information （W） retrieval可检得含有固定词组“information retrieval”的文献全文。 45第45页，共52页，2022年，5月20日，0点54分，星期一词位置级检索（2）位置顺序隔词（nW） 表示由算符（nW）所连接的检索词之间最多只能含有n（n可以为0）个单词，并且两词的顺序不能颠倒。 例如：? select computer （1W） communication 其检索式表示含有下述词组的文献都可作为检索命中结果：computer communication；computer and communication；computer for communication。 46第46页，共52页，2022年，5月20日，0点54分，星期一词位置级检索（3）词位置相邻（N） 若文献满足由算符（N）构成的检索式，这些文献中必须包含算符（N）两侧的词，并且它们是紧连的，但两词的顺序可以颠倒。 例如 ：? select computer （N） television其检索结果是所有含有词组“computer television”或“televisi