文本索引和搜索

《文本索引和搜索》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章:文本索引和搜索任飞亮东北大学自然语言处理实验室2010大纲索引和搜索的概念倒排文件索引后缀数组索引签名文件索引文本搜索技术大纲索引和搜索的概念倒排文件索引后缀数组索引签名文件索引文本搜索技术应用索引的例子检索的目的是为了在一大堆的信息中发现自己感兴趣的信息;但是,当有了一大堆资料之后,并不能立即开始搜索.为什么?图书馆实例在检索前必须建立索引!索引的定义所谓建立索引,是指将待搜索的信息进行一定的分析,并将分析的结果按照一定的组织方式存储起来,通常是存储在文件中.存储了分析结果的文件的集合就是所谓

2、的索引.准确定义:索引（Index）是一种数据结构，其将关键词与包含该关键词的文档（或关键词在文档中的位置）建立了一种映射关系，以加快检索的速度。文本搜索的概念不使用任何索引技术，而快速的在给定文本或文本集合中查找是否出现某一关键词，这种技术通常被称为单模式匹配应用领域信息过滤、检索结果后处理等常用算法BFKMPBM大纲索引和搜索的概念倒排文件索引后缀数组索引签名文件索引文本搜索技术倒排索引主要内容倒排索引简介倒排文件的使用倒排文件的建立倒排文件的维护倒排文件的压缩倒排文件的性能分析词汇表的存

3、取倒排索引主要内容倒排索引简介倒排文件的使用倒排文件的建立倒排文件的维护倒排文件的压缩倒排文件的性能分析词汇表的存取倒排文件简介倒排文件(InvertedFile)也称倒排索引，索引对象是文档或文档集合中的单词等，用来存储这些单词在一个文档或者一组文档中的存储位置，是对文档或文档集合的一种最常用的索引机制倒如:有些书往往在最后提供的索引(单词—页码列表表)就可以看成是一种倒排索引.即通过一些关键词,在全书中检索出与之相关的部分;这种思想也被应用于数据库技术中,即对数据库中需要经常进行检索的域建立索引结构,从而实

4、现快速查询.在关系数据库上建索引姓名地址姓名索引张三哈尔滨工业大学张三查询式:姓名=“张三”如上图所示,对”姓名”字段使用便于查找的数据结构(如排序数组、B树或散列等)建立索引，当查询某个名字时，就不需要从头至尾遍历整个字段，而可以快速找到该姓名，从而查找出与其对应的信息。倒排文件组成词汇表(vocabulary)+记录表(postinglist)词汇表文档或文档集合中所包含的所有不同单词的集合β占用的空间V=cn，c是常数，n是文档集合的大小，β是一个0到1之间的常数，一般在0.4到0.6之间记录表对于词汇表中的每一

5、个单词在文档中出现的位置或者其出现的文档编号构成的列表占用的空间P=cn，其中c是常数，随着记录表中存储的信息丰富程度而变化记录表既可以存储文本中单词的编号位置，也可以指向单词首字母的字符位置，还可以是其所在的文档编号，即可以根据不同的应用需求，使用不同的寻址粒度(addressinggranularity)对单文档的倒排文件对文档集合的倒排文件倒排索引主要内容倒排索引简介倒排文件的使用倒排文件的建立倒排文件的维护倒排文件的压缩倒排文件的性能分析词汇表的存取倒排文件的使用三个步骤词汇表检索将出现在查询（Que

6、ry）中的单词分离出来，并在词汇表中进行检索。记录表检索检索出所有找到的单词对应的记录表。记录表操作对检索出的记录表进行后处理，以实现短语查询、相邻查询或者布尔查询。词汇表检索规模相对较小的独立文件，全部调入内存常用数据结构树状结构，如：B树和Trie树前缀查询和范围查询散列检索速度快，但是不支持前缀查询和范围查询等需要根据实际需求情况，决定采用什么样的数据结构。记录表操作如果查询中仅包含一个单词，则在词汇表中找到该单词，并取出其对应的记录表即完成了检索操作如果查询中包含多个单词，则需将各个单词检索出的记录

7、表进行合并同步遍历记录表，实现合并过程倒排索引主要内容倒排索引简介倒排文件的使用倒排文件的建立倒排文件的维护倒排文件的压缩倒排文件的性能分析词汇表的存取倒排文件的建立建立倒排文件的最关键问题是由于需要索引的文档数量过大，有可能导致不能在内存中存储整个倒排文件。根据索引文档的大小，介绍三种倒排文件的建立方法。基于内存的方法基于排序的方法基于归并的方法倒排文件的建立建立倒排文件的最关键问题是由于需要索引的文档数量过大，有可能导致不能在内存中存储整个倒排文件。根据索引文档的大小，介绍三种倒排文件的建立方法。

8、基于内存的方法基于排序的方法基于归并的方法基于内存的方法输入：文档集合输出：基于文档集合的倒排文件算法：(1)初始遍历文档集合。对于每一个单词w，统计包含该单词的文档数f；w(2)在内存中建立长度为∑fw∈词表w的数组，并且对于每