This post is written in Chinese. Please consider using Google Translate

PageRank是搜索引擎結果排序的重要算法，其依賴的方式是鏈接結構分析，大致解釋就是一個網頁A有一個指向另一個網頁B的鏈接，就相當於A給B投票，獲得投票越多的網頁的PageRank值越高。並不是每個網頁的投票權重都是一樣的，自己PageRank越大的網頁投票權重越大，所以PageRank的計算公式是遞歸的，需要迭代計算，直到結果收斂。

我使用Go語言對真實網頁的數據WT2g進行了PageRank的計算，計算出的結果分佈如下圖：

觀察發現，PageRank的分佈服從齊普夫分佈(Zipf Distribution)，其中32%的網頁的PageRank爲最小值9.459×10^-7，超過一半的網頁的PageRank的值小於6.600×10^-6，而PageRank的最大值爲1.885×10^-3。

值得一提的是Go語言，推薦一個對Go語言特性的介紹：Go在Google：以軟件工程爲目的的語言設計。使用Go語言最大的感受是它的函數可以有多返回值，而且在各種API中這個特性被大量使用，而且約定多返回值的最後一個參數是error類型，表示是否有錯誤發生。這種錯誤處理的方法和C++、Java、Python、JavaScript使用的異常不同，倒是與C語言的錯誤處理相似。C語言習慣於把函數的返回值作爲「是否有錯誤發生」的標記，如果有錯誤再通過其他的手段（如全局變量error）來獲取，Go語言直接把錯誤作爲了一個返回值。Go語言還支持一等函數(First Class Function)和閉包，因此方便用來實現yield功能，下面代碼中的lineReader函數就是返回了一個生成器，用來按行讀取文件，每調用一次讀取一行，讀完以後釋放內存。Go語言還是一個顯式有指針的語言，同時也提供了垃圾回收，省去了手動維護內存的麻煩。

以下是用Go語言計算PageRank的代碼：

package main

import (
    "bufio"
    "errors"
    "fmt"
    "io"
    "math"
    "os"
    "strings"
)

type vertex struct {
    inDegree  int
    outDegree int
    pagerank  float64
}

type edge struct {
    start int
    end   int
}

var vertexs []vertex
var edges []edge
var vertexID map[string]int = make(map[string]int)
var numVertex int = 0

func lineReader(filename string) (func() (string, error), error) {
    f, err := os.Open(filename)
    if err != nil {
        return nil, err
    }
    buf := bufio.NewReaderSize(f, 64)
    return func() (string, error) {
        line, isPrefix, err := buf.ReadLine()
        if err != nil {
            if err == io.EOF {
                if err := f.Close(); err != nil {
                    return "", err
                }
            }
            return "", err
        }
        if isPrefix {
            return "", errors.New("buffer size to small")
        }
        return string(line), nil
    }, nil
}

func addVertex(vertexName string) int {
    var ID int
    var ok bool
    if ID, ok = vertexID[vertexName]; !ok {
        ID = numVertex
        vertexID[vertexName] = ID
        vertexs = append(vertexs, vertex{})
        numVertex++
    }
    return ID
}

func read() {
    readline, err := lineReader("wt2g_inlinks.source")
    if err != nil {
        panic(err)
    }
    for {
        line, err := readline()
        if err != nil {
            if err == io.EOF {
                break
            }
            panic(err)
        }
        // Line format is like "ID1\tID2"
        sections := strings.Split(line, "\t")
        if len(sections) != 2 {
            panic(errors.New("Illegal line format"))
        }
        start := addVertex(sections[0])
        end := addVertex(sections[1])
        edges = append(edges, edge{start, end})
    }
}

func calcPagerank(alpha float64, numIterations int) {
    // Initialize out degree of every vertex
    for i := range edges {
        edge := &edges[i]
        vertexs[edge.start].outDegree++
        vertexs[edge.end].inDegree++
    }
    var I = make([]float64, numVertex)
    var S float64
    for i := 0; i < numVertex; i++ {
        vertexs[i].pagerank = 1 / float64(numVertex)
        I[i] = alpha / float64(numVertex)
    }
    // Calculate pagerank repeatedly until converge (numIterations times)
    for k := 0; k < numIterations; k++ {
        for i := range edges {
            edge := &edges[i]
            I[edge.end] += (1 - alpha) * vertexs[edge.start].pagerank / float64(vertexs[edge.start].outDegree)
        }
        S = 0
        for i := 0; i < numVertex; i++ {
            if vertexs[i].outDegree == 0 {
                S += (1 - alpha) * vertexs[i].pagerank / float64(numVertex)
            }
        }
        for i := 0; i < numVertex; i++ {
            vertexs[i].pagerank = I[i] + S
            I[i] = alpha / float64(numVertex)
        }
    }
}

func main() {
    read()
    calcPagerank(0.15, 30)
    fmt.Println("Done")
}

BYVNotes是一個我用Go語言實現的簡單在線記事本網站，使用了Revel框架。