第4章 信息检索技术

1第四章信息检索技术2内容提要倒排文档检索加权检索全文检索34.1倒排文档检索4信息检索系统的体系结构文本数据库数据库管理建索引索引提问处理搜索排序排序后的文档用户反馈文本处理用户界面检出的文档用户需求文本提问逻辑视图倒排文档5建立索引的目的对文档或文档集合建立索引，以加快检索速度倒排文档（或倒排索引）是一种最常用的索引机制倒排文档的索引对象是文档或文档集合中的单词等。6在关系数据库上建索引这种想法也被应用于数据库技术中，即对数据库中需要经常进行检索的域建立索引结构，进行快速的查询。索引结构:hashing,B+-tree可以索引全部记录，在全部记录上进行搜索精确地快速地查找地址姓名姓名索引查询式:姓名=“张三”张三哈尔滨工业大学张三7对文档进行索引索引结构:hashing,B+-trees,tries.可以进行部分匹配:’%comput%’可以进行短语搜索:查找包含“computergraphics”的文档文档索引D1D2D3computerD1,23,97,104D3,43graphicsD2,5D3,44“computer”在D1中出现的位置8倒排文档组成倒排文档一般由两部分组成：词汇表（vocabulary）和记录表（postinglist）词汇表是文本或文本集合中所包含的所有不同单词的集合。对于词汇表中的每一个单词，其在文本中出现的位置或者其出现的文本编号构成一个列表，所有这些列表的集合就称为记录表9一般的倒排索引索引文件可以用任何文件结构来实现索引文件中的词项是文档集合中的词表architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3索引项/词表索引/索引文件/索引数据库Postings列表Q=term1,term2,term3,...附加信息例如：词位置，出现次数10例子12345678910111213141516这是一本关于信息检索的教材。介绍了检索的基本技术。…技术教材检索信息…15,…8,…6,12,…5,……词汇表Postinglist文本倒排文件11以文本为记录表记录表既可以存储文本中单词的编号位置，也可以指向单词首字母的字符位置，还可以是其所在的文本编号，下图是一个以文本为记录表的情况12距离约束：需要位置信息为记录表常常需要知道邻接条件，例如：–“database”后面紧跟着“systems”例如：短语搜索“databasesystems”–“database”和“systems”之间不能间隔超过3个词–“database”和“architecture”在同一个句子里需求扩展:–倒排索引中保存着关键词在文档中的位置，文档的组成单元(标题,小标题,句子分割标记等)–检索算法和位置信息相关联，并需检查文档的组成单元13以位置信息为记录表–保存段落、句子和词的位置：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个词14以权重信息为记录表可保存出现频率，以便支持基于统计的检索:databasefilesystems...D345,10D348,20D350,1D123,82D128,8D345,12在D345中“systems”比“database”重要1.2倍Postings中的第二个单元可以是该term的权重(例如,可以被归一化在0和1之间)，或者是该term的出现频率15同义词扩展词汇表同义词对于提高召回率很有意义同义词可以通过指针指向同一个postingslist....databasedatabasessystemsD345,2,3,5D348,37,5,9D350,8,12,1D123,5,4,3D128,25,1,12D345,2,3,6dataset16建立索引的过程17建立索引的过程识别文档中的词删除停用词(stopwords)提取词干(stemming)用索引项的标号代替词干(stems)统计词干的数量(tf)(可选)对低频词项使用同义词词典(thesaurus)(可选)对高频词项构成短语计算所有单个词项、短语和语义类的权重18英文词根还原(Stemming)进行词根还原：stop/stops/stopping/stopped􀃎stop–好处：减少词典量；坏处：按词形查不到，词根还原还可能出现错误不进行词根还原：–Stopped􀃎sto+ppe+d–好处：支持词形查询；坏处：增加词典量19停用词消除停用词(stopwords)是指那些出现频率高但是无重要意义，通常不会作为查询词出现的词，如“的”、“地”、“得”、“都”、“是”等等–消除：通常是通过查表的方式去除，去除的好处----大大较少索引量，坏处----有些平时的停用词在某些上下文可能有意义–保留：索引空间很大20建立索引的过程–举例输入文本–Theanalysisof25indexingalgorithmshasnotproducedconsistentretrievalperformance.Thebestindexingtechniqueforretrievingdocumentsisnotknown删除stopwords–analysisindexingalgorithmsproducedconsistentretrievalperformancebestindexingtechniqueretrievingdocumentsknownStemming–analysisindexalgorithmproducconsistentretrievperformbestindextechniqueretrievdocumentknown转换为索引编号–123345110223443235652302566345432135657551128计算tf–11011231345214321566175511128123021234413565243211计算词项的权值(依赖于使用的模型)21检索过程给定query对query进行stemming，算法与对文档的处理相同用索引编号代替stems计算所有queryterms的权重形成query向量（对VSM模型而言）计算query向量和文档向量之间的相似度返回排序后的文档集合22倒排索引上的布尔检索一个布尔检索包含n个用布尔操作连接的词项，例如：“computerANDnewsANDNOTnewsgroup”–可以用括号来调整逻辑运算次序每个term从倒排索引中返回一个postingslist如果term不在任何文档中出现，则postingslist为空检索结果根据逻辑关系相结合：AND:集合做交运算OR:集合做并运算NOT:集合做差运算ABAandB23倒排索引上的布尔检索查询:中国AND文化–查找Dictionary，定位中国;读取对应的postings.–查找Dictionary，定位文化;读取对应的postings.–“Merge”合并(AND)两个postings:12834248163264123581321中国文化2434128248163264123581321合并Lists的合并算法34248163264123581321中国文化28Ifthelistlengthsarexandy,themergetakesO(x+y)operations.Crucial:postingssortedbydocID.25倒排索引上的布尔检索标准的优化技术应用：–从最短的postinglist开始做“与”操作，保证中间结果越小越好–“网络”AND“病毒”AND“蠕虫”–从哪个词项开始做交运算呢？显然是：“病毒”和“蠕虫”26倒排索引的优点快速索引(长query需要更多时间)灵活性:不同类型的信息都可以存储在postingslist中如果存储了足够多的信息，则可以支持复杂的检索操作–例如：如果记录了词在文档中的准确位置，就可以支持短语检索，或模糊检索27倒排索引的缺点很大的存储开销–50%-150%-300%更新、插入和删除都需要很高的维护开销，倒排索引相对静态的环境(很少插入和更新)中使用比较好处理开销随着布尔操作的增加而增长由于postings越来越多(例如引入同义词)，导致索引检索的代价越来越大，需要对位置进行很多处理(例如短语匹配)28倒排文档中研究的问题倒排文档的压缩倒排文档的删除倒排文档的插入29索引压缩理论上，(全文)索引的大小和原始文件相当，因为每个词的每次出现都必须在postinglist中记录。需不需要压缩？–要压缩：索引大小通常和原始文本大小相当，不压缩可能会耗费大量存储开销–不压缩：硬盘很便宜，数据量不是特别大，而且不需要解压缩的消耗30倒排索引的更新情况一：出现了新的词，则需要修改词典结构，在词典中增加词条。情况二：出现了新的文档，则在相应的词条下增加postinglist。情况三：某些文档不复存在，则在相应的位置进行标记，等积累到一定时期进行一次性操作。31词汇表的组织顺序排序数组：采用字典序，查找采用二分法。空间消耗小，查找较快，但是插入删除麻烦。二叉搜索树、B树、Trie树等。Hash表：通过Hash函数直接把词映射到地址，空间消耗和Hash函数设计有关。较快，插入删除容易。324.2加权检索加权检索根据每个词在检索要求中的重要程度不同，分别给予一定的数值（权值）加以区别，同时利用给出的检索命中界限值（阈值，Threshold）限定检索结果的输出。加权检索是布尔逻辑检索的一种扩充，把量化思想引入定性检索中。加权检索分为标引加权和检索加权两种类型。334.2.1检索词赋权检索对每一检索词给定一权值，代表其重要性。检索时，对存在的检索词的记录计算其权值总和。当权值总和大于阈值时，则认为命中。最简单、最容易实现的加权检索系统。34举例一个企业管理者为了改进企业管理模式，接受新的管理理念，提高企业的竞争力，希望获取知识管理、竞争情报、企业文化方面的文献资料，用加权法列出的提问式如下：W=知识管理（4）竞争情报（2）企业文化（1）表中“√”表示相应检索词与文献中主题词匹配，若设定阈值为4，由上表可知，组合1至4为命中文献。35检索词赋权检索的优缺点检索词赋权检索的优点：–明确了检索词在检索中的重要程度；–通过提高或降低阈值来扩大和缩小检索输出的范围；–检索结果按符合检索需求的重要程度顺序排列。检索词赋权检索的缺点：–加权法提问式表达不如逻辑式直观；–权值的确定较为困难。364.2.2加权标引加权标引是指在对文献进行标引时，根据每个标引词在文献中的重要程度不同，为它们附上不同的权值，检索时通过对检索词的标引权值相加来筛选命中记录。37加权标引在进行加权标引时，对反映文献主要内容的标引词给予高权值，反映文献次要内容的标引词给予较低的权值。词频加权检索方法应建立在对全文数据库和文摘数据库基础之上，否则词频加权将失去意义。38简单词频加权简单词频加权检索：指检索时累计检索词在记录中出现的次数来决定记录的权值。最大缺点就是不论文章长短、词频高低都采用的是统一的词频标准。39相对词频加权检索将每一个检索词在本文中频率和在整个数据库中的频率综合考虑，进行加权检索的方法。文内频率=指定词在本文中的频次/该文本词汇总频次文外频率=指定词在本文中的频次/该词在整个数据库(所有文献)中总次数文内频率解决了短文章中词频过低的问题，文外频率解决了新词、专用词的低频问题。404.2.3标引加权的检索