mapreducePageRank算法.doc

Mapreduce程序设计报告姓名： 学号： 题目： Wiki网页PageRank算法 1、 实验环境联想pc机虚拟机：VM 10.0操作系统：Centos 6.4Hadoop版本：hadoop 1.2.1Jdk版本：jdk-7u25Eclipse版本：eclipse-SDK-4.2.2-linux-gtk-x86_642、 实验设计及源程序2.1实验说明PageRank是Google的专有算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。PageRank实现了将链接价值概念作为排名因素。PageRank是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术，是Google用于用来标识网页的等级或重要性的一种方法。其级别从1到10级，PR值越高说明该网页越受欢迎、越重要。本次程序根据各网页之间的超链接关系和初始PR值，最终得到各网页的PR值，并按PR值排序。PR值高的网页说明有许多优质网页链接过来。每个网页的PR值可由公式2.1得到。 (2.1) 其中，pj为链接到网页i的所有网页。d表示阻尼因子，通常设为0.85。公式的前半部分表示一个上网者从一个随机网页开始浏览，随机浏览模型更符合用户的行为，一定程度上解决了rank sink的问题并且保证PageRank存在唯一值。公式的后半部分即表示由其他网页链接到网页i的PR值。2.2实验设计本实验由3个mapreduce程序完成，分别为GraphBuilder，PageRankIter，PageRankViewer，PageRankDriver。2.2.1 GraphBuilderGraphBuilder主要用来分析原始数据，建立各个网页之间的链接关系。 GraphBuilderMap这个类实现的map方法是逐行分析原始数据，输出，其中网页的URL作为key，PageRank初始值(PR_init)和网页的出度列表一起作为value，以字符串表示value，用特定的符号，如”:”将两者分开。static class GraphBuilder_Mapper extends Mapperprivate Text url = new Text();private Text url_list = new Text();public void map(LongWritable key, Text value, Context context)throws IOException, InterruptedException String vals = value.toString().split(s+);url.set(vals0);url_list.set(1:+vals1); /将每个网页的初始pr值设为1context.write(url, url_list);2.2.2 PangeRankIter PageRankIter主要用来迭代计算PR值，直到PR值收敛或迭代预定次数。 PageRankIterMap这个类的map方法实现的是对GraphBuilder的输出产生两种对，分别为和，其中u表示当前URL所链接到的网页ID，并作为key；Cur_rank为当前URL的PageRank值，|link_list|为当前URL的出度数量，cur_rank/|link_list|作为value。而输出的保持原来图的结构。static class PageRankIter_Mapper extends MapperOverrideprotected void setup(Context context)throws IOException, InterruptedException / TODO Auto-generated method stubN = 0;super.setup(context);Overridepublic void map(LongWritable key, Text value,Context context)throws IOException, InterruptedException String vals = value.toString().split(s+);String url = vals0;float cur = Float.parseFloat(vals1.split(:)0);String url_list = vals1.split(:)1.split(,);for(String u:url_list)float val = cur/url_list.length;context.write(new Text(u),new Text(+Float.toString(val);N+;context.write(new Text(url), new Text(vals1.split(:)1); PageRankIterReduce这个类的reduce方法中输入为两种形式的键值对，分别为和。其中为当前URL的链出信息，为当前URL的链如网页对其贡献的PageRank值。计算所有val的和，并乘上d，再加上常数(1-d)/N得到new_rank。输出为。static class PageRankIter_Reducer extends ReducerOverrideprotected void reduce(Text key, Iterable values,Context context)throws IOException, InterruptedException float pr = 0;float d = (float) 0.85;String url_list = null;for(Text val:values)String v = val.toString();if(v.contains() /含有的value为带有pr值的valuev = v.replace(,);pr = pr+Float.parseFloat(v);continue;url_list = v;float cur_pr = (1-d)/N+d*pr; /计算新的pr值 String out_value = Float.toString(cur_pr)+:+url_list;context.write(key, new Text(out_value);2.2.3PageRankViewerPageRankviewer输出最终排序结果。PageRankviewer从最后一次迭代的结果读出文件，并将文件名和其PR值读出，并以PR值作为key网页名为value，并且以PR值从大到小的顺序输出。 PageRankViewer_Mapperstatic class PageRankViewer_Mapper extends MapperOverrideprotected void map(LongWritable key, Text value, Context context)throws IOException, InterruptedException String vals = value.toString().split(s+);String url = vals0;float pr = Float.parseFloat(vals1.split(:)0);context.write(new FloatWritable(pr), new Text(url);/复写比较函数来实现从大到小逆序输出private static class DecFloatWritableComparator extends FloatWritable.ComparatorOverridepublic int compare(Object a, Object b) / TODO Auto-generated method stubreturn -pare(a, b);Overridepublic int compare(WritableComparable a, WritableComparable b) / TODO Auto-generated method stubreturn -pare(a, b);Overridepublic int compare(byte b1, int s1, int l1, byte b2, int s2, int l2) / TODO Auto-generated method stubreturn -pare(b1, s1, l1, b2, s2, l2);2.2.4PageRankDriverPageRankDriver主要是实现迭代的过程，用来完成迭代计算pr值的任务。public class PageRankDriver /deletetmp函数用来删除临时存储目录public static void deletetmp(String dir) throws IOExceptionConfiguration conf = new Configuration();Path path = new Path(dir);FileSystem fs = path.getFileSystem(conf);FileStatus fsts = fs.listStatus(path);for(FileStatus fst:fsts)if (fst.getPath().toString().contains(Data)fs.deleteOnExit(fst.getPath();fs.close();public static void main(String args) throws Exception / TODO Auto-generated method stubString path = hdfs:/localhost:8000/user/tzj/PageRank;String forItr = Data,Data;GraphBuilder.main(null);int i=0;for(i=0;i100;i+)forItr0 = path+/Data+(i);f