大数据 | 实验二:文档倒排索引算法实现

这篇具有很好参考价值的文章主要介绍了大数据 | 实验二:文档倒排索引算法实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

📚实验目的

倒排索引(Inverted Index)被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射,是目前几乎所有支持全文索引的搜索引擎都需要依赖的一个数据结构。通过对倒排索引的编程实现,熟练掌握 MapReduce 程序在集群上的提交与执行过程,加深对 MapReduce 编程框架的理解。

📚实验平台

  1. 操作系统:Linux
  2. Hadoop 版本:3.2.2
  3. JDK 版本:1.8
  4. Java IDE:Eclipse

📚实验内容

关于倒排索引
倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法

🐇在本地编写程序和调试

在本地 eclipse 上编写带词频属性的对英文文档的文档倒排索引程序,要求程序能够实现对 stop-words(如 a,an,the,in,of 等词)的去除,能够统计单词在每篇文档中出现的频率。文档数据和停词表可在此链接上下载,在伪分布式环境下完成程序的编写和调试。

倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法

🥕代码框架思路

  • Map():对输入的Text切分为多个word。这里的Map()包含setup()map()。每一次map都伴随着一次setup,进行停词,筛选那些不需要统计的。
  • Combine():将Map输出的中间结果相同key部分的value累加,减少向Reduce节点传输的数据量。
  • Partition():为了将同一个word的键值对发送到同一个Reduce节点,对key进行临时处理。将原key的(word, filename)临时拆开,使Partitioner只按照word值进行选择Reduce节点。基于哈希值的分片方法。
  • Reduce():利用每个Reducer接收到的键值对中,word是排好序的,来进行最后的整合。将word#filename拆分开,将filename与累加和拼到一起,存在str中。每次比较当前的word和上一次的word是否相同,若相同则将filename和累加和附加到str中,否则输出:key:word,value:str,并将新的word作为key继续。
  • 上述reduce()只会在遇到新word时,处理并输出前一个word,故对于最后一个word还需要额外的处理。重载cleanup(),处理最后一个word并输出
    倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法

倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法倒排索引的Map、Combiner、Partitioner部分就和上图一样

  • 一个Map对应一个Combiner,借助Combiner对Map输出进行一次初始整合
  • 一个Combiner又对应一个Partitioner,Partitioner将同一个word的键值对发送到同一个Reduce节点

🥕代码实现

(关注本地路径)

package index;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Vector;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.mapreduce.lib.partition.HashPartitioner;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.input.FileSplit;
 
public class index
{
	public static class Map extends Mapper<Object, Text, Text, IntWritable> 
	{
		/**
		 * setup():读取停词表到vector stop_words中
		 */
	    Vector<String> stop_words;//停词表
	    protected void setup(Context context) throws IOException 
	    {
		     stop_words = new Vector<String>();//初始化停词表
		     Configuration conf = context.getConfiguration();
		     //读取停词表文件
		     BufferedReader reader = new BufferedReader(new InputStreamReader(FileSystem.get(conf).open(new Path("hdfs://localhost:9000/user/hadoop/input/stop_words_eng.txt"))));
		     String line;
		     while ((line = reader.readLine()) != null) 
		     {//按行处理
		    	 StringTokenizer itr=new StringTokenizer(line);
		    	 while(itr.hasMoreTokens())
		    	 {//遍历词,存入vector
		    		 stop_words.add(itr.nextToken());
		    	 }
		     }
		     reader.close();
	    }
        
        /**
         * map():对输入的Text切分为多个word
         * 输入:key:当前行偏移位置     value:当前行内容
         * 输出:key:word#filename    value:1
         */
    	protected void map(Object key, Text value, Context context) throws IOException, InterruptedException 
    	{
    		FileSplit fileSplit = (FileSplit) context.getInputSplit();
            String fileName = fileSplit.getPath().getName();//获取文件名,转换为小写
            String line = value.toString().toLowerCase();//将行内容全部转为小写字母
            //只保留数字和字母
            String new_line="";
            for(int i = 0; i < line.length(); i ++) 
            {
            	if((line.charAt(i)>=48 && line.charAt(i)<=57) || (line.charAt(i)>=97 && line.charAt(i)<=122)) 
            	{//按行处理
            		new_line += line.charAt(i);
            	} 
            	else 
            	{
            		//其他字符保存为空格
            		new_line +=" ";
            	}
            }
        	line = new_line.trim();//去掉开头和结尾的空格
            StringTokenizer strToken=new StringTokenizer(line);//按照空格拆分
            while(strToken.hasMoreTokens())
            {
            	String str = strToken.nextToken();
            	if(!stop_words.contains(str)) 
            	{//不是停词则输出key-value对
            		context.write(new Text(str+"#"+fileName), new IntWritable(1));
            	}
            }
        }
	}
 
    public static class Combine extends Reducer<Text, IntWritable, Text, IntWritable> 
    {
        /**
         * 将Map输出的中间结果相同key部分的value累加,减少向Reduce节点传输的数据量
         * 输入:key:word#filename    value:1
         * 输出:key:word#filename    value:累加和(词频)
         */
		protected void reduce(Text key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException 
		{
            int sum = 0;
            for (IntWritable val : values) 
            {
                sum ++;
            }
            context.write(key, new IntWritable(sum));
        }
    }
 
    public static class Partition extends HashPartitioner<Text, IntWritable> 
    {
        /**
         * 为了将同一个word的键值对发送到同一个Reduce节点,对key进行临时处理
         * 将原key的(word, filename)临时拆开,使Partitioner只按照word值进行选择Reduce节点
         * 基于哈希值的分片方法
         */
        public int getPartition(Text key, IntWritable value, int numReduceTasks) 
        {
        	//第三个参数numPartitions表示每个Mapper的分片数,也就是Reducer的个数
            String term = key.toString().split("#")[0];//获取word#filename中的word
            return super.getPartition(new Text(term), value, numReduceTasks);//按照word分配reduce节点       
        }
    }
 
    public static class Reduce extends Reducer<Text, IntWritable, Text, Text> 
    {
    	/**
         * Reduce():利用每个Reducer接收到的键值对中,word是排好序的,来进行最后的整合
         * 将word#filename拆分开,将filename与累加和拼到一起,存在str中
         * 每次比较当前的word和上一次的word是否相同,若相同则将filename和累加和附加到str中,否则输出:key:word,value:str,并将新的word作为key继续
         * 输入:
         *         key                  value
         *    word1#filename 1        [num1,num2,...]
         *    word1#filename 2        [num1,num2,...]
         *    word2#filename 1        [num1,num2,...]
         * 输出:
         *    key:word   value:<filename1,词频><filename2,词频>...<total,总词频>
         */
        private String lastfile = null;//存储上一个filename
        private String lastword = null;//存储上一个word
        private String str = "";//存储要输出的value内容
        private int count = 0;
        private int totalcount = 0;
        protected void reduce(Text key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException 
        {
            String[] tokens = key.toString().split("#");
            //将word和filename存在tokens数组中
            if(lastword == null) 
            {
            	lastword = tokens[0];
            }
            if(lastfile == null) 
            {
            	lastfile = tokens[1];
            }
            if (!tokens[0].equals(lastword)) 
            {
            	//此次word与上次不一样,则将上次的word进行处理并输出
                str += "<"+lastfile+","+count+">;<total,"+totalcount+">.";
                context.write(new Text(lastword), new Text(str));//value部分拼接后输出
                lastword = tokens[0];//更新word
                lastfile = tokens[1];//更新filename
                count = 0;
                str="";
                for (IntWritable val : values) 
                {
                	//累加相同word和filename中出现次数
                	count += val.get();//转为int
                }
                totalcount = count;
                return;
            }
            
            if(!tokens[1].equals(lastfile)) 
            {//新的文档
            	str += "<"+lastfile+","+count+">;";
            	lastfile = tokens[1];//更新文档名
            	count = 0;//重设count值
            	for (IntWritable value : values)
            	{//计数
            		count += value.get();//转为int
                }
            	totalcount += count;
            	return;
            }
            
            //其他情况,只计算总数即可
            for (IntWritable val : values) 
            {
            	count += val.get();
            	totalcount += val.get();
            }
        }
        /**
         * 上述reduce()只会在遇到新word时,处理并输出前一个word,故对于最后一个word还需要额外的处理
         * 重载cleanup(),处理最后一个word并输出
         */
        public void cleanup(Context context) throws IOException, InterruptedException 
        {
            str += "<"+lastfile+","+count+">;<total,"+totalcount+">.";
            context.write(new Text(lastword), new Text(str));
            super.cleanup(context);
        }
    }
 
    public static void main(String args[]) throws Exception 
    {
    	Configuration conf = new Configuration();
    	conf.set("fs.defaultFS", "hdfs://localhost:9000");
        if(args.length != 2) 
        {
            System.err.println("Usage: Relation <in> <out>");
            System.exit(2);
        }
        
    	Job job = Job.getInstance(conf, "InvertedIndex");//设置环境参数
        job.setJarByClass(index.class);//设置整个程序的类名
        job.setMapperClass(Map.class);//设置Mapper类
        job.setCombinerClass(Combine.class);//设置combiner类
        job.setPartitionerClass(Partition.class);//设置Partitioner类
        job.setReducerClass(Reduce.class);//设置reducer类
        job.setOutputKeyClass(Text.class);//设置Mapper输出key类型
        job.setOutputValueClass(IntWritable.class);//设置Mapper输出value类型
        FileInputFormat.addInputPath(job, new Path(args[0]));//输入文件目录
        FileOutputFormat.setOutputPath(job, new Path(args[1]));//输出文件目录
        System.exit(job.waitForCompletion(true) ? 0 : 1);//参数true表示检查并打印 Job 和 Task 的运行状况
    }
 
}

补充:当我们新建一个Package和Class后运行时,可能会出现如下报错(主要是在MapReduce编程输入输出里会遇到)
倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法
解决办法

  • “Run As”选中“Run Configurations…”

倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法

  • 然后在“Arguments”里输入input output,然后再run就行了。

倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法


🐇在集群上提交作业并执行

集群的服务器地址为 10.102.0.198,用户主目录为/home/用户名,hdfs 目录为/user/用户名。集群上的实验文档存放目录为 hdfs://10.102.0.198:9000/input/. 英文停词表文件存放位置为hdfs://10.102.0.198:9000/stop_words/stop_words_eng.txt。

🥕在集群上提交作业并执行,同本地执行相比即需修改路径。

倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法

🥕修改后通过expoet,导出jar包,关注 Main-Class 的设置!

  • 选中index.java右键Export。
    倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法
  • 如下图选中JAR file后点Next。
    倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法
  • 确认选中index及其src,JAR的命名要和class名一样,比如这里是index.java,就是class index,也就是index.jar。然后点Next。
    倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法
  • 到如下页面,再点Next。

倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法

  • Main class那点Browse,选中index。

倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法

  • 如下图。
    倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法
  • 最后点finish完成导出,可在文件夹里找到index.jar。双击index.jar,在它的METS-INT里头查看Main-Class是否设置成功。
    倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法
    倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法

🥕在终端依次输入以下指令,完成提交

  • 使用 scp InvertedIndex.jar 用户名@10.102.0.198:/home/用户名 命令将本地程序提交到 Hadoop 集群
  • 通过 ssh 用户名@10.102.0.198 命令远程登录到 Hadoop 集群进行操作;
  • 使用 hadoop jar InvertedIndex.jar /input /user/用户名/output 命令在集群上运行 Hadoop 作业,指定输出目录为自己 hdfs 目录下的 output。
  • 使用 diff 命令判断自己的输出结果与标准输出的差异
scp index.jar bigdata_学号@10.102.0.198:/home/bigdata_学号
ssh bigdata_学号@10.102.0.198
hadoop jar index.jar /input /user/bigdata_学号/output
diff <(hdfs dfs -cat /output/part-r-00000) <(hdfs dfs -cat /user/bigdata_学号/output/part-r-00000)

在浏览器中打开 http://10.102.0.198:8088,可以查看集群上作业的基本执行情况。

倒排索引实验,大数据与数据分析,# 大数据管理与分析实验,大数据,算法文章来源地址https://www.toymoban.com/news/detail-733307.html

到了这里,关于大数据 | 实验二:文档倒排索引算法实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构实验任务八:排序算法的实现与分析

    问题描述 统计成绩:给出 n 个学生的考试成绩表,每条信息由姓名和分数组成,试设 计一个算法: 1.按分数高低次序,打印出每个学生在考试中获得的名次,分数相同的为同 一名次; 2.按名次列出每个学生的姓名与分数。 输入要求 输入 n+1 行,前 n 行是 n 个学生的信息(姓

    2024年02月04日
    浏览(69)
  • Elasticsearch 查询命令执行时,如何通过词项索引、词项字典、倒排表定位文档逻辑介绍

    这里不涉及到源码,只是根据网上的一些文章总结一下,目前不需要细究,只需要知道大概就好,除非你的工作是二次开发ES 这张图你可以认为粗糙的描述倒排索引对应关系,下面的文章也是主要讲解这张图各个部分含义 看这个 ​Term Index 是不是特别想树的数据结构?比如二

    2024年02月03日
    浏览(52)
  • [C++项目] Boost文档 站内搜索引擎(3): 建立文档及其关键字的正排 倒排索引、jieba库的安装与使用...

    之前的两篇文章: 第一篇文章介绍了本项目的背景, 获取了 Boost 库文档 🫦[C++项目] Boost文档 站内搜索引擎(1): 项目背景介绍、相关技术栈、相关概念介绍… 第二篇文章 分析实现了 parser 模块. 此模块的作用是 对所有文档 html 文件, 进行清理并汇总 🫦[C++项目] Boost文档 站内搜

    2024年02月07日
    浏览(58)
  • Python实战:在搜索引擎开发中的倒排索引与检索算法

    在信息检索领域,搜索引擎是一个至关重要的工具,它可以帮助用户在大量的数据中找到所需的信息。而倒排索引是搜索引擎的核心技术之一,它能够提高检索的效率。 倒排索引是一种数据结构,它将文档的内容和文档的ID关联起来。在倒排索引中,每个词项都有一个列表,

    2024年04月26日
    浏览(34)
  • 【分布式存储】数据存储和检索~倒排索引&pageRank

    通过前两篇的文章介绍,B+树主要针对的是读多写少的场景,而LSM针对的是写多读少的场景,其实在日常开发中,我们会将数据存储到搜索引擎中,然后进行数据的搜索,这种场景其实针对的是快速根据查询。对于MySQL这种B+树结构来说,其实没有办法保证快速查询。要

    2024年02月12日
    浏览(40)
  • 搜索引擎:常用信息检索方式介绍与倒排索引实现(Python)

    (1)线性扫描 计算机对于文档内容检索有多种可能的方式,如直接从头遍历至尾端,根据我们输入的提取内容。 这类检索方式与我们人类阅读的习惯相同,因此实现简单且很容易被接受。 若问你《三国演义》中是否存在’舌战群儒’这一词语,我们常常会选择浏览全文

    2024年02月08日
    浏览(44)
  • 倒排索引的数据结构:Term index、Term Dictionary、Posting List

    倒排索引其实包含了三种数据,分别是 倒排表(Posting List) 词项字典(Term Dictionary) 词项索引(Term Index) 这几种文件分别存储了不同的数据 其中倒排表包含某个词项的所有id的数据存储了在.doc文件中; 词项字典包含了index field的所有经过normalization token filters处理之后的词

    2023年04月17日
    浏览(23)
  • 基于Python机器学习算法农业数据可视化分析预测系统(完整系统源码+数据库+详细文档+论文+部署教程)

    基于python机器学习XGBoost算法农业数据可视化分析预测系统,旨在帮助农民和相关从业者更好地预测农作物产量,以优化农业生产。该系统主要包括四个功能模块。 首先,农作物数据可视化模块利用Echarts、Ajax、Flask、PyMysql技术实现了可视化展示农作物产量相关数据的功能。

    2024年04月27日
    浏览(42)
  • Hadoop系统应用之MapReduce相关操作【IDEA版】---经典案例“倒排索引、数据去重、TopN”

      倒排索引是文档检索系统中最常用的数据结构,被广泛应用于全文搜索引擎。倒排索引主要用来存储某个单词(或词组)在一组文档中的存储位置的映射,提供了可以根据内容来查找文档的方式,而不是根据文档来确定内容,因此称为倒排索引(Inverted Index)。带有倒排索引

    2024年02月07日
    浏览(49)
  • 计算机毕业设计 基于大数据的智能家居销量数据分析系统的设计与实现 Java实战项目 附源码+文档+视频讲解

    博主介绍:✌从事软件开发10年之余,专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找不到哟 ——————————

    2024年02月04日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包