PageRank算法java实现版本

浏览数：23 / 时间：2015年06月08日

PageRank算法是Google的核心搜索算法，在所有链接型文档搜索中有极大用处，而且在我们的各种关联系统中都有好的用法，比如专家评分系统，微博搜索/排名,SNS系统等。 
   PageRank算法的依据或思想： 
    1，被重要的网页链接的越多（外链）  ，此网页就越重要 
    2，此网页对外的链接越少越重要 
    这两个依据不能是独立的，是需要一起考虑的。但是问题来了，我们怎样判断本网页的外链是很重要的呢？循环判断？那不死循环了？ 
    解决办法是：给定阀值，让循环在此临界处停止。 
   首先，我们准备了7个测试网页，这几个网页的链接情况如下: 
                                           

i\j test1 test2 test3 test4 test5 test6 test7
test1 0 1 1 0 0 0 0
test2 1 0 0 1 0 0 0
test3 0 0 0 1 1 1 0
test4 0 1 0 0 1 0 1
test5 0 0 1 1 0 0 0
test6 1 0 0 0 1 0 0
test7 0 1 0 1 0 0 1



  表格的意思是 test1链接到 test2,test3 ....依次类推 ，我们大致的根据上面两个原则可以猜一下，哪个将会是排名第一的网页?哪个最不重要? 
   貌似是test4和test6? 
   下面我们看看怎样用java实现PageRank算法。 
   首先创建html实体表示类，代码如下： 

Java代码  
  1. /** 
  2.  * 网页entity 
  3.  *  
  4.  * @author afei 
  5.  *  
  6.  */  
  7. class 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. }  


    
核心算法代码如下： 

Java代码  
  1. /** 
  2.  * pagerank算法实现 
  3.  *  
  4.  * @author afei 
  5.  *  
  6.  */  
  7. public 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 

此算法可以无限改造，以满足自身要求。 
另外说一句：这个table咋编辑成这幅德行了？改都改不回来。 


By 阿飞哥 转载请说明 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢