基于hadoop的mapreduce实现倒排索引

标签: hadoop mapreduce 倒排索引 | 发表时间:2013-10-22 18:22 | 作者:
出处:http://www.iteye.com

基于 hadoop mapreduce 实现倒排索引

倒排索引(英语: Inverted index ,也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。

倒排索引 有两种不同的反向索引形式:一条记录的水平反向索引(或者反向档案索引)包含每个引用单词的文档的列表。一个单词的水平反向索引(或者完全反向索引)又包含每个单词在一个文档中的位置。后者的形式提供了更多的兼容性(比如短语搜索),但是需要更多的时间和空间来创建。现代搜索引擎的索引 [3] 都是基于倒排索引。相比“签名文件”、“后缀树”等索引结构, “倒排索引”是实现单词到文档映射关系的最佳实现方式和最有效的索引结构。

 

实现目标:

输入一组文档:

 

file1 xiao lin lin
file2 yu yu xiao lin
file3 xiao lin xiao lin

 

 

输出结果:

lin file1:2;file2:1;file3:2
xiao file3:2;file2:1;file1:1
yu file2:2

 

实现代码:

 

package com.ds.demo;
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 InvertedIndexMapper 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());
				
				valueInfo.set("1");
				
				context.write(keyInfo, valueInfo);
			}
		}
	}
	
	public static class InvertedIndexCombiner 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 splitIndex = key.toString().indexOf(":");
			
			info.set(key.toString().substring(splitIndex + 1) + ":" + sum);
			
			key.set(key.toString().substring(0, splitIndex));
			
			context.write(key, info);
		}
	}
	
	public static class InvertedIndexReducer extends
			Reducer<Text, Text, Text, Text>{
		
		private Text result = new Text();
		
		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.9.201:9001");
		
		String[] ars=new String[]{"B","InvertedOut"};
		
		String[] otherArgs = new GenericOptionsParser(conf, ars).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);
		
		job.setMapperClass(InvertedIndexMapper.class);
		
		job.setMapOutputKeyClass(Text.class);
		job.setMapOutputValueClass(Text.class);
		
		job.setCombinerClass(InvertedIndexCombiner.class);
		
		job.setReducerClass(InvertedIndexReducer.class);
		
		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);
	}

}

 

 

经过Map

 

key value
xiao:file1 1
lin:file1 1
lin:file1 1
......

 

经过shuffle

 

xiao:file1 [1]
lin:file1 [1,1]
yu:file2 [1,1]
....

 

经过reduce

 

xiao file1:1
lin file1:2
yu file2:2
xiao file2:1
lin file2:1
....

 

再次 shuffle

xiao [file1:1,file2:1.file3:2]
lin [file1:2,file2:1,file3:2]
yu [file2:2]

 

再次reduce 得到结果

 

 

 

 

 

 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [hadoop mapreduce 倒排索引] 推荐:

基于hadoop的mapreduce实现倒排索引

- - ITeye博客
基于 hadoop 的 mapreduce 实现倒排索引. 倒排索引(英语: Inverted index ),也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射. 它是文档检索系统中最常用的数据结构.

hadoop倒排索引

- - CSDN博客云计算推荐文章
看到很多的hadoop关于倒排索引的例子,但是我想写一个属于我自己的,加入了本人对于hadoop中mapreduce的理解. CHENGDU - Death toll from a colliery blast on Saturday in southwest China's Sichuan Province rose to 27, local authorities said.

MapReduce 编程之 倒排索引

- - CSDN博客云计算推荐文章
本文调试环境: ubuntu 10.04 , hadoop-1.0.2. hadoop装的是伪分布模式,就是只有一个节点,集namenode, datanode, jobtracker, tasktracker...于一体. 本文实现了简单的倒排索引,单词,文档路径,词频,重要的解释都会在代码注视中.

MapReduce案例之倒排索引

- - 行业应用 - ITeye博客
1       倒排索引. "倒排索引"是文档检索系统中最常用的数据结构,被广泛地应用于全文搜索引擎. 它主要是用来存储某个单词(或词组)在一个文档或一组文档中的存储位置的映射,即提供了一种根据内容来查找文档的方式. 由于不是根据文档来确定文档所包含的内容,而是进行相反的操作,因而称为倒排索引(Inverted Index).

Hadoop MapReduce技巧

- - 简单文本
我在使用Hadoop编写MapReduce程序时,遇到了一些问题,通过在Google上查询资料,并结合自己对Hadoop的理解,逐一解决了这些问题. Hadoop对MapReduce中Key与Value的类型是有要求的,简单说来,这些类型必须支持Hadoop的序列化. 为了提高序列化的性能,Hadoop还为Java中常见的基本类型提供了相应地支持序列化的类型,如IntWritable,LongWritable,并为String类型提供了Text类型.

下一代Hadoop MapReduce

- Jia - NoSQLFan
本文来自Hadoop Summit大会的一个演讲稿,主讲是Hadoop核心开发团队的Arun C Murthy (@acmurthy),同时他也是Yahoo!刚刚剥离的Hadoop独立公司Hortonworks的 Founder和架构师. 演讲中他讲述了现在的Hadoop存在的一些问题和集群上限,并展望了下一代Hadoop和其MapReduce将会得到的巨大提升.

"Hadoop/MapReduce/HBase"分享总结

- - ITeye博客
此分享是关于hadoop生态系统的简单介绍包括起源到相对应用. Hadoop和HBase.pdf (2.1 MB). 已有 0 人发表留言,猛击->> 这里<<-参与讨论. —软件人才免语言低担保 赴美带薪读研.

Hadoop之MapReduce单元测试

- - ITeye博客
通常情况下,我们需要用小数据集来单元测试我们写好的map函数和reduce函数. 而一般我们可以使用Mockito框架来模拟OutputCollector对象(Hadoop版本号小于0.20.0)和Context对象(大于等于0.20.0). 下面是一个简单的WordCount例子:(使用的是新API).

Hadoop MapReduce高级编程

- - 互联网 - ITeye博客
•combine函数把一个map函数产生的对(多个key, value)合并成一个新的. 将新的作为输入到reduce函数中,其格式与reduce函数相同. •这样可以有效的较少中间结果,减少网络传输负荷. •什么情况下可以使用Combiner.

[转]基于mapreduce的Hadoop join实现

- -
对于一个大数据的分析应用,join是必不可少的一项功能.现在很多构建与hadoop之上的应用,如Hive,PIG等在其内部实现了join程序,可以通过很简单的sql语句或者数据操控脚本完成相应的Join工作.那么join应该如何实现呢?今天我们就对join做一个简单的实现. 我们来看一个例子,现在有两组数据:一组为单位人员信息,如下:.