使用复合键优化倒排索引

巧用复合键优化倒排索引程序

之前写了一个倒排索引的程序，但是可以注意在到生成的索引文档中，一个单词对应的文档并非是按照词频的大小进行排列的。这不是我们最想要的结果，我们希望对应的文档按照词频的大小进行排列。

这里我们使用复合键来完成对文档的排序。

巧用复合键可以达到一些优化效果，比如说将多个细粒度的键值对合并为一个处理度的键值对，这样可以减小集群中网络的开销。

 比如：

可以优化为：<a,<b:1,c:3,d:5,e:8,f:4>>

上面的例子将5个<K,V>优化为一个<K,V>，减小了网络的开销。特别是当数据量很大的时候，这样合并的机会就会很多。优化的效果也会很客观。

当然，我们亦可以使用复合键来完成排序功能。

在倒排索引中，我们希望单词对应的文档按照词频大小来排列。但是如果在本地进行排序的话往往因为数据量很大而出现各种问题。此时，我们想到MapReduce框架，在Mapper过程中，框架会自动进行排序。

因此，我们将要进行排序的词频和原来的K一起，组成复合键作为Reducer的输入。因此可以看到在Combiner类中，输出发生变化。如图：

 

好了，接下来我们该写reduce()方法了，我们需要按照词频输出单词所在的文档，而实际上，reduce()的输入已经是按照词频输入了。因此，我们看下面伪代码：

MyReducer class start

String preKey=null;

String preValue="";

Reduce method start

if(preKey==null)

给preKey和preValue赋值

if(preKey!=null)

if(preKey.equals(strs[0])){

为preValue添加内容

}

if(!preKey.equals(strs[0])){

将preKey和preValue输出

重置preKey和preValue的值

preKey = strs[0];

}

}

}

Reduce method end

将preKey和preValue输出

MyReducer class end

 

至此，代码优化工作已将完成，但是，问题又来了，因为Combiner输出的时候K值包含词频，所以如果按照原来的方式Shuffle的话，会将统一单词映射到不同的Reducer中，显然这是不对的，因此，我们重写getPartition()方法。伪代码如下：

MyPartitioner class start

getPartition method start

  调用HashPartitioner类的getPartition()方法，并将从K中提取出的单词那部分作为参数

getPartition method end

MyPartitioner class end

 

优化的代码见附件。