PageRank算法是Google的核心搜索算法，在所有链接型文档搜索中有极大用处，而且在我们的各种关联系统中都有好的用法，比如专家评分系统，微博搜索/排名,SNS系统等。
PageRank算法的依据或思想：
1，被重要的网页链接的越多（外链） ，此网页就越重要
2，此网页对外的链接越少越重要
这两个依据不能是独立的，是需要一起考虑的。但是问题来了，我们怎样判断本网页的外链是很重要的呢？循环判断？那不死循环了？
解决办法是：给定阀值，让循环在此临界处停止。
首先，我们准备了7个测试网页，这几个网页的链接情况如下:
表格的意思是 test1链接到 test2,test3 ....依次类推 ，我们大致的根据上面两个原则可以猜一下，哪个将会是排名第一的网页?哪个最不重要?
貌似是test4和test6?
下面我们看看怎样用java实现PageRank算法。
首先创建html实体表示类，代码如下：
1/** 2 * 网页entity 3 * 4 * @author afei 5 * 6 */ 7class HtmlEntity { 8 9 private String path; 10 private String content; 11 /* 外链(本页面链接的其他页面) */ 12 private List<String> outLinks = new ArrayList<String>(); 13 14 /* 内链(另外页面链接本页面) */ 15 private List<String> inLinks = new ArrayList<String>(); 16 17 private double pr; 18 19 public String getPath() { 20 return path; 21 } 22 23 public void setPath(String path) { 24 this.path = path; 25 } 26 27 public String getContent() { 28 return content; 29 } 30 31 public void setContent(String content) { 32 this.content = content; 33 } 34 35 public double getPr() { 36 return pr; 37 } 38 39 public void setPr(double pr) { 40 this.pr = pr; 41 } 42 43 public List<String> getOutLinks() { 44 return outLinks; 45 } 46 47 public void setOutLinks(List<String> outLinks) { 48 this.outLinks = outLinks; 49 } 50 51 public List<String> getInLinks() { 52 return inLinks; 53 } 54 55 public void setInLinks(List<String> inLinks) { 56 this.inLinks = inLinks; 57 } 58 59}
核心算法代码如下：
1/** 2 * pagerank算法实现 3 * 4 * @author afei 5 * 6 */ 7public class HtmlPageRank { 8 9 /* 阀值 */ 10 public static double MAX = 0.00000000001; 11 12 /* 阻尼系数 */ 13 public static double alpha = 0.85; 14 15 public static String htmldoc = "D:\\workspace\\Test\\WebRoot\\htmldoc"; 16 17 public static Map<String, HtmlEntity> map = new HashMap<String, HtmlEntity>(); 18 19 public static List<HtmlEntity> list = new ArrayList<HtmlEntity>(); 20 21 public static double[] init; 22 23 public static double[] pr; 24 25 public static void main(String[] args) throws Exception { 26 loadHtml(); 27 pr = doPageRank(); 28 while (!(checkMax())) { 29 System.arraycopy(pr, 0, init, 0, init.length); 30 pr = doPageRank(); 31 } 32 for (int i = 0; i < pr.length; i++) { 33 HtmlEntity he=list.get(i); 34 he.setPr(pr[i]); 35 } 36 37 List<HtmlEntity> finalList=new ArrayList<HtmlEntity>(); 38 Collections.sort(list,new Comparator(){ 39 40 public int compare(Object o1, Object o2) { 41 HtmlEntity h1=(HtmlEntity)o1; 42 HtmlEntity h2=(HtmlEntity)o2; 43 int em=0; 44 if(h1.getPr()> h2.getPr()){ 45 em=-1; 46 }else{ 47 em=1; 48 } 49 return em; 50 } 51 52 }); 53 54 for(HtmlEntity he:list){ 55 System.out.println(he.getPath()+" : "+he.getPr()); 56 } 57 58 } 59 60 /* pagerank步骤 */ 61 62 /** 63 * 加载文件夹下的网页文件，并且初始化pr值(即init数组)，计算每个网页的外链和内链 64 */ 65 public static void loadHtml() throws Exception { 66 File file = new File(htmldoc); 67 File[] htmlfiles = file.listFiles(new FileFilter() { 68 69 public boolean accept(File pathname) { 70 if (pathname.getPath().endsWith(".html")) { 71 return true; 72 } 73 return false; 74 } 75 76 }); 77 init = new double[htmlfiles.length]; 78 for (int i = 0; i < htmlfiles.length; i++) { 79 File f = htmlfiles[i]; 80 BufferedReader br = new BufferedReader(new InputStreamReader( 81 new FileInputStream(f))); 82 String line = br.readLine(); 83 StringBuffer html = new StringBuffer(); 84 while (line != null) { 85 line = br.readLine(); 86 html.append(line); 87 } 88 HtmlEntity he = new HtmlEntity(); 89 he.setPath(f.getAbsolutePath()); 90 he.setContent(html.toString()); 91 Parser parser = Parser.createParser(html.toString(), "gb2312"); 92 HtmlPage page = new HtmlPage(parser); 93 parser.visitAllNodesWith(page); 94 NodeList nodelist = page.getBody(); 95 nodelist = nodelist.extractAllNodesThatMatch( 96 new TagNameFilter("A"), true); 97 for (int j = 0; j < nodelist.size(); j++) { 98 LinkTag outlink = (LinkTag) nodelist.elementAt(j); 99 he.getOutLinks().add(outlink.getAttribute("href")); 100 } 101 102 map.put(he.getPath(), he); 103 list.add(he); 104 init[i] = 0.0; 105 106 } 107 for (int i = 0; i < list.size(); i++) { 108 HtmlEntity he = list.get(i); 109 List<String> outlink = he.getOutLinks(); 110 for (String ol : outlink) { 111 HtmlEntity he0 = map.get(ol); 112 he0.getInLinks().add(he.getPath()); 113 } 114 } 115 116 } 117 118 /** 119 * 计算pagerank 120 * 121 * @param init 122 * @param alpho 123 * @return 124 */ 125 private static double[] doPageRank() { 126 double[] pr = new double[init.length]; 127 for (int i = 0; i < init.length; i++) { 128 double temp = 0; 129 HtmlEntity he0 = list.get(i); 130 for (int j = 0; j < init.length; j++) { 131 HtmlEntity he = list.get(j); 132 // 计算对本页面链接相关总值 133 if (i != j && he.getOutLinks().size() != 0 134 && he.getOutLinks().contains(he0.getPath())/*he0.getInLinks().contains(he.getPath())*/) { 135 temp = temp + init[j] / he.getOutLinks().size(); 136 } 137 138 } 139 //经典的pr公式 140 pr[i] = alpha + (1 - alpha) * temp; 141 } 142 return pr; 143 } 144 145 /** 146 * 判断前后两次的pr数组之间的差别是否大于我们定义的阀值 假如大于，那么返回false，继续迭代计算pr 147 * 148 * @param pr 149 * @param init 150 * @param max 151 * @return 152 */ 153 private static boolean checkMax() { 154 boolean flag = true; 155 for (int i = 0; i < pr.length; i++) { 156 if (Math.abs(pr[i] - init[i]) > MAX) { 157 flag = false; 158 break; 159 } 160 } 161 return flag; 162 } 163 164 165 166 167}
直接运行算法类，得到的结果如下：
D:\workspace\Test\WebRoot\htmldoc\test4.html : 1.102472450686259
D:\workspace\Test\WebRoot\htmldoc\test5.html : 1.068131842865856
D:\workspace\Test\WebRoot\htmldoc\test2.html : 1.0249590169406457
D:\workspace\Test\WebRoot\htmldoc\test3.html : 1.0046891014946187
D:\workspace\Test\WebRoot\htmldoc\test1.html : 0.9943895104008613
D:\workspace\Test\WebRoot\htmldoc\test7.html : 0.9051236225340915
D:\workspace\Test\WebRoot\htmldoc\test6.html : 0.9002344550746025
此算法可以无限改造，以满足自身要求。
By 阿飞哥 转载请说明