基于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 得到结果
相关推荐
基于MapReduce的简单倒排索引的建立
MapReduce程序 完整实验报告 和 jar包 和简单实验数据
实现基于爬虫获取的语料库,建立全文倒排索引并实现搜索功能的项目。主要分为以下三个阶段: 爬虫:选取网站并进行爬虫获取初始数据; 获取语料库:将爬虫获取的原始数据经过加工及中文分词后建立本地语料库; ...
人工智能-hadoop
利用Mapreduce进行的倒排索引,并且建立二级索引 并且提供了与后台交互的接口实现代码 -------- 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传...
基于Hadoop的文档检索系统 利用Mapreduce进行的倒排索引,并且建立二级索引 并且提供了与后台交互的接口实现代码
search-1047基于Nutch和Hadoop简易搜索引擎,排序的依据主要是PageRank以及由倒排索引文件计算的url page与输入模式的余弦距离值。Nutch & HadoopNutch-1.9:. Nutch爬取产生的链接数据库(MapFile Format)linkdb,...
Hadoop_MapReduce 使用Hadoop进行大数据处理 该项目在Hadoop框架上使用Map-Reduce从零开始实现基本的文本处理任务,例如字数,n元语法,倒排索引,关系连接和k近邻算法。
5. 编写程序实现倒排索引 首先准备数据:1.txt,文件内容如下: The Apache Hadoop software library is a framework that allows for the distributed processing of large data sets across clusters of ...
利用倒排索引,获取query的候选集,然后从'dbinfo'中读取相应条目,在本地完成tfidf相似度计算以及排序。 代码:query.py 代码构成 --- 构建数据库 creatTables.py 创建数据库表 deleteTables.py 删除数据库...
并行正则表达式搜索加密数据[RESeED] ...在所有群集上并行构造倒排索引 支持常规扩展搜索-不仅是关键字搜索者 正则表达式在并行分布的反向索引上匹配 使用Hadoop Map Reduce来构建分布式反向索引和并行搜索