第五讲文本索引和搜索

《第五讲文本索引和搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五讲文本索引和搜索索引：是一种数据结构，它在关键词与包含该关键词的文档之间建立了一种映射关系，从而加快检索的速度。搜索：一般定义为在不使用索引技术时而快速在给定文本或文本集合中查找是否出现某一关键词，通常也称为单模式匹配。本讲就是针对以上三种索引结构和三种搜索算法来进行介绍和学习。常用的文本索引技术：倒排文件、后缀数组和签名文件。常用的文本搜索技术：BF算法、KMP算法和BM算法。倒排文件结构关于倒排文件在第四讲有所介绍，你还记得吗？湖畔夏夜花园蛙鸣诗社诗会d1：log3/2：1d2：log3/2：1,6d1：log3：4d2：log3：9,1

2、2d2：1/2log3/2：15d3：log3/2：2，10d3：1/2log3：5d3：1/2log3：13词汇表记录表倒排文件一般由词汇表和记录表两部分组成。在记录表中可存储词在文档中出现的位置、文档编号等需要存储的信息。d1：湖畔的夏夜常常很凉d2：湖畔有家“湖畔”花园，花园里蛙鸣一片d3：“蛙鸣”诗社举办“蛙鸣”诗会倒排文件另一种结构湖畔：2夏夜：1花园：1蛙鸣：2诗社：1诗会：1d1：log3/2：1d2：log3/2：1,6d1：log3：4d2：log3：9,12d2：1/2log3/2：15d3：log3/2：2,10d3：1/2

3、log3：5d3：1/2log3：13词汇表记录表显然，若记录表采用顺序存储，则不利于文档集合的更新。湖畔有家“湖畔”花园，花园里蛙鸣一片文档数湖畔的夏夜常常很凉“蛙鸣”诗社举办“蛙鸣”诗会文档集合倒排文件的使用利用倒排文件进行检索，通常分为三个步骤：1、词汇表检索：即利用查询中的词检索词汇表。2、记录表检索：即检索出所有找到的词的记录表。3、记录表操作：即对检索出的记录表进行后处理，以实现相似度计算、摘要生成等所需要任务。显然，就倒排文件索引结构而言，词汇表检索的速度将决定该索引的效率。对于词汇表的组织一般可采用以下几种方式：1、排序数组：即将

4、词排序顺序存储，采用二分法查找。2、散列：可按词的首字机内编码进行散列，但词的第二个字再散列就不再适合散列处理，一般采用线性表存放。3、B树：4、Trie树：B树和Trie树在《数据结构》中有所介绍。下面仅给出示例加以说明。B树与Trie树结构B树结构花园蛙鸣湖畔夏夜Trie树结构诗会诗社记录表湖畔记录表花园诗会社蛙鸣夏夜显然，Trie树结构不太适合于汉语词汇的组织。你还记得在第三讲切词中所采用的方法吗？推荐方法：所有词存放在一个数组中，词所在的数组下标即为词的编号；而倒排文件中的词汇表即按此词编号顺序存储，即词编号就是词汇表中词所在数组的下标。

5、在对查询文本切词时将查询中的词转换为对应的词编号，利用此词编号即可在词汇表中直接进行定位。这个过程相当于对词的散列。推荐方法示例d1：log3/2：1d2：log3/2：1,6d1：log3：4d2：log3：9,12d2：1/2log3/2：15d3：log3/2：2，10d3：1/2log3：5d3：1/2log3：13词汇数组例如，查询为“花园”，在切词时即可获得该词编号为3，则通过A[3]可立即得到该词所对应的记录表信息。湖畔夏夜花园蛙鸣诗社诗会123456123456倒排文件A倒排文件的存储一般来说，检索系统的词汇表都是长期驻留内存的。

6、而文档集合都是在磁盘上以文件的方式存储。若检索系统的文档集合不大，即倒排文件的记录表完全可以存储在内存中，则此时在对每一个文档进行描述的过程中即可在内存中建立该倒排文件结构。正如第四讲所述。若检索系统的文档集合非常庞大，以致于记录表无法存储在内存中。此时可考虑为每个词所对应的记录表建立一个文件。文件的命名可以利用词汇名或词汇组号。如图所示。显然，此时I/O次数就成为检索系统效率的瓶颈。湖畔：2夏夜：1花园：1蛙鸣：2诗社：1诗会：1d1：log3/2：1d2：log3/2：1,6d1：log3：4d2：log3：9,12d2：1/2log3/2：

7、15d3：log3/2：2,10d3：1/2log3：5d3：1/2log3：13词汇表文件1文件2文件3文件4文件5文件6磁盘倒排文件的使用所谓磁盘倒排文件：是指倒排文件的记录表以文件的方式存储在磁盘上。显然，针对用户所提交的每一个查询词都必须通过读取磁盘文件来获得该词的记录信息。问题：如何才能最大限度地减少I/O次数呢？方法是建立一个内存缓冲区。该缓冲区内维护一个小型的倒排文件子集。此时需要在检索系统中开发一个缓冲区管理程序，来负责缓冲区的维护。磁盘湖畔：2夏夜：1花园：1蛙鸣：2诗社：1诗会：1d1：log3/2：1d2：log3/2：1,

8、6d3：1/2log3：5d3：1/2log3：13词汇表缓冲区调度原则：1、当用户检索词记录表在缓冲区中，则不必I/O操作记录表内存缓