倒排索引
倒排索引是文档检索系统中最常见的数据结构，被广泛的应用于搜索引擎。它是一种根据内容查找文档的方式。由于不是根据文档来找内容，而是根据进行了相反的操作，因此叫做倒排索引。
倒排索引的一个简单结构如下图所示：
单词文档列表
最常见的是使用词频作为权重，即单词在一个文档中出现的次数。如图所示，已知3个文档。
则他们的索引文件为
因此，当搜索条件为“MapReduce”“is”“simple”的时候，对应的集合为{(0.txt,1),(1.txt,1),(2.txt,2)}且{(0.txt,1),(1.txt,2)}且{(0.txt,1),(1.txt,1)}={0.txt,1.txt}
即关键字出现在0.txt和1.txt中。
以上只是词频作为权重，当然实际应用中权重可能很复杂，这里仅仅以词频为权重进行编码。
结合MapReduce框架的执行流程，倒排索引的处理步骤设计如下：
InputFormat处理后：
map()方法处理后：(之所以把文本位置放到K,为了方便Mapper处理)
Mapper框架进行处理：(之所以把文本位置放到K,为了方便此处处理)
Combiner进行处理：
为了方便Reducer框架进行处理，Combiner的输出需要改变一下：
Reducer框架进行处理：
Reduce()方法进行处理
以上过程转化为代码，仅仅需要重写map(),combine(),reduce()方法即可。
需要注意的是，对于输入输出的处理，上一环节的输入格式应该和上一环节的输出格式一样。