博士研究生學(xué)位論文 題目： 歷史網(wǎng)頁的持續(xù)收藏及其再訪問的關(guān)鍵技術(shù)研究 姓 名： 學(xué) 號： 10208821 院 系： 信息科學(xué)技術(shù)學(xué)院 專 業(yè)： 計算機(jī)系統(tǒng)結(jié)構(gòu) 研究方向： 網(wǎng)絡(luò)與分布式系統(tǒng) 導(dǎo)師姓名： 李曉明 二 00 八 年 五 月 On a in of ( i 2008 版權(quán)聲明 任何收存和保管本論文各種版本的單位和個人，未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問題，將可能承擔(dān)法律責(zé)任。 i 摘 要 網(wǎng)頁是一種易逝的信息資源，在新網(wǎng)頁不斷涌現(xiàn)的同時舊網(wǎng)頁也在逐步消失。如果沒有專門的機(jī)構(gòu)來對網(wǎng)頁進(jìn)行收集和保存，它們就會在不經(jīng)意之間消失。而隨著互聯(lián)網(wǎng)成為一種不可忽視的新媒體，網(wǎng)頁內(nèi)容的重要性已經(jīng)不言而喻。因此，持續(xù)收藏并永久保存出現(xiàn)過的網(wǎng)頁具有重要的意義，可以為后人提供珍貴的歷史資料。顯然，人們還希望能 夠以一種比較方便的方式來再訪問這些保存下來的海量網(wǎng)頁，從而才能體現(xiàn)出這種收藏的價值。這里所說的“再訪問”可以有多方面的含義，包括根據(jù) 鏈接關(guān)系來瀏覽歷史網(wǎng)頁，像搜索引擎那樣查詢相關(guān)網(wǎng)頁，等等。 不難想到，這項工作可以大致分成兩個部分，一是有計劃地進(jìn)行網(wǎng)頁的持續(xù)搜集，二是將搜集到的網(wǎng)頁適當(dāng)?shù)亟M織起來，以便再訪問。本文的工作屬于后者。即我們假定有一個搜集系統(tǒng)源源不斷地將網(wǎng)頁搜集下來，我們需要對它們進(jìn)行有效地組織和存儲，并提供對它們有意義的訪問方式。 針對這種需求，本文確定了四個關(guān)鍵技術(shù)問題，對它們分別進(jìn)行了深入的研究，并基于研究的成果設(shè)計并實(shí)現(xiàn)了兩個系統(tǒng)。本文的主要貢獻(xiàn)包括： 1）提出了一種帶有時間標(biāo)簽的鏈接圖的存儲及壓縮方法。鏈接圖是表達(dá)網(wǎng)頁之間關(guān)系的一種重要數(shù)據(jù)結(jié)構(gòu)，它是鏈接分析技術(shù)的基礎(chǔ)，廣泛應(yīng)用于 據(jù)的分析、挖掘、檢索領(lǐng)域。通常，鏈接圖上是沒有時間信息的。而由于本文工作所針對的是長時間持續(xù)搜集的歷史網(wǎng)頁，對應(yīng)同一個 網(wǎng)頁的不同版本會在不同時間被搜集下來，于是網(wǎng)頁的鏈接 關(guān)系會隨著時間發(fā)生改變，因而就形成了帶有時間標(biāo)簽的鏈接圖。本文 研究 了帶有時間標(biāo)簽的鏈接圖新型表示模型，詳細(xì)設(shè)計了存儲格式和 壓縮方法。 這方面的研究成果的有效性在我們所收藏的 24 億歷史網(wǎng)頁集 合 上得到驗(yàn)證， 從該集 合 我們構(gòu) 造 了一個包含有1546 億條帶有時間標(biāo)簽鏈接 的鏈接圖 系統(tǒng) ，并得到一些初步應(yīng)用 。 2）提出了一種從雜亂無章的網(wǎng)頁集合中篩選出文章型網(wǎng)頁的方法。我們稱新聞報道、分析評論、論壇帖子、博客日記等由人創(chuàng)作完成的作品，具有標(biāo)題以及一段邏輯上連續(xù)的正文，為網(wǎng)絡(luò)文章。文章型網(wǎng)頁指的是包含網(wǎng)絡(luò)文章的網(wǎng)頁。直覺上，它們具有較高的挖掘和檢索價值。本文提出的方法基于對文章一般性規(guī)律的認(rèn)識，具有通用性和較好的效果。簡要地說，首先從網(wǎng)頁內(nèi)容中提取 出標(biāo)題，然后從標(biāo)題位置后面的文字內(nèi)容中提取出正文來。 實(shí)驗(yàn)表明精度和召回率都很高。 根據(jù)這一方法 （但 在大規(guī)模數(shù)據(jù)條件下 因個別技術(shù) 難點(diǎn) 沒有完整實(shí)現(xiàn)） ，本文從 24 億網(wǎng)頁中提取出了約 篇網(wǎng)絡(luò)文章。 3）提出了一種新型的相似網(wǎng)頁檢測算法，同時具備高準(zhǔn)確率與高覆蓋率的優(yōu)點(diǎn)。該算法采用基于 相 似性度量方法，設(shè)計了一個包含了三個步驟的檢測過程框架，保證了算法 的效率。綜合實(shí)驗(yàn)表明本文的算法同時獲得了高準(zhǔn)確率與高覆蓋率。該算法成功應(yīng)用于上述網(wǎng)絡(luò)文章的消重，將 文章型網(wǎng)頁分割為 個相似網(wǎng)頁子集（即得到 篇不同的網(wǎng)絡(luò)文章），整個過程使用 6 臺 務(wù)器僅花費(fèi)了 5 天的時間。 4）提出了一種網(wǎng)絡(luò)文章發(fā)表時間的估計方法。發(fā)表時間是文章的一個重要屬性。比較容易想到的方法是通過從網(wǎng)頁文字內(nèi)容中提取出來的時間、網(wǎng)頁的 網(wǎng)頁搜集時間這三種信息來推斷文章發(fā)表時間。然而其效果并不足夠理想。因而在此之上本文進(jìn)一步提出了利用鏈接分析和檢測相同 文章的方法來提高計算精度。綜合實(shí)驗(yàn)表明，前者可以提高約 35%的計算精度，而后者的作用更加 顯著， 如果能夠檢測到文章的多個其它拷貝，則有很大的概率計算出來的文章發(fā)表時間是準(zhǔn)確的。 5）設(shè)計并實(shí)現(xiàn)了一個大規(guī)模歷史網(wǎng)頁倉儲系統(tǒng)，并提供歷史網(wǎng)頁回放服務(wù)，稱為 ）。它用于存儲搜集系統(tǒng)持續(xù)不斷搜集來的歷史網(wǎng)頁，用戶可以在上面使用 獲取和瀏覽歷史網(wǎng)頁?？蓴U(kuò)展和增量存儲是本系統(tǒng)的兩個重要特性。對此，本文設(shè)計了相應(yīng)的存儲組織結(jié)構(gòu)和索引結(jié)構(gòu)，它們經(jīng)歷了海量網(wǎng) 頁數(shù)據(jù)的考驗(yàn)并具備較好的性能。到目前為止，已經(jīng)收藏了近六年來在中國互聯(lián)網(wǎng)上出現(xiàn)過的近 30 億網(wǎng)頁，壓縮以后的數(shù)據(jù)量超過 20外，本文還設(shè)計了一種適合網(wǎng)頁長期保存的存儲格式。 6）在上述研究成果的基礎(chǔ)上，設(shè)計并初步實(shí)現(xiàn)了一種面向歷史事件報道蹤跡的搜索引擎系統(tǒng)，稱為 ）。它用于檢索在歷史網(wǎng)頁中所記錄、描述的歷史事件對象，并按時間的順序?qū)⑺鼈冋宫F(xiàn)出來。當(dāng)前系統(tǒng)建立在一個規(guī)模為 24 億的歷史網(wǎng)頁集上，采用前面所描述的方法和技術(shù)，從中提取出 篇文章，在消重之后得到 篇不同的文章，并為每篇文章計算出它的最早發(fā)表時間。然后，為這些 文章的標(biāo)題建立了索引，當(dāng)用戶輸入歷史事件的關(guān)鍵詞時，系統(tǒng)返回與它關(guān)聯(lián)的所有文章（網(wǎng)頁），并按發(fā)表時間的順序排列出來。 關(guān)鍵詞 ：歷史網(wǎng)頁， 儲， 信息檢索， 相似性檢測 v On a eb is a or If by in a be of of is of on a be up of to be in a to of is 1) ) by a It is to be is to in a is to In to we a up we to In to in we on At on we of 1) A of is is is an is of in no is on in so we is a of In we a of of is in A of on a .4 we a 54.6 on 2) A a of is We on eb as of at a of to a of is on of so it is we we s a s we s s of to of to we .4 3) A of is of is a 3is to A to a 30 8 of of to a 4) of is an of to a re by by by So we to 5% of of is if s we to 5) A ), is It is to by a by of we of As of a of 0 a of 6) on a of is ). It is to of in is in a is on a .4 of of a of a s it in a to 目 錄 第 1 章 緒論 . 1 究工作的背景和意義 . 1 存現(xiàn)狀 . 5 文研究內(nèi)容概述 . 10 第 2 章 背景知識與相關(guān)研究 . 14 史網(wǎng)頁的搜集 . 14 史網(wǎng)頁的倉儲 . 20 史網(wǎng)頁的挖掘與檢索 . 25 章小節(jié) . 31 第 3 章 一種帶有時間標(biāo)簽的鏈接圖存儲方法 . 33 言 . 33 關(guān)研究 . 34 有時間標(biāo)簽的鏈接圖表示模型 . 34 關(guān)模型簡介 . 35 型設(shè)計 . 36 計理念 . 38 縮存儲格式設(shè)計 . 40 接圖壓縮技術(shù)綜述 . 40 儲格式設(shè)計 . 42 接表存儲格式設(shè)計 . 43 術(shù)實(shí)現(xiàn)情況 . 46 章小結(jié) . 48 第 4 章 一種從網(wǎng)頁集合中篩選網(wǎng)絡(luò)文章的方法 . 50 言 . 50 關(guān)研究 . 50 絡(luò)文章的特點(diǎn)分析 . 53 選方法 . 55 x 驗(yàn)與評測 . 57 定標(biāo)點(diǎn)符號分布特征的閾值參數(shù) . 57 體效果評測 . 61 能及運(yùn)行結(jié)果 . 62 章小結(jié) . 62 第 5 章 一種基于 相似網(wǎng)頁檢測算法 . 64 言 . 64 關(guān)研究 . 64 于 相似性度量 . 66 景知識 . 66 量方法 . 67 似性度量的一般過程 . 67 度的比較 . 68 法與實(shí)現(xiàn) . 69 統(tǒng)框架 . 69 能相似子集的計算 . 69 檔過濾框架的計算 . 71 信 部分（ 計算 . 72 驗(yàn)評測 . 75 紋數(shù)量的影響 . 76 動窗口長度的影響 . 77 似度閾值的影響 . 79 行效率 . 80 法的比較 . 81 度的比較 . 82 章小結(jié) . 83 第 6 章 網(wǎng)絡(luò)文章發(fā)表時間的計算方法研究 . 84 言 . 84 關(guān)研究 . 84 章的時間屬性分析 . 85 章發(fā)表時間的計算方法 . 86 究數(shù)據(jù)來源 . 86 礎(chǔ)計算方法及其問題 . 86 高計算精度的方法 . 89 驗(yàn)與評測 . 91 章小結(jié) . 94 第 7 章 種歷史網(wǎng)頁倉儲系統(tǒng)的設(shè)計與實(shí)現(xiàn) . 95 言 . 95 統(tǒng)設(shè)計 . 95 頁的存儲 . 99 據(jù)的組織 . 99 儲結(jié)構(gòu) . 101 據(jù)管理與壓縮 . 103 儲性能 . 105 據(jù)訪問 . 106 索引 . 106 索引 . 107 據(jù)服務(wù) . 109 能與優(yōu)化 . 110 頁歷史回放 . 111 頁的長期保存 . 112 章小結(jié) . 114 第 8 章 種面向事件報道歷史的搜索引擎 設(shè)計與初步實(shí)現(xiàn) . 116 言 . 116 往探索與經(jīng)驗(yàn) . 117 統(tǒng)設(shè)計 . 120 統(tǒng)概念框架 . 120 要環(huán)節(jié)分析 . 123 系結(jié)構(gòu)設(shè)計 . 125 統(tǒng)實(shí)現(xiàn)情況 . 126 章小結(jié) . 129 第 9 章 總結(jié)與展望 . 130 文的總結(jié) . 130 一步的研究工作 . 134 參考文獻(xiàn) . 136 在讀期間發(fā)表的文章 . 143 在讀期間參加的科研項目 . 144 致謝 . 145 圖示 圖 2出的增量搜集體系結(jié)構(gòu) . 17 圖 2同域名的網(wǎng)頁變化周期 . 18 圖 2基本模型 . 27 圖 2個網(wǎng)頁歷史回放的例子 . 28 圖 3接圖的超級節(jié)點(diǎn)表示法 . 36 圖 3分布圖 . 41 圖 3 存儲 . 43 圖 3接表存儲格式 . 44 圖 3個鏈接查詢示例 . 48 圖 4標(biāo)簽樹實(shí)例 . 52 圖 4個典型的記錄型網(wǎng)頁片段 . 54 圖 4個典型的新聞類文章型網(wǎng)頁片段 . 55 圖 4人民日報語料庫中文章的標(biāo)點(diǎn)符號比例分布