搜索
信息检索信息检索第第0303章章文本索引和搜索文本索引和搜索软件学院教研室软件学院教研室陈鄞陈鄞PDF文件使用pdfFactoryPro试用版本创建引言引言•索引–是一种数据结构，它在关键词与包含关键词的文档之间建立了一种映射关系，从而加快检索的速度。•建立索引的目的–加快检索速度•常用的索引技术–倒排索引–后缀数组–签名文件PDF文件使用pdfFactoryPro试用版本创建本章内容本章内容•3.1倒排索引•3.2后缀数组•3.3签名文件•3.4文本搜索技术PDF文件使用pdfFactoryPro试用版本创建倒排索引倒排索引•3.1.1什么是倒排索引•3.1.2倒排索引的建立•3.1.3基于倒排索引的检索•3.1.4倒排索引的维护•3.1.5倒排索引的压缩•3.1.6倒排索引性能分析PDF文件使用pdfFactoryPro试用版本创建什么是倒排索引什么是倒排索引知识管理，企业文化，管理创新…10管理信息系统，竞争情报…9管理信息系统，企业文化…8知识管理，知识创新，竞争情报…7企业信息化，信息结构，竞争情报…6技术创新，知识空间，知识创新…5知识管理，学习型组织…4知识管理，知识创新，知识共享…3知识管理，知识链，学习型组织，知识创新…2知识管理，管理信息系统，企业信息化…1关键词题目文档编号131211109876543211;2;3;4;7;106知识管理31知识共享51知识空间21知识链2;3;5;74知识创新2;42学习型组织61信息结构1;62企业信息化8;102企业文化6;7;93竞争情报51技术创新1;8;93管理信息系统101管理创新文档集合目长关键词建立索引PDF文件使用pdfFactoryPro试用版本创建倒排索引的定义倒排索引的定义•倒排索引–也称倒排文档，是从关键词快速查询到文档的索引结构。文档正常表示为关键词的集合，建立倒排索引是把每个关键词表示为其出现的文档的集合，这个过程称为inversion，即倒排。•这种想法也被应用于数据库技术中，即对数据库中需要经常进行检索的域建立索引结构，进行快速的查询。PDF文件使用pdfFactoryPro试用版本创建倒排文档的结构倒排文档的结构•倒排文档组成–词汇表（vocabulary）•关键词组成的集合–记录表（postinglist）•关键词在文档集合中的位置组成的集合architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3词汇表postingslistQ=term1,term2,term3,...附加信息例如：词位置，出现次数等等PDF文件使用pdfFactoryPro试用版本创建记录表中存储关键词在文档中的位置记录表中存储关键词在文档中的位置•关键词在文档中的位置–文档中的哪一段–段中的哪一句–句中的哪一个词–关键词所在的单元（标题,小标题）•目的：支持位置检索技术，例如：–“database”后面紧跟着“systems”•例如：短语搜索“databasesystems”–“database”和“systems”之间不能间隔超过3个词–“database”和“architecture”在同一个句子里PDF文件使用pdfFactoryPro试用版本创建•文本•倒排文档12345678910111213141516这是一本关于信息检索的教材。介绍了检索的基本技术。…技术教材检索信息…15,…8,…6,12,…5,……词汇表记录表PDF文件使用pdfFactoryPro试用版本创建•保存句子位置•保存段落、句子和词的位置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个词PDF文件使用pdfFactoryPro试用版本创建中，“systems”比“database”重要1.2倍记录表中存储统计信息记录表中存储统计信息•统计信息–频率–权重databasefilesystems...D345,10D348,20D350,1D123,82D128,8D345,12PDF文件使用pdfFactoryPro试用版本创建同义词扩展词汇表同义词扩展词汇表•同义词对于提高检索的召回率很有意义•同义词可以通过指针指向同一个记录表...databasedatabasessystemsD345,2,3,5D348,37,5,9D350,8,12,1D123,5,4,3D128,25,1,12D345,2,3,6datasetPDF文件使用pdfFactoryPro试用版本创建倒排索引的建立倒排索引的建立•步骤–在文档中抽取关键词，并在其后附上其文档编号–对抽出的关键词进行排序，使之便于归并相同关键词–对相同关键词进行归并，把合并后的关键词放入倒排文档的词汇表。统计每一关键词的文档频率作为目长，把每一关键词后的记录号顺序放在记录表中PDF文件使用pdfFactoryPro试用版本创建以前的方法需要对23个项进行排序分裂为三个相同大小的文件12342,431,2,52,3建索引1234531,3,42,4131234551155,1171234512,141212,1312,1413,14分裂加载file1加载file2加载file3•词ID总是被追加到后边•每一部分有已知的大小，可以预先分配存储空间1213141,2,3,43,51,4,5建索引57111,3,452,4建索引PDF文件使用pdfFactoryPro试用版本创建基于倒排索引的检索基于倒排索引的检索•由于倒排文档的组成特点，使得许多数学检索模型（如布尔模型、集合运算等）能够方便地用于信息检索中。•它将关键词之间的逻辑运算转换成了检索词对应的文档集合之间的集合运算补非3并或2交与1文档集合之间的集合运算检索词之间的逻辑运算ABtAandtBPDF文件使用pdfFactoryPro试用版本创建倒排文档的维护倒排文档的维护•插入文档•删除文档•更新文档PDF文件使用pdfFactoryPro试用版本创建插入文档插入文档•调用该文档包含的关键词所对应的记录表，在后面插入关键词的位置信息，该表再放回倒排文件中–最坏的情况:•文档包含n个关键词，并且每个关键词都不重复，插入时需要调用并更新n个记录表PDF文件使用pdfFactoryPro试用版本创建批量插入批量插入•首先为待插入的多个文档建立临时内存索引结构（批倒排文件相当小，因此创建它并不难）•然后一次性地将此索引结构插入到原索引中–从倒排文件中检索出一个记录表，插入若干记录项，该表再放回倒排文件中DocidTermpaperreportnovelnovel……1111…reporthuman……22…humannovelnovelpaperreportreport……211112…排序human2,1novel1,2paper1,1report1,12,1合并在此记录频率PDF文件使用pdfFactoryPro试用版本创建•批量插入的优点–提高了效率（因为一个词可能出现在多个文档中）•批量插入需要注意的问题–索引内容滞后问题•临时内存索引•使用后台进程在机器空闲时进行插入操作–批量插入的规模•批不能太小，否则很少会出现多个文件包含一个词的情况•批不能太大，否则批的生成本身开销也很大–当我们设计一个新的插入操作时，我们必须考虑主存和临时存储器中可利用的空间大小PDF文件使用pdfFactoryPro试用版本创建删除文档删除文档•为了支持删除操作，需要维护一个前向索引(forwardindex)来记录文档中包含的词•步骤–找到将要被删除的文档ID–从前向索引中获得该文档中包含的词–根据该文档中的词定位倒排索引中的记录表，并在这些记录表中将该文档ID删除•批量删除•保持删除的及时性–维护一张“删除文件列表”，如果检索结果包含列表中的文件，则将其从结果中删除即可–使用后台进程在机器空闲时进行删除操作DocIDword1,word2,….PDF文件使用pdfFactoryPro试用版本创建更新文档更新文档•代价较高–即使该文档仅仅改动很少的部分，文档中出现的大部分单词的记录表都需要做出改动，因为其位置很可能发生变化•因此，一般不进行更新操作，而只是使用“删除+插入”操作代替•对于数据量不大的应用，如对小型图书馆中图书信息的检索，重建的速度很快。而且相对于复杂更新操作而言，重建是比较容易实现的PDF文件使用pdfFactoryPro试用版本创建倒排文档的压缩倒排文档的压缩•压缩的目的–空间–时间•压缩的内容–词汇表–记录表PDF文件使用pdfFactoryPro试用版本创建词汇表的压缩词汇表的压缩•定宽数组–浪费存储空间–不能表示所有的词•字符串表词汇表………………2计算机………………3检索………………链接文档数关键词记录表2……9……721……文档号词汇表………………2………………3………………链接文档数关键词指针记录表2……9……721……文档号……检索\0……计算机\0……PDF文件使用pdfFactoryPro试用版本创建记录表的压缩记录表的压缩•问题–一般用16位或32位整数表示文档和单词位置的绝对编号。–16位很容易溢出，32位又浪费空间•解决办法–仅记录相邻位置之间的差异•类似视频压缩中仅记录本帧和上一帧的差异databaseD345,25,34,98,120D348,37,71,85database345,25,9,64,223,37,34,14WordpositionsPDF文件使用pdfFactoryPro试用版本创建变长整数描述变化变长整数描述变化•对于有些常用词，例如“的”，文本编号的相对变化多数是1，如果仍然使用16位编码，显然浪费了太多的空间•而另外一方面，对于某些词，有可能仅存在于少数的文本之中，而这些文本编号的相对变化也很有可能超过65,536，即216。这时，如果仍然使用16位整数表示，就会溢出•一般使用变长整数来表示这种相对变化。其基本原理就是使用较少的位数表示较小的整数，而较大的整数，则需要使用较多的位数表示PDF文件使用pdfFactoryPro试用版本创建压缩技术带来的负面影响压缩技术带来的负面影响•在搜索时必须花些时间对压缩的数据进行解码•在维护时，特别是进行删除