第五章文本索引和搜索

1、信息组织、存储与检索信息组织、存储与检索第五章第五章 文本索引和检索文本索引和检索信息组织、存储与检索信息组织、存储与检索信息检索系统工作流程信息检索系统工作流程用户界面用户界面文本操作文本操作查询操作查询操作标引标引检索检索排序排序索引索引数据库管理数据库管理模块模块文本数据库文本数据库用户需求用户需求逻辑视图逻辑视图逻辑视图逻辑视图用用户户反反馈馈查询查询检出文档检出文档排序文档排序文档倒排文档倒排文档文本文本文本文本信息组织、存储与检索信息组织、存储与检索建立索引的目的建立索引的目的n对文档或文档集合建立索引，以加快检索速度n倒排文档（或倒排索引）是一种最常用的索引机制n倒排文档的索引对

2、象是文档或文档集合中的词语等。例如，有些书往往在最后提供的索引（单词页码列表对），就可以看成是一种倒排索引信息组织、存储与检索信息组织、存储与检索在关系数据库上建索引在关系数据库上建索引n 这种想法也被应用于数据库技术中，即对数据库中需要经常进行检索的域建立索引结构，进行快速的查询。n 索引结构: hashing, B+-treen 可以索引全部记录，在全部记录上进行搜索n 精确地快速地查找地址姓名姓名索引查询式:姓名 = “张三”张三南京理工大学泰州科技学院张三信息组织、存储与检索信息组织、存储与检索倒排文档的组成倒排文档的组成n倒排文档一般由两部分组成：词汇表（vocabulary）和记录

3、表（posting list）n词汇表是文本或文本集合中所包含的所有不同单词的集合。n对于词汇表中的每一个单词，其在文本中出现的位置或者其出现的文本编号构成一个列表，所有这些列表的集合就称为记录表。信息组织、存储与检索信息组织、存储与检索对文档进行索引对文档进行索引n索引结构: hashing, B+-trees.n可以进行部分匹配: %comput% n可以进行短语搜索:查找包含“computer graphics”的文档文档索引D1D2D3computerD1, 23, 97, 104D3, 43graphicsD2, 5D3, 44“computer”在D1中出现的位置信息组织、存储与检

4、索信息组织、存储与检索一般的倒排索引一般的倒排索引n 索引文件可以用任何文件结构来实现n 索引文件中的词项是文档集合中的词表architecturecomputerdatabaseretrieval.D1, a1D1, a2D1, a3索引项索引项/词表词表索引索引/索引文件索引文件/索引数据库索引数据库Postings 列表列表Q = term1, term2, term3, .附加信息例如：词位置，出现次数信息组织、存储与检索信息组织、存储与检索例子例子12345678910111213141516这是一本 关于 信息 检索 的教材 。介绍 了检索 的基本 技术 。技术教材检索信息15,

5、8, 6, 12, 5, 词汇表记录表文本倒排文件信息组织、存储与检索信息组织、存储与检索以文本为记录表以文本为记录表 记录表既可以存储文本中单词的编号位置，也可以指向单词首字母的字符位置，还可以是其所在的文本编号，下图是一个以文本为记录表的情况信息组织、存储与检索信息组织、存储与检索倒排文档的使用倒排文档的使用n词汇表检索n将出现在查询中的单词分离出来，并在词汇表中进行检索；n记录表检索n检索出所有找到的单词对应的记录表；n记录表操作n对检索出的记录表进行处理，实现短语查询、相邻查询或布尔查询等。信息组织、存储与检索信息组织、存储与检索倒排文档的建立倒排文档的建立 基于内存基于内存n基于内存

6、的建立倒排文档算法n输入：文档集合n输出：基于文档集合的倒排文档n算法：n1.初始遍历文档集合，对于每一个单词w，统计包含该单词的文档数fw；n2.在内存中建立长度为 的数组，并且对每一个单词w生成指向其记录表块首的指针pw；n3.第二次遍历文档集合，对每个文档d中的每一个单词w，在pw中追加文档d的序号， pw后移。词表wwf信息组织、存储与检索信息组织、存储与检索倒排文档的建立倒排文档的建立 基于排序基于排序单词 文档编号技术技术1教材1检索1信息1计算机2检索2排序技术技术1计算机2检索1检索2教材1信息1合并技术技术计算机检索信息12121倒排文档基于排序的建立倒排文档方法信息组织、存

7、储与检索信息组织、存储与检索倒排文档的建立倒排文档的建立基于归并基于归并n 输入：文档集合n 输出：基于文档集合的倒排文档n 算法：n1.初始生成一个基于内存的临时索引结构，其中词汇表和记录表均使用动态数据结构存储；n2.读取一个文档，并在其中出现的单词的记录表中加入文档编号，直到占用的内存大小超过一定的阈值为止；n3.将生成的包括词汇表和其记录表的临时索引结构转存到磁盘，并清空内存；n4.如果所有文档处理完毕，则转到5，否则转到1；n5.归并以上生成的字索引，生成单一索引。信息组织、存储与检索信息组织、存储与检索倒排文档的更新倒排文档的更新删除删除n 倒排文档更新就是一个删除操作，后面跟着一

8、个插入操作n 为了支持删除操作，需要维护一个前向索引(forward index)来记录文档中包含的词Doc IDword1, word2, .n找到将要被删除的文档IDn从前向索引中获得该文档中包含的词n根据该文档中的词定位倒排索引中的posting项，并在这些posting项中将该文档ID删除信息组织、存储与检索信息组织、存储与检索倒排文档的更新倒排文档的更新插入插入n 一个文档插入时最坏的情况:n 当文档包含n个词，并且每个词都不重复，插入时需要更新n个posting表n 对于posting表中的每个更新操作:n 如果postings表没有排序，新的posting项可以被追加到表的末端，

9、更新操作很快，但是检索无序的posting表很慢n 如果posting表示排序了的，那么插入一个新的posting项需要很大的开销databaseD345, 25D348, 37D350, 8新文档:D349 包含“database”D349, 10databaseD345, 25D348, 37D349, 10D350, 8信息组织、存储与检索信息组织、存储与检索通过排序进行批插入通过排序进行批插入n 收集所有将被插入索引中的新文档n 从每个文档中提取term，并准备一个倒排文件:Doc idTermpaperreportnovelnovel 1111 reporthuman 22 huma

10、nnovelnovelpaperreportreport 211112 排序human2,1novel1,2paper1,1report1,12,1合并在此记录频率，词的位置也可以记录信息组织、存储与检索信息组织、存储与检索倒排索引上的布尔检索倒排索引上的布尔检索考虑查询：同时包含Brutus和Caesar的文档。词汇表倒排记录表BrutusCaesarCalpurnia12358132134248163264 128131612834248163264123581321BrutusBrutusCaesarCaesar28信息组织、存储与检索信息组织、存储与检索合并过程合并过程34128248

11、16326412358132112834248163264123581321BrutusBrutusCaesarCaesar28信息组织、存储与检索信息组织、存储与检索合并算法的伪代码描述合并算法的伪代码描述信息组织、存储与检索信息组织、存储与检索查询优化查询优化n查询处理中是否存在处理的顺序问题？n考虑n 个词项的 AND n对每个词项，取出其倒排记录表，然后两两合并n查询: Brutus AND Caesar AND Calpurnian查询优化：（Calpurnia AND Brutus） AND Caesarn按照表从小到大(即df从小到大)的顺序进行处理n每次从最小的开始合并信息组织

12、、存储与检索信息组织、存储与检索词汇表的存取词汇表的存取排序数组排序数组n排序数组中的每个元素由三个部分组成：n关键词n记录表大小n指向其记录表的指针 .Term1记录表的大小记录表的地址Term2记录表的大小记录表的地址Term3记录表的大小记录表的地址信息组织、存储与检索信息组织、存储与检索词汇表的存取词汇表的存取树结构树结构n二叉树n除根节点、叶子节点外的每个节点都有两个子节点。信息组织、存储与检索信息组织、存储与检索词汇表的存取词汇表的存取树结构树结构nB树是一种平衡的多叉树，一棵m阶的B树满足下列条件：n1 )树中每个节点至多有m个孩子；n2 )除根节点和叶子节点外，其他每个节点至少

13、有m/2个孩子；n3 )若根节点不是叶子节点，则至少有2个孩子；n4 )所有叶子节点都出现在同一层，叶子节点不包含任何关键词信息；n5)有k个孩子的非终端节点恰好包含有k-1个关键词；信息组织、存储与检索信息组织、存储与检索B树实例树实例10 20 301 5 811 15 1821 2632 34 35 43 53m=5信息组织、存储与检索信息组织、存储与检索词汇表的存取词汇表的存取哈希表哈希表(散列文件散列文件)n散列文件也称直接存取文件，即根据文件中关键词的特点，设计哈希函数（散列函数）和冲突处理方法，将记录散列存储到设备上。n记录存储的逻辑地址=HASH(记录的关键词值)n除留余数法n

14、HASH（KEY）=KEY mod P信息组织、存储与检索信息组织、存储与检索哈希表实例哈希表实例n某一文件有16个记录，其关键字分别为：23，05，26，01，18，02，27，12，07，09，04，19，06，16，33，24。桶的容量m=3，桶数b=7。求哈希表的分布。KEY2305260118022712KEY%725514265KEY0709041906163324KEY%702456253信息组织、存储与检索信息组织、存储与检索哈希表实例哈希表实例07012302091418040526122706161933基桶溢出桶桶编号0123456信息组织、存储与检索信息组织、存储与检索

15、倒排索引的特点倒排索引的特点n快速索引 (长query需要更多时间)；n灵活性: 不同类型的信息都可以存储在记录表中；n如果存储了足够多的信息，则可以支持复杂的检索操作；n存储开销较大；n更新、插入和删除都需要很高的维护开销，倒排索引相对静态的环境(很少插入和更新)中使用比较好。信息组织、存储与检索信息组织、存储与检索后缀数组的定义后缀数组的定义n可以将文本看作是一个长的字符串，文本中的每个位置都被认为是文本的一个后缀，即一个从当前文本位置到文本末尾的字符串。n索引的位置可以是每个字符的位置、单词的位置或者汉字的位置等。n后缀数组：后缀数组：就是对文本中的所有后缀按照词典序存放每个后缀对应的起

16、始位置的列表。信息组织、存储与检索信息组织、存储与检索原始文本，按字的顺序位置索引文本中的部分后缀，按位置索引相同的部分后缀，按词典顺序索引后缀数组的构造后缀数组的构造 024681012141618202224262830323436384042444648这是一本关于信息检索的教材。介绍了检索的基本技术。021216223444这是是一信息检索教材检索技术441634222120技术检索检索教材是一信息这是信息组织、存储与检索信息组织、存储与检索后缀数组的使用后缀数组的使用 n在使用后缀数组进行检索的时候，将每个查询同样截取前n个字节，并于索引中进行查找；n如果没有找到，则表明不包含所需查

17、询；n如果查找成功，则需要在相应的文本位置上，进行进一步的字符串比较，以确定文本中是否包含查询；信息组织、存储与检索信息组织、存储与检索后缀数组的分析后缀数组的分析 n对于需要大数据量的检索问题，后缀数组并不适用 ；n因为构造出的后缀数组需要占用大量的空间，通常是原文本的1.7倍 ；n和倒排文档相比，后缀数组里面储存了较多的重复信息 ；信息组织、存储与检索信息组织、存储与检索文本检索技术文本检索技术布尔检索布尔检索ANDORNOT信息组织、存储与检索信息组织、存储与检索布尔检索布尔检索n布尔逻辑运算符n逻辑与：”AND” 或”*”n逻辑或： ”OR” 或”+”n逻辑非： ”NOT” 或”-”n

18、使用布尔运算符注意事项n运算执行顺序：NOTANDOR;先执行括号内的逻辑运算；n使用规则：不同检索工具规则不同信息组织、存储与检索信息组织、存储与检索文本检索技术文本检索技术截词检索截词检索n 利用词干或不完整的词形查找信息的检索技术；n 按截断字符的数量，分为有限截断、无限截断；n 按截断字符的位置，分为n后截断检索（也称前方一致检索）n无限后截断检索：coagula*(coagulacoagulantcoagulasecoagulate)n有限后截断检索：mold?(moldmoldedmolder)n后截断检索的利用n单词复数：apple?n年代：199？n作者：smith*n同根词：attract*信息组织、存储与检索信息组织、存储与检索文本检索技术文本检索技术截词检索截词检索n前截断检索（也称后方一致检索）n无限前截断检索：*metern有限前截断检索：？metern前截断和后截断结合使用：*econom*n中截断检索（也称中间一致检索）nm?n,wom?nn截断检索的特点n减少检索词输入量，提高召回率，降低准确率信息组织、存储与检索信息组织、存储与检索文本检索技术文本检索技术限制检索限制检