新闻动态
索引的两遍文档遍历法
https://www.sytm.net 发布日期:2013/8/25 6:08:48

索引两遍文档顾名思义就是搜索引擎需要对文档集合进行两遍扫描,这种遍历索引是搜索引擎优化比较有深度的理论addb基础。值得注意的一点是:此方法完全是在内存里完成索引的创建过程的,而另外两种方法则是通过内存和磁盘相互配合来完成索引建立任务的。

第一遍文档索引

搜索引擎在第一遍扫描文档集合时,该方法并没有立即开始建立索引,而是收集一些全局的统计信息。比如文档集合包含的文档个数N,文档集合内所包含的不同单词个数M,每个单词在多少个文档中出现过的信息DF。将所有单词对应的DF值全部相加,就可以知道建立最终索引产生的内存大小是多少,因为一个单词对应的DF值如果是10,说明有10个文档包含这个单词,那么这个单词对应的倒排列表应该包括10项内容,每一项记载某个文档ID和单词在该文档对应的出现次数TF。

搜索引擎在获得了上述3项信息后,就可以知道最终索引的大小,于是在内存分配足够大的空间,用来存储倒排索引的内容。遍历时在内存中可以开辟一个连续的存储区域,因为第一遍扫描已经获得了每个单词的DF信息,所以将连续存储区划分成不同大小的片段,词典内某个单词根据自己对应的DF信息,可以通过指针,指向属于自己的内存片段的起始位置和终止位置,将来在第二遍扫描时,这个单词对应的倒排列表信息好会被填充进这个片段中。

综上所述,第一遍扫描的主要目的是获得一些统计信息,并根据统计信息分配内存等资源,同时建立好单词行对应倒排列表在内存中的位置信息,即主要做些资源准备工作。

第二遍文档遍历

搜索引擎在第二遍文档遍历的时候,开始真正建立每个单词的倒排列表信息,即对某个单词来说,获得包含这个单词的每个文档的文档ID,以及这个单词在文档中出现的次数TF,这样就可以不断的填充第一遍扫描所分配的内存空间。当第二遍扫描结束的时候,分配的内存空间正好被填充满,而每个单词用指针所指向的内存区域“片段”,其起始位置之间的数据就是这个单词对应的倒排列表。

经过两遍的扫描建立的索引完成后,搜索引擎即可将内存倒排列表和词典信息写入磁盘,这样就完成了建立索引过程。从上述流程可以看出,索引的构建完全是在内存中完成的,这就要求内存一定要足够大,否则如果文档集合太大,内存未必能够满足需求。

从另一个角度来讲,在建立索引的过程中,从磁盘读取文档并解析文档基本是最消耗时间的一个步骤,而两遍扫描法因为要对文档集合进行两遍遍历,所以从速度上不占优势,在实际中采用这种方法的系统并不常见。

更多阅读
返回列表
© 2010 TianMei Technology All rights reserved. ICP:辽B2-20150138辽公网安备 21010202000010号  目录概览