PageRankアルゴリズムjava実装バージョン
PageRankアルゴリズムはGoogleのコア検索アルゴリズムであり、すべてのリンク型ドキュメントの検索に大きな役割を果たしています.また、専門家採点システム、微博検索/ランキング、SNSシステムなど、様々な関連システムに良い使い方があります.
PageRankアルゴリズムの根拠または思想:
1,重要なページにリンクされたものが多い(チェーン外) ,このホームページはもっと重要です.
2,このページの対外的なリンクが少ないほど重要です.
この二つの根拠は独立ではなく、一緒に考えるべきです.しかし、問題が来ました.このページの外部チェーンをどう判断するかが重要です.サイクル判定?では死なないようにしますか?
解決方法は、しきい値を与えて、この臨界でループを停止させることです.
まず、7つのテストページを用意しました.このいくつかのページのリンク状況は以下の通りです.
i\j
test 1
test 2
test 3
test 4
test 5
test 6
test 7
test 1
0
1
1
0
0
0
0
test 2
1
0
0
1
0
0
0
test 3
0
0
0
1
1
1
0
test 4
0
1
0
0
1
0
1
test 5
0
0
1
1
0
0
0
test 6
1
0
0
0
1
0
0
test 7
0
1
0
1
0
0
1
表の意味はtest 1がtest 2、test 3にリンクしているということです.逐次類推します.私たちは大体上の二つの原則から推測してみます.どれがランキング1のページになりますか?どれが一番重要ではないですか
test 4とtest 6のようです.
次に、JavaでPageRankアルゴリズムを実現する方法を見てみます.
まずhtmlエンティティ表示クラスを作成します.コードは以下の通りです.
コアアルゴリズムコードは以下の通りです.
アルゴリズムクラスを直接実行して得られた結果は以下の通りです.
D:\workspace\Test\WebRoot\httmldoc\test 4.html:1.1024724506859
D:\workspace\Test\WebRoot\httmldoc\test 5.html:1.068138428656
D:\workspace\Test\WebRoot\httmldoc\test 2.html:1.024959016940457
D:\workspace\Test\WebRoot\httmldoc\test 3.html:1.004068910946187
D:\workspace\Test\WebRoot\httmldoc\test 1.html:0.994389510808613
D:\workspace\Test\WebRoot\httmldoc\test 7.html:0.90536225340915
D:\workspace\Test\WebRoot\httmldoc\test 6.html:0.900234545746025
このアルゴリズムは自身の要求を満たすために無限に改造できる.
このテーブルはどうやってこの徳行に編集されましたか?もう全部直せません.
Byトビの転載について説明してください.
騰訊微博:
http://t.qq.com/duyunfeiRoom
新浪微博:
http://weibo.com/u/1766094735
PageRankアルゴリズムの根拠または思想:
1,重要なページにリンクされたものが多い(チェーン外) ,このホームページはもっと重要です.
2,このページの対外的なリンクが少ないほど重要です.
この二つの根拠は独立ではなく、一緒に考えるべきです.しかし、問題が来ました.このページの外部チェーンをどう判断するかが重要です.サイクル判定?では死なないようにしますか?
解決方法は、しきい値を与えて、この臨界でループを停止させることです.
まず、7つのテストページを用意しました.このいくつかのページのリンク状況は以下の通りです.
i\j
test 1
test 2
test 3
test 4
test 5
test 6
test 7
test 1
0
1
1
0
0
0
0
test 2
1
0
0
1
0
0
0
test 3
0
0
0
1
1
1
0
test 4
0
1
0
0
1
0
1
test 5
0
0
1
1
0
0
0
test 6
1
0
0
0
1
0
0
test 7
0
1
0
1
0
0
1
表の意味はtest 1がtest 2、test 3にリンクしているということです.逐次類推します.私たちは大体上の二つの原則から推測してみます.どれがランキング1のページになりますか?どれが一番重要ではないですか
test 4とtest 6のようです.
次に、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\httmldoc\test 4.html:1.1024724506859
D:\workspace\Test\WebRoot\httmldoc\test 5.html:1.068138428656
D:\workspace\Test\WebRoot\httmldoc\test 2.html:1.024959016940457
D:\workspace\Test\WebRoot\httmldoc\test 3.html:1.004068910946187
D:\workspace\Test\WebRoot\httmldoc\test 1.html:0.994389510808613
D:\workspace\Test\WebRoot\httmldoc\test 7.html:0.90536225340915
D:\workspace\Test\WebRoot\httmldoc\test 6.html:0.900234545746025
このアルゴリズムは自身の要求を満たすために無限に改造できる.
このテーブルはどうやってこの徳行に編集されましたか?もう全部直せません.
Byトビの転載について説明してください.
騰訊微博:
http://t.qq.com/duyunfeiRoom
新浪微博:
http://weibo.com/u/1766094735