[硕士论文] 垂直搜索引擎的设计与实现(17)

[硕士论文] 垂直搜索引擎的设计与实现

规模增大后，可以采用分组索引，然后再归并索引的策略。该策略是，建立索引的模块根据当时运行系统所在的计算机的内存大小，将索引分为ｎ组，使得每组运算所需内存都小于系统能够提供的最大使用内存的大小。按照倒捧索引的生成算法，生成ｎ组倒捧索引。然后将这ｎ组索引归并，即将相同索引项对应的数据合并到一起，就得到了以索引项为主键的最终的倒捧文件索引，即反向索引。

网页１

网页２索引项１索引项２索引项１索引项２网页１网页２

网页ｋ索引项１

索引项２

索引项３索引项ｋ网页１网页２网页３

图２－９由正向索引建立反向索引

倒排文件机制是一种面向索引项的机制，利用它可以提高检索速度。倒排文

件结构由索引项和索引项出现情况两部分组成。对于每个索引项，都必须有一个列表（称为词汇表）来记录索引项在所有文本中出现的位置。

在倒排索引中，词汇表对空间的需求相对较小，它的增长率为Ｏ（ｎＢ），其中

Ｂ为０到１之间的常量。在实际操作中，Ｂ的取值一般在０．４到０．６之间。这样，

对于１ＧＢ的文本信息来说，词汇表的大小也就是５ＭＢ。可以利用词干提取技术和其他标准化技术来进一步对词汇表进行压缩处理。由于倒排索引要涉及文本中出现的每个索引项，所以索引项出现情况的空间需求为Ｏ（ｎ）。在实际应用中，由

于存放索引项出现情况的过程中，还有一些描述信息，因此索引项出现情况列表所占的空间要比整个信息库中的文本所占的空间多出３０９６到４０％。

为了缩小这种空间需求，可以采用块寻址技术。在块寻址技术中，文本被分

成一个一个的块，倒排文件的索引项出现情况列表记录索引项所出现的块。这些块可以是固定长度的（利用基于文本数据库上的逻辑块结构进行分割），也可以是不定长度的（利用文本本来的属性进行自然分割），比如可以根据文件、Ｗｅｂ页面等进行分割。利用固定大小的块可以提高信息获取的效率，因为如果块的大小不一致，将导致平均访问文档数量的增加（大的块与查询串相匹配的机会会增大，

但是遍历这些块要花更多的时间）。

索引的更新一般分两种情况：一种是小批量的索引扩展；一种是大批量的索

引重建。在索引过程中，并不是每次新的文档加入进去，索引都重新进行一次索引文件的写入操作（文件Ｉ／Ｏ操作非常消耗资源）；而是先在内存中进行索引操作，并根掘一定的批量进行文件的写入。这个批次的Ｉ’日Ｊ隔越大，文件的写入次数