新闻动态
搜索引擎的排序方法
https://www.sytm.net 发布日期:2013/9/1 7:31:07

两遍遍历发在建立索引分过程中,对内存的消耗要求较高,不同的文档集合包含文档数量大小不同,其所需内存大小事不确定的。当文档集合非常大时,可能因内存不够,导致无法建立索引。排序法对此做出了改进,改方法在建立索引的过程中,始终在内存中分配固定大小的空间,用来存放词典信息和索引的中间结果,当分配的空间被消耗光的时候,把中间结果写入磁盘,清空内存里中间结果所占空间,以用做下轮存放索引中间结果的存储区。这种方法由于只需要固定大小的内存,所以可以对任意大小的 文档集合建立索引。

中间结果内存排序的方法是读入文档后,对文档进行编号,赋予唯一的文档ID,并对文档中出现的单词,通过查词典将单词转为对应的单词ID,如果词典中没有这个单词,说明是第一次碰到,则赋予单词以唯一的单词ID并插入词典中。在完成看由单词映射为单词ID的过程之后,可以对改文档内每个单词建立一个三元组,这个三元组就是单词对应文档的倒排列表项,将这个三元组追加中间结果存储区末尾。如果文档内的所有单词都经过如此处理,形成三元组序列的形式,则该文档被处理完成,开始依次处理下一文档,过程与此类似。

随着新的文档不断被处理完成,存储三元组集合的中间结果所占用的内存会越来越大,词典里包含的新单词也越来越多,当分配的内存定额被占满时,该方法对三元组中间结果进行排序。排序的原则是:主键是单词ID,即首先要按照单词ID由小到大排序;次键那是文档ID,即在相同单词ID的情况下,按照文档ID由小到大排序。通过以上方式,三元组变为有序形式。为了腾出内存空间,将排好序的三元组写入磁盘临时文件中,这样就空出内存来进行后续文档的处理。这里需要注意的是:在建立索引的过程中,词典是一直存储在内存中的,每次清空内存只是将中间结果写入磁盘。随着处理文档的增加,词典占用的内存会逐渐增加,由于分配内存是固定大小,而词典占用内存越来越大,也就是说,越往后,可用来存储三元组的空间是越来越是少。

之所以要对中间结果进行排序,主要是为了方便后续的处理。因为每一轮处理都会在磁盘产生一个对应的中间结果文件,当所有文档处理完成后,在磁盘中会有多个中间结果文件,为了产生一个对应的中间结果文件,当所有文档处理完成后,在磁盘中会有多个中间结果文件,为了产生最终的索引,需要将这些中间结果文件合并。

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