反向索引（Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜尋下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的資料結構。
有兩種不同的反向索引形式：
一條記錄的水準反向索引（或者反向檔案索引）包含每個引用單詞的文檔的清單。
一個單詞的水準反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
後者的形式提供了更多的相容性（比如短語搜尋），但是需要更多的時間和空間來建立。
舉例：
以英文為例，下面是要被索引的文本：
<code>T0 = "it is what it is"</code>
<code>T1 = "what is it"</code>
<code>T2 = "it is a banana"</code>
我們就能得到下面的反向檔案索引：
1
2
3
4
5
<code>"a": {2}</code>
<code>"banana": {2}</code>
<code>"is": {0, 1, 2}</code>
<code>"it": {0, 1, 2}</code>
<code>"what": {0, 1}</code>
檢索的條件<code>"what"</code>, <code>"is"</code> 和 <code>"it"</code> 将對應這個集合：{0,1}∩{0,1,2}∩{0,1,2}={0,1}。
對相同的文字，我們得到後面這些完全反向索引，有文檔數量和目前查詢的單詞結果組成的的成對資料。 同樣，文檔數量和目前查詢的單詞結果都從零開始。
是以，<code>"banana": {(2, 3)}</code> 就是說 “banana”在第三個文檔裡 (T2)，而且在第三個文檔的位置是第四個單詞(位址為 3)。
<code>"a": {(2, 2)}</code>
<code>"banana": {(2, 3)}</code>
<code>"is": {(0, 1), (0, 4), (1, 1), (2, 1)}</code>
<code>"it": {(0, 0), (0, 3), (1, 2), (2, 0)}</code>
<code>"what": {(0, 2), (1, 0)}</code>
如果我們執行短語搜尋<code>"what is it"</code> 我們得到這個短語的全部單詞各自的結果所在文檔為文檔0和文檔1。但是這個短語檢索的連續的條件僅僅在文檔1得到。
（1）Map過程
首先使用預設的TextInputFormat類對輸入檔案進行處理，得到文本中每行的偏移量及其内容，Map過程首先必須分析輸入的<key, value>對，得到反向索引中需要的三個資訊：單詞、文檔URI和詞頻，如圖所示：
存在兩個問題，第一：<key, value>對隻能有兩個值，在不使用Hadoop自定義資料類型的情況下，需要根據情況将其中的兩個值合并成一個值，作為value或key值；
第二，通過一個Reduce過程無法同時完成詞頻統計和生成文檔清單，是以必須增加一個Combine過程完成詞頻統計
public static class Map extends Mapper<Object,Text,Text,Text>{
private Text keyInfo = new Text();
private Text valueInfo = new Text();
private FileSplit split; //存儲所在檔案的路徑
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()){
keyInfo.set(itr.nextToken()+"+"+split.getPath().toString()); //keyvalue是由單詞和URI組成的
valueInfo.set("1");
//value值設定成1
context.write(keyInfo,valueInfo);
}
}
}
（2）Combine過程
将key值相同的value值累加，得到一個單詞在文檔中的詞頻，如圖
public static class Combiner extends Reducer<Text,Text,Text,Text>{
private Text info = new Text();
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 index = key.toString().indexOf("+");
// info.set(key.toString().substring(index+1)+":"+sum);
// key.set(key.toString().substring(0,index));
String record = key.toString();
String[] str = record.split("[+]");
info.set(str[1]+":"+sum);
key.set(str[0]);
context.write(key,info);
（3）Reduce過程
講過上述兩個過程後，Reduce過程隻需将相同key值的value值組合成反向索引檔案所需的格式即可，剩下的事情就可以直接交給MapReduce架構進行處理了
public static class Reduce extends Reducer<Text,Text,Text,Text>{
private Text result = new Text();
String value =new String();
for(Text value1:values){
value += value1.toString()+" ; ";
result.set(value);
context.write(key,result);
完整代碼如下：
package ReverseIndex;
import java.io.*;
import java.util.StringTokenizer;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.*;
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;
public class ReverseIndex {
public static class Map extends Mapper<Object,Text,Text,Text>{
public static class Combiner extends Reducer<Text,Text,Text,Text>{
//下面三行注釋和緊接着四行功能一樣，隻不過實作方法不一樣罷了
//對傳進來的key進行拆分，以+為界
public static class Reduce extends Reducer<Text,Text,Text,Text>{
public static void main(String[] args) throws IOException, ClassNotFoundException,
InterruptedException {
// TODO Auto-generated method stub
Job job = new Job();
job.setJarByClass(ReverseIndex.class);
job.setNumReduceTasks(1); //設定reduce的任務數量為1，平常的小測試不需要開辟太多的reduce任務程序
job.setMapperClass(Map.class);
job.setMapOutputKeyClass(Text.class);
job.setMapOutputValueClass(Text.class);
job.setCombinerClass(Combiner.class);
job.setReducerClass(Reduce.class);
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(Text.class);
FileInputFormat.addInputPath(job, new Path("/thinkgamer/input"));
FileOutputFormat.setOutputPath(job, new Path("/thinkgamer/output"));
System.exit(job.waitForCompletion(true) ? 0 : 1);
}