程序员人生 网站导航

【Hadoop基础教程】9、Hadoop之倒排索引

栏目:服务器时间:2015-03-12 08:49:00

开发环境


硬件环境:Centos 6.5 服务器4台(1台为Master节点,3台为Slave节点)
软件环境:Java 1.7.0_45、hadoop⑴.2.1

1、倒排索引


倒排索引是文档检索系统中最经常使用的数据结构,被广泛用于全文搜索引擎。它主要是用来存储某个单词(或词组)在1个文档或1组文档的存储位置的映照,即提供了1种根据内容来查找文档的方式。由于不是根据文档来肯定文档所包括的内容,而是进行了相反的操作(根据关键字来查找文档),因此称为倒排索引(Inverted Index)。通常情况下,倒排索引由1个单词(词组)和相干的文档列表(标示文档的ID号,或是指定文档所在位置的URI)组成,以下图所示:

 倒排索引结构

从上图可以看出,单词1出现在{文档1、文档4、文档13、……}中,单词2出现在{文档3、文档5、文档15、…..}中,而单词3出现在{文档1、文档8、文档20、….}中,还需要给每一个文档添加1个权值,用来指出每一个文档与搜素内容相干的相干度,以下图所示:

 添加权重的倒排索引

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

 添加权重的倒排索引

2、Map进程

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

 map过程

这里将单词和URI组成Key值(如“MapReduce :1.txt”),将词频作为value,这样做的好处是可以利用MapReduce框架自带的Map端排序,将同1文档的相同单词的词频组成列表,传递给Combine进程,实现类似于WordCount的功能。
Map进程核心代码实现以下,详细源码请参考:InvertedIndexsrccomzonesionhdfsInvertedIndex.java。

public static class InvertedIndexMapper extends 
    Mapper<Object,Text,Object,Text>{
    private Text keyInfo = new Text();//存储单词和URI的组合
    private  Text valueInfo = new Text();//存储词频
    private FileSplit split;//存储Split对象
    @Override
    public void map(Object key, Text value, Context context)
            throws IOException, InterruptedException {
        split = (FileSplit)context.getInputSplit();
        StringTokenizer itr = new StringTokenizer(value.toString());
        while(itr.hasMoreTokens()){
            //key值由单词和URI组成
            keyInfo.set(itr.nextToken()+":"+split.getPath().toString());
            valueInfo.set("1");
            context.write(keyInfo, valueInfo);//输出:<key,value>---<"MapReduce:1.txt",1>
        }
    }
}

3、Combine进程

经过map方法处理以后,Combine进程将key值相同的value值累加,得到1个单词在文档中的词频,以下图所示。如果直接将Map的输出结果作为Reduce进程的输入,在Shuffle进程时将面临1个问题:所有具有相同单词的记录(由单词、URI和词频组成)应当交由同1个Reduce处理,但当前key值没法保证这1点,所以必须修改key值和value值。这次将单词作为key值,URI和词频作为value值。这样做的好处是可以利用MapReduce框架默许的HashPartitioner类完成Shuffle进程,将相同单词的所有记录发送给同1个Reducer处理。

 combine过程

Combine进程核心代码实现以下,详细源码请参考:InvertedIndexsrccomzonesionhdfsInvertedIndex.java。

public static class InvertedIndexCombiner 
    extends Reducer<Text, Text, Text, Text>{
    private Text info = new Text();
    @Override
    protected void reduce(Text key, Iterable<Text> values,Context context)
            throws IOException, InterruptedException {
        //输入:<key,value>---<"MapReduce:1.txt",list(1,1,1,1)>
        int sum = 0;
        for(Text value : values){
            sum += Integer.parseInt(value.toString());
        }
        int splitIndex = key.toString().indexOf(":");
        info.set(key.toString().substring(splitIndex+1)+":"+sum);
        key.set(key.toString().substring(0,splitIndex));
        context.write(key, info);//输出:<key,value>----<"Mapreduce","0.txt:2">
    }
}

4、Reduce进程


经过上述两个进程后,Reduce进程只需要将相同key值的value值组合成倒排索引文件所需的格式便可,剩下的事情就能够直接交给MapReduce框架处理了,以下图所示。

 reduce过程

Reduce进程核心代码实现以下,详细源码请参考:InvertedIndexsrccomzonesionhdfsInvertedIndex.java。

public static class InvertedIndexReducer 
    extends Reducer<Text, Text, Text, Text>{
    private Text result = new Text();
    @Override
    protected void reduce(Text key, Iterable<Text> values,Context context)
            throws IOException, InterruptedException {
        //输入:<"MapReduce",list("0.txt:1","1.txt:1","2.txt:1")>
        String fileList = new String();
        for(Text value : values){//value="0.txt:1"
            fileList += value.toString()+";";
        }
        result.set(fileList);
        context.write(key, result);//输出:<"MapReduce","0.txt:1,1.txt:1,2.txt:1">
    }
}

5、驱动实现


驱动核心代码实现以下,详细源码请参考:InvertedIndexsrccomzonesionhdfsInvertedIndex.java。

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);
    //设置Mapper类、Combiner类、Reducer类;
    job.setMapperClass(InvertedIndexMapper.class);
    job.setCombinerClass(InvertedIndexCombiner.class);
    job.setReducerClass(InvertedIndexReducer.class);
    //设置了Map进程和Reduce进程的输出类型,设置key、value的输出类型为Text;
    job.setOutputKeyClass(Text.class);
    job.setOutputValueClass(Text.class);
    //设置任务数据的输入、输前途径;
    FileInputFormat.addInputPath(job, new Path(otherArgs[0]));
    FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));
    //履行job任务,履行成功后退出;
    System.exit(job.waitForCompletion(true) ? 0 : 1);
}

6、部署运行


1)启动Hadoop集群

[hadoop@K-Master CompanyJoinAddress]$ start-dfs.sh
[hadoop@K-Master CompanyJoinAddress]$ start-mapred.sh
[hadoop@K-Master CompanyJoinAddress]$ jps
5283 SecondaryNameNode
5445 JobTracker
5578 Jps
5109 NameNode

2)部署源码

#设置工作环境
[hadoop@K-Master ~]$ mkdir -p /usr/hadoop/workspace/MapReduce
#部署源码
将InvertedIndex文件夹拷贝到/usr/hadoop/workspace/MapReduce/ 路径下;

… 你可以直接 下载 InvertedIndex

3)编译文件

#切换工作目录
[hadoop@K-Master ~]$ cd /usr/hadoop/workspace/MapReduce/InvertedIndex
#编译文件
[hadoop@K-Master InvertedIndex]$ javac -classpath /usr/hadoop/hadoop-core⑴.2.1.jar:/usr/hadoop/lib/commons-cli⑴.2.jar -d bin src/com/zonesion/hdfs/InvertedIndex.java
[hadoop@K-Master InvertedIndex]$ ls bin/com/zonesion/hdfs/ -la
总用量 20
drwxrwxr-x 2 hadoop hadoop 4096 9月  18 17:09 .
drwxrwxr-x 3 hadoop hadoop   17 9月  18 17:09 ..
-rw-rw-r-- 1 hadoop hadoop 1982 9月  18 17:09 InvertedIndex.class
-rw-rw-r-- 1 hadoop hadoop 2173 9月  18 17:09 InvertedIndex$InvertedIndexCombiner.class
-rw-rw-r-- 1 hadoop hadoop 2103 9月  18 17:09 InvertedIndex$InvertedIndexMapper.class
-rw-rw-r-- 1 hadoop hadoop 1931 9月  18 17:09 InvertedIndex$InvertedIndexReducer.class

4)打包jar文件

[hadoop@K-Master InvertedIndex]$ jar -cvf InvertedIndex.jar -C bin/ .
已添加清单
正在添加: com/(输入 = 0) (输出 = 0)(存储了 0%)
正在添加: com/zonesion/(输入 = 0) (输出 = 0)(存储了 0%)
正在添加: com/zonesion/hdfs/(输入 = 0) (输出 = 0)(存储了 0%)
正在添加: com/zonesion/hdfs/InvertedIndex$InvertedIndexMapper.class(输入 = 2103) (输出 = 921)(紧缩了 56%)
正在添加: com/zonesion/hdfs/InvertedIndex$InvertedIndexCombiner.class(输入 = 2173) (输出 = 944)(紧缩了 56%)
正在添加: com/zonesion/hdfs/InvertedIndex$InvertedIndexReducer.class(输入 = 1931) (输出 = 830)(紧缩了 57%)
正在添加: com/zonesion/hdfs/InvertedIndex.class(输入 = 1982) (输出 = 1002)(紧缩了 49%)

5)上传输入文件

#创建InvertedIndex/input/输入文件夹
[hadoop@K-Master InvertedIndex]$ hadoop fs -mkdir InvertedIndex/input/
#上传文件到InvertedIndex/input/输入文件夹
[hadoop@K-Master InvertedIndex]$ hadoop fs -put input/*.txt /user/hadoop/InvertedIndex/input
#验证上传文件是不是成功
[hadoop@K-Master InvertedIndex]$ hadoop fs -ls /user/hadoop/InvertedIndex/input
Found 3 items
-rw-r--r--   1 hadoop supergroup 20 2014-09⑴8 17:12 /user/hadoop/InvertedIndex/input/0.txt
-rw-r--r--   1 hadoop supergroup 32 2014-09⑴8 17:12 /user/hadoop/InvertedIndex/input/1.txt
-rw-r--r--   1 hadoop supergroup 30 2014-09⑴8 17:12 /user/hadoop/InvertedIndex/input/2.txt

6)运行Jar文件

[hadoop@K-Master InvertedIndex]$ hadoop jar InvertedIndex.jar com.zonesion.hdfs.InvertedIndex InvertedIndex/input InvertedIndex/output
14/09/18 17:16:40 INFO input.FileInputFormat: Total input paths to process : 3
14/09/18 17:16:40 INFO util.NativeCodeLoader: Loaded the native-hadoop library
14/09/18 17:16:40 WARN snappy.LoadSnappy: Snappy native library not loaded
14/09/18 17:16:41 INFO mapred.JobClient: Running job: job_201409150922_0003
14/09/18 17:16:42 INFO mapred.JobClient:  map 0% reduce 0%
14/09/18 17:16:45 INFO mapred.JobClient:  map 100% reduce 0%
14/09/18 17:16:51 INFO mapred.JobClient:  map 100% reduce 33%
14/09/18 17:16:53 INFO mapred.JobClient:  map 100% reduce 100%
14/09/18 17:16:53 INFO mapred.JobClient: Job complete: job_201409150922_0003
14/09/18 17:16:53 INFO mapred.JobClient: Counters: 29
......

7)查看输出结果

#查看HDFS上output目录内容
[hadoop@K-Master InvertedIndex]$ hadoop fs -ls /user/hadoop/InvertedIndex/output
Found 3 items
-rw-r--r--   1 hadoop supergroup  0 2014-07⑵1 15:31 /user/hadoop/InvertedIndex/output/_SUCCESS
drwxr-xr-x   - hadoop supergroup  0 2014-07⑵1 15:30 /user/hadoop/InvertedIndex/output/_logs
-rw-r--r--   1 hadoop supergroup665 2014-07⑵1 15:31 /user/hadoop/InvertedIndex/output/part-r-00000
#查看结果输出文件内容
[hadoop@K-Master InvertedIndex]$ hadoop fs -cat /user/hadoop/InvertedIndex/output/part-r-00000
Hello           hdfs://Master:9000/user/hadoop/InvertedIndex/input/2.txt:1;
MapReduce   hdfs://Master:9000/user/hadoop/InvertedIndex/input/2.txt:2;hdfs://Master:9000/user/hadoop/InvertedIndex/input/1.txt:1;hdfs://Master:9000/user/hadoop/InvertedIndex/input/0.txt:1;
Powerful    hdfs://Master:9000/user/hadoop/InvertedIndex/input/1.txt:1;
bye         hdfs://Master:9000/user/hadoop/InvertedIndex/input/2.txt:1;
is          hdfs://Master:9000/user/hadoop/InvertedIndex/input/0.txt:1;hdfs://Master:9000/user/hadoop/InvertedIndex/input/1.txt:2;
simple      hdfs://Master:9000/user/hadoop/InvertedIndex/input/1.txt:1;hdfs://Master:9000/user/hadoop/InvertedIndex/input/0.txt:1;

您可能喜欢

【Hadoop基础教程】5、Hadoop之单词计数
【Hadoop基础教程】6、Hadoop之单表关联查询
【Hadoop基础教程】7、Hadoop之1对多关联查询
【Hadoop基础教程】8、Hadoop之1对多关联查询
【Hadoop基础教程】9、Hadoop之倒排索引

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐