您當前位置：首頁 > 服務器 > 【Hadoop基礎教程】9、Hadoop之倒排索引

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

來源：程序員人生發(fā)布時間：2015-03-12 08:49:00 閱讀次數(shù)：3582次

開發(fā)環(huán)境

硬件環(huán)境：Centos 6.5 服務器4臺（1臺為Master節(jié)點，3臺為Slave節(jié)點）
軟件環(huán)境：Java 1.7.0_45、hadoop⑴.2.1

1、倒排索引

倒排索引是文檔檢索系統(tǒng)中最經(jīng)常使用的數(shù)據(jù)結構，被廣泛用于全文搜索引擎。它主要是用來存儲某個單詞（或詞組）在1個文檔或1組文檔的存儲位置的映照，即提供了1種根據(jù)內(nèi)容來查找文檔的方式。由于不是根據(jù)文檔來肯定文檔所包括的內(nèi)容，而是進行了相反的操作（根據(jù)關鍵字來查找文檔），因此稱為倒排索引（Inverted Index）。通常情況下，倒排索引由1個單詞（詞組）和相干的文檔列表（標示文檔的ID號，或是指定文檔所在位置的URI）組成，以下圖所示：

倒排索引結構

從上圖可以看出，單詞1出現(xiàn)在{文檔1、文檔4、文檔13、……}中，單詞2出現(xiàn)在{文檔3、文檔5、文檔15、…..}中，而單詞3出現(xiàn)在{文檔1、文檔8、文檔20、….}中，還需要給每一個文檔添加1個權值，用來指出每一個文檔與搜素內(nèi)容相干的相干度，以下圖所示：

添加權重的倒排索引

最經(jīng)常使用的是使用詞頻作為權重，即記錄單詞在文檔中出現(xiàn)的次數(shù)了。以英文為例，以下圖所示，索引文件中的“MapReduce”1行表示：“MapReduce”這個單詞在文本T0中出現(xiàn)過1次，T1中出現(xiàn)過1次，T2中出現(xiàn)過2次。當搜索條件為“MapReduce”、“is”、“simple”時，對應的集合為：{T0，T1，T2}∩{ T0，T1}∩{ T0，T1}={ T0，T1}，即文本T0和T1包括所要索引的單詞，而且只有T0是連續(xù)的。

添加權重的倒排索引

2、Map進程

首先使用默許的TextInputFormat類對輸入文件進行處理，得到文本中每行的偏移量及其內(nèi)容。明顯，Map進程首先必須分析輸入的< key，value>對，得到倒排索引中需要的3個信息：單詞、文檔URI和詞頻，以下圖所示。這里存在兩個問題：第1，< key,value>對只能有兩個值，在不使用Hadoop自定義數(shù)據(jù)類型的情況下，需要根據(jù)情況將其中兩個值合并成1個值，作為key或value值；第2，通過1個Reduce進程沒法同時完成詞頻統(tǒng)計和文檔列表，所以必須增加1個Combine進程完成詞頻統(tǒng)計。

map過程

這里將單詞和URI組成Key值（如“MapReduce :1.txt”），將詞頻作為value，這樣做的好處是可以利用MapReduce框架自帶的Map端排序，將同1文檔的相同單詞的詞頻組成列表，傳遞給Combine進程，實現(xiàn)類似于WordCount的功能。
Map進程核心代碼實現(xiàn)以下，詳細源碼請參考：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進程

經(jīng)過map方法處理以后，Combine進程將key值相同的value值累加，得到1個單詞在文檔中的詞頻，以下圖所示。如果直接將Map的輸出結果作為Reduce進程的輸入，在Shuffle進程時將面臨1個問題：所有具有相同單詞的記錄（由單詞、URI和詞頻組成）應當交由同1個Reduce處理，但當前key值沒法保證這1點，所以必須修改key值和value值。這次將單詞作為key值，URI和詞頻作為value值。這樣做的好處是可以利用MapReduce框架默許的HashPartitioner類完成Shuffle進程，將相同單詞的所有記錄發(fā)送給同1個Reducer處理。

combine過程

Combine進程核心代碼實現(xiàn)以下，詳細源碼請參考：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進程

經(jīng)過上述兩個進程后，Reduce進程只需要將相同key值的value值組合成倒排索引文件所需的格式便可，剩下的事情就能夠直接交給MapReduce框架處理了，以下圖所示。

reduce過程

Reduce進程核心代碼實現(xiàn)以下，詳細源碼請參考：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、驅(qū)動實現(xiàn)

驅(qū)動核心代碼實現(xiàn)以下，詳細源碼請參考：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);
    //設置任務數(shù)據(jù)的輸入、輸前途徑；
    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）部署源碼

#設置工作環(huán)境
[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）上傳輸入文件

#創(chuàng)建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目錄內(nèi)容
[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
#查看結果輸出文件內(nèi)容
[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之單詞計數(shù)
【Hadoop基礎教程】6、Hadoop之單表關聯(lián)查詢
【Hadoop基礎教程】7、Hadoop之1對多關聯(lián)查詢
【Hadoop基礎教程】8、Hadoop之1對多關聯(lián)查詢
【Hadoop基礎教程】9、Hadoop之倒排索引

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生