980PageRank的MapReduce实现.ppt

《980PageRank的MapReduce实现.ppt》由会员分享，可在线阅读，更多相关《980PageRank的MapReduce实现.ppt（35页珍藏版）》请在三一办公上搜索。

1、PageRank的MapReduce实现,2011-09,PageRank算法介绍PageRank算法的MapReduce实现实现一个简单的搜索引擎WordCount例程源码讲解,PageRank算法介绍,PageRank算法由Google创始人之一Larry Page提出，它是Google排名运算法则的一部分，是Google用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站好坏的重要标准之一。Google通过PageRank来调整结果，使那些更具“等级/重要性”的网页在搜索结果中的排名获得提升，从而提高搜索结果的相关性和质量。该算法的基本思想是被大量高质量网页引用（链接）的

2、网页也是高质量网页。,PageRank算法介绍,PR(A)是网页A的PageRank值；a是一个权值，例如可以设定为0.5，经过多次迭代，PR(A)接近精确值；ti表示链向页面A的第i个网页；C(ti)表示页面i的链出链接数,PageRank算法介绍PageRank算法的MapReduce实现实现一个简单的搜索引擎WordCount例程源码讲解,PageRank的MapReduce实现,Step 1:分析一个页面的链接数并赋初值；Step 2:多次迭代计算页面的PageRank值；Step 3:根据PageRank值排序。,Step1 分析页面链接数,Map:-input:(0,index.h

3、tml)-output:(index.html,1.html)(index.html,2.html)(index.html,n.html)说明：输出为(key，value)键值对，key为当前网页路径，value为当前网页中的对外的链接。,Reduce:-input:key:“index.html”value:“1.html”,”n.html”-output:key:”index.html”value:“1.0 1.html,n.html”说明：Hadoop把Map函数输出的key合并，相同key的value合并成一个集合作为reduce的value。输出key网页的PR值（初值为1.0）,S

4、tep1 分析页面链接数,对于MapReduce程序，Map函数的输入为用户指定的文件，那么输入的value值就是文件内容（可以配置成按行读取或者把整个文件视作一个大字符串），key值是读入文本的偏移量。程序员对输入的key,value进行一系列操作，然后按(key,value)键值对的形式输出。需要注意的是：输出的key,value是程序员自己定义的，可以和输入的key,value毫不相关。系统获取Map函数的输出，把相同的key合并，再把key和value集合作为键值对作为reduce函数的输入。程序员自定义reduce函数中的处理方法，输出(key,value)键值对到磁盘文件。,Ste

5、p2 迭代计算PageRank值,Map:-input:key:index.html value:1.html,2.html-output:key:“1.html”Value:“index.html”Key:“2.html”Value:”index.html”,Reduce:-input:Key:“1.html”Value:”index.html 0.5 23”,”2.html 2.4 2”,key:“2.html”value:“index.html 0.5 23”,“1.html 1.3 3”,-output:key:”1.html”value:“index.html,2.html”,注意，

6、这是1.html的新PR值,Step2 迭代计算PageRank值,说明：step2是一个迭代过程，每次将磁盘上的文件读入，key为每一个网页链接，value的第一项为当前网页的PangRank值，后面接该网页中的对外链接。Map函数将输入的每一对(key,value)“反转”成多对(value,key)输出，也就是说，每个输出的key为输入value中的每一个链接，而输出value为输入key的链接+输入key的PR值+输入key的对外链接数。在reduce函数中，就可以根据输入的value中的参数来计算每一个key新的PageRank值，并按Map函数的格式输出到磁盘，以作为下一次迭代的输

7、入。迭代多次后，PageRank值趋于稳定，就得出了较为精确的PageRank值。,Step3 根据PageRank值排序,Map:-input:key:“index.html”value:“1.html,2.html”-output:key:“”value:“index.html”,Step3 根据PageRank值排序,说明：系统在处理Map函数的输出时，将把所有相同的key合并，并排序输出到Reduce函数的输入中。所以，Map函数只需要把PageRank值作为key输出，系统就会自动把key排序输出到reduce函数。Reduce函数只需依次输出每个value中的链接，就得到了按Pag

8、eRank排序的网页链接。至此，算法结束。,PageRank算法介绍PageRank算法的MapReduce实现实现一个简单的搜索引擎WordCount例程源码讲解,实现一个简单的搜索引擎,Step1：安装Hadoop运行环境Step2：获取网页集合存放到HDFS中Step3：编写MapReduce程序*Step4：将输出结果存储到分布式数据库中,Step1 安装Hadoop运行环境,1，安装linux系统，如Ubuntu11.04，这一步网上有详细的教程，请同学们自行学习2，在linux 平台上安装Hadoop。在Hadoop 官网(http:/hadoop.apache.org/)下载一个

9、Hadoop 版本：在以下页面中选择一个镜像站点下载，获取hadoop-0.20.2.tar.gz。http:/www.apache.org/dyn/closer.cgi/hadoop/common/,Step1 安装Hadoop运行环境,3，在Ubuntu系统上安装openssh-server:$sudo apt-get install openssh-server4，建立ssh无密码登陆：$ssh-keygen t dsa P f/.ssh/id_dsa该命令在/.ssh目录生成id_dsa和id_dsa.pub密钥对，我们把id_dsa.pub追加授权到key里面：$cat/.ssh/i

10、d_dsa.pub/.ssh/authorized_keys完成以后，就可以实现无密码登陆本机$ssh localhost5，关闭防火墙：$sudo ufw disable,Step1 安装Hadoop运行环境,6，安装jdk。http:/安装路径为/home/uname/jdk，添加环境变量到/etc/profile中：export JAVA_HOME=/home/uname/jdkexport JRE_HOME=/home/uname/jdk/jreexport CLASSPATH=.:$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATH（注：网上有许多jdk的安

11、装教程，同学们可以参考）,Step1 安装Hadoop运行环境,7，安装hadoop。$mv hadoop-0.20.2.tar.gz/hadoop-0.20.2.tar.gz$cd$tar zvxf hadoop-0.20.2.tar.gz添加hadoop的安装路径到/etc/profile中：export HADOOP_HOME=/home/uname/hadoop-0.20.2export path=$HADOOP_HOME/bin:$PATH,Step1 安装Hadoop运行环境,8，配置hadoop：(1)$HADOOP_HOME/conf/hadoop-env.sh中添加：expo

12、rt JAVA_HOME=/home/uname/jdk(2)conf/masters和conf/slaves文件中，将master和slave的地址都改为127.0.0.1(3)配置conf/core-site.xml,conf/hdfs-site.xml,conf/mapred-site.xml：,Step1 安装Hadoop运行环境,Core-site.xmlhadoop.tmp.dir/home/uname/tmpfs.default.namehdfs:/127.0.0.1:9000,Step1 安装Hadoop运行环境,hdfs-site.xmldfs.replication1由于是

13、只有一台机器的伪分布式，所以replication必须设置为1，否则运行会报错,Step1 安装Hadoop运行环境,mapred-site.xmlmapred.job.tracker127.0.0.1:9001,Step1 安装Hadoop运行环境,9，运行hadoop：$cd$HADOOP_HOME$cd bin格式化文件系统$hadoop namenode format启动hadoop$start-all.sh用jps命令查看java进程，可以知道hadoop是否启动成功,Step1 安装Hadoop运行环境,*10，安装eclipse，进行hadoop开发(在ubuntu图形界面下安装

14、eclipse，也可以用apt-get工具安装）。当然，也可以不使用eclipse，直接用vim编辑java程序，使用javac手动编译hadoop程序。,Step2 获取网页集合存放到HDFS中,在网上下载一些网页（当然如果能用爬虫爬取最好），最好是英文网页，这样可以以空格来区分关键字。把网页保存到一个文件夹中，例如取名叫web_set把所有网页存放到HDFS中：$hadoop fs copyFromLocal./web_set dfs_web_set,Step3 编写mapreduce程序,Map:-input:key:0value:x.htmlMap函数内的操作：读取value所代表的网

15、页文件，提取出网页的文本内容，按空格划分单词（参考WordCount.java的写法）-output:key:wordvalue:x.html,Reduce:-input:key:word value:Reduce函数的操作：对value中的网页根据pageRank排序。-output:key:word value:排序后的网页,Step3 编写mapreduce程序,说明：这个程序和标准的wordcount程序非常类似，请同学们仔细阅读hadoop源码包当中的WordCount.java的源代码。,*Step4：将输出结果存储到分布式数据库中,这一步需要安装HBase或者Cassandra分

16、布式数据库，模拟google的bigtable。有兴趣的同学可以可以查阅一些关于HBase或者Cassandra的资料，把Hadoop的计算结果存入到分布式数据库中，然后使用数据库提供的查询接口，就可以查出关键词所对应的网页了。（该步不作要求）,PageRank算法介绍PageRank算法的MapReduce实现实现一个简单的搜索引擎WordCount例程源码讲解,main函数,public static void main(String args)throws Exception Configuration conf=new Configuration();String otherArgs=

17、new GenericOptionsParser(conf,args).getRemainingArgs();if(otherArgs.length!=2)System.err.println(Usage:wordcount);System.exit(2);Job job=new Job(conf,word count);job.setJarByClass(WordCount.class);job.setMapperClass(TokenizerMapper.class);job.setCombinerClass(IntSumReducer.class);job.setReducerClass

18、(IntSumReducer.class);job.setOutputKeyClass(Text.class);job.setOutputValueClass(IntWritable.class);FileInputFormat.addInputPath(job,new Path(otherArgs0);FileOutputFormat.setOutputPath(job,new Path(otherArgs1);System.exit(job.waitForCompletion(true)?0:1);,main函数,MapReduce的Main函数的作用是做一些系统的配置，例如初始化Hado

19、op的Configuration类，Job类，设置Map,Reduce函数的输入输出参数类型，文件输入输出路径等工作。Main函数的编写有一些固定的规律和模式，我们可以对照一些经典的MapReduce程序或者参照一些编程文档来编写。,Map函数,1 private final static IntWritable one=new IntWritable(1);2 private Text word=new Text();3 public void map(Object key,Text value,Context context)4throws IOException,InterruptedE

20、xception 5 StringTokenizer itr=new StringTokenizer(value.toString();6 while(itr.hasMoreTokens()7 word.set(itr.nextToken();8 context.write(word,one);,第1,2行，IntWritable和Text类我们可以看作就是一个int类型和一个string类型。由于hadoop使用了JAVA RPC机制来实现通讯，所以调用的基本类型需要用对象来传递。因此Hadoop就用IntWritable和Text类来对int和string进行封装，对int和文本内容进行存

21、储、编码、解码，以此确保RPC的高效执行。,Map函数,第3行，Map函数的第一个参数，key是文本在文件中的偏移值，在这个程序中没有使用。根据Main函数中的设置，第二个参数value是整个文件文本对象，因此第5行value.toString()就把整个文本作为一个大字符串返回。该字符串返回到一个StringTokenizer的构造函数中。StringTokenizer是一个java自带的对象，用于分裂字符串。例如，new StringTokenizer(str,“,”)就表示以逗号为分隔符，分裂字符串str。如果没有第二个参数，就是默认以空格作为分隔符。所以，第五行，就是把整个文本以空格分

22、开成多个字符串（每个字符串就是一个单词了，因为单词以空格分开），保存到变量itr中。在接下来的循环语句中，就依次取出每个单词，并设置为Text，然后用context.write()输出。Map函数的第三个参数context是一个hadoop的类型，context.write()方法用于输出一个键值对。context.write(word,one)就输出了一个单词和它的计数。每个单词的计数当然为1，这个键值对输出到系统后，系统根据key进行合并。例如，一个文本中含有3个单词hello，那么map函数就是输出3个键值对(“hello”,1)，系统根据key值进行合并，于是合并为(“hello”,)

23、，这个键值对就输入给reduce函数。,Reduce函数,1 private IntWritable result=new IntWritable();2 public void reduce(Text key,Iterable values,Context context)3throws IOException,InterruptedException 4 int sum=0;5 for(IntWritable val:values)6 sum+=val.get();7 8 result.set(sum);9 context.write(key,result);,看懂了Map函数，Reduce函数应该很容易懂了。Key就是每一个单词，第57行的循环用于计算每一个key出现的次数。由于map函数中的输出是context.write(word,one)，因此这里的每个val.get()返回值都是1，sum就是最终的key的计数。由于sum是一个int型，而hadoop的输入输出键值对不能是java基本类型，必须是一个对象，所以需要用result.set(sum)实现类型转换，然后输出（key,result）。(key,result)键值对直接输出到了磁盘文件中，其输出路径在main函数中被指定。,谢谢,