基于二进制数组(位图)的整数序列合并算法
2008年01月17日 星期四 09:38
搜索引擎检索时,常常要将两个结果进行组合处理,例如查询“中国北京”,则需要将包含“中国”和“北京”的文档编号序列进行合并的操作。常用的算法有归并,先排序后去重等,但这些算法在大数据量的情况下,如对包含“中国”的10万个文档编号序列和包含“北京”的8万个文档编号序列进行组合时,效率比较低,无法满足搜索引擎高速的检索要求。我们引入了基于二进制数组的算法来解决这个问题。
基于二进制数组的整数序列合并算法是一种高速的多个整数序列组合的算法。它的基本原理是将各整数序列保存在一个二进制的数组当中,然后对这些二进制数组进行并,或的运算。 下面详细介绍一下此算法的处理过程。 1. 将整数序列转为二进制数组。 先申请一个二进制数组,其大小为有可能出现的最大的整数值,如500万,如图所示。 (图1)
假设有5个整数组成的序列{2,3,200,7000,12000},则我们可以将这个序列保存在二进制数组当中,如图2所示,第n位如果为1,则表示n存在于这个序列中: (图2)
2. 对两个序列进行位运算。 (图3)
整数序列{2,3}即是我们最终所要的结果。
|