数据结构域算法设计-hadoop环境搭建及实现倒排索引

《数据结构域算法设计-hadoop环境搭建及实现倒排索引》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录 1.应用介绍3 1.1实验环境介绍3 1.2应用背景介绍3 1.3应用的意义与价值4 2.数据及存储5 2.1数据来源及数据量5 2.2数据存储解决方案5 3.分析处理架构 5 3.1架构设计和处理方法5 3.2核心处理算法代码7 4.系统实现9 5.总结271.应用介绍 1.1实验环境介绍 本实验是在Hadoop伪分布式处理架构下完成的。我用自己的笔记本在ubuntu14.04操作系统下自己搭建了hadoop2.7.1架构，并配置了伪分布式模式进行数据的处理。 1.2应用背景介绍 本次云计算大作业实现的是文档

2、检索系统中最常用的数据结构—倒排索引。我通过查阅资料了解了倒排索引的实现过程，借鉴已有的实现程序完成了该算法在hadoop平台上的运行，并处理了相关的数据，得到了相应的处理结果。在关系数据库系统里，索引是检索数据最有效率的方式,。但对于搜索引擎，它并不能满足其特殊要求： 1）海量数据：搜索引擎面对的是海量数据，像Google、百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量，面对如此海量数据,使得数据库系统很难有效的管理。 2）数据操作简单：搜索引擎使用的数据操作简单,一般而言,只需要增、删、改、查几个功能

3、，而且数据都有特定的格式，可以针对这些应用设计出简单高效的应用程序。而一般的数据库系统则支持大而全的功能，同时损失了速度和空间。最后，搜索引擎面临大量的用户检索需求，这要求搜索引擎在检索程序的设计上要分秒必争，尽可能的将大运算量的工作在索引建立时完成，使检索运算尽量的少。一般的数据库系统很难承受如此大量的用户请求，而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。 1.3应用的意义与价值 倒排索引，也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档

4、中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。 现代搜索引擎的索引都是基于倒排索引。相比“签名文件”、“后缀树”等索引结构，“倒排索引”是实现单词到文档映射关系的最佳实现方式和最有效的索引结构。 2.数据及存储 2.1数据来源及数据量 数据的存储格式主要是txt文本文档格式的。数据主要来自于网上的英文原版书籍。我从网上下载了超过千万个英文单词的英文文档，文件大小为百兆级别。 2.2数据存储解决方案 因为数据主要是一些txt文本文件，所以下载下来后直接

5、存储在本地即可。之后上传到Hdfs下的目录中。 3.分析处理架构 3.1架构设计和处理方法 实现倒排索引只要关注的信息为：单词、文档URL及词频。输入的文档格式为“文件名.txt”格式。 1）Map过程 首先使用默认的TextInputFormat类对输入文件进行处理，得到文本中每行的偏移量及其内容。显然，Map过程首先必须分析输入的publicstaticclassMapextendsMapper{privateTextkeyInfo=newText();//存储单词和

6、URL组合privateTextvalueInfo=newText();//存储词频privateFileSplitsplit;//存储Split对象//实现map函数publicvoidmap(Objectkey,Textvalue,Contextcontext)throwsIOException,InterruptedException{//获得对所属的FileSplit对象split=(FileSplit)context.getInputSplit();StringTokenizeritr

7、=newStringTokenizer(value.toString());while(itr.hasMoreTokens()){//key值由单词和URL组成，如"MapReduce：file1.txt"//获取文件的完整路径//keyInfo.set(itr.nextToken()+":"+split.getPath().toString());//这里为了好看，只获取文件的名称。intsplitIndex=split.getPath().toString().indexOf("file");keyInfo.se

8、t(itr.nextToken()+":"+split.getPath().toString().substring(splitIndex));//词频初始化为1valueInfo.set("1");context.write(keyInfo,valueInfo);}}}publicstaticclassCombineextendsReduce