1 反向索引
1.1 反向索引
"反向索引"是文檔檢索系統中最常用的資料結構，被廣泛地應用于全文搜尋引擎。它主要是用來存儲某個單詞（或詞組）在一個文檔或一組文檔中的存儲位置的映射，即提供了一種根據内容來查找文檔的方式。由于不是根據文檔來确定文檔所包含的内容，而是進行相反的操作，因而稱為反向索引（Inverted Index）。
1.2 應用場景
通常情況下，反向索引由一個單詞（或詞組）以及相關的文檔清單組成，文檔清單中的文檔或者是辨別文檔的ID号，或者是指文檔所在位置的URL，如圖6.1-1所示。
從上圖可以看出，單詞1出現在{文檔1，文檔4，文檔13，……}中，單詞2出現在{文檔3，文檔5，文檔15，……}中，而單詞3出現在{文檔1，文檔8，文檔20，……}中。在實際應用中，還需要給每個文檔添加一個權值，用來指出每個文檔與搜尋内容的相關度，如下圖所示。
最常用的是使用詞頻作為權重，即記錄單詞在文檔中出現的次數。以英文為例，如下圖所示，索引檔案中的"MapReduce"一行表示："MapReduce"這個單詞在文本T0中出現過1次，T1中出現過1次，T2中出現過2次。當搜尋條件為"MapReduce"、"is"、"Simple"時，對應的集合為：{T0，T1，T2}∩{T0，T1}∩{T0，T1}={T0，T1}，即文檔T0和T1包含了所要索引的單詞，而且隻有T0是連續的。
更複雜的權重還可能要記錄單詞在多少個文檔中出現過，以實作TF-IDF（Term Frequency-Inverse Document Frequency）算法，或者考慮單詞在文檔中的位置資訊（單詞是否出現在标題中，反映了單詞在文檔中的重要性）等。
1.3 設計思路
實作"反向索引"隻要關注的資訊為：單詞、文檔URL及詞頻，如圖3-11所示。但是在實作過程中，索引檔案的格式與圖6.1-3會略有所不同，以避免重寫OutPutFormat類。下面根據MapReduce的處理過程給出反向索引的設計思路。
1）Map過程
首先使用預設的TextInputFormat類對輸入檔案進行處理，得到文本中每行的偏移量及其内容。顯然，Map過程首先必須分析輸入的<key,value>對，得到反向索引中需要的三個資訊：單詞、文檔URL和詞頻，如下圖所示。
這裡存在兩個問題：第一，<key,value>對隻能有兩個值，在不使用Hadoop自定義資料類型的情況下，需要根據情況将其中兩個值合并成一個值，作為key或value值；第二，通過一個Reduce過程無法同時完成詞頻統計和生成文檔清單，是以必須增加一個Combine過程完成詞頻統計。
這裡講單詞和URL組成key值（如"MapReduce：file1.txt"），将詞頻作為value，這樣做的好處是可以利用MapReduce架構自帶的Map端排序，将同一文檔的相同單詞的詞頻組成清單，傳遞給Combine過程，實作類似于WordCount的功能。
2）Combine過程
經過map方法處理後，Combine過程将key值相同的value值累加，得到一個單詞在文檔中的詞頻，如下圖所示。如果直接将下圖所示的輸出作為Reduce過程的輸入，在Shuffle過程時将面臨一個問題：所有具有相同單詞的記錄（由單詞、URL和詞頻組成）應該交由同一個Reducer處理，但目前的key值無法保證這一點，是以必須修改key值和value值。這次将單詞作為key值，URL和詞頻組成value值（如"file1.txt：1"）。這樣做的好處是可以利用MapReduce架構預設的HashPartitioner類完成Shuffle過程，将相同單詞的所有記錄發送給同一個Reducer進行處理。
3）Reduce過程
經過上述兩個過程後，Reduce過程隻需将相同key值的value值組合成反向索引檔案所需的格式即可，剩下的事情就可以直接交給MapReduce架構進行處理了。如下圖所示：
4）需要解決的問題
本執行個體設計的反向索引在檔案數目上沒有限制，但是單詞檔案不宜過大（具體值與預設HDFS塊大小及相關配置有關），要保證每個檔案對應一個split。否則，由于Reduce過程沒有進一步統計詞頻，最終結果可能會出現詞頻未統計完全的單詞。可以通過重寫InputFormat類将每個檔案為一個split，避免上述情況。或者執行兩次MapReduce，第一次MapReduce用于統計詞頻，第二次MapReduce用于生成反向索引。除此之外，還可以利用複合鍵值對等實作包含更多資訊的反向索引。
1.4 程式代碼
程式代碼如下所示：
| 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.IntWritable; 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" 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.job.tracker", "192.168.1.2:9001"); 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); } } |