pagerank演算法實現java

1. pagerank是什麼

PageRank是Google衡量網頁重要性的工具，測量值范圍為從1至10分別表示某網頁的重要性。在Google工具欄可以隨時獲得某網頁的PageRank值。在這里我們將透視PageRank的一些特殊之處，從而對其能夠獲得較為深入的了解，使廣大用戶能夠更好的使用和了解Googel。

網站 排名的歷史淵源

上世紀90年代早期網路剛剛興起之時，每天都有大量的含有特別行業內容的站點發布於網上。網上沖浪者卻沒有相應的工具定位這些他們認為存在的，但是卻沒有辦法找到域名或網址的站點。到了1993年，雅虎誕生了。雅虎的誕生為網民減輕了這些煩惱。雅虎最初將每一個它所找到的網站，按照所屬的分類目錄進行劃分組織，建立起一個整潔的、可以逐級查找的資料庫，雅虎同時也在網站上置入一個 搜索引擎可以根據資料庫中存在的「關鍵詞」搜索到網站。接著其他搜索引擎如Altavista ，Excite， Lycos等也相繼推出供用戶使用的搜索工具。他們中的大多數是根據找到的元標識中的關鍵詞來識別網站的相關性。

事情好像發展地很順利，但是當站主及網管意識到可以在元標識中插入行業關鍵詞或其他站點代碼，就可以巧妙的得到搜索結果頁面上的較高的位置的時候問題來了。有一段時間，搜索引擎的結果被這些垃圾網站搞得亂七八糟，他們用某些相關的關鍵詞充斥於網站的各個角落，可是展現在用戶面前的實際內容確實糟糕透頂。那些信用較高、地位重要的搜索引擎開始受到挑戰，他們必須採取更好的措施精確為用戶輸出的搜索結果。

Google網頁級別祥解

Google意識到了傳統搜索引擎所面臨的這種問題。如果相關性有網管來控制的話，那麼排名結果必將被他們人為安排的大量相關關鍵詞所污染，掩蔽了真正的相關性。

網路的本質就是超鏈接。我們從邏輯上分析，每個人都讓自己的網站與某些重要的站點相鏈接，那麼，本質上，這個站點就投了對方的一票。當上百上千個站點鏈接到這個站點時，我們認為這個站點是一個很好的很重要的站點也就非常符合邏輯了。

就是在這樣的邏輯推理下，Google的兩位創始人Sergey Brin及Larry Page建立了一個搜索引擎演算法公式，即將排名比重轉移到了網頁意外的因素上。他們的公式被命名為「PageRank」（以創建人Larry Page的名字命名）。Google就是利用這一公式計算鏈接到某一網頁的網站數量，然後按照從1－10分別給予表示重要度的分數。鏈接到網頁的站點越多，PageRank的分數越高。

Sergey Brin和Larry Page在1998年把PageRank技術配置進Google一同推出。結果出乎的成功。Google這種難以認為控制的演算法公司得出的出眾的相關結果大大超過了競爭對手。這種新的演算法不僅有助於提供出權威的高質量的信息，而且使得站主即網管很難利用作弊手段取得較高排名。

Google的PageRank之所以如此重要，就是因為影響網頁排名的因素主要是依賴於網頁意外的因素，而非能夠認為操縱的因素。

Google對PageRank的解釋

在Google網站上有一個專門的域名介紹PageRank（http://www.Google.com/technology/）

PageRank完全依靠的是網路的民主特性，利用大量的鏈接結構表明某個單獨頁面的價值。本質上來說，Google把鏈接轉換為一次投票，當從網頁 A 鏈接到網頁 B 時，Google 就認為「網頁 A 投了網頁 B 一票」。 Google 也不是純粹考慮投票的數量，還對投票的網頁進行分析。本身很重要的網頁的投票有助於增強其他對方網頁的重要度。

重要的是，Google會記錄每次的搜索行為，高質量的網站能夠獲得較高的PageRank分值。當然，重要的網頁如果不能匹配你的查詢就沒有任何價值。所以，Google把PageRank技術及文本匹配技術進行結合從而搜索出既重要又相關的的結果。Google的匹配技術不是只考慮詞條在網頁上的出現次數，而是檢查網頁內容（及鏈接網頁的內容）的所有方面，從而決定該網頁是否匹配你的查詢。

更多信息訪問Google PageRank介紹：

搜索引擎排名與PageRank的關系

雖然每個搜索引擎都嚴格保密各自的明確的搜索演算法，但是搜索引擎分析人士相信搜索引擎結果（排名列表）是「Page Relevance」與「PageRank」因素綜合承繼的結果。

Ranking = (Page Relevance) x (PageRank)

PageRank邏輯演算法無疑是具有重大意義的，而且這種演算法不能夠被網管人員輕易操縱。Google的搜索結果能夠顯示出如此高的相關性無疑也是它能夠獲得徹底成功的重要原因之一。大多數其他搜索引擎已經完全採用同類模式作為自己的搜索演算法，而有的搜索引擎將這種演算法在決定結果排名中的重要程度進行定義後應用與自己的搜索結果中。
自網路發展的初期，搜索引擎就一直不斷的努力試圖開發出可以排列相關網頁的搜索演算法。大多數搜索引擎重視於「鏈接流行度」（link popularity），作為評價網頁重要度及用於索引的標准

Google 工具欄

Google工具欄供人免費下載安裝，除了某些有用的功能外，比較顯著的一個特點就是它可以告訴用戶目前正在訪問的每個網頁的PageRank值。

下載後的Google工具欄位於瀏覽器窗口下部，可隨時隨地進行網上搜索。工具欄顯示出每個頁面從1－10不等的PageRank分值。對於Google未索引的網頁，工具欄不會顯示出該頁的PageRank分值。需要提醒的是，該分值是針對網頁而言，而非網站。

註：PR值越高，說明營銷人員要針對相應的搜索詞條獲得較高的排名位置就有更多的競爭。所以，我們建議根據關鍵詞優化你的網頁PR值。

什麼是鏈接流行度？

「鏈接流行度」系統是基於網頁獲得的鏈接的數量及質量而定的。也就是說，指向你的網頁的鏈接數量越多，你的網頁將被搜索引擎認為越重要。數量並不是決定網站重要度的唯一因素，重要度還取決於其他因素，包括被鏈接到本站點的站點的質量、他們的內容的質量及與本站點的行業相關性等。

鏈接到本站點的網頁會把PageRank的部分分值分配到本站點。所以鏈接頁面的PageRank分值越高，分配給本站點的分值也就越高。

PageRank也會被鏈接頁面商店所有導出鏈接所瓜分。譬如，同樣PR為5的鏈接網頁，導出鏈接只有15個的網頁會比導出鏈接為100個的網頁分配給你更多的分值。

所以重要的是要從PR值較高並且總體導出鏈接數量較少網頁才能獲得安全鏈接。

如何檢測鏈接流行度

最簡單的檢測網站流行度的方法就是利用Google搜索，方法如下：

link:www.yoursite.com

其它主要搜索引擎在搜索你的鏈接流行度時都有不同的規則。

建立鏈接流行度提高PageRank

建立鏈接流行度是搜索引擎營銷的一個重要方面。盡管認為的提高PageRank不是意見容易的事，但是你通過改善鏈接流行度就可以不難做到。通過長期不懈的關注建立鏈接的工作，你就會提高站點的PageRank，大大改善自己的站點排名。

就在不久前，Google及其他搜索引擎配製了某些類似與PageRank的演算法成分（如TSPR」Topic Sensitive PageRank」，Hilltop「Links from expert document.」），進一步將決定排名的比重放置在頁面以外因素上。
隨著頁面以外因素在網站排名中受到重視，所以提高加強這些因素的重視就變得越來越重要。當越來越多的網管意識到PageRank及鏈接流行度的重要性時，就不難在同行業中與其他站點進行鏈接交換了。

2. 數據挖掘演算法 PageRank

數據挖掘演算法：PageRank
1. 引言
PageRank是Sergey Brin與Larry Page於1998年在WWW7會議上提出來的，用來解決鏈接分析中網頁排名的問題。在衡量一個網頁的排名，直覺告訴我們：
1、當一個網頁被更多網頁所鏈接時，其排名會越靠前；
2、排名高的網頁應具有更大的表決權，即當一個網頁被排名高的網頁所鏈接時，其重要性也應對應提高。
對於這兩個直覺，PageRank演算法所建立的模型非常簡單：一個網頁的排名等於所有鏈接到該網頁的網頁的加權排名之和：

PRi表示第i個網頁的PageRank值，用以衡量每一個網頁的排名；若排名越高，則其PageRank值越大。
網頁之間的鏈接關系可以表示成一個有向圖代表了網頁j鏈接到了網頁i；Oj為網頁j的出度，也可看作網頁j的外鏈數（ the number of out-links）。
假定P=(PR1,PR2,?,PRn)T為n維PageRank值向量，A為有向圖G所對應的轉移矩陣，

n個等式(1)可改寫為矩陣相乘：

但是，為了獲得某個網頁的排名，而需要知道其他網頁的排名，這不就等同於「是先有雞還是先有蛋」的問題了么？幸運的是，PageRank採用power iteration方法破解了這個問題怪圈。欲知詳情，請看下節分解。
2. 求解
為了對上述及以下求解過程有個直觀的了解，我們先來看一個例子，網頁鏈接關系圖如下圖所示：

那麼，矩陣A即為

所謂power iteration，是指先給定一個P的初始值P0，然後通過多輪迭代求解:

最後收斂於||Pk?Pk?1||<ξ，即差別小於某個閾值。
我們發現式子(2)為一個特徵方程（characteristic equation），並且解P是當特徵值（eigenvalue）為1時的特徵向量（eigenvector）。為了滿足(2)是有解的，則矩陣A應滿足如下三個性質：
1、stochastic matrix，則行至少存在一個非零值，即必須存在一個外鏈接（沒有外鏈接的網頁被稱為dangling pages）；
2、不可約（irrecible），即矩陣A所對應的有向圖G必須是強連通的，對於任意兩個節點u,v∈V，存在一個從u到v的路徑；
3、非周期性（aperiodic），即每個節點存在自迴路。
顯然，一般情況下矩陣A這三個性質均不滿足。為了滿足性質stochastic matrix，可以把全為0的行替換為e/n，其中e為單位向量；同時為了滿足性質不可約、非周期，需要做平滑處理：

其中，d為 damping factor，常置為0與1之間的一個常數；E為單位陣。那麼，式子(1)被改寫為

3. Pagerank演算法

一. Pagerank介紹
PageRank演算法以前就是Google的網頁排序演算法。PageRank演算法，對每個目標網頁進行附上權值，權值大的就靠前顯示，權值小的就靠後顯示。PageRank演算法就是給每個網頁附加權值的。PageRank演算法借鑒學術界論文重要性的評估方法：誰被引用的次數多，誰就越重要。
註：PageRank演算法不單單是按照「被索引數」來給網頁付權值的，用PR值表示每個網頁被PageRank演算法附加的權值。

二. PageRank演算法的核心細想
（1）如果一個網頁被很多其他網頁鏈接到的話,說明這個網頁比較重要，也就是PageRank值會相對較高
（2）如果一個PageRank值很高的網頁鏈接到一個其他的網頁，那麼被鏈接到的網頁的PageRank值會相應地因此而提高

三. 基本概念
（1）出鏈

如果在網頁A中附加了網頁B的超鏈接B-Link，用戶瀏覽網頁A時可以點擊B-Link然後進入網頁B。上面這種A附有B-Link這種情況表示A出鏈B。可知，網頁A也可以出鏈C，如果A中也附件了網頁C的超鏈接C-Link。

（2）入鏈

上面通過點擊網頁A中B-Link進入B，表示由A入鏈B。如果用戶自己在瀏覽器輸入欄輸入網頁B的URL，然後進入B，表示用戶通過輸入URL入鏈B

（3）無出鏈

如果網頁A中沒有附加其他網頁的超鏈接，則表示A無出鏈

（4）只對自己出鏈

如果網頁A中沒有附件其他網頁的超鏈接，而只有他自己的超鏈接A-Link，則表示A只對自己出鏈

（5）PR值

一個網頁的PR值，概率上理解就是此網頁被訪問的概率，PR值越高其排名越高。

四. 幾種網頁出入鏈關系
case1：網頁都有出入鏈

case2：存在沒有出鏈的網頁

網頁C是沒有出鏈。因為C沒有出鏈，所以對A,B,D網頁沒有PR值的貢獻。PageRank演算法的策略：從數學上考慮，為了滿足Markov鏈，設定C對A,B,C,D都有出鏈（也對他自己也出鏈~）。你也可以理解為：沒有出鏈的網頁，我們強制讓他對所有的網頁都有出鏈，即讓他對所有網頁都有PR值貢獻。
此種情況PR(A)的計算公式：

case3：存在只對自己出鏈的網頁

C是只對自己出鏈的網頁。

此時訪問C時，不會傻乎乎的停留在C頁面，一直點擊C-Link循環進入C，即C網頁只對自己的網頁PR值有貢獻。正常的做法是，進入C後，存在這種情況：在地址輸入欄輸入A/B/C/D的URL地址，然後跳轉到A/B/C/D進行瀏覽，這就是PageRank演算法解決這種情況的策略：設定存在一定概率為α，用戶在地址欄輸入A/B/C/D地址，然後從C跳轉到A/B/C/D進行瀏覽。
此時PR(A)的計算公式為：

五. 演算法公式
一般情況下，一個網頁的PR值計算公式為：

所有網頁PR值一直迭代計算，停止直到下面兩種情況之一發生：每個網頁的PR值前後誤差小於自定義誤差閾值，或者迭代次數超過了自定義的迭代次數閾值

六. PageRank演算法的缺點
這是一個天才的演算法，原理簡單但效果驚人。然而，PageRank演算法還是有一些弊端。

第一，沒有區分站內導航鏈接。很多網站的首頁都有很多對站內其他頁面的鏈接，稱為站內導航鏈接。這些鏈接與不同網站之間的鏈接相比，肯定是後者更能體現PageRank值的傳遞關系。

第二，沒有過濾廣告鏈接和功能鏈接（例如常見的「分享到微博」）。這些鏈接通常沒有什麼實際價值，前者鏈接到廣告頁面，後者常常鏈接到某個社交網站首頁。

第三，對新網頁不友好。一個新網頁的一般入鏈相對較少，即使它的內容的質量很高，要成為一個高PR值的頁面仍需要很長時間的推廣。

針對PageRank演算法的缺點，有人提出了TrustRank演算法。其最初來自於2004年斯坦福大學和雅虎的一項聯合研究，用來檢測垃圾網站。TrustRank演算法的工作原理：先人工去識別高質量的頁面(即「種子」頁面)，那麼由「種子」頁面指向的頁面也可能是高質量頁面，即其TR值也高，與「種子」頁面的鏈接越遠，頁面的TR值越低。「種子」頁面可選出鏈數較多的網頁，也可選PR值較高的網站。

TrustRank演算法給出每個網頁的TR值。將PR值與TR值結合起來，可以更准確地判斷網頁的重要性。

補充:
谷歌用PR值來劃分網頁的等級，有0~10級，一般4級以上的都是比較好的網頁了。谷歌自己PR值為9，網路也是9，博客園的PR值則為6。

如今PR值雖不如以前重要了（沒有區分頁面內的導航鏈接、廣告鏈接和功能鏈接導致PR值本身能夠反映出的網頁價值不精確，並且對新網頁不友好），但是流量交易里PR值還是個很重要的參考因素。

4. pagerank演算法是什麼

PageRank演算法是谷歌曾經獨步天下的「倚天劍」，該演算法由Larry Page和Sergey Brin在斯坦福大學讀研時發明的。PageRank，網頁排名，又稱為網頁級別，Google左側排名，是一種由網頁之間相互的超鏈接計算的技術，作為網頁排名的要素之一。

Google用它來體現網頁的相關性和重要性，在搜索引擎優化操作中是經常被用來評估網頁優化的成效因素之一。

PageRank的思想

PageRank認為，一個節點對系統施加影響的結果，就是與它相連的節點也具有一定的影響力。PageRank的想法看起來很簡單，實際上給我們留了一個難題：各個節點的PR值計算是存在依賴的，得先計算出PR(node1)才能計算PR(node0)。

也就是說需要首先把所有未被引用的節點的PR值算出來(一般默認是1.0)；然後把以它們為源頭、只和源頭相連、距離為1的節點的PR值算出來；接著計算距離為2、只和已經具有PR值節點相連的，所有節點的PR值；直到所有的節點都有PR值為止。這個計算方法復雜度比較高，不實用。

5. hadoop的maprece常見演算法案例有幾種

基本MapRece模式

計數與求和
問題陳述:
有許多文檔，每個文檔都有一些欄位組成。需要計算出每個欄位在所有文檔中的出現次數或者這些欄位的其他什麼統計值。例如，給定一個log文件，其中的每條記錄都包含一個響應時間，需要計算出平均響應時間。
解決方案:
讓我們先從簡單的例子入手。在下面的代碼片段里，Mapper每遇到指定詞就把頻次記1，Recer一個個遍歷這些詞的集合然後把他們的頻次加和。

1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Recer
7 method Rece(term t, counts [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)

這種方法的缺點顯而易見，Mapper提交了太多無意義的計數。它完全可以通過先對每個文檔中的詞進行計數從而減少傳遞給Recer的數據量:

1 class Mapper
2 method Map(docid id, doc d)
3 H = new AssociativeArray
4 for all term t in doc d do
5 H{t} = H{t} + 1
6 for all term t in H do
7 Emit(term t, count H{t})

如果要累計計數的的不只是單個文檔中的內容，還包括了一個Mapper節點處理的所有文檔，那就要用到Combiner了:

1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Combiner
7 method Combine(term t, [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)
12
13 class Recer
14 method Rece(term t, counts [c1, c2,...])
15 sum = 0
16 for all count c in [c1, c2,...] do
17 sum = sum + c
18 Emit(term t, count sum)

應用：Log 分析, 數據查詢

整理歸類

問題陳述:
有一系列條目，每個條目都有幾個屬性，要把具有同一屬性值的條目都保存在一個文件里，或者把條目按照屬性值分組。 最典型的應用是倒排索引。
解決方案：
解決方案很簡單。 在 Mapper 中以每個條目的所需屬性值作為 key，其本身作為值傳遞給 Recer。 Recer 取得按照屬性值分組的條目，然後可以處理或者保存。如果是在構建倒排索引，那麼 每個條目相當於一個詞而屬性值就是詞所在的文檔ID。
應用：倒排索引， ETL
過濾 (文本查找)，解析和校驗
問題陳述:
假設有很多條記錄，需要從其中找出滿足某個條件的所有記錄，或者將每條記錄傳換成另外一種形式（轉換操作相對於各條記錄獨立，即對一條記錄的操作與其他記錄無關）。像文本解析、特定值抽取、格式轉換等都屬於後一種用例。
解決方案:
非常簡單，在Mapper 里逐條進行操作，輸出需要的值或轉換後的形式。
應用：日誌分析，數據查詢，ETL，數據校驗

分布式任務執行

問題陳述:
大型計算可以分解為多個部分分別進行然後合並各個計算的結果以獲得最終結果。
解決方案: 將數據切分成多份作為每個 Mapper 的輸入，每個Mapper處理一份數據，執行同樣的運算，產生結果，Recer把多個Mapper的結果組合成一個。
案例研究： 數字通信系統模擬
像 WiMAX 這樣的數字通信模擬軟體通過系統模型來傳輸大量的隨機數據，然後計算傳輸中的錯誤幾率。 每個 Mapper 處理樣本 1/N 的數據，計算出這部分數據的錯誤率，然後在 Recer 里計算平均錯誤率。
應用：工程模擬，數字分析，性能測試
排序
問題陳述:
有許多條記錄，需要按照某種規則將所有記錄排序或是按照順序來處理記錄。
解決方案: 簡單排序很好辦 – Mappers 將待排序的屬性值為鍵，整條記錄為值輸出。 不過實際應用中的排序要更加巧妙一點， 這就是它之所以被稱為MapRece 核心的原因（「核心」是說排序？因為證明Hadoop計算能力的實驗是大數據排序？還是說Hadoop的處理過程中對key排序的環節？）。在實踐中，常用組合鍵來實現二次排序和分組。
MapRece 最初只能夠對鍵排序， 但是也有技術利用可以利用Hadoop 的特性來實現按值排序。想了解的話可以看這篇博客。
按照BigTable的概念，使用 MapRece來對最初數據而非中間數據排序，也即保持數據的有序狀態更有好處，必須注意這一點。換句話說，在數據插入時排序一次要比在每次查詢數據的時候排序更高效。
應用：ETL，數據分析

非基本 MapRece 模式

迭代消息傳遞 (圖處理)

問題陳述：
假設一個實體網路，實體之間存在著關系。 需要按照與它比鄰的其他實體的屬性計算出一個狀態。這個狀態可以表現為它和其它節點之間的距離， 存在特定屬性的鄰接點的跡象， 鄰域密度特徵等等。
解決方案：
網路存儲為系列節點的結合，每個節點包含有其所有鄰接點ID的列表。按照這個概念，MapRece 迭代進行，每次迭代中每個節點都發消息給它的鄰接點。鄰接點根據接收到的信息更新自己的狀態。當滿足了某些條件的時候迭代停止，如達到了最大迭代次數（網路半徑）或兩次連續的迭代幾乎沒有狀態改變。從技術上來看，Mapper 以每個鄰接點的ID為鍵發出信息，所有的信息都會按照接受節點分組，recer 就能夠重算各節點的狀態然後更新那些狀態改變了的節點。下面展示了這個演算法：

1 class Mapper
2 method Map(id n, object N)
3 Emit(id n, object N)
4 for all id m in N.OutgoingRelations do
5 Emit(id m, message getMessage(N))
6
7 class Recer
8 method Rece(id m, [s1, s2,...])
9 M = null
10 messages = []
11 for all s in [s1, s2,...] do
12 if IsObject(s) then
13 M = s
14 else // s is a message
15 messages.add(s)
16 M.State = calculateState(messages)
17 Emit(id m, item M)

一個節點的狀態可以迅速的沿著網路傳全網，那些被感染了的節點又去感染它們的鄰居，整個過程就像下面的圖示一樣：

案例研究： 沿分類樹的有效性傳遞
問題陳述：
這個問題來自於真實的電子商務應用。將各種貨物分類，這些類別可以組成一個樹形結構，比較大的分類（像男人、女人、兒童）可以再分出小分類（像男褲或女裝），直到不能再分為止（像男式藍色牛仔褲）。這些不能再分的基層類別可以是有效（這個類別包含有貨品）或者已無效的（沒有屬於這個分類的貨品）。如果一個分類至少含有一個有效的子分類那麼認為這個分類也是有效的。我們需要在已知一些基層分類有效的情況下找出分類樹上所有有效的分類。
解決方案：
這個問題可以用上一節提到的框架來解決。我們咋下面定義了名為 getMessage和 calculateState 的方法：

1 class N
2 State in {True = 2, False = 1, null = 0},
3 initialized 1 or 2 for end-of-line categories, 0 otherwise
4 method getMessage(object N)
5 return N.State
6 method calculateState(state s, data [d1, d2,...])
7 return max( [d1, d2,...] )

案例研究：廣度優先搜索
問題陳述：需要計算出一個圖結構中某一個節點到其它所有節點的距離。
解決方案： Source源節點給所有鄰接點發出值為0的信號，鄰接點把收到的信號再轉發給自己的鄰接點，每轉發一次就對信號值加1：

1 class N
2 State is distance,
3 initialized 0 for source node, INFINITY for all other nodes
4 method getMessage(N)
5 return N.State + 1
6 method calculateState(state s, data [d1, d2,...])
7 min( [d1, d2,...] )

案例研究：網頁排名和 Mapper 端數據聚合
這個演算法由Google提出，使用權威的PageRank演算法，通過連接到一個網頁的其他網頁來計算網頁的相關性。真實演算法是相當復雜的，但是核心思想是權重可以傳播，也即通過一個節點的各聯接節點的權重的均值來計算節點自身的權重。

1 class N
2 State is PageRank
3 method getMessage(object N)
4 return N.State / N.OutgoingRelations.size()
5 method calculateState(state s, data [d1, d2,...])
6 return ( sum([d1, d2,...]) )

要指出的是上面用一個數值來作為評分實際上是一種簡化，在實際情況下，我們需要在Mapper端來進行聚合計算得出這個值。下面的代碼片段展示了這個改變後的邏輯 （針對於 PageRank 演算法）：

1 class Mapper
2 method Initialize
3 H = new AssociativeArray
4 method Map(id n, object N)
5 p = N.PageRank / N.OutgoingRelations.size()
6 Emit(id n, object N)
7 for all id m in N.OutgoingRelations do
8 H{m} = H{m} + p
9 method Close
10 for all id n in H do
11 Emit(id n, value H{n})
12
13 class Recer
14 method Rece(id m, [s1, s2,...])
15 M = null
16 p = 0
17 for all s in [s1, s2,...] do
18 if IsObject(s) then
19 M = s
20 else
21 p = p + s
22 M.PageRank = p
23 Emit(id m, item M)

應用：圖分析，網頁索引

值去重 （對唯一項計數）
問題陳述: 記錄包含值域F和值域 G，要分別統計相同G值的記錄中不同的F值的數目 (相當於按照 G分組).
這個問題可以推而廣之應用於分面搜索（某些電子商務網站稱之為Narrow Search）
Record 1: F=1, G={a, b}
Record 2: F=2, G={a, d, e}
Record 3: F=1, G={b}
Record 4: F=3, G={a, b}

Result:
a -> 3 // F=1, F=2, F=3
b -> 2 // F=1, F=3
d -> 1 // F=2
e -> 1 // F=2

解決方案 I:
第一種方法是分兩個階段來解決這個問題。第一階段在Mapper中使用F和G組成一個復合值對，然後在Recer中輸出每個值對，目的是為了保證F值的唯一性。在第二階段，再將值對按照G值來分組計算每組中的條目數。
第一階段：

1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...]])
3 for all category g in [g1, g2,...]
4 Emit(record [g, f], count 1)
5
6 class Recer
7 method Rece(record [g, f], counts [n1, n2, ...])
8 Emit(record [g, f], null )

第二階段：

1 class Mapper
2 method Map(record [f, g], null)
3 Emit(value g, count 1)
4
5 class Recer
6 method Rece(value g, counts [n1, n2,...])
7 Emit(value g, sum( [n1, n2,...] ) )

解決方案 II:
第二種方法只需要一次MapRece 即可實現，但擴展性不強。演算法很簡單-Mapper 輸出值和分類，在Recer里為每個值對應的分類去重然後給每個所屬的分類計數加1，最後再在Recer結束後將所有計數加和。這種方法適用於只有有限個分類，而且擁有相同F值的記錄不是很多的情況。例如網路日誌處理和用戶分類，用戶的總數很多，但是每個用戶的事件是有限的，以此分類得到的類別也是有限的。值得一提的是在這種模式下可以在數據傳輸到Recer之前使用Combiner來去除分類的重復值。

1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...] )
3 for all category g in [g1, g2,...]
4 Emit(value f, category g)
5
6 class Recer
7 method Initialize
8 H = new AssociativeArray : category -> count
9 method Rece(value f, categories [g1, g2,...])
10 [g1', g2',..] = ExcludeDuplicates( [g1, g2,..] )
11 for all category g in [g1', g2',...]
12 H{g} = H{g} + 1
13 method Close
14 for all category g in H do
15 Emit(category g, count H{g})

應用：日誌分析，用戶計數
互相關
問題陳述：有多個各由若干項構成的組，計算項兩兩共同出現於一個組中的次數。假如項數是N，那麼應該計算N*N。
這種情況常見於文本分析（條目是單詞而元組是句子），市場分析（購買了此物的客戶還可能購買什麼）。如果N*N小到可以容納於一台機器的內存，實現起來就比較簡單了。
配對法
第一種方法是在Mapper中給所有條目配對，然後在Recer中將同一條目對的計數加和。但這種做法也有缺點：
使用 combiners 帶來的的好處有限，因為很可能所有項對都是唯一的
不能有效利用內存

1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 for all item j in [i1, i2,...]
5 Emit(pair [i j], count 1)
6
7 class Recer
8 method Rece(pair [i j], counts [c1, c2,...])
9 s = sum([c1, c2,...])
10 Emit(pair[i j], count s)

Stripes Approach（條方法？不知道這個名字怎麼理解）
第二種方法是將數據按照pair中的第一項來分組，並維護一個關聯數組，數組中存儲的是所有關聯項的計數。The second approach is to group data by the first item in pair and maintain an associative array (「stripe」) where counters for all adjacent items are accumulated. Recer receives all stripes for leading item i, merges them, and emits the same result as in the Pairs approach.
中間結果的鍵數量相對較少，因此減少了排序消耗。
可以有效利用 combiners。
可在內存中執行，不過如果沒有正確執行的話也會帶來問題。
實現起來比較復雜。
一般來說， 「stripes」 比 「pairs」 更快

1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 H = new AssociativeArray : item -> counter
5 for all item j in [i1, i2,...]
6 H{j} = H{j} + 1
7 Emit(item i, stripe H)
8
9 class Recer
10 method Rece(item i, stripes [H1, H2,...])
11 H = new AssociativeArray : item -> counter
12 H = merge-sum( [H1, H2,...] )
13 for all item j in H.keys()
14 Emit(pair [i j], H{j})

應用：文本分析，市場分析
參考資料：Lin J. Dyer C. Hirst G. Data Intensive Processing MapRece
用MapRece 表達關系模式
在這部分我們會討論一下怎麼使用MapRece來進行主要的關系操作。
篩選（Selection）

1 class Mapper
2 method Map(rowkey key, tuple t)
3 if t satisfies the predicate
4 Emit(tuple t, null)

投影（Projection）
投影只比篩選稍微復雜一點，在這種情況下我們可以用Recer來消除可能的重復值。

1 class Mapper
2 method Map(rowkey key, tuple t)
3 tuple g = project(t) // extract required fields to tuple g
4 Emit(tuple g, null)
5
6 class Recer