信息检索技术 第五章 文本索引和搜索 (1)

第五章文本索引和搜索复习复习文本操作技术文本操作技术中英文预处理技术拼写检查查错错上下文无关的错误，上下文有关的错误纠错纠错词语相似度：编辑距离动态规划方法求解：动态规划方法求解：1)昀优子结构，2)定义递归解，3)递推，4)回溯2011/11/13251引言5.1引言信息检索的基本流程信息检索的基本流程数据采集数据预处理数据加工：将采集到本地的数据进行编排索引，数据加工将采集到本地的数据进行编排索引，以做好查询准备。用户检索用户检索相关反馈2011/11/133建立索引的必要性举例：图书馆建立索引的必要性举例：图书馆2011/11/134所谓建立索引就是将这些索引的信息进行定所谓建立索引，就是将这些索引的信息进行一定的分析，并将分析的结果按照一定的组织方式存储起来通常是存储在文件之中储起来，通常是存储在文件之中。当以后需要查询某条信息的时候，就需要到索引中去查找，由于索引是按照一定的结构组织的，这样的查询速度会非常快。举例：数据结构中的哈希表数据结构中的哈希表2011/11/135索引的定义索引的定义索引d是种数据结构其将关键词与包索引（Index）是一种数据结构，其将关键词与包含该关键词的文档（或关键词在文档中的位置）建立了种映射关系以加快检索的速度建立了一种映射关系，以加快检索的速度。2011/11/13652倒排文件5.2倒排文件种常有的索引技术三种常有的索引技术倒排文件后缀数组签名文件签名文件2011/11/137521倒排文件简介5.2.1倒排文件简介倒排文件dil也称倒排索引索引对倒排文件(InvertedFile)也称倒排索引，索引对象是文档或文档集合中的单词等，用来存储这些单词在个文档或者组文档中的存储位置是单词在一个文档或者一组文档中的存储位置，是对文档或文档集合的一种昀常用的索引机制.举例：单词-页码列表对2011/11/138举例：在关系数据库上建索引举例：在关系数据库上建索引对数据库中需要经常进行检索的域建立索引结构对数据库中需要经常进行检索的域建立索引结构，进行快速的查询索引结构hashing,B+-treeg,地址姓名姓名索引张三哈尔滨工业大学姓名索引查询式:张三哈尔滨工业大学张三查询式:姓名=“张三”2011/11/139倒排文件组成倒排文件组成词汇表bl记录表ili词汇表(vocabulary)+记录表(postinglist)词汇表文档或文档集合中所包含的所有不同单词的集合占用的空间V=cnβ，β是一个0到1之间的常数，占用的空间Vcn，β是个0到1之间的常数，一般在0.4到0.6之间。记录表记录表对于词汇表中的每一个单词在文档中出现的位置或者其出现的文档编号构成的列表或者其出现的文档编号构成的列表占用的空间P=cn，其中c是常数，随着记录表中存储的信息丰富程度而变化存储的信息丰富程度而变化。2011/11/1310举例：对一篇文档中单词的位置建立索引举例：对篇文档中单词的位置建立索引2011/11/1311对文档集合建立倒排索引对文档集合建立倒排索引2011/11/1312522倒排文件的使用5.2.2倒排文件的使用利用倒排文件进行检索通常分为个步骤利用倒排文件进行检索，通常分为三个步骤：词汇表检索，将出现在查询（Query）中的单词分离出来，并在词汇表中进行检索。记录表检索，检索出所有找到的单词对应的记录表。记录表操作，对检索出的记录表进行后处理，以实现短语查询、相邻查询或者布尔查询。2011/11/1313词汇表检索词汇表检索词汇表规模相对较小的独立文件全部调入内词汇表：规模相对较小的独立文件，全部调入内存。常用数据结构树状结构，如：B树和Trie树树状结构，如树和树优点：前缀查询和范围查询散列散列优点：检索速度快，但是不支持前缀查询和范围查询等询等2011/11/1314记录表检索记录表检索词项存储在词汇表中每个词项有个指针指向记词项存储在词汇表中，每个词项有个指针指向记录表。倒排记录表，规模较大，往往放在磁盘中。定长数组定长数组优点：顺序存储，随机读取缺点：长度固定，不利于缺点：长度固定，不利于插入，删除2011/11/1315记录表检索记录表检索词项存储在词汇表中每个词项有个指针指向记词项存储在词汇表中，每个词项有个指针指向记录表。倒排记录表，规模较大，往往放在磁盘中。定长数组定长数组单链表优点：灵和的内存动态管理不需要知道数据大小优点：灵和的内存动态管理，不需要知道数据大小，便于插入和删除。缺点：不能随机读取数据，内存开销大缺点不能随机读取数据，内存开销大2011/11/1316记录表检索记录表检索词项存储在词汇表中每个词项有个指针指向记词项存储在词汇表中，每个词项有个指针指向记录表。倒排记录表，规模较大，往往放在磁盘中。定长数组定长数组单链表变长数组变长数组2011/11/1317记录表操作记录表操作将各个单词检索出的记录表进行合并将各个单词检索出的记录表进行合并同步遍历记录表，实现合并过程如果某个记录表比其它记录表小得多，那么在较长记录表中查找小型记录表中的元素将非常有效，这种方法可以替换通常的线性合并的方法。2011/11/1318倒排文件使用举例（1）倒排文件使用举例（1）QCliQuery:BrutusANDCalpurnia操作：查找倒排文件词汇表，定位“Brutus”，返回其倒排记录表，返回其倒排记录表，查找倒排文件词汇表，定位“Calpurnia”，返回其倒排记录表返回其倒排记录表，2011/11/1319倒排文件使用举例（2）倒排文件使用举例（2）QCliQuery:BrutusANDCalpurnia操作：对两个倒排记录表求交集算法2011/11/1320倒排文件使用举例（3）倒排文件使用举例（3）QCliQuery:BrutusANDCalpurnia操作：对两个倒排记录表求交集2011/11/1321523倒排文件的建立5.2.3倒排文件的建立1基内存的倒排文件建立方法1.基于内存的倒排文件建立方法输入：文档集合输出：基于文档集合的倒排文件算法：算法(1)初始遍历文档集合。对于每一个单词w，统计包含该单词的文档数fw；单词的文档数fw；(2)在内存中建立长度为∑fw的数组，并且对于每一个单词w，生成指向其记录表块首的指针pw。单词w，生成指向其记录表块首的指针pw。(3)第二次遍历文档集合，对每个文档d中的每一个单词w，在pw中追加文档d的序号，pw后移。w，在pw中追加文档d的序号，pw后移。2011/11/1322举例举例：Document1:newhomesalestopforecastsDocument2:homesalesriseinjulyDocument3:increaseinhomesalesinjulyjyDocument4:julynewhomesalesrise2011/11/1323算法执行算法执行1）new:2,home:4,sales:4,top:1,forecasts:1,rise:2,in:2,july:3,increase:1,2)3)3)2011/11/1324基内存的倒排文件建立方法优点基于内存的倒排文件建立方法优点充分利用内存。基于内存的倒排文件建立方法缺点基于内存的倒排文件建立方法需要从磁盘中读取基于内存的倒排文件建立方法需要从磁盘中读取文件2次，因此，它需要花费较多的时间在磁盘读取和分析文档的操作上。取和分析文档的操作。需要内存比昀终生成的倒排文件大。2011/11/1325523倒排文件的建立5.2.3倒排文件的建立2基排序的倒排文件建立方法2.基于排序的倒排文件建立方法这种方法将用单词，文档编号二元组构成数组或者文件，将有原来的按照文档编号排序，变为由单词排序，生成昀终的倒排文件。2011/11/1326举例举例：Document1:newhomesalestopforecastsDocument2:homesalesriseinjulyDocument3:increaseinhomesalesinjulyjyDocument4:julynewhomesalesrise2011/11/1327（1）为每篇文档的所有词项加上文档ID（1）为每篇文档的所有词项加上文档ID词项词项docIDnew1h词项docIDincrease3home1sales1top1in3home3sales3top1forecasts1home2sales3in3july3sales2rise2i2jyjuly4new4in2july2home4sales4rise42011/11/1328rise4（2）将词项按照字母顺序排序（2）将词项按照字母顺序排序词项词项docIDforecasts1h词项docIDjuly3july4home1home2home3july4new1new4i2home3home4in2rise2rise4sales1in3in3i3sales2sales3sales4increase3july2sales4top12011/11/1329（3）同一词项进行合并（3）同词项进行合并词项词项docIDforecasts1h词项docIDjuly3july4home1home2home3july4new1new4i2home3home4in2rise2rise4sales1in3in3i3sales2sales3sales4increase3july2sales4top12011/11/1330（3）同一词项进行合并(续)（3）同词项进行合并(续)词项记录表词项-记录表forecasts-1forecasts1home-1234home1---234in-2-323increase-3july-2--342011/11/1331（3）同一词项进行合并(续)（3）同词项进行合并(续)词项记录表词项-记录表new-14new1rise-2-4-42-4sales-1---234top-12011/11/1332(4)将词项和文档ID分开(4)将词项和文档ID分开词汇表词汇表forecasts记录表1home11234….……2011/11/1333（5）扩展（5）扩展词汇表中以存储些该词项的其他概要信息词汇表中可以存储一些该词项的其他概要信息，比如词项的文档频率（df）。home-1---2344每个倒排记录表存储了词项出现的文档列表，也可以存储一些其他信息比如词项频率（tf）和可以存储些其他信息，比如词项频率（tf）和词项在文档中出现的位置。forecasts-1142011/11/1334课堂练习课堂练习画出该文档集的倒排索引画出该文档集的倒排索引Document1:breakthroughdrugforschizophreniaDocument2:newdrugforschizophreniaDocument3:Document3:newapproachfortreatmentofschizophreniaDocment4:Document4:newhopesforschizophreniapatients2011/11/1335答案答案词项记录表词项记录表approach-3pp3breakthrough-1drug-1-2for-1---234new-234hopes-42011/