基于文本的索引构建技术.ppt

《基于文本的索引构建技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章基于文本的索引构建技术本章内容顺序文档索引基于内存单次扫描的索引构建技术基于块的排序索引技术本章小结倒排文档索引概要概要基于文本的检索技术信息检索技术基于内容的检索技术概要概要顺排文档把记录按照一定顺序完整地组织起来如：物品数据库依据物品记录号顺序进行建立。顺排文档（SequentialFile）把顺排文档中具有检索属性的项目信息抽取出来，重新排列组织成新的数据文档如：将物品数据库中的价格数据项抽取出来，依据物品价格有高到低重新建立新的索引文档。倒排文档（InvertedFile）3.1基于块

2、的排序索引技术3.1.1索引文档建立必须考虑的硬件性能3.1基于块的排序索引技术利用缓冲区压缩数据硬件性能连续存放数据块内存调用利用磁盘3.1基于块的排序索引技术内存调用：访问内存数据比访问磁盘数据快得多（5×10−9sVS2×10−8s），尽可能地把数据放在内存中。连续存放数据块：磁盘的寻道时间平均为4ms-5ms，连续读取的数据块也应该在磁盘上连续存放。3.1基于块的排序索引技术利用缓冲区：操作系统往往以数据块为单位进行读写。数据块的大小通常为8KB、16KB、32KB或64KB。压缩数据：数据

3、从磁盘传输到内存是由系统总线而不是处理器来实现的，这意味着在磁盘I/0时处理器仍然可以处理数据。3.1基于块的排序索引技术利用磁盘：系统的服务器往往有数GB甚至数十GB的内存，可以利用服务器磁盘空间大小一般比内存大小要高几个数量级：TB-PB。3.1基于块的排序索引技术3.1.2基于块的排序索引方法首先扫描一篇文档集合得到所有具有检索意义的词语的“此项-文档ID”数据集；然后依据此项的索引文档及的主键和文档ID为次键进行排序；最后将每个此项的文档ID组织成为倒排记录表，并计算此项频率或文档频率的统计

4、量。思想图3-1桂林电子科技大学-新闻模块目录实例3.1基于块的排序索引技术3.1基于块的排序索引技术图3-2桂林电子科技大学-新闻内容文档实例3.1基于块的排序索引技术表3-1桂林电子科技大学-新闻文档集统计数据表3.1基于块的排序索引技术基于磁盘的外部排序算法ESA（ExternalSortingAlgorithm）核心在索引排序时，尽量减少磁盘寻道次数基础BSBI算法（BlockedSort-basedIndexingAlgorithm,基于块的排序算法）3.1基于块的排序索引技术BSBI算法

5、步骤：1将文档集分割成多个大小相等的部分4将所有的中间文件合并成最终的索引2将每个部分的词项ID—文档ID对排序3将中间产生的临时排序结果存放到磁盘中3.1基于块的排序索引技术选择合适的块算法，下图的算法将每个块的倒排索引存入文件中f1…fn，最后合并为fmerged。图3-3基于块的排序索引算法3.1基于块的排序索引技术依据图3-3的算法将待合并的倒排记录表（两个数据块）从磁盘读入内存，然后在内存中合并后写入磁盘（见图3-4）。图3-4基于块的排序方法合并示意图3.2基于内存单次扫描的排序构建技术

6、基于内存单次扫描的索引算法SPIMI(single-passin-memoryindexing)：每块采用不同的词典，将每个块的词典写入磁盘，对于下一个块则重新采用新的词典。只要硬盘空间足够大，SPIMI就能够索引任何大小的文档集。原因基于块的排序索引算法具有很好的可扩展性，但是需要一种将所有词项放到内存。对于大规模的文档集来说，该数据结构会很大以致在内存中难以存放。3.2基于内存单次扫描的排序构建技术SPIMI算法的步骤：ClicktoaddTitleClicktoaddTitleClicktoa

7、ddTitle2将所有的中间文件合并成最终的索引1处理文档，直到内存不足，写入磁盘3.2基于内存单次扫描的排序构建技术图3-5SPIMI算法的块倒排索引生成算法3.2基于内存单次扫描的排序构建技术SPIMI算法与BSBI的区别：通过判定循环动态增加排序记录表的，倒排记录表的SPIMI算法直接在倒排记录表中增加定位符项，且开始就需要处理形成所有项的“词项－文档ＩＤ”并进行排序BSBI算法3.3顺排文档索引将文档中的每一条记录依次去匹配用户的检索提问集合，文档处理完毕后，将各提问的命中结果归并分发给有关

8、用户。思想用文档中记录一条一条去匹配提问的，是顺序对文档记录检索的方法定义采用列表处理方法将提问逻辑式（检索式）变换成等价的提问展开式，按提问展开表的内容对顺排文档的每篇文献进行检索关键技术表展开法、逻辑树法等常见方法3.3顺排文档索引3.3.1表展开法索引1968年，日本学者菊池敏典提出，又称“菊池敏典算法”。目前主要用于面向定向服务的检索系统，旨在将代表用户的逻辑提问式转换成检索表的形式，该检索表规定了表内容走向和检索命中与否的判断，检索时根据表内容走向及其他相关