PageRank的MapReduce实现

Report
PageRank的MapReduce实现
2011-09

PageRank算法介绍

PageRank算法的MapReduce实现

实现一个简单的搜索引擎

WordCount例程源码讲解
PageRank算法介绍


PageRank算法由Google创始人之一Larry Page提
出,它是Google排名运算法则的一部分,是
Google用来标识网页的等级/重要性的一种方法,
是Google用来衡量一个网站好坏的重要标准之一。
Google通过PageRank来调整结果,使那些更具
“等级/重要性”的网页在搜索结果中的排名获得
提升,从而提高搜索结果的相关性和质量。该算
法的基本思想是被大量高质量网页引用(链接)
的网页也是高质量网页。
PageRank算法介绍
PR ( A )  (1  a )  a (
PR ( t1 )
C ( t1 )





PR ( t 2 )
C (t 2 )
 ... 
PR ( t n )
C (t n )
n
)  (1  a )  a 
i 1
PR ( t i )
C (ti )
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.html)
-output: (index.html , 1.html)
(index.html , 2.html)
…
(index.html , n.html)
Reduce:
-input:
key: “index.html”
value: “1.html”,…,”n.html”
-output:
key: ”index.html”
value: “1.0 1.html,…,n.html”
说明:输出为(key,value)键
值对,key为当前网页路径, 说明:Hadoop把Map函数输
value为当前网页中的对外
出的key合并,相同key的
的链接。
value合并成一个集合作为
reduce的value。输出key网页
的PR值(初值为1.0)
Step1 分析页面链接数
对于MapReduce程序,Map函数的输入为用户指定的
文件,那么输入的value值就是文件内容(可以配置成按
行读取或者把整个文件视作一个大字符串),key值是读
入文本的偏移量。程序员对输入的key,value进行一系列操
作,然后按(key,value)键值对的形式输出。需要注意的是:
输出的key,value是程序员自己定义的,可以和输入的
key,value毫不相关。
系统获取Map函数的输出,把相同的key合并,再把
key和value集合作为键值对作为reduce函数的输入。程序
员自定义reduce函数中的处理方法,输出(key,value)键值
对到磁盘文件。
Step2 迭代计算PageRank值
<number of outlinks>
Map:
-input:
<PageRank>
key: index.html
value:<PR>1.html,2.html…
Reduce:
-input:
Key: “1.html”
Value: ”index.html 0.5 23”,
-output:
key: “1.html”
Value: “index.html<PR>
<number of outlinks>”
Key: “2.html”
Value:” index.html<PR>
<number of outlinks>”
……
注意,这是
1.html的新PR值
”2.html 2.4 2”,……
key: “2.html”
value: “index.html 0.5 23”,
“1.html 1.3 3”,……
-output:
key:”1.html”
value:“<new PR>
index.html,2.html”
Step2 迭代计算PageRank值
说明:
step2是一个迭代过程,每次将磁盘上的文件读
入,key为每一个网页链接,value的第一项为当前
网页的PangRank值,后面接该网页中的对外链接。
Map函数将输入的每一对(key,value)“反转”成多对
(value,key)输出,也就是说,每个输出的key为输入
value中的每一个链接,而输出value为输入key的链
接+输入key的PR值+输入key的对外链接数。
在reduce函数中,就可以根据输入的value中的
参数来计算每一个key新的PageRank值,并按Map函
数的格式输出到磁盘,以作为下一次迭代的输入。
迭代多次后,PageRank值趋于稳定,就得出了较为
精确的PageRank值。
Step3 根据PageRank值排序
Map:
-input:
key: “index.html”
value: “<PR> 1.html,2.html”
-output:
key: “<PR>”
value: “index.html”
Step3 根据PageRank值排序
说明:系统在处理Map函数的输出时,将把所
有相同的key合并,并排序输出到Reduce函
数的输入中。所以,Map函数只需要把
PageRank值作为key输出,系统就会自动把
key排序输出到reduce函数。Reduce函数只
需依次输出每个value中的链接,就得到了
按PageRank排序的网页链接。至此,算法
结束。

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/ )下载一个
Hadoop 版本:在以下页面中选择一个镜像
站点下载,获取hadoop-0.20.2.tar.gz。
http://www.apache.org/dyn/closer.cgi/had
oop/common/
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追加授权到key里面 :
$cat ~/.ssh/id_dsa.pub >>~/.ssh/authorized_keys
完成以后,就可以实现无密码登陆本机
$ssh localhost
 5,关闭防火墙:$sudo ufw disable

Step1 安装Hadoop运行环境
6,安装jdk。
http://www.oracle.com/technetwork/java/javase
/downloads/index.html
安装路径为/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/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/hadoop0.20.2
export path=$HADOOP_HOME/bin:$PATH

Step1 安装Hadoop运行环境
8,配置hadoop:
(1)$HADOOP_HOME/conf/hadoop-env.sh中
添加:export
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.xml
<configuration>
<property>
<name>hadoop.tmp.dir</name>
<value>/home/uname/tmp</value>
</property>
<property>
<name>fs.default.name</name>
<value>hdfs://127.0.0.1:9000</value>
</property>
</configuration>
Step1 安装Hadoop运行环境
hdfs-site.xml
<configuration>
<property>
<name>dfs.replication</name>
<value>1</value>
</property>
</configuration>
由于是只有一台机器的伪分布式,所以
replication必须设置为1,否则运行会报错
Step1 安装Hadoop运行环境
mapred-site.xml
<configuration>
<property>
<name>mapred.job.tracker</name>
<value>127.0.0.1:9001</value>
</property>
</configuration>
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图形界面下安装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:0
value: x.html
Map函数内的操作:
读取value所代表的网页文
件,提取出网页的文本内
容,按空格划分单词(参
考WordCount.java的写法)
-output:
key: word
value: x.html
Reduce:
-input:
key: word
value: <1.html,2.html,…>
Reduce函数的操作:
对value中的网页根据
pageRank排序。
-output:
key: word
value: 排序后的网页
Step3 编写mapreduce程序

说明:这个程序和标准的wordcount程序非
常类似,请同学们仔细阅读hadoop源码包
当中的WordCount.java的源代码。
*Step4:将输出结果存储到分布式数据库中

这一步需要安装HBase或者Cassandra分布
式数据库,模拟google的bigtable。有兴趣
的同学可以可以查阅一些关于HBase或者
Cassandra的资料,把Hadoop的计算结果存
入到分布式数据库中,然后使用数据库提
供的查询接口,就可以查出关键词所对应
的网页了。(该步不作要求)

PageRank算法介绍

PageRank算法的MapReduce实现

实现一个简单的搜索引擎

WordCount例程源码讲解
main函数
public static void 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 <in> <out>");
System.exit(2);
}
Job job = new Job(conf, "word count");
job.setJarByClass(WordCount.class);
job.setMapperClass(TokenizerMapper.class);
job.setCombinerClass(IntSumReducer.class);
job.setReducerClass(IntSumReducer.class);
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(IntWritable.class);
FileInputFormat.addInputPath(job, new Path(otherArgs[0]));
FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));
System.exit(job.waitForCompletion(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
4
5
6
7
8
public void map(Object key, Text value, Context context)
throws IOException, InterruptedException {
StringTokenizer itr = new StringTokenizer(value.toString());
while (itr.hasMoreTokens()) {
word.set(itr.nextToken());
context.write(word, one);
}
}
第1,2行,IntWritable和Text类我们可以看作就是一个int类型
和一个string类型。由于hadoop使用了JAVA 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.write(word,one)就输出了一个单词和它的计数。
每个单词的计数当然为1,这个键值对输出到系统后,系统根据key进行合
并。例如,一个文本中含有3个单词hello,那么map函数就是输出3个键值
对(“hello”,1),系统根据key值进行合并,于是合并为 (“hello” , <1,1,1>),这
个键值对就输入给reduce函数。
Reduce函数
1 private IntWritable result = new IntWritable();
2 public void reduce( Text key, Iterable<IntWritable> values, Context context)
3
throws 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就是每一个单词,第
5~7行的循环用于计算每一个key出现的次数。由于map函数中的输出是
context.write(word, one),因此这里的每个val.get()返回值都是1,sum就是
最终的key的计数。由于sum是一个int型,而hadoop的输入输出键值对不
能是java基本类型,必须是一个对象,所以需要用result.set(sum)实现类型
转换,然后输出(key,result)。(key, result)键值对直接输出到了磁盘文件
中,其输出路径在main函数中被指定。
 谢谢 

similar documents