前瞻文檔排名系統的製作方法
2023-09-20 01:10:10 3
專利名稱：前瞻文檔排名系統的製作方法
前瞻文檔排名系統
背景
如Google(谷歌)和Yahoo (雅虎)等許多搜尋引擎服務能夠搜索能經由因特 網訪問的信息。這些搜尋引擎服務允許用戶搜索用戶可能感興趣的顯示頁面， 如網頁。在用戶提交包含搜索項的搜索請求(即，查詢)之後，搜尋引擎服務 標識可能與這些搜索項相關的網頁。為快速標識相關的網頁，搜尋引擎服務可 維護關鍵詞到網頁的映射。該映射可以通過"爬尋(crawl) "web (即，全球資訊網) 來標識每一網頁的關鍵詞來生成。為爬尋web，搜尋引擎服務可使用根網頁列 表來標識能通過這些根網頁訪問的所有網頁。任何特定網頁的關鍵詞可使用各 種公知信息檢索技術來標識，如標識標題行的文字、在網頁的元數據中提供的 文字、突出顯示的文字等等。搜尋引擎服務基於網頁的關鍵詞與查詢的文字匹 配得如何來標識可能與搜索請求相關的網頁。搜尋引擎服務隨後將到所標識的 網頁的連結以基於排名的順序顯示給用戶，該排名可以按照其與查詢的相關 度、流行度、重要性和/或某一其它度量來確定。
用於頁面排名的一種公知技術是PageRank，其基於網頁將具有到重要網 頁的連結(即，"引出連結")的原理。網頁重要性基於連結到該網頁(即， "引入連結")的其它網頁的數量與重要性。PageRank基於訪問web圖(頂 點表示網頁而連結表示超連結)的網頁的隨機網蟲(surfer)模型，且將網頁 的重要性表示為訪問此網頁的固定概率。在隨機網蟲模型中，訪問當前頁面的 網蟲將通過隨機選擇當前網頁的連結來訪問下一頁面。如果當前網頁具有三個 到目標網頁的引出連結，則從當前網頁訪問每一目標網頁的概率是1/3。 PageRank因此基於僅依賴於當前網頁的信息(例如，超連結)的馬爾可夫隨 機遊動。
web圖可被表示為G= ，其中「=卩,2，...，"}是頂點集合而 ￡ = {</，_/〉|/,./￡^是邊集合。網頁之間的連結可以由鄰接矩陣^來表示，其中
在存在從源網頁虔j目標網頁j'的引出連結時將4設為1。網頁y的重要性分數w,可以如下表示
formula see original document page 6(1)
該等式可以通過基於下式的迭代計算來求解
formula see original document page 6(2)
其中w是網頁的重要性分數的向量，並且是,的主本徵向量。 PageRank還可以將網蟲可以隨機選擇接下來訪問未由當前網頁連結到的 網頁計算在內。因此，網蟲可以有"的概率接下來訪問當前網頁的目標網頁， 而有l-a的概率接下來訪問隨機所選的網頁。為了將對網頁的這種隨機選 擇計算在內，PageRank通過使用其元素之和來歸一化鄰接矩陣的每一非零行 來生成初始轉移矩陣屍。PageRank隨後將矩陣屍中的零行的每一元素設置為 1//7來生成轉移概率矩陣7。表示對目標網頁的連結的隨機選擇和對網頁的隨
機選擇^模型可表示如下
formula see original document page 6(3)
其中^是組合轉移概率矩陣，而U是其中每--元素被設置為1/w的統一概 率分布矩陣。PageRank認為轉移概率矩陣？的固定分布;r = ;r2,…,;rj7表示
每一網頁的重要性。PageRank可以通過如下表示的迭代過程來計算固定分布
formula see original document page 6 (4)
其中;r(0)—U,...，1)/， ？表示迭代計數，且迭代過程繼續直到;r收斂於一解。
PageRank的基礎假設是用戶隨機地選擇當前網頁的任何超連結。然而， 在用戶具有幫助決定選擇哪個超連結的附加信息可用時，此假設是不正確的。
用戶可能想要最大化他們的信息收穫，並且因此具有這種附加信息的用戶將可 能選擇將導致最大信息收穫的超連結。
概述
提供了用於基於從源文檔到目標文檔的轉移概率來計算文檔的重要性的 方法和系統，其中轉移概率基於對源文檔的目標文檔的信息內容的前瞻。該前 瞻重要性系統基於對到源文檔的目標文檔的連結的分析來生成在任一對源文 檔和目標文檔之間轉移的轉移概率。該前瞻重要性系統可以基於特定前瞻距離遠的文檔的內容來計算從源文檔到直接目標文檔的轉移概率。該前瞻重要性系 統可以基於相距一前瞻距離的文檔上的連結的數量來計算轉移概率。在該前瞻 重要性系統從這些轉移概率中生成轉移概率矩陣之後，它求出訪問每一文檔的 固定概率。文檔的固定概率表示文檔的重要性。
提供本概述是為了以簡化的形式介紹將在以下詳細描述中進一步描述的 一些概念。該概述不旨在標識所要求保護的主題的關鍵特徵或必要特徵，也不 旨在用於幫助確定所要求保護的主題的範圍。
附圖簡述
圖1是示出一個實施例中的前瞻重要性系統的組件的框圖。 圖2是示出一個實施例中的前瞻重要性系統的計算前瞻重要性組件的處 理的流程圖。
圖3是示出一實施例中的前瞻重要性系統的生成初始轉移矩陣組件的處 理的流程圖。
圖4是示出一實施例中的前瞻重要性系統的計算每頁面連結組件的處理
的流程圖。
圖5是示出一實施例中的前瞻重要性系統的計算固定概率組件的處理的 流程圖。
詳細描述
提供了用於基於從源文檔到目標文檔的轉移概率來計算文檔的重要性的 方法和系統，其中轉移概率基於對源文檔的目標文檔的信息內容的前瞻。在一 個實施例中， 一種前瞻重要性系統基於對到源文檔的目標文檔的連結的分析來 生成在任一對源文檔和目標文檔之間轉移的轉移概率。通過源文檔的連結直接 或間接可訪問的文檔是源文檔的目標文檔。例如，文檔a可以包含到文檔b、 c、 和d的連結，且文檔b可以包含到文檔b'和b"的連結。文檔a是直接目標文檔 b、 c和d的源文檔，且是間接目標文檔b'和b"的源文檔。文檔b是直接目標文 檔b'和b"的源文檔。文檔b、 c和d與源文檔a相隔前瞻距離一，而文檔b'和 b"與源文檔a相隔前瞻距離二。該前瞻重要性系統可以基於特定前瞻距離遠的
7文檔的內容來計算從源文檔到直接目標文檔的轉移概率。例如，如果目標文檔
b、 c和d各自分別包含2、 3、和4個連結，則基於前瞻距離一的從源文檔a 轉移到目標文檔b、 c和d的轉移概率可以分別是2/9、 3/9、和4/9。因為文檔 b、 c和d包含總共9個連結，所以任何目標文檔的轉移概率是它所包含的連結 總數的分數。因此，該前瞻重要性系統基於相距一前瞻距離的文檔上的連結的 數量來計算轉移概率。在該前瞻重要性系統從這些轉移概率中生成轉移概率矩 陣之後，它求出訪問每一文檔的固定概率。文檔的固定概率表示文檔的重要性。 以這種方式，該前瞻重要性系統在將可通過源文檔的不同連結獲得的相對信息 量計算在內的情況下確定文檔的重要性。
用戶可以基於通過選擇一個連結而不選另一個連結所感知到的信息收穫 來選擇連結，而不是隨機選擇當前網頁的連結。幫助用戶作出信息收穫的判定 所需的附加信息可以用各種方式來提供。例如，可以擴充網頁來為每一連結顯 示可通過此連結訪問的相距一前瞻距離的連結的百分比。在用戶將指針懸停在 一連結上時，該百分比可以顯示在該連結旁邊。繼續具有到文檔b、 c和d的 連結的文檔a的示例，在指針懸停於到文檔b的連結上時，隨後可以在該連結 旁邊顯示22%。作為另一個示例，在顯示網頁時，可以顯示web圖(例如，頂 點和邊)中與當前網頁相距一前瞻距離的一部分的圖形。用戶可以評估web圖 的所顯示的部分來評估通過各種連結可獲得的信息。
本領域的技術人員可以理解，可以使用許多不同的技術來基於前瞻生成轉 移概率。以上描述的技術將從源網頁到直接目標網頁的轉移概率設置為通過在 特定前瞻距離處的目標網頁可訪問的連結的分數。繼續具有到文檔b、 c和d 的連結的文檔a與具有到文檔b'和b"的連結的文檔b的示例，如果前瞻距離是 二且文檔b'和b"分別包含2個與5個連結，且c的直接目標文檔上的連結總數 是14，而d的直接目標文檔上的連結總數是21 ，則文檔b的轉移概率將是7/42， 文檔c的轉移概率將是14/42，以及文檔d的轉移概率將是21/42。替換技術可 以將轉移概率設置為無前瞻的轉移概率和前瞻的轉移概率的組合、或前瞻不同 的前瞻距離的轉移概率的組合。繼續此示例，在不前瞻的情況下，對文檔b、 c 和d來說轉移概率將是1/3，而在前瞻距離為一的情況下，轉移概率將是2/9、 3/9、和4/9。進行前瞻和不進行前瞻的轉移概率的線性組合可以是2.5/9 3/9、禾口 3.5/9。
在一個實施例中，前瞻重要性系統可以將網頁之間的轉移概率表示如下
(")"(G)
其中/表示源網頁，y'表示直接目標網頁，TV-l表示前瞻距離，以及^w一0
表示通過在前瞻距離W-1處的目標網頁/的網頁上的連結的數量。繼續上述 示例，目標文檔b、 c和d與源文檔a相距前瞻距離一。因此，《(')是3，《2)是 2，《(2>是3，""是4，以及c^)是2，且等式5的分母是這些值的總和。該前
瞻重要性系統可以根據下式來生成初始轉移矩陣
(6)
其中屍W表示基於前瞻距離iV-l的初始轉移矩陣，X表示指示文檔之間 的連結的鄰接矩陣，以及DW表示其對角元素被設置為"^的對角矩陣，其 中"(^根據下式來計算 ,)=" (7)
其中= (1,1,..., 1):'。矩陣(Dw)—'是在,)中的相應元素為零的任何元
素都為零值的擴展逆矩陣。矢量"(w)包含用於每一網頁的元素，且包含與該 網頁相距前瞻距離W-l的網頁上的連結總數。
該前瞻重要性系統隨後將屍W中的零行的每一元素設置為1—，從而給
出轉移概率矩陣7("。該前瞻重要性系統如下表示經由連結對直接目標網頁的 隨機選擇，以及在不選擇連結的情況下對網頁的隨機選擇 、,)+(l一豐(8)
其中 'V)是組合轉移概率矩陣，而f/是其中每一元素被設置為1/"的統一
概率分布矩陣。該前瞻重要性系統如下表示固定概率
=(w)、".
屍
,)(9)
其中7r^表示前瞻距離iV-l情況下的固定概率。該前瞻重要性系統可以 使用迭代過程來計算固定概率。
圖1是示出一個實施例中的前瞻重要性系統的組件的框圖。前瞻重要性系 統IIO可以經由通信鏈路130來連接到網站120。該前瞻重要性系統可以包括
9爬尋網站的網頁來生成鄰接矩陣112的爬尋器組件111。可作為稀疏矩陣來存
儲的該鄰接矩陣指示網頁之間的連結並表示web圖。該前瞻重要性系統還可以
包括搜尋引擎組件113，該搜尋引擎組件接收搜索請求、標識匹配搜索請求的
網頁、並至少部分基於前瞻重要性系統生成的重要性分數來對匹配網頁進行排 名。該前瞻重要性系統包括計算前瞻重要性組件115、生成初始轉移矩陣(屍)
組件116、計算固定概率(;r)組件117、以及計算每頁面連結(^組件118。計算
前瞻重要性組件調用生成初始轉移矩陣組件來計算初始轉移矩陣並隨後生成 轉移概率矩陣。生成初始轉移矩陣組件調用計算每頁面連結組件來為每一源網
頁生成相距一前瞻距離的網頁上的連結總數。計算前瞻重要性組件調用計算固 定概率組件來計算固定概率並將該固定概率作為重要性分數存儲在重要性存
儲119中。
在其上實現該前瞻重要性系統的計算設備可包括中央處理單元、存儲器、 輸入設備(例如，鍵盤和定點設備)、輸出設備(例如，顯示設備)和存儲設 備(例如，盤驅動器)。存儲器和存儲設備是可以用實現該前瞻重要性系統的 計算機可執行指令來編碼的計算機可讀介質，這意味著包含該指令的計算機可 讀介質。此外，指令、數據結構和消息結構可被存儲或經由諸如通信鏈路上的 信號之類的數據傳送介質發送。可以使用各種通信鏈路，諸如網際網路、區域網、 廣域網、點對點撥號連接、蜂窩電話網絡等。
該系統的實施例可以在各種操作環境中實現，這些操作環境包括個人計算 機、伺服器計算機、手持式或膝上型設備、多處理器系統、基於微處理器的系 統、可編程消費電子產品、數位相機、網絡PC、小型計算機、大型計算機、 包括任何上述系統或設備中任一種的計算環境等。
該前瞻重要性系統可以在諸如程序模塊等由一個或多個計算機或其他設 備執行的計算機可執行指令的通用上下文中描述。 一般而言，程序模塊包括執 行特定任務或實現特定抽象數據類型的例程、程序、對象、組件、數據結構等 等。通常，程序模塊的功能可以在各個實施例中按需進行組合或分布。例如， 單獨的計算系統可以爬尋web並生成鄰接矩陣。同樣，搜尋引擎可被主存在單 獨的計算系統上。
圖2是示出一個實施例中的前瞻重要性系統的計算前瞻重要性組件的處
10理的流程圖。向該組件傳遞鄰接矩陣的指示和前瞻距離的指示。該組件基於所 傳遞的前瞻距離來生成轉移概率矩陣，並將此轉移概率矩陣的固定概率作為網 頁的重要性來存儲。在框201，該組件調用生成初始轉移矩陣組件來生成初始
轉移矩陣。在框202，該組件歸一化行中的值並將具有全零元素的任何行的元 素設為具有相等概率來生成轉移概率矩陣。在框203，該組件生成中間矩陣來 將使用因子h"加權的、通過不選擇當前網頁的連結來接著訪問網頁的概率計 算在內。在框204，該組件生成使用因子"對轉移概率矩陣加權的中間矩陣。 在框205，該組件組合中間矩陣來生成前瞻距離為^-l情況下的組合轉移概率 矩陣。在框206，該組件調用計算固定概率組件來計算轉移概率矩陣的固定概 率。在框207，該組件將固定概率作為每一網頁的重要性存儲在重要性存儲中 並隨後完成。
圖3是示出一實施例中的前瞻重要性系統的生成初始轉移矩陣組件的處 理的流程圖。向該組件傳遞前瞻距離的指示且該組件生成初始轉移矩陣。在框 301，該組件調用計算每頁面連結組件來生成矢量^^和^w一)。在框302， 該組件將矩陣D('v-')生成為具有對角元素爿^的對角矩陣。在框303，該組 件將矩陣D(w)生成為具有對角元素J(W的對角矩陣。在框304，該組件通過 將鄰接矩陣^乘以矩陣^w-')來生成中間矩陣r。在框305，該組件通過將D^ 的逆矩陣乘以中間矩陣r來生成初始轉移矩陣。該組件隨後返回該初始轉移矩 陣。
圖4是示出一實施例中的前瞻重要性系統的計算每頁面連結組件的處理 的流程圖。向該組件傳遞前瞻距離的指示並且該組件計算與源網頁相距該前瞻 距離的目標網頁上的連結的計數。在框401，該組件初始化矢量t/(0)。在框 402-404，該組件循環計算每一網頁的計數。在框402，該組件遞增索引。在判 定框403，如果該索引大於該前瞻距離加一，則該組件返回最近兩個計算出的 矢量，否則該組件在框404繼續。在框404，該組件將鄰接矩陣乘以最近計算 出的矢量來給出下一計算出的矢量並循環到框401來遞增該索引。
圖5是示出一實施例中的前瞻重要性系統的計算固定概率組件的處理的 流程圖。向該組件傳遞概率轉移矩陣並且該組件為每一網頁計算相應的固定概 率。在框501，該組件初始化迭代變量/。在框502，該組件初始化固定概率。在框503-505，該組件循環計算新的固定概率直到滿足了終止條件。在框503， 該組件遞增到下一迭代。在框504，該組件通過將轉移概率矩陣的變換乘以上 一次迭代的固定概率來為當前迭代計算固定概率。在判定框505，如果滿足終 止條件，例如固定概率已經收斂於一個解或已經執行了特定次數的迭代，則組 件返回該固定概率，否則該組件循環至框503來遞增到下一迭代。
儘管用對結構特徵和/或方法動作專用的語言描述了本主題，但可以理解， 所附權利要求書中定義的主題不必限於上述具體特徵或動作。相反，上述具體 特徵和動作是作為實現權利要求的示例形式公開的。本領域的技術人員可以理 解，文檔可以包括任何包含連結或以其它方式標識其它內容的信息內容。例如， 文檔可以是具有到其它網頁的連結的網頁、具有對其它學術文章的引用的學術 文章、具有對其它司法意見的引用的司法意見、具有對其它專利的引用的專利 等等。因此，本發明只由所附權利要求來限制。
1權利要求
1.一種計算設備中的用於確定具有文檔之間的連結的文檔的重要性的方法，所述方法包括通過對源文檔的每一目標文檔的信息內容進行前瞻，基於對通過該目標文檔可用的信息的判定，來生成(116)在各對源文檔與目標文檔之間轉移的轉移概率；基於所生成的轉移概率的固定概率來計算(117)文檔的重要性；以及存儲(115)計算出的文檔的重要性。
2. 如權利要求1所述的方法，其特徵在於，所述轉移概率的生成包括將 在不選擇源文檔的連結的情況下從源文檔到另一文檔的轉移計算在內。
3. 如權利要求1所述的方法，其特徵在於，所述轉移概率的生成包括生 成轉移概率矩陣。
4. 如權利要求1所述的方法，其特徵在於，根據下式來計算初始轉移矩陣其中P^表示基於前瞻距離A^-1的初始轉移矩陣，^表示指示文檔之間 的連結的鄰接矩陣，以及D^表示具有設置為"(^的對角元素的對角矩陣， 其中"(")根據下式來計算 = ')其中z)"u,...，i);;。
5. 如權利要求4所述的方法，其特徵在於，包括通過使用每一行的元素 的總和歸一化該行的元素來將所述初始轉移矩陣轉化為轉移概率矩陣。
6. 如權利要求1所述的方法，其特徵在於，所述轉移概率是根據下式來 計算的.-y 一 s:("(,剩G)其中/f)表示基於前瞻距離7V-l從文檔/轉移到文檔/的轉移概率，而4")表示來自與文檔,'相距前瞻距離1的文檔j'的連結的計數。
7. 如權利要求1所述的方法，其特徵在於，迭代地執行所述重要性的計 算，直到所述文檔的固定概率收斂於一解。
8. 如權利要求1所述的方法，其特徵在於，所述轉移概率被表示為轉移 概率矩陣，且所述重要性的計算是通過標識轉移概率矩陣的主本徵向量來執行 的。
9. 如權利要求1所述的方法，其特徵在於，包括基於所述計算出的重要 性對文檔進行排名。
10. 如權利要求1所述的方法，其特徵在於，所述文檔是針對搜索請求的搜索結果的網頁，且所述網頁基於與搜索結果的相關性和計算出的重要性來排 名。
11. 如權利要求l所述的方法，其特徵在於，在源文檔和目標文檔之間轉 移的轉移概率是基於與所述源文檔相距一前瞻距離的文檔上的連結的數量的。
12. —種用指令編碼的計算機可讀介質，所述指令用於控制計算設備通過一種方法來對具有到其它網頁的超連結的網頁進行排名，所述方法包括通過對源網頁的每一目標網頁的信息內容進行前瞻，基於通過該目標網頁可用的信息，來生成(116)在各對源網頁與直接目標網頁之間轉移的轉移概率；基於所生成的轉移概率的固定概率來計算(117)網頁的重要性； 搜索(113)要包括在針對搜索請求的搜索結果中的網頁；以及 基於計算出的重要性來對搜索結果的網頁進行排名(113)。
13. 如權利要求12所述的計算機可讀介質，其特徵在於，所述轉移概率的生成包括將在不選擇超連結的情況下從一網頁到另一網頁的轉移計算在內。
14. 如權利要求12所述的計算機可讀介質，其特徵在於，所述轉移概率 的生成包括生成轉移概率矩陣。
15. 如權利要求12所述的計算機可讀介質，其特徵在於，迭代地執行所 述重要性的計算，直到所述網頁的固定概率收斂於一解。
16. 如權利要求12所述的計算機可讀介質，其特徵在於，所述轉移概率 被表示為轉移概率矩陣，且所述重要性的計算通過標識轉移概率矩陣的主本徵 向量來執行。
17. 如權利要求12所述的計算機可讀介質，其特徵在於，所述網頁基於 與搜索結果的相關性來排名。
18. —種用於計算具有到其它網頁的超連結的網頁的重要性的計算設備， 所述計算設備包括通過對目標網頁的信息內容進行前瞻來生成在各對網頁之間轉移的轉移 概率的組件(116);基於所述轉移概率的固定概率來計算網頁的重要性的組件(117); 基於計算出的重要性對網頁進行排名的組件(113)。
19. 如權利要求18所述的計算設備，其特徵在於，所述生成轉移概率的組件將在不選擇超連結的情況下從一網頁到另一網頁的轉移計算在內。
20. 如權利要求18所述的計算設備，其特徵在於，從源網頁轉移到直接 目標網頁的轉移概率通過對源網頁的每一直接目標網頁的信息內容進行前瞻 而基於通過該目標網頁可用的信息。
全文摘要
提供了用於基於從源文檔到目標文檔的轉移概率來計算文檔的重要性的方法和系統，其中轉移概率基於對源文檔的目標文檔的信息內容進行前瞻。前瞻重要性系統基於對到源文檔的目標文檔的連結的分析來生成在任一對源文檔和目標文檔之間轉移的轉移概率。該系統可以基於相隔一前瞻距離的文檔上的連結的數量來計算轉移概率。該系統隨後求出轉移概率的固定概率。該固定概率表示文檔的重要性。
文檔編號G06F17/21GK101652773SQ200880010756
公開日2010年2月17日 申請日期2008年3月29日 優先權日2007年3月30日
發明者T-Y·劉 申請人:微軟公司