PageRank的MapReduce实现

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: -inp

3、ut: (0 , index.html) -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合并成一个

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

5、duce函数中的处理方法，输出(key,value)键值对到磁盘文件。,Step2 迭代计算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”,

6、 “1.html 1.3 3”, -output: key:”1.html” value:“ index.html,2.html”,注意，这是1.html的新PR值,Step2 迭代计算PageRank值,说明： step2是一个迭代过程，每次将磁盘上的文件读入，key为每一个网页链接，value的第一项为当前网页的PangRank值，后面接该网页中的对外链接。Map函数将输入的每一对(key,value)“反转”成多对(value,key)输出，也就是说，每个输出的key为输入value中的每一个链接，而输出value为输入key的链接+输入key的PR值+输入key的对外链接数。 在red

7、uce函数中，就可以根据输入的value中的参数来计算每一个key新的PageRank值，并按Map函数的格式输出到磁盘，以作为下一次迭代的输入。迭代多次后，PageRank值趋于稳定，就得出了较为精确的PageRank值。,Step3 根据PageRank值排序,Map: -input: key: “index.html” value: “ 1.html,2.html” -output: key: “” value: “index.html”,Step3 根据PageRank值排序,说明：系统在处理Map函数的输出时，将把所有相同的key合并，并排序输出到Reduce函数的输入中。所以，Ma

8、p函数只需要把PageRank值作为key输出，系统就会自动把key排序输出到reduce函数。Reduce函数只需依次输出每个value中的链接，就得到了按PageRank排序的网页链接。至此，算法结束。,PageRank算法介绍 PageRank算法的MapReduce实现 实现一个简单的搜索引擎 WordCount例程源码讲解,实现一个简单的搜索引擎,Step1：安装Hadoop运行环境 Step2：获取网页集合存放到HDFS中 Step3：编写MapReduce程序 *Step4：将输出结果存储到分布式数据库中,Step1 安装Hadoop运行环境,1，安装linux系统，如Ubunt

9、u11.04，这一步网上有详细的教程，请同学们自行学习 2，在linux 平台上安装Hadoop。在Hadoop 官网( )下载一个Hadoop 版本：在以下页面中选择一个镜像站点下载，获取hadoop-0.20.2.tar.gz。,Step1 安装Hadoop运行环境,3，在Ubuntu系统上安装openssh-server: $sudo apt-get install openssh-server 4，建立ssh无密码登陆： $ssh-keygen t dsa P f /.ssh/id_dsa 该命令在/.ssh目录生成id_dsa和id_dsa.pub密钥对，我们把id_dsa.pub追

10、加授权到key里面 ： $cat /.ssh/id_dsa.pub /.ssh/authorized_keys 完成以后，就可以实现无密码登陆本机 $ssh localhost 5，关闭防火墙：$sudo ufw disable,Step1 安装Hadoop运行环境,6，安装jdk。 安装路径为/home/uname/jdk，添加环境变量到/etc/profile中： export JAVA_HOME=/home/uname/jdk export JRE_HOME=/home/uname/jdk/jre export CLASSPATH= .:$JAVA_HOME/lib:$JRE_HOME/

11、lib:$CLASSPATH （注：网上有许多jdk的安装教程，同学们可以参考）,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.2 export path=$HADOOP_HOME/bin:$PATH,Step1 安装Hadoop运行环境,8，配置hadoop： (1)$

12、HADOOP_HOME/conf/hadoop-env.sh中添加：export JAVA_HOME=/home/uname/jdk (2)conf/masters和conf/slaves文件中，将master和slave的地址都改为 (3)配置conf/core-site.xml, conf/hdfs-site.xml, conf/mapred-site.xml：,Step1 安装Hadoop运行环境,Core-site.xml hadoop.tmp.dir /home/uname/tmp hdfs:/:9000 ,Step

13、1 安装Hadoop运行环境,hdfs-site.xml dfs.replication 1 由于是只有一台机器的伪分布式，所以replication必须设置为1，否则运行会报错,Step1 安装Hadoop运行环境,mapred-site.xml mapred.job.tracker :9001 ,Step1 安装Hadoop运行环境,9，运行hadoop： $ cd $HADOOP_HOME $ cd bin 格式化文件系统 $ hadoop namenode format 启动hadoop $ start-all.sh 用jps命令查看java进程，可以知道hadoop

14、是否启动成功,Step1 安装Hadoop运行环境,*10，安装eclipse，进行hadoop开发(在ubuntu图形界面下安装eclipse，也可以用apt-get工具安装）。当然，也可以不使用eclipse，直接用vim编辑java程序，使用javac手动编译hadoop程序。,Step2 获取网页集合存放到HDFS中,在网上下载一些网页（当然如果能用爬虫爬取最好），最好是英文网页，这样可以以空格来区分关键字。把网页保存到一个文件夹中，例如取名叫web_set 把所有网页存放到HDFS中： $hadoop fs copyFromLocal ./web_set dfs_web_set,St

15、ep3 编写mapreduce程序,Map: -input: key:0 value: x.html Map函数内的操作： 读取value所代表的网页文件，提取出网页的文本内容，按空格划分单词（参考WordCount.java的写法） -output: key: word value: x.html,Reduce: -input: key: word value: Reduce函数的操作： 对value中的网页根据pageRank排序。 -output: key: word value: 排序后的网页,Step3 编写mapreduce程序,说明：这个程序和标准的wordcount程序非常类似

16、，请同学们仔细阅读hadoop源码包当中的WordCount.java的源代码。,*Step4：将输出结果存储到分布式数据库中,这一步需要安装HBase或者Cassandra分布式数据库，模拟google的bigtable。有兴趣的同学可以可以查阅一些关于HBase或者Cassandra的资料，把Hadoop的计算结果存入到分布式数据库中，然后使用数据库提供的查询接口，就可以查出关键词所对应的网页了。（该步不作要求）,PageRank算法介绍 PageRank算法的MapReduce实现 实现一个简单的搜索引擎 WordCount例程源码讲解,main函数,public static void

17、 main(String args) throws Exception Configuration conf = new Configuration(); String otherArgs = 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

18、.class); job.setMapperClass(TokenizerMapper.class); job.setCombinerClass(IntSumReducer.class); job.setReducerClass(IntSumReducer.class); job.setOutputKeyClass(Text.class); job.setOutputValueClass(IntWritable.class); (job, new Path(otherArgs0); (job, new Path(otherArgs1); System.exit(job.waitForCompl

19、etion(true) ? 0 : 1); ,main函数,MapReduce的Main函数的作用是做一些系统的配置，例如初始化Hadoop的Configuration类，Job类，设置Map, Reduce函数的输入输出参数类型，文件输入输出路径等工作。 Main函数的编写有一些固定的规律和模式，我们可以对照一些经典的MapReduce程序或者参照一些编程文档来编写。,Map函数,1 private final static IntWritable one = new IntWritable(1); 2 private Text word = new Text(); 3 public voi

20、d map(Object key, Text value, Context context) 4throws IOException, InterruptedException 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使用了JA

21、VA RPC机制来实现通讯，所以调用的基本类型需要用对象来传递。因此Hadoop就用IntWritable和Text类来对int和string进行封装，对int和文本内容进行存储、编码、解码，以此确保RPC的高效执行。,Map函数,第3行，Map函数的第一个参数，key是文本在文件中的偏移值，在这个程序中没有使用。 根据Main函数中的设置，第二个参数value是整个文件文本对象，因此第5行value.toString() 就把整个文本作为一个大字符串返回。该字符串返回到一个StringTokenizer的构造函数中。StringTokenizer是一个java自带的对象，用于分裂字符串。例如，new StringTokenizer(str , “,”)就表示以逗号为分隔符，分裂字符串str。如果没有第二个参数，就是默认以空格作为分隔符。所以，第五行，就是把整个文本以空格分开成多个字符串（每个字符串就是一个单词了，因为单词以空格分开），保存到变量itr中。在接下来的循环语句中，就依次取出每个单词，并设置为Text，然后用context.write()输出。 Map函数的第三个参数context是一个hadoop的类型，context.write()方法用于输出一个键值对。context.