4章 信息检索技术

第四章信息检索技术1内容提要要倒排文档档检索加权检索索全文检索索24.1倒排文档档检索3信息检索索系统的的体系结结构文本数据库数据库管理建索引索引提问处理理搜索排序排序后的文档用户反馈文本处理理用户界面面检出的文文档用户需求文本提问逻辑视图图倒排文档档4建立索引引的目的的对文档或或文档集集合建立立索引，，以加快快检索速速度倒排文档档（或倒倒排索引引）是一一种最常常用的索索引机制制倒排文档档的索引引对象是是文档或或文档集集合中的的单词等等。5在关系数数据库上上建索引引这种想法法也被应应用于数数据库技技术中，，即对数数据库中中需要经经常进行行检索的的域建立立索引结结构，进进行快速速的查询询。索引结构构:hashing,,B++-tree可以索引引全部记记录，在在全部记记录上进进行搜索索精确地快快速地查查找地址姓名姓名索引查询式:姓名

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