3.4 实战：倒排索引

3.4.1 倒排索引简介

倒排索引是文档检索系统中最常用的数据结构，被广泛地应用于全文搜索引擎。它主要是用来存储某个单词（或词组）在一个文档或一组文档中的存储位置的映射，即提供了一种根据内容来查找文档的方式。由于不是根据文档来确定文档所包含的内容，而是进行了相反的操作，因而称为倒排索引（Inverted Index）。通常情况下，倒排索引由一个单词（或词组）以及相关的文档列表组成，文档列表中的文档或者是标识文档的ID号，或者是指定文档所在位置的URI，如图3-9所示。

从图3-9可以看出，单词1出现在{文档1，文档4，文档13，……}中，单词2出现在{文档3，文档5，文档15，……}中，而单词3出现在{文档1，文档8，文档20，……}中。在实际应用中，还需要给每个文档添加一个权值，用来指出每个文档与搜索内容的相关度，如图3-10所示。

最常用的是使用词频作为权重，即记录单词在文档中出现的次数。以英文为例，如图3-11所示，索引文件中的“MapReduce”一行表示：“MapReduce”这个单词在文本T0中出现过1次，T1中出现过1次，T2中出现过2次。当搜索条件为“MapReduce”、“is”、“simple”时，对应的集合为：{T0, T1, T2}∩{T0, T1}∩{T0, T1}={T0, T1}，即文本T0和T1包含了所要索引的单词，而且只有T0是连续的。

更复杂的权重还可能要记录单词在多少个文档中出现过，以实现TFIDF（Term Frequency-Inverse Document Frequency）算法，或者考虑单词在文档中的位置信息（单词是否出现在标题中，反映了单词在文档中的重要性）等。使用TF-IDF等综合信息作为权重的倒排索引详见第11章，本节将针对英文文本，使用词频作为权重，讲解如何使用MapReduce分析、设计和实现倒排索引。

3.4.2 分析与设计

本节实现的倒排索引主要关注的信息为：单词、文档URI及词频，如图3-11所示。但是在实现过程中，索引文件的格式与图3-11会略显不同，以避免重写OutputFormat类。同时，本节所涉及的设计思想还会运用一些小技巧，尽量避免使用本书第5章所涉及的内容，方便读者入门。下面根据MapReduce的处理过程给出倒排索引的设计思路。

1.Map过程

首先使用默认的TextInputFormat类对输入文件进行处理，得到文本中每行的偏移量及其内容。显然，Map过程首先必须分析输入的＜key, value＞对，得到倒排索引中需要的三个信息：单词、文档URI和词频，如图3-12所示。这里存在两个问题：第一，＜key, value＞对只能有两个值，在不使用Hadoop自定义数据类型的情况下，需要根据情况将其中两个值合并成一个值，作为key或value值；第二，通过一个Reduce过程无法同时完成词频统计和生成文档列表，所以必须增加一个Combine过程完成词频统计。

这里将单词和URI组成key值（如“MapReduce：1.txt”），将词频作为value，这样做的好处是可以利用MapReduce框架自带的Map端排序，将同一文档的相同单词的词频组成列表，传递给Combine过程，实现类似于WordCount的功能。

2.Combine过程

经过map方法处理后，Combine过程将key值相同的value值累加，得到一个单词在文档中的词频，如图3-13所示。如果直接将图3-13所示的输出作为Reduce过程的输入，在Shuffle过程时将面临一个问题：所有具有相同单词的记录（由单词、URI和词频组成）应该交由同一个Reducer处理，但当前的key值无法保证这一点，所以必须修改key值和value值。这次将单词作为key值，URI和词频组成value值（如“1.txt：1”）。这样做的好处是可以利用MapReduce框架默认的HashPartitioner类完成Shuffle过程，将相同单词的所有记录发送给同一个Reducer进行处理。

3.Reduce过程

经过上述两个过程后，Reduce过程只需将相同key值的value值组合成倒排索引文件所需的格式即可，剩下的事情就可以直接交给MapReduce框架进行处理了，如图3-14所示。索引文件的内容除分隔符外与图3-11解释相同。

4.需要解决的问题

本节设计的倒排索引在文件数目上没有限制，但是单个文件不宜过大（具体值与默认HDFS块大小及相关配置有关），要保证每个文件对应一个split。否则，由于Reduce过程没有进一步统计词频，最终结果可能会出现词频未统计完全的单词。可以通过重写InputFormat类将每个文件作为一个split，避免上述情况。或者执行两次MapReduce，第一次MapReduce用于统计词频，第二次MapReduce用于生成倒排索引。除此之外，还可以利用复合键值对等实现包含更多信息的倒排索引。读者可以尝试在阅读完本书第5章后，修改或优化本节给出的代码。

3.4.3 倒排索引完整源码

根据3.4.2节的分析而编写的倒排索引完整源代码如下所示，对代码的详细分析以注释的形式给出。

import java.io.IOException;
import java.util.StringTokenizer;


import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.input.FileSplit;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.util.GenericOptionsParser;


public class InvertedIndex {


    public static class InvertedIndexMapper extends
                  Mapper＜Object, Text, Text, Text＞{


       private Text keyInfo = new Text(); //存储单词和URI的组合
       private Text valueInfo = new Text(); //存储词频
       private FileSplit split;   //存储Split对象


       public void map(Object key, Text value, Context context)
                   throws IOException, InterruptedException{


            //获得＜key, value＞对所属的FileSplit对象
            split = (FileSplit)context.getInputSplit();


            StringTokenizer itr = new StringTokenizer(value.toString());
            while(itr.hasMoreTokens()){
                  //key值由单词和URI组成，如“MapReduce：1.txt”
                  keyInfo.set(itr.nextToken() + "：" + split.getPath().toString());
                  //词频初始为1
                  valueInfo.set("1");
                  context.write(keyInfo, valueInfo);
             }
       }
}


public static class InvertedIndexCombiner extends
           Reducer＜Text, Text, Text, Text＞{
       private Text info= new Text();


       public void reduce(Text key, Iterable＜Text＞ values, Context context)
                 throws IOException, InterruptedException{
           //统计词频
           int sum = 0;
           for(Text value ：values){
                 sum += Integer.parseInt(value.toString());
           }


           int splitIndex = key.toString().indexOf("：");
           //重新设置value值由URI和词频组成
           info.set(key.toString().substring(splitIndex + 1) + "：" + sum);
           //重新设置key值为单词
           key.set(key.toString().substring(0, splitIndex));
           context.write(key, info);
        }
    }


    public static class InvertedIndexReducer extends
                  Reducer＜Text, Text, Text, Text＞{
           private Text result = new Text();


           public void reduce(Text key, Iterable＜Text＞ values, Context context)
                  throws IOException, InterruptedException{
           //生成文档列表
           String fileList = new String();
           for(Text value ：values){
                 fileList += value.toString() + ";";
           }
           result.set(fileList);


           context.write(key, result);
        }
     }
     public static void main(String[] args) throws Exception{
         Configuration conf = new Configuration();
         String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();
         if(otherArgs.length != 2){
                System.err.println("Usage：invertedindex ＜in＞ ＜out＞");
              System.exit(2);
         }


         Job job = new Job(conf, "InvertedIndex");
         job.setJarByClass(InvertedIndex.class);
         job.setMapperClass(InvertedIndexMapper.class);
         job.setMapOutputKeyClass(Text.class);
         job.setMapOutputValueClass(Text.class);
         job.setCombinerClass(InvertedIndexCombiner.class);
         job.setReducerClass(InvertedIndexReducer.class);
         job.setOutputKeyClass(Text.class);
         job.setOutputValueClass(Text.class);
         FileInputFormat.addInputPath(job, new Path(otherArgs[0]));
         FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));
         System.exit(job.waitForCompletion(true) ? 0 ：1);
   }
}