第五章-文本索引和搜索

第五章文本索引和检索信息检索系统工作流程用户界面文本操作查询操作标引检索排序索引数据库管理模块文本数据库用户需求逻辑视图逻辑视图用户反馈查询检出文档排序文档倒排文档文本文本建立索引的目的对文档或文档集合建立索引，以加快检索速度倒排文档（或倒排索引）是一种最常用的索引机制倒排文档的索引对象是文档或文档集合中的词语等。例如，有些书往往在最后提供的索引（单词—页码列表对），就可以看成是一种倒排索引在关系数据库上建索引这种想法也被应用于数据库技术中，即对数据库中需要经常进行检索的域建立索引结构，进行快速的查询。索引结构:hashing,B+-tree可以索引全部记录，在全部记录上进行搜索精确地快速地查找地址姓名姓名索引查询式:姓名

=“张三”张三南京理工大学泰州科技学院张三倒排文档的组成倒排文档一般由两部分组成：词汇表（vocabulary）和记录表（postinglist）词汇表是文本或文本集合中所包含的所有不同单词的集合。对于词汇表中的每一个单词，其在文本中出现的位置或者其出现的文本编号构成一个列表，所有这些列表的集合就称为记录表。对文档进行索引索引结构:hashing,B+-trees.可以进行部分匹配:’%comput%’可以进行短语搜索:查找包含“computergraphics”的文档文档索引D1D2D3computerD1,23,97,104D3,43graphicsD2,5D3,44“computer”在D1中出现的位置一般的倒排索引索引文件可以用任何文件结构来实现索引文件中的词项是文档集合中的词表architecturecomputerdatabaseretrieval...D1,a1D1,a2D1,a3索引项/词表索引/索引文件/索引数据库Postings列表Q=term1,term2,term3,...附加信息例如：词位置，出现次数例子12345678910111213141516这是一本关于信息检索的教材。介绍了检索的基本技术。…技术教材检索信息…15,…8,…6,12,…5,……词汇表记录表文本倒排文件以文本为记录表记录表既可以存储文本中单词的编号位置，也可以指向单词首字母的字符位置，还可以是其所在的文本编号，下图是一个以文本为记录表的情况倒排文档的使用词汇表检索将出现在查询中的单词分离出来，并在词汇表中进行检索；记录表检索检索出所有找到的单词对应的记录表；记录表操作对检索出的记录表进行处理，实现短语查询、相邻查询或布尔查询等。倒排文档的建立—基于内存基于内存的建立倒排文档算法输入：文档集合输出：基于文档集合的倒排文档算法：1.初始遍历文档集合，对于每一个单词w，统计包含该单词的文档数fw；2.在内存中建立长度为的数组，并且对每一个单词w生成指向其记录表块首的指针pw；3.第二次遍历文档集合，对每个文档d中的每一个单词w，在pw中追加文档d的序号，pw后移。倒排文档的建立—基于排序单词文档编号技术1教材1检索1信息1……计算机2检索2……排序技术1计算机2检索1检索2教材1信息1……合并技术计算机检索信息12121倒排文档基于排序的建立倒排文档方法倒排文档的建立—基于归并输入：文档集合输出：基于文档集合的倒排文档算法：1.初始生成一个基于内存的临时索引结构，其中词汇表和记录表均使用动态数据结构存储；2.读取一个文档，并在其中出现的单词的记录表中加入文档编号，直到占用的内存大小超过一定的阈值为止；3.将生成的包括词汇表和其记录表的临时索引结构转存到磁盘，并清空内存；4.如果所有文档处理完毕，则转到5，否则转到1；5.归并以上生成的字索引，生成单一索引。倒排文档的更新—删除倒排文档更新就是一个删除操作，后面跟着一个插入操作为了支持删除操作，需要维护一个前向索引(forwardindex)来记录文档中包含的词DocIDword1,word2,….找到将要被删除的文档ID从前向索引中获得该文档中包含的词根据该文档中的词定位倒排索引中的posting项，并在这些posting项中将该文档ID删除倒排文档的更新—插入一个文档插入时最坏的情况:当文档包含n个词，并且每个词都不重复，插入时需要更新n个posting表对于posting表中的每个更新操作:如果postings表没有排序，新的posting项可以被追加到表的末端，更新操作很快，但是检索无序的posting表很慢如果posting表示排序了的，那么插入一个新的posting项需要很大的开销databaseD345,25D348,37D350,8新文档:D349

包含“database”D349,10databaseD345,25D348,37D349,10D350,8通过排序进行批插入收集所有将被插入索引中的新文档从每个文档中提取term，并准备一个倒排文件:DocidTermpaperreportnovelnovel……1111…reporthuman……22…humannovelnovelpaperreportreport……211112…排序human2,1novel1,2paper1,1report1,12,1合并在此记录频率，词的位置也可以记录倒排索引上的布尔检索考虑查询：同时包含Brutus和Caesar的文档。词汇表倒排记录表BrutusCaesarCalpurnia12358132134248163264128131612834248163264123581321BrutusCaesar28合并过程3412824816326412358132112834248163264123581321BrutusCaesar28合并算法的伪代码描述查询优化查询处理中是否存在处理的顺序问题？考虑n个词项的AND对每个词项，取出其倒排记录表，然后两两合并查询:Brutus

AND

CaesarAND

Calpurnia查询优化：（CalpurniaANDBrutus）

AND

Caesar按照表从小到大(即df从小到大)的顺序进行处理每次从最小的开始合并词汇表的存取—排序数组排序数组中的每个元素由三个部分组成：关键词记录表大小指向其记录表的指针……..Term1记录表的大小记录表的地址Term2记录表的大小记录表的地址Term3记录表的大小记录表的地址词汇表的存取—树结构二叉树除根节点、叶子节点外的每个节点都有两个子节点。词汇表的存取—树结构B树是一种平衡的多叉树，一棵m阶的B树满足下列条件：1)树中每个节点至多有m个孩子；2)除根节点和叶子节点外，其他每个节点至少有m/2个孩子；3)若根节点不是叶子节点，则至少有2个孩子；4)所有叶子节点都出现在同一层，叶子节点不包含任何关键词信息；5)有k个孩子的非终端节点恰好包含有k-1个关键词；B树实例10203015811151821263234354353m=5词汇表的存取—哈希表(散列文件)散列文件也称直接存取文件，即根据文件中关键词的特点，设计哈希函数（散列函数）和冲突处理方法，将记录散列存储到设备上。记录存储的逻辑地址=HASH(记录的关键词值)除留余数法HASH（KEY）=KEYmodP哈希表实例某一文件有16个记录，其关键字分别为：23，05，26，01，18，02，27，12，07，09，04，19，06，16，33，24。桶的容量m=3，桶数b=7。求哈希表的分布。KEY2305260118022712KEY%725514265KEY0709041906163324KEY%702456253哈希表实例07^01^23020914^1804^0526122706^16^1933^基桶溢出桶桶编号0123456倒排索引的特点快速索引(长query需要更多时间)；灵活性:不同类型的信息都可以存储在记录表中；如果存储了足够多的信息，则可以支持复杂的检索操作；存储开销较大；更新、插入和删除都需要很高的维护开销，倒排索引相对静态的环境(很少插入和更新)中使用比较好。后缀数组的定义可以将文本看作是一个长的字符串，文本中的每个位置都被认为是文本的一个后缀，即一个从当前文本位置到文本末尾的字符串。索引的位置可以是每个字符的位置、单词的位置或者汉字的位置等。后缀数组：就是对文本中的所有后缀按照词典序存放每个后缀对应的起始位置的列表。原始文本，按字的顺序位置索引文本中的部分后缀，按位置索引相同的部分后缀，按词典顺序索引后缀数组的构造024681012141618202224262830323436384042444648…这是一本关于信息检索的教材。介绍了检索的基本技术。…021216223444…这是…是一…信息…检索…教材…检索…技术……441634222120…技术…检索…检索…教材…是一…信息…这是……后缀数组的使用在使用后缀数组进行检索的时候，将每个查询同样截取前n个字节，并于索引中进行查找；如果没有找到，则表明不包含所需查询；如果查找成功，则需要在相应的文本位置上，进行进一步的字符串比较，以确定文本中是否包含查询；后缀数组的分析对于需要大数据量的检索问题，后缀数组并不适用；因为构造出的后缀数组需要占用大量的空间，通常是原文本的1.7倍；和倒排文档相比，后缀数组里面储存了较多的重复信息；文本检索技术—布尔检索ANDORNOT布尔检索布尔逻辑运算符逻辑与：”AND”或”*”逻辑或：”OR”或”+”逻辑非：”NOT”或”-”使用布尔运算符注意事项运算执行顺序：NOT>AND>OR;先执行括号内的逻辑运算；使用规则：不同检索工具规则不同文本检索技术—截词检索利用词干或不完整的词形查找信息的检索技术；按截断字符的数量，分为有限截断、无限截断；按截断字符的位置，分为后截断检索（也称前方一致检索）无限后截断检索：coagula*(coagula\coagulant\coagulase\coagulate…)有限后截断检索：mold??(mold\molded\molder…)后截断检索的利用单词复数：apple?年代：199？作者：smith*同根词：attract*文本检索技术—截词检索前截断检索（也称后方一致检索）无限前截断检索：*meter有限前截断检索：？？？？meter前截断和后截断结合使用：*econom*中截断检索（也称中间一致检索）m?n,wom?n截断检索的特点减少检索词输入量，提高召回率，降低准确率文本检索技术—限制检索通过给检索词附加一定的条件来缩小或约束检索结果。限制字段检索主题字段非主题字段限定位置检索记录级字段级