MapReduce實作反向索引(Inverted Index)

前言："反向索引"是文檔檢索系統中最常用的資料結構，被廣泛地應用于全文搜尋引擎。它主要是用來存儲某個單詞（或詞組）在一個文檔或一組文檔中的存儲位置的映射，即提供了一種根據内容來查找文檔的方式。由于不是根據文檔來确定文檔所包含的内容，而是進行相反的操作，因而稱為反向索引（Inverted Index）

注意：

(1)這裡存在兩個問題：第一，<key,value>對隻能有兩個值，在不使用Hadoop自定義資料類型的情況下，需要根據情況将其中兩個值合并成一個值，作為key或value值；第二，通過一個Reduce過程無法同時完成詞頻統計和生成文檔清單，是以必須增加一個Combine過程完成詞頻統計。

(2)這裡将單詞和URL組成key值（如"MapReduce：file1.txt"），将詞頻作為value，這樣做的好處是可以利用MapReduce架構自帶的Map端排序，将同一文檔的相同單詞的詞頻組成清單，傳遞給Combine過程，實作類似于WordCount的功能。

(3)Combine過程：經過map方法處理後，Combine過程将key值相同的value值累加，得到一個單詞在文檔在文檔中的詞頻，如果直接輸出作為Reduce過程的輸入，在Shuffle過程時将面臨一個問題：所有具有相同單詞的記錄（由單詞、URL和詞頻組成）應該交由同一個Reducer處理，但目前的key值無法保證這一點，是以必須修改key值和value值。這次将單詞作為key值，URL和詞頻組成value值（如"file1.txt：1"）。這樣做的好處是可以利用MapReduce架構預設的HashPartitioner類完成Shuffle過程，将相同單詞的所有記錄發送給同一個Reducer進行處理。

2.将資料上傳到hdfs上：

[[email protected] q1]$ hadoop fs -mkdir /user/hadoop/index_in

[[email protected] q1]$ hadoop fs -put file1.txt /user/hadoop/index_in

[[email protected] q1]$ hadoop fs -put file2.txt /user/hadoop/index_in

[[email protected] q1]$ hadoop fs -put file3.txt /user/hadoop/index_in

3、對應的Java程式如下所示：

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 Map extends Mapper<Object, Text, Text, Text> {         private Text keyInfo = new Text(); // 存儲單詞和URL組合         private Text valueInfo = new Text(); // 存儲詞頻         private FileSplit split; // 存儲Split對象         // 實作map函數         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值由單詞和URL組成，如"MapReduce：file1.txt"                 // 擷取檔案的完整路徑                 // keyInfo.set(itr.nextToken()+":"+split.getPath().toString());                 // 這裡為了好看，隻擷取檔案的名稱。                 int splitIndex = split.getPath().toString().indexOf("file");                 keyInfo.set(itr.nextToken() + ":" + split.getPath().toString().substring(splitIndex));                 // 詞頻初始化為1                 valueInfo.set("1");                  context.write(keyInfo, valueInfo);             }         }     }     public static class Combine extends Reducer<Text, Text, Text, Text> {         private Text info = new Text();         // 實作reduce函數         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值由URL和詞頻組成             info.set(key.toString().substring(splitIndex + 1) + ":" + sum);             // 重新設定key值為單詞             key.set(key.toString().substring(0, splitIndex));             context.write(key, info);         }     }     public static class Reduce extends Reducer<Text, Text, Text, Text> {         private Text result = new Text();         // 實作reduce函數         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();         conf.set("mapred.jar", "ii.jar");         String[] ioArgs = new String[] { "index_in", "index_out" };         String[] otherArgs = new GenericOptionsParser(conf, ioArgs).getRemainingArgs();         if (otherArgs.length != 2) {             System.err.println("Usage: Inverted Index <in> <out>");             System.exit(2);         }         Job job = new Job(conf, "Inverted Index");         job.setJarByClass(InvertedIndex.class);         // 設定Map、Combine和Reduce處理類         job.setMapperClass(Map.class);         job.setCombinerClass(Combine.class);         job.setReducerClass(Reduce.class);         // 設定Map輸出類型         job.setMapOutputKeyClass(Text.class);         job.setMapOutputValueClass(Text.class);         // 設定Reduce輸出類型         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);     } }

4.知識點延伸：

(1)int indexOf(String str) ：傳回第一次出現的指定子字元串在此字元串中的索引。 

(2)int indexOf(String str, int startIndex)：從指定的索引處開始，傳回第一次出現的指定子字元串在此字元串中的索引。 

(3)int lastIndexOf(String str) ：傳回在此字元串中最右邊出現的指定子字元串的索引。 

(4)int lastIndexOf(String str, int startIndex) ：從指定的索引處開始向後搜尋，傳回在此字元串中最後一次出現的指定子字元串的索引。

(5)indexOf("a")是從字元串的0個位置開始查找的。比如你的字元串："abca"，那麼程式将會輸出0，之後的a是不判斷的。

(6)str＝str.substring(int beginIndex);截取掉str從首字母起長度為beginIndex的字元串，将剩餘字元串指派給str

(7)str＝str.substring(int beginIndex，int endIndex);截取str中從beginIndex開始至endIndex結束時的字元串，并将其指派給str

5.執行：

[[email protected] q1]$ /usr/jdk1.7.0_25/bin/javac InvertedIndex.java

[[email protected] q1]$ /usr/jdk1.7.0_25/bin/jar cvf xx.jar InvertedIndex*class

[[email protected] q1]$ hadoop jar xx.jar InvertedIndex

6.檢視結果：

[ha[email protected] q1]$ hadoop fs -cat /user/hadoop/index_out/part-r-00000

bye     file3.txt:1;

hello   file3.txt:1;

is      file1.txt:1;file2.txt:2;

mapreduce       file2.txt:1;file3.txt:2;file1.txt:1;

powerful        file2.txt:1;

simple  file2.txt:1;file1.txt:1;