使用MapReduce实现反向索引

（1）案例说明

反向索引也称为倒排索引或反向档案，用来存储某个单词在一个文档或一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构，搜索引擎就是利用反向索引来进行搜索的。通过反向索引可以快速地通过文章内的单词反向检索获取包含这个单词的文档标识列表，从而完成巨大文件的快速搜索。

以下用一个简单的示例来介绍反向索引实现原理。假设有两个文件a. txt 和b. txt，其内容如下：

通过反向索引后，得到的结果如下：

整个实现过程：map 函数解析输入的文档，输出一系列<单词，文档标识及单词次数>的键值对。MapReduce 将键值对按照单词进行排序，然后局部合并相同单词的文档，形成一批“ <单词，list（文档标识及单词次数） >”。reduce 函数再将这些键值对进行进一步的排序、合并，最后输出反向索引结果。MapReduce 反向索引实现原理示意图如图4.20 所示。

图4.20　MapReduce 反向索引实现原理示意图

（2）数据集

本案例的数据集为“InverseData.zip”，包含三个英文文件，first.txt、second.txt 和third.txt。首先，需要将这三个文件上传到HDFS 的“/mrtest/in/”目录下。文件上传到DFS 的方法可以选择以下两种方法中的任意一种。

第一种方法：将三个文件复制到master 节点的“/home/apache/data/test”目录下，然后打开终端，创建目录“hdfs dfs -mkdir -p /mrtest/in”。上传文件：切换到“/home/apache/data/test”目录下，执行命令进行文件上传“hdfs dfs -put first.txt /mrtest/in”“hdfs dfs -put second.txt /mrtest/in”“hdfs dfs -put third.txt /mrtest/in”。查看文件“hdfs dfs -ls /mrtest/in/”，结果如图4.21 所示。

图4.21　linux 终端上传文件

图4.22　Eclipse 上传文件

第二种方法：直接通过Eclipse 远程操作。首先在DFS Locations 的master 节点上单击鼠标右键，选择“Create new directory”，创建新目录“mrtest”并在其下创建目录“in”，然后在“in”目录上单击鼠标右键，选择“Upload files to DFS”，将三个数据文件上传到DFS；最后刷新Eclipse 的DFS Locations，查看文件是否上传成功，如图4.22 所示。

（3）案例开发思路

本案例的最终目标是找出单词出现的文档列表及单词在文档中出现的次数，最终输出是“ <单词，文档列表及单词次数>”的映射。在编写MapReduce 程序之前，必须先明确Map和Reduce 任务的输入输出的<key，value>对。以前面的例子来说，要输出结果“hello a.txt：2；b.txt：2”，则Reduce 输出为“ <hello，a.txt：2；b.txt：2 >”。为了达到这个目标，首先在Map端将每行数据进行解析，得到形如“ < hello，a. txt：1 >”“ < hello，a. txt：1 >”“ < hello，b.txt：1 >”“ <hello，b.txt：1 >”形式的一批键值对。经过MapReduce 的排序合并过程，产生Reduce 的输入键值对为“ <hello，list（a.txt：1，a.txt：1，b.txt：1，b.txt：1） >”。此时，需要在Reduce 任务中将每个key 的value 值列表进行处理，将同一个文件中的单词个数进行累加，从而得到最终的输出结果。

（4）程序实现

1）构建MapReduce 项目

打开Eclipse，单击File→New→Project，选择“Map/Reduce Project”，单击“Next”按钮。在弹出的对话框中，输入项目名称为“mrproject”，项目名称可以自己设置，如图4.23 所示。单击“Configure Hadoop install directory”，进入图4.24 进行Hadoop 安装路径的设置。

在开发项目前，还需要导入jar 包。选中项目，右击鼠标，选择“Build Path→Configure Build Path”命令。单击“Libraries→Add External JARs”，将本地“hadoop/share/hadoop”目录下相应文件夹下的jar 包导入即可。或者在工程中新建文件夹名为“lib”，将“hadoop/share/hadoop”下文件夹中的jar 包复制进去，然后使用“bulid path”进行导入，最后单击“Add JARs”，选择工程下的lib 文件夹。

图4.23　新建Map/Reduce 项目

图4.24　配置Hadoop 安装路径(https://www.xing528.com)

在src 目录上单击鼠标右键，新建一个名为“com.mapreduce.test”的包，如图4.25 所示。

在包“com.mapreduce.test”上单击鼠标右键，新建类“InverseIndex”，如图4.26 所示。

注意，需要设置Eclipse 的编码为UTF-8，具体为Windows→Preferences→Workspace，设置“Text file encoding”为“UTF-8”。

图4.25　新建包

图4.26　新建类

2）完整的程序实现

定义主类InverseIndex，在其中分别定义Mapper 类和Reducer 类。

①定义Mapper 类，具体如下：

②定义Reducer 类，具体如下：

③主类InverseIndex 的main 方法中对Job 进行设置，具体如下：

3）项目运行过程中配置参数

在InverseIndex.java 上单击鼠标右键，选择“Run As→Run Configurations”，在弹出的对话框的左侧窗口中单击“Java Application”下的“InverseIndex”。在对应的右侧窗口中选择“Arguments”，在“Program arguments”中输入参数“hdfs：/ /master：9000/mrtest/in/”和“hdfs：/ /master：9000/mrtest/out/”，也就是文件的输入输出路径，如图4.27 所示。

图4.27　配置参数

4）项目运行结果

项目运行的部分结果如图4.28 所示。

图4.28　项目运行结果

从结果可以看出，输出结果即是单词的反向索引。