`
chencang
  • 浏览: 421982 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

PageRank算法的原理和源代码实现(java)

阅读更多

参考文章:

理论:竹笋炒肉:Google的PageRank算法学习 http://hedong.3322.org/archives/000199.html

算法: PageRank算法的原理和源代码实现(C++)http://renxijun.blog.sohu.com/60220486.html

模仿上面这个算法实现了java版的计算,我写的这个性能不好,3496987篇网页迭代1次居然需要3分钟左右,贴出来希望高手帮我指点改正。

package pagerank;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.Hashtable;
/*
linkmaptest.txt内容为
d00000-0 d00000-0 d00000-1 d00000-2
d00000-1 d00000-2 d00000-1
d00000-2 d00000-0
d00000-3 
*/
public class PageRank {

	public static void main(String[] args) throws Exception {

		String[] linesarr;
		Hashtable<String, Integer> docIDandNum = new Hashtable<String, Integer>();
		int total = 0;
		int father, son;
		int outdegree = 0;

		// 读取文件,得到docid,计算链接总数total,outdegree在迭代的时候计算
		File linkfile = new File("E:/larbin/linkmaptest.txt");
		BufferedReader linkinput = new BufferedReader(new FileReader(linkfile));
		String line = linkinput.readLine();
		while (line != null) {
			++total;
			linesarr = line.split(" ");
			if (linesarr.length > 0) {
				// outdegree = linesarr.length - 1;
				// for(int j = 1; j <= linesarr.length - 1; ++j) {
				// if(linesarr[j].equals(linesarr[0]))
				// outdegree--;
				// }
				if (linesarr[0] != null) {
					docIDandNum.put(linesarr[0], total);
					// System.out.println("链接" + linesarr[0] + "的出度为" + outdegree);
				}
			}
			linesarr = null;
			line = linkinput.readLine();
		}
		linkinput.close();
		// System.out.println("链接总数为:" + total);

		if (total > 0) {
			// pageRank[]存放PR值
			float[] pageRank = new float[total + 1]; 

			// 链入页面的计算总和
			float[] prTmp = new float[total + 1]; 

			 // 设置pageRank[]初始值为1.0f
			for (int i = 1; i <= total; ++i) {
				pageRank[i] = 1.0f;
				prTmp[i] = 0.0f;
			}

			 // 当前页面的PR值
			float fatherRank = 1f;

			// 阻尼系数d或称为alpha
			float alpha = 0.85f; 

			// 进行10次迭代
			for (int iterator = 0; iterator < 10; iterator++) { 
				long startTime = System.currentTimeMillis();

				linkinput = new BufferedReader(new FileReader(linkfile));
				line = linkinput.readLine();
				// 读出docid和outdegree和sons
				while (line != null) { 
					linesarr = line.split(" ");
					if (linesarr.length > 0) {
						outdegree = linesarr.length - 1;
						for (int j = 1; j <= linesarr.length - 1; ++j) {
							 // 指向自身的链接无效,不计算在内
							if (linesarr[j].equals(linesarr[0]))
								outdegree--;
						}
					}
					if (outdegree > 0) {
						father = (int) docIDandNum.get(linesarr[0]);
						 // 对应公式中的pr(Ti)/c(Ti),Ti为指向father的页面
						fatherRank = pageRank[father] / outdegree;
						for (int k = 1; k <= linesarr.length - 1; ++k) {
							if (linesarr[k].equals(linesarr[0])) {
								continue;
							}
							son = docIDandNum.get(linesarr[k]);
							if (total >= son && son >= 0) {
								prTmp[son] += fatherRank;
							}
						}
					}
					linesarr = null;
					line = linkinput.readLine();
				}

				// 准备下次迭代的初始值
				for (int i = 1; i <= total; ++i) 	{
					// PR公式1
					// prTmp[i] = 0.15f + alpha * prTmp[i];
					
					// PR公式2
					prTmp[i] = 0.15f / total + alpha * prTmp[i]; 

					// 每次迭代后的真正pr值
					pageRank[i] = prTmp[i]; 

					prTmp[i] = 0.0f;
				}
				// 打印出每次迭代值,此操作耗费时间和内存
				// for (int i = 1; i <= total; ++i)
				// System.out.print(pageRank[i] + " \t ");
				// System.out.println(" ");
				linkinput.close();

				long endTime = System.currentTimeMillis();
				System.out.println("第" + iterator + "次迭代耗时" + (endTime - startTime) + "ms");
			}

			//最终PR值输出至文件
			BufferedWriter newlink = new BufferedWriter(new FileWriter(
					new File("E:/larbin/pageranktest.txt")));
			for (int i = 1; i <= total; ++i) {
				// System.out.println(docIDandNum.toString());
				newlink.write(String.valueOf(pageRank[i]));
				newlink.newLine();
			}
			newlink.flush();
			newlink.close();
			pageRank = null;
			prTmp = null;
		}
	}
}

 

 学java有段时间了,但是总感觉自己不着道,第一次在论坛发帖,也希望大家指出我的很多不规范的地方,给我些改正的建议,分享些经验给新手们,(比如有什么好的书适合我,在编程习惯技巧等方面我应该如何去改正以便更加规范些),谢谢。

分享到:
评论
9 楼 opencvImage 2012-05-06  
你好!请问能不能把你Lucene结合PR进行排序优化的代码贴出来分享呢?不知道怎么把两者结合……谢谢啦!
8 楼 plantegg 2008-12-02  
这么晦涩的代码也给你翻译过来了,呵呵
你这性能有比较大的问题
检查IO,有没有反复读?
检查一些反复调用的计算

原始代码中BuildIndex很有用的,你再瞅瞅
7 楼 mayday85 2008-11-20  
对, 怎么全堆到main里了
6 楼 chencang 2008-11-20  
phz50 写道

这个好像写得很不错啊,不过我还是没能看太明白,想问一下linkmaptest.txt文件里面的内容是什么意思呢?

就是页面之间的链接关系啊
5 楼 chencang 2008-11-20  
frenchmay 写道

编码风格不是很好,面向对象的一些原则还没有搞清楚建议回归基础

嗯,谢谢建议
4 楼 frenchmay 2008-11-01  
编码风格不是很好,面向对象的一些原则还没有搞清楚
建议回归基础
3 楼 phz50 2008-10-31  
这个好像写得很不错啊,不过我还是没能看太明白,想问一下linkmaptest.txt文件里面的内容是什么意思呢?
2 楼 shellkk 2008-07-30  
这个速度很正常
1 楼 yining 2008-07-30  
做个profiling看看瓶颈在哪里,实在不行就先用NIO替换一下吧。

相关推荐

    搜索引擎PageRank算法实现及测试数据

    1. **源代码**:实现PageRank算法的编程语言代码,可能是Python、Java或C++等,用于计算网页的PageRank值。 2. **测试输入**:一组网页链接关系的数据结构,如邻接矩阵或邻接表,描述了网页间的链接关系。 3. **测试...

    java实现网页排名算法

    在压缩包中的"PageRank"文件可能包含了具体实现PageRank算法的Java源代码,包括数据结构、算法逻辑和测试用例。通过分析和运行这些代码,你可以更深入地理解PageRank算法的实现细节,并可能学习到如何优化算法性能,...

    基于Java实现的无向图+加权图的pagerank算法.zip

    这个Java实现的项目可以帮助开发者和学习者深入理解PageRank算法的细节,通过源代码调试和修改,可以更好地掌握算法的核心思想和实际操作。同时,对于网络分析和数据挖掘的初学者,这是一个很好的实践平台。

    Java_PageRank.rar_pageRank_pagerank java

    在这个"Java_PageRank.rar_pageRank_pagerank java"压缩包中,包含了几个关键的Java源代码文件,用于实现PageRank算法以及查询网站的收录情况。 1. **SimpleWebClient.java**:这是一个简单的网络客户端类,用于...

    搜索引擎源代码用java、jsp编写的搜索引擎源代码

    本项目提供了一套用Java和JSP(JavaServer Pages)编写的搜索引擎源代码,这对于学习和理解搜索引擎的工作原理,以及Java后端开发与Web交互有极大的帮助。下面我们将深入探讨相关知识点。 首先,Java是一种广泛使用...

    pagerank算法实现

    `MyPageRank`可能是Java源代码文件,实现了PageRank算法。代码中可能会包括以下几个关键部分: 1. 图结构的构建:使用邻接矩阵或邻接表来表示网页之间的链接关系。 2. 初始化PageRank值:所有网页初始PageRank值...

    山东大学大数据实验三:Hadoop实现PageRank

    2. **PageRankIter.java**:这是PageRank算法的主要实现部分。在Hadoop MapReduce框架中,迭代器通常用于处理需要多次迭代直到收敛的情况,如PageRank算法。在这个类中,可能包含了计算和更新每个网页PageRank值的...

    truncated-pagerank 计算源代码

    `truncated-pagerank`是一种优化的PageRank算法,它在大规模网络数据处理中非常有用,尤其是在图论和搜索引擎优化领域。PageRank是Google最早使用的网页排名算法之一,用于评估网页在网络中的重要性。这个算法的基本...

    PageRank:PageRank算法的一个实现

    通过阅读和分析源代码,我们可以深入理解PageRank算法的工作原理,并将其应用到实际的网页索引和搜索排名系统中。 PageRank算法虽然简单但强大,它不仅应用于搜索引擎,还在推荐系统、社交网络分析等领域有广泛的...

    经典算法实现 java C 实现 去 百度,google 的福音

    这个压缩包很可能包含了一系列的Java和C语言实现的经典算法源代码,这对于学习和参考非常有价值。通过阅读和理解这些代码,开发者可以加深对算法的理解,提升编程技能。同时,这些实现也可以直接应用于项目中,节省...

    使用Spark GraphX基于PageRank算法构建的一个仿微博用户好友的分布式推荐系统+源代码+文档说明

    1、资源内容: 2、代码特点:内含运行结果,不会运行可私信,参数化编程、...在社交网络中,PageRank算法有着广泛的应用,因此,本篇文章主要介绍其原理以及实战进行好友的推荐 ,最后实战项目的全部代码会在GitHub上开

    基于Spark+PageRank算法构建仿微博用户好友的分布式推荐系统.zip

    在项目文件"9876"中,可能包含了项目的源代码、数据文件、配置文件和运行脚本等。为了运行这个项目,你需要一个配置好的Spark环境,并按照提供的指南配置和运行代码。这可能涉及到设置Hadoop或HDFS(如果有的话)以...

    JAVA搜索引擎源代码,修正错误了

    在深入研究源代码之前,建议先了解搜索引擎的基本工作原理和Java编程基础。对于初学者,可以逐个文件阅读,理解每个类的功能,逐步建立起整个系统的工作流程。对于有经验的开发者,这个源代码可以作为参考,研究不同...

    【Web大数据挖掘】PageRank具体实现、推荐系统实现、大作业、大数据挖掘项目、毕业设计+源代码+文档说明

    ### 实现细节:1 算法简介:略2 WikiData数据集说明 2.1 数据总行数:103689--------该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用!&lt;项目介绍&gt;1...

    JSP搜索引擎的研究与实现(源代码).zip

    总结来说,这个压缩包提供了学习和研究如何使用JSP构建搜索引擎的完整资料,包括源代码、文档和项目报告,对于想要深入理解搜索引擎工作原理以及JSP开发的人来说,这是一个宝贵的资源。通过阅读文档、分析源码和实践...

    pagerank-clj:pagerank 算法的 Clojure 实现

    - `src/`: 源代码文件夹,包含了实现 PageRank 算法的 Clojure 代码。 - `test/`: 测试文件夹,包含了单元测试用例,用于验证算法的正确性。 - `project.clj`: 项目配置文件,定义了项目的依赖、版本和其他构建信息...

    Pagerank Example

    4. 编译Java源代码(Calculate.java, PageSystem.java, PageRank.java)。 5. 运行编译后的程序,并根据README中的指示输入参数。 通过这个示例,你可以深入理解PageRank算法的逻辑,学习如何在实际编程中应用这个...

    CH-8.6---PageRank.rar_Java 8

    总的来说,Java 8实现的Hadoop PageRank算法是一种高效、可扩展的解决方案,尤其适合处理大规模的互联网数据,帮助我们理解和评估网络中的信息结构。通过理解并应用这个算法,我们可以更好地优化网站的SEO策略,提升...

    北京大学网络大数据管理与应用大作业:pagerank

    - `src`:源代码目录,包含了实现Pagerank算法的Java或Scala代码。这里可能包含多个类,分别对应Spark和Hadoop的实现,以及数据读取、处理和结果输出的逻辑。 - `input_small`:这可能是输入数据的一个小样本或者...

    java简单搜索器源码(系统)

    Java简单搜索器源码系统是...总的来说,Java简单搜索器源码系统涵盖了Java编程基础、数据结构与算法、文件I/O、搜索算法、并发控制和自然语言处理等多个IT领域的知识点,是学习和理解搜索引擎工作原理的良好实践案例。

Global site tag (gtag.js) - Google Analytics