`
AngelAndAngel
  • 浏览: 234302 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

PageRank算法java实现版本

阅读更多
   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实体表示类,代码如下:
/**
 * 网页entity
 * 
 * @author afei
 * 
 */
class HtmlEntity {

	private String path;
	private String content;
	/* 外链(本页面链接的其他页面) */
	private List<String> outLinks = new ArrayList<String>();

	/* 内链(另外页面链接本页面) */
	private List<String> inLinks = new ArrayList<String>();

	private double pr;

	public String getPath() {
		return path;
	}

	public void setPath(String path) {
		this.path = path;
	}

	public String getContent() {
		return content;
	}

	public void setContent(String content) {
		this.content = content;
	}

	public double getPr() {
		return pr;
	}

	public void setPr(double pr) {
		this.pr = pr;
	}

	public List<String> getOutLinks() {
		return outLinks;
	}

	public void setOutLinks(List<String> outLinks) {
		this.outLinks = outLinks;
	}

	public List<String> getInLinks() {
		return inLinks;
	}

	public void setInLinks(List<String> inLinks) {
		this.inLinks = inLinks;
	}

}

   
核心算法代码如下:
/**
 * pagerank算法实现
 * 
 * @author afei
 * 
 */
public class HtmlPageRank {

	/* 阀值 */
	public static double MAX = 0.00000000001;

	/* 阻尼系数 */
	public static double alpha = 0.85;

	public static String htmldoc = "D:\\workspace\\Test\\WebRoot\\htmldoc";

	public static Map<String, HtmlEntity> map = new HashMap<String, HtmlEntity>();

	public static List<HtmlEntity> list = new ArrayList<HtmlEntity>();

	public static double[] init;

	public static double[] pr;

	public static void main(String[] args) throws Exception {
		loadHtml();
		pr = doPageRank();
		while (!(checkMax())) {
			System.arraycopy(pr, 0, init, 0, init.length);
			pr = doPageRank();
		}
		for (int i = 0; i < pr.length; i++) {
			HtmlEntity he=list.get(i);
			he.setPr(pr[i]);
		}
		
		List<HtmlEntity> finalList=new ArrayList<HtmlEntity>();
		Collections.sort(list,new Comparator(){

			public int compare(Object o1, Object o2) {
				HtmlEntity h1=(HtmlEntity)o1;
				HtmlEntity h2=(HtmlEntity)o2;
				int em=0;
				if(h1.getPr()> h2.getPr()){
					em=-1;
				}else{
					em=1;
				}
				return em;
			}
			
		});
		
		for(HtmlEntity he:list){
			System.out.println(he.getPath()+" : "+he.getPr());
		}

	}

	/* pagerank步骤 */

	/**
	 * 加载文件夹下的网页文件,并且初始化pr值(即init数组),计算每个网页的外链和内链
	 */
	public static void loadHtml() throws Exception {
		File file = new File(htmldoc);
		File[] htmlfiles = file.listFiles(new FileFilter() {

			public boolean accept(File pathname) {
				if (pathname.getPath().endsWith(".html")) {
					return true;
				}
				return false;
			}

		});
		init = new double[htmlfiles.length];
		for (int i = 0; i < htmlfiles.length; i++) {
			File f = htmlfiles[i];
			BufferedReader br = new BufferedReader(new InputStreamReader(
					new FileInputStream(f)));
			String line = br.readLine();
			StringBuffer html = new StringBuffer();
			while (line != null) {
				line = br.readLine();
				html.append(line);
			}
			HtmlEntity he = new HtmlEntity();
			he.setPath(f.getAbsolutePath());
			he.setContent(html.toString());
			Parser parser = Parser.createParser(html.toString(), "gb2312");
			HtmlPage page = new HtmlPage(parser);
			parser.visitAllNodesWith(page);
			NodeList nodelist = page.getBody();
			nodelist = nodelist.extractAllNodesThatMatch(
					new TagNameFilter("A"), true);
			for (int j = 0; j < nodelist.size(); j++) {
				LinkTag outlink = (LinkTag) nodelist.elementAt(j);
				he.getOutLinks().add(outlink.getAttribute("href"));
			}

			map.put(he.getPath(), he);
			list.add(he);
			init[i] = 0.0;

		}
		for (int i = 0; i < list.size(); i++) {
			HtmlEntity he = list.get(i);
			List<String> outlink = he.getOutLinks();
			for (String ol : outlink) {
				HtmlEntity he0 = map.get(ol);
				he0.getInLinks().add(he.getPath());
			}
		}

	}

	/**
	 * 计算pagerank
	 * 
	 * @param init
	 * @param alpho
	 * @return
	 */
	private static double[] doPageRank() {
		double[] pr = new double[init.length];
		for (int i = 0; i < init.length; i++) {
			double temp = 0;
			HtmlEntity he0 = list.get(i);
			for (int j = 0; j < init.length; j++) {
				HtmlEntity he = list.get(j);
				// 计算对本页面链接相关总值
				if (i != j && he.getOutLinks().size() != 0
						&& he.getOutLinks().contains(he0.getPath())/*he0.getInLinks().contains(he.getPath())*/) {
					temp = temp + init[j] / he.getOutLinks().size();
				}

			}
			//经典的pr公式
			pr[i] = alpha + (1 - alpha) * temp;
		}
		return pr;
	}

	/**
	 * 判断前后两次的pr数组之间的差别是否大于我们定义的阀值 假如大于,那么返回false,继续迭代计算pr
	 * 
	 * @param pr
	 * @param init
	 * @param max
	 * @return
	 */
	private static boolean checkMax() {
		boolean flag = true;
		for (int i = 0; i < pr.length; i++) {
			if (Math.abs(pr[i] - init[i]) > MAX) {
				flag = false;
				break;
			}
		}
		return flag;
	}
	
	
	

}


  
直接运行算法类,得到的结果如下:

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 阿飞哥 转载请说明
腾讯微博:http://t.qq.com/duyunfeiRoom
新浪微博:http://weibo.com/u/1766094735
分享到:
评论
21 楼 cyxy99 2016-06-15  
u012534143 写道
我用同样的方法,同样的节点关系,为什么的得到的结果与您不一样呢?请教!!!

请问您的问题解决了吗?我也有相同的困惑///
20 楼 cyxy99 2016-06-15  
schaha123 写道
楼主还有一个问题想请教一下,下面这2段代码
for (int i = 0; i < list.size(); i++) {
HtmlEntity he = list.get(i);
List<String> outlink = he.getOutLinks();
for (String ol : outlink) {
HtmlEntity he0 = map.get(ol);
he0.getInLinks().add(he.getPath());
}
}
我理解的应该是获取网页的内链集合。但是在计算pr值时代码为:
if (i != j && he.getOutLinks().size() != 0
&& he.getOutLinks().contains(he0.getPath()))
{
    temp = temp + init[j] / he.getOutLinks().size();
}好像并没有用到内链集合。

我用爬虫抓取了几个简单的网页去测试该算法:在he0.getInLinks().add(he.getPath());这里会报错(空指针异常),如果注释掉第一段获取内链集合的代码,程序一切正常。使用您提供的测试集,结果和原来没注释一模一样,使用自己下载的网页,结果全是0.85(可能是下载的网页之间没什么相互链接关系吧).

这是什么原因了?

我也是相同的问题,改了路径和文件名一样,还是不行。
19 楼 u012534143 2016-04-21  
我用同样的方法,同样的节点关系,为什么的得到的结果与您不一样呢?请教!!!
18 楼 zhang_guiren 2014-10-30  
//经典的pr公式 
pr[i] = alpha + (1 - alpha) * temp; 
公式应该是
pr[i] =  alpha * temp+1-alpha;
1-alpha表示用户从URL进入网页的概率
17 楼 AngelAndAngel 2014-07-10  
lliiqiang 写道
厉害还要被别人知道.

???
16 楼 lliiqiang 2014-07-02  
厉害还要被别人知道.
15 楼 wangyh_87 2014-04-16  
AngelAndAngel 写道
schaha123 写道
楼主还有一个问题想请教一下,下面这2段代码
for (int i = 0; i < list.size(); i++) {
HtmlEntity he = list.get(i);
List<String> outlink = he.getOutLinks();
for (String ol : outlink) {
HtmlEntity he0 = map.get(ol);
he0.getInLinks().add(he.getPath());
}
}
我理解的应该是获取网页的内链集合。但是在计算pr值时代码为:
if (i != j && he.getOutLinks().size() != 0
&& he.getOutLinks().contains(he0.getPath()))
{
    temp = temp + init[j] / he.getOutLinks().size();
}好像并没有用到内链集合。

我用爬虫抓取了几个简单的网页去测试该算法:在he0.getInLinks().add(he.getPath());这里会报错(空指针异常),如果注释掉第一段获取内链集合的代码,程序一切正常。使用您提供的测试集,结果和原来没注释一模一样,使用自己下载的网页,结果全是0.85(可能是下载的网页之间没什么相互链接关系吧).

这是什么原因了?

你直接拿来用的话还要改装一下,因为你在网上抓取的网页的链接都是http开头,而不是具体的网页名字,我这里为了突出算法,就把链接地址当作文件名了。



请问楼主该怎么改装呢?
14 楼 wangyh_87 2014-04-16  
wangyh_87 写道
楼主, Parser parser = Parser.createParser(html.toString(), "gb2312");
HtmlPage page = new HtmlPage(parser);
parser.visitAllNodesWith(page);
NodeList nodelist = page.getBody();
nodelist = nodelist.extractAllNodesThatMatch(
new TagNameFilter("A"), true);
for (int j = 0; j < nodelist.size(); j++) {
LinkTag outlink = (LinkTag) nodelist.elementAt(j);
he.getOutLinks().add(outlink.getAttribute("href"));
}
Parse,NodeList,HtmlPage都是在哪个包中呀?程序前面有小叉号




知道了,htmlparser.jar
13 楼 wangyh_87 2014-04-16  
楼主, Parser parser = Parser.createParser(html.toString(), "gb2312");
HtmlPage page = new HtmlPage(parser);
parser.visitAllNodesWith(page);
NodeList nodelist = page.getBody();
nodelist = nodelist.extractAllNodesThatMatch(
new TagNameFilter("A"), true);
for (int j = 0; j < nodelist.size(); j++) {
LinkTag outlink = (LinkTag) nodelist.elementAt(j);
he.getOutLinks().add(outlink.getAttribute("href"));
}
Parse,NodeList,HtmlPage都是在哪个包中呀?程序前面有小叉号
12 楼 zy353003874 2014-03-12  
楼主,你这个是加载文件得到链接,那要是我要去爬取网站的链接改如何做呢?你知道的一个网站有上千个链接呀!
11 楼 AngelAndAngel 2012-10-22  
zzjj0116 写道
你好,如何加载进我的JAVA环境中,新手,不好意思了

把地址改成你自己的html所在地址,并且把你需要操作的网页里面改成互相连接的地址
10 楼 zzjj0116 2012-10-20  
你好,如何加载进我的JAVA环境中,新手,不好意思了
9 楼 hupenghui1224 2012-08-30  
楼主,为什么在初始化时把 init[]元素初始化为0?刚开始每个页面不都应该有一个初始的pr值吗?
8 楼 AngelAndAngel 2012-06-06  
schaha123 写道
楼主还有一个问题想请教一下,下面这2段代码
for (int i = 0; i < list.size(); i++) {
HtmlEntity he = list.get(i);
List<String> outlink = he.getOutLinks();
for (String ol : outlink) {
HtmlEntity he0 = map.get(ol);
he0.getInLinks().add(he.getPath());
}
}
我理解的应该是获取网页的内链集合。但是在计算pr值时代码为:
if (i != j && he.getOutLinks().size() != 0
&& he.getOutLinks().contains(he0.getPath()))
{
    temp = temp + init[j] / he.getOutLinks().size();
}好像并没有用到内链集合。

我用爬虫抓取了几个简单的网页去测试该算法:在he0.getInLinks().add(he.getPath());这里会报错(空指针异常),如果注释掉第一段获取内链集合的代码,程序一切正常。使用您提供的测试集,结果和原来没注释一模一样,使用自己下载的网页,结果全是0.85(可能是下载的网页之间没什么相互链接关系吧).

这是什么原因了?

你直接拿来用的话还要改装一下,因为你在网上抓取的网页的链接都是http开头,而不是具体的网页名字,我这里为了突出算法,就把链接地址当作文件名了。
7 楼 schaha123 2012-06-02  
schaha123 写道
程序中:pr[i] = alpha + (1 - alpha) * temp; 
为什么不是pr[i] =(1 - alpha)+ alpha * temp;
没看明白?

但是你的阻尼系数也是使用的通用值0.85啊。程序中为什么不是pr[i] =(1 - alpha)+ alpha * temp;难道您采用的不是常用值,是一个随便的值来计算的?
6 楼 schaha123 2012-06-02  
楼主还有一个问题想请教一下,下面这2段代码
for (int i = 0; i < list.size(); i++) {
HtmlEntity he = list.get(i);
List<String> outlink = he.getOutLinks();
for (String ol : outlink) {
HtmlEntity he0 = map.get(ol);
he0.getInLinks().add(he.getPath());
}
}
我理解的应该是获取网页的内链集合。但是在计算pr值时代码为:
if (i != j && he.getOutLinks().size() != 0
&& he.getOutLinks().contains(he0.getPath()))
{
    temp = temp + init[j] / he.getOutLinks().size();
}好像并没有用到内链集合。

我用爬虫抓取了几个简单的网页去测试该算法:在he0.getInLinks().add(he.getPath());这里会报错(空指针异常),如果注释掉第一段获取内链集合的代码,程序一切正常。使用您提供的测试集,结果和原来没注释一模一样,使用自己下载的网页,结果全是0.85(可能是下载的网页之间没什么相互链接关系吧).

这是什么原因了?
5 楼 AngelAndAngel 2012-06-01  
schaha123 写道
程序中:pr[i] = alpha + (1 - alpha) * temp; 
为什么不是pr[i] =(1 - alpha)+ alpha * temp;
没看明白?

呵呵 转换个思维啊,你说的和我说的没两样啊,看你对alpha怎么定义咯?
4 楼 schaha123 2012-06-01  
程序中:pr[i] = alpha + (1 - alpha) * temp; 
为什么不是pr[i] =(1 - alpha)+ alpha * temp;
没看明白?
3 楼 schaha123 2012-06-01  
AngelAndAngel 写道
schaha123 写道
楼主,程序有错误啊。
Exception in thread "main" java.lang.NullPointerException
at edu.guet.pagerank.HtmlPageRank.loadHtml(HtmlPageRank.java:108)
at edu.guet.pagerank.HtmlPageRank.main(HtmlPageRank.java:24)

是路径的问题,除了改动一下程序里面的路径,html里面的链接路径也改一下


明白了,可以运行了,谢谢!
2 楼 AngelAndAngel 2012-05-31  
schaha123 写道
楼主,程序有错误啊。
Exception in thread "main" java.lang.NullPointerException
at edu.guet.pagerank.HtmlPageRank.loadHtml(HtmlPageRank.java:108)
at edu.guet.pagerank.HtmlPageRank.main(HtmlPageRank.java:24)

是路径的问题,除了改动一下程序里面的路径,html里面的链接路径也改一下

相关推荐

    java实现和Matlab语言实现的pagerank算法

    **Java实现PageRank** 在`PageRank.java`中,Java版的PageRank算法通常会涉及以下几个关键步骤: 1. **初始化矩阵**:创建一个表示网页链接关系的矩阵,矩阵元素表示一个网页指向另一个网页的链接权重。 2. **迭代...

    无向图pagerank算法(Java)

    在"PageRank-master"这个压缩包文件中,可能包含了完整的PageRank算法Java实现,包括数据结构的定义、图的构建、PageRank的计算以及可能的测试用例。通过阅读源码,你可以更深入地理解算法的细节和实现技巧。

    pagerank算法实现

    二、pagerank算法的java实现 以下是pagerank算法的java实现代码: ```java package pagerank; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileReader; ...

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

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

    pagerank-java实现查询

    通过对这份资料的学习,我们可以深入理解PageRank算法的工作原理,并掌握如何用Java实现这一重要搜索引擎技术。这对于从事搜索引擎优化、网络数据分析或分布式计算等相关工作的人员来说是非常宝贵的资源。

    基于Java实现的pagerank算法.zip

    基于Java实现的Pagerank算法可以帮助开发者理解并应用这个概念。 首先,我们来详细解释一下Pagerank算法的基本原理。在互联网中,每个网页可以看作是一个节点,而链接则构成了这些节点之间的边。Pagerank算法通过...

    PageRank算法的C#实现

    近来自己在研究一下排序算法,结果在网上找了很久都只有两个Java实现的PageRank算法,其余的基本上是理论研究,对初学者帮助不大,希望能对你有些帮助。

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

    本项目提供了一个基于Java实现的无向图和加权图的PageRank算法版本,这将有助于我们理解算法的工作原理并进行实际应用。 1. **PageRank算法基础** PageRank算法的核心思想是:一个网页的重要性取决于链接到它的...

    java实现网页排名算法

    在本话题中,我们将专注于Java实现PageRank算法的详细过程。 PageRank是由Google创始人拉里·佩奇(Larry Page)提出的,它的基本思想是:一个被许多高质量网页链接的页面具有较高的PageRank值。这个概念反映了...

    在heritrix中使用pagerank算法

    在Heritrix网络爬虫中使用PageRank算法是提高网页抓取质量和效率的重要手段。PageRank是Google创始人 Larry Page提出的一种衡量网页重要性的算法,它通过分析网页之间的链接关系来评估网页的重要性。Heritrix是一个...

    PageRank-java.rar_pageRank_pagerank java

    这个"PageRank-java.rar_pageRank_pagerank java"压缩包包含的是PageRank算法的Java实现,对于理解该算法及其在网页排名中的应用具有实际价值。 在Java源码中,我们可以看到PageRank的基本思想和计算过程。PageRank...

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

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

    Java_PageRank.rar_pageRank_pagerank java

    Java中的PageRank算法是搜索引擎优化(SEO)...开发者可以通过这个项目学习到网络爬虫的基本工作方式,链接分析的技巧,以及如何用Java实现复杂的数学算法。同时,它也为网络数据挖掘和搜索引擎优化提供了实用的工具。

    PageRank简单演示算法

    以下是对PageRank算法的详细解释以及如何用Java实现的简要介绍。 PageRank的基本思想是:一个网页被其他网页链接的数量和质量决定了它的PageRank值。如果一个高PageRank的网页链接到另一个网页,那么被链接的网页也...

    pagerank.zip

    总结来说,本项目是使用Java和MapReduce技术实现PageRank算法,处理的数据集来源于"web-Google.txt"文件,它展示了如何在分布式环境中高效处理大规模的网络链接数据,评估网页的重要性。这不仅加深了对PageRank算法...

    pagerank算法

    PageRank算法是Google搜索引擎早期核心的排名算法之一,用于评估网页的重要性。这个算法的核心思想是,一个网页的价值不仅在于其自身的质量,更在于有多少高质量的网页链接到它。PageRank算法通过模拟用户在互联网上...

    TextRank, TextRank算法提取关键词的Java实现.zip

    这个“TextRank, TextRank算法提取关键词的Java实现.zip”压缩包文件包含了一个开源项目,名为“TextRank-master”,它提供了一种Java实现来提取文本中的关键词。 TextRank算法的核心思想是模拟PageRank在文本处理...

    PageRank1984.rar_PageRank1984_PageRank值_pageRank_pagerank java_p

    这个算法在1998年被引入,但在这个“PageRank1984.rar”压缩包中,我们可以看到一个早期的实现版本,尽管标题中出现了“1984”,实际上PageRank算法是在1998年才被公开的。 PageRank算法的基本原理是将互联网视为一...

    pageRank简单实现(Java)

    实现PageRank算法最为简单的代码,此代码使用java编写,适合与学习搜索引擎了解pageRank算法的初学者。

Global site tag (gtag.js) - Google Analytics