新闻动态
搜索引擎的归并法
https://www.sytm.net 发布日期:2013/9/1 8:16:42

排序法分配固定大小内存来建立索引,所以无论要建立索引的文档集合有多大,都可以通过这种方式完成。但是如上所述,在分配的内存定额被消耗光时,排序法只是将中间结果写入磁盘,而词典信息一直在内存在中进行维护,随着处理的文档越来越多,词典里包含的词典项越来越多,所以占用内存越来越大,导致后期中间结果可用内存越来越少。归并法对此做出了改进,即每次讲内存中数据写入磁盘时,包括词典在内的所有中间结果信息都被写入磁盘,这样内存所有内容都可以被清空,后续建立索引可以使用全部的定额内存。

归并法的整体流程和排序法大致相同,也是分为两个大的阶段,首先在内存里维护中间结果,当内存占满后,将内存数据写入磁盘临时文件,第二阶段临时文件进行归并形成最终索引。尽管从整体流程看,和排序大致相同,但是在具体实现方式上有较大差异。

首先,排序法在内存中存放的是词典信息和三元组数据,在建立索引的过程中,词典和三元组数据并没有直接的联系,词典只是为了将单词映射为单词ID。而归并法则是在内存中建立一个完整的内存索引结构,相当于对目前处理的文档子集单独在内存中建立起了一整套倒排索引,和最终索引相比,其结构和形式是相同的,区别只是这个索引只是部分文档的索引而非全部文档的索引。

其次,在将中间结果写入磁盘临时文件时,归并法会将整个内存分倒排索引写入临时文件,对于某个单词的倒排列表在写入磁盘文件时,将词典项放在列表最前端,之后跟随相应的倒排列表,这样依次将单词和对应的倒排列表写入磁盘文件,随后彻底清空所占内存。而排序法只是将三元组数据排序写入磁盘临时文件,词典作为一个映射表一直存储在内存中。

在最后的临时文件合并为最终索引的过程中,两者也有差异。排序法因为保护的是有序三元组信息,所以在合并时,是对同一单词的三元组依次进行合并;而归并法的临时文件则是每个单词对应的部分倒排列表,所以在合并时针对每个单词的倒排列表进行合作,形成这个单词的最终倒排列表、另外,归并法在最后的合并过程中形成最终的词典信息。

更多阅读
  • 线上订货系统让全渠道销售触手可及 近年来,中国电商平台发展迅速,以淘宝、京东等电商为代表的新兴商业模式被越来越多的客户所推崇,中国网民...
  • 添美订货系统十月更新日志 添美订货系统是东北开发订货软件的厂商,该订货软件实现了全渠道全客户端的覆盖。拥有南方的易订货、订货宝...
  • 三好街的渠道订货系统 现如今,人们对电子数码产品的需求与日俱增,但是不少电子数码产品企业的生意却未见起色,为什么?以三好街...
返回列表
© 2010 TianMei Technology All rights reserved. ICP:辽B2-20150138辽公网安备 21010202000010号  目录概览