先跟版主还有板友们说声抱歉啊 这不是学校作业啦(囧),只是想研究看看啊 我大致上了解PageRank的演算法啦: PR(pi) = (1-d)/N + Σ( PR(pj)/L(pj) ) PR(pi)为目标网页i的PR值 PR(pj)为具有指向网页i连结的网页j的PR值 L(pj)为网页j中超连结的数目 N为网页总数 d为随机浏览的机率,一般设定为0.85 不过在实作上就碰到了满多困难,例如如何parse之前所讲到的纪录所有连结资讯的txt档 然後把对所一网页的inLink outLink资讯作储存,才有办法算PageRank 因为八月才开始学java的关系,在写比较长的程式码时会碰到很多问题 於是之後找到了一个Package-WebLA http://webla.sourceforge.net/ 首页 http://webla.sourceforge.net/javadocs/ API documentation 其中包含了许多Link Analysis的演算法如PageRank'HITS和SimRank等等 比较重要的是WebGraph这个Class,可以parse文件档然後储存连结资讯 虽然里面写的输入格式跟我现有的资料格式不同,不过在修改和测试後也可以使用了 目前的问题就卡在另一个Class-PageRank上面了 其中的方法PageRank: public Double pageRank(String link) 输入参数为目标网址,会传回该网只在计算过後的PR值 计算了手边纪录了数十万笔连结资讯的txt档後(记忆体加到1G才有办法算) 出现了以下问题(连结资讯格式为url1 -> url2): 1.出现在右边的连结(如上一行的url2),传回值全都会是Infinity 2.出现在左边的连结(如上一行的url1),传回值几乎全部一样(PR值完全相同, 小部分不相同) 想说应该是计算PR值的方法出了问题吧,但是又一直找不出来问题在哪 因此想麻烦各位大大帮我看看是哪边写错了 谢谢 public void computePagerank(int iter) //iter为重复计算次数 { int n=graph.numNodes(); //WebGraph的方法 numNodes(),传回总节点(网页)数 double aux = (1-dampening)/n; //dampening即为d,随机浏览机率(0.85) while((iter--)>0) { Map newScore = new HashMap(); for (int j=0;j<n;j++) { Map inlinks = graph.inLinks(new Integer(j)); //inLinks方法传回参数型态为map,纪录所有具有连向网页pj超连结的网页url Iterator it = inlinks.keySet().iterator(); Double weight2 = new Double(0); while (it.hasNext()) { Integer link = (Integer)(it.next()); Double weight = (Double)(inlinks.get(link)); if(weight!=null && weight.doubleValue()>0) { int numLinks = 0; Map outlinks = graph.outLinks(link); Iterator it2 = inlinks.keySet().iterator(); while (it.hasNext()) { Integer l = (Integer)(it.next()); Double w = (Double)(outlinks.get(l)); if(w!=null && w.doubleValue()>0) numLinks++; } weight2 = new Double(weight2.doubleValue() + (((Double)(scores.get(link))).doubleValue()/numLinks)); } } weight2 = new Double(aux + dampening*weight2.doubleValue()); newScore.put(new Integer(j),weight2); } for (int j=0;j<n;j++) { scores.put(new Integer(j),(Double)(newScore.get(new Integer(j)))); } } } 整个程式码太长了所以贴我觉得有问题的部分 如果有需要再把其他部分也贴出来,或是上面网页也有程式码可以下载 先谢谢大家了 ※ 引述《willieliao (Willie Liao)》之铭言： : ※ 引述《kians (临兵斗者皆阵列在前)》之铭言： : : 如题,Google利用页面分析+PageRank技术达成了搜寻引擎霸主的地位 : : PageRank就是给予每一个网页一个value啦,用google自己发展的PageRank演算法 : : 用在搜寻後的网页排序,越重要的网页会放在越前面 : : 最近对PageRank满有兴趣的,要如何让电脑对数以亿计的网页进行运算 : : 一般的电脑根本不可能达成吧,有点想知道演算法是怎麽写的 : : 还是说关键在硬体? 用multiprocess的方式达成? : GOOG是用分散式运算 : : 有人用java写过PageRank的演算法嘛? : 单纯回答你的问题，有（举手） : 这是我在CARNEGIE MELLON CS大二资料结构的第三还是第四个作业，两周要写出来， : 而且包括CRAWLER（读取网页并TOKENIZE），INDEXER﹛让USER搜寻关键字），和PAGE : RANKING。我是用JAVA写的，据说GOOGLE是用RUBY写的，不过还请板上强者补充。 : 这里是我的作业的CLASS DIAGRAM，看看是不是你想要的 : http://www.willieliao.com/ooad/src/default.dfPackage.wmf : : 希望能找到范例来参考一下,想对手边有的几十万笔的连结资讯算出所有url的PageRank值 : : (格式(txt): url1->url2 : : url1->url3 : : url2->url3 : : . : : . : : . ) : : 不知道有没有办法办到,先谢谢各位罗 : 既然你只要算PAGERANK，那左边都不用管，建一个HASHMAP，对每一个右边的 : URL先去看看MAP里面有没有，没有的话用URL当KEY（假设你是STRING），用一个 : INTEGER HOLDER当DATA丢进去，KEY存在的话就把DATA的VALUE 加一 : 话说我怎麽闻到作业文的味道... --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.230.201.125