網(wǎng)頁(yè)去重策略和實(shí)現(xiàn)

網(wǎng)頁(yè)去重的策略和實(shí)現(xiàn)0 引言互聯(lián)網(wǎng)時(shí)代的到來(lái)，極大地影響了人們的日常生活，改變著人類的生活習(xí)慣。同時(shí)，也給人們帶來(lái)了極大的便利。人們?cè)絹?lái)越喜歡通過(guò)搜索引擎來(lái)查找自己想要得到的內(nèi)容和信息，這是搜索引擎技術(shù)的機(jī)遇，然而也是挑戰(zhàn)，因?yàn)槿藗兊囊笠苍絹?lái)越苛刻。在我們用搜索引擎搜索信息的時(shí)候，常常會(huì)遇到這樣一種情況：很多內(nèi)容相同或相似的網(wǎng)頁(yè)會(huì)被搜索引擎提交給我們。這對(duì)用戶來(lái)說(shuō)，是很不便利的，不僅浪費(fèi)了時(shí)間，也占用了大量的資源。同時(shí)，也降低了搜索引擎的服務(wù)效率。因而網(wǎng)頁(yè)去重技術(shù)也慢慢被人們重視起來(lái)。網(wǎng)頁(yè)去重的算法有很多種，本文重點(diǎn)介紹一種基于網(wǎng)頁(yè)中文字主題要素的網(wǎng)頁(yè)去重算法。1網(wǎng)頁(yè)去重的理論基礎(chǔ)1.1搜索引擎搜索引擎是指根據(jù)一定的策略、運(yùn)用特定的計(jì)算機(jī)程序從互聯(lián)網(wǎng)上搜集信息，在對(duì)信息進(jìn)行組織和處理后，為用戶提供檢索服務(wù)，將用戶檢索相關(guān)的信息展示給用戶的系統(tǒng)。搜索引擎包括全文索引、目錄索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、門戶搜索引擎與免費(fèi)鏈接列表等。搜索引擎的工作原理：第一步：爬行搜索引擎是通過(guò)一種特定規(guī)律的軟件跟蹤網(wǎng)頁(yè)的鏈接，從一個(gè)鏈接爬到另外一個(gè)鏈接，像蜘蛛在蜘蛛網(wǎng)上爬行一樣，所以被稱為“蜘蛛”也被稱為“機(jī)器人”。搜索引擎蜘蛛的爬行是被輸入了一定的規(guī)則的，它需要遵從一些命令或文件的內(nèi)容。第二步：抓取存儲(chǔ)搜索引擎是通過(guò)蜘蛛跟蹤鏈接爬行到網(wǎng)頁(yè)，并將爬行的數(shù)據(jù)存入原始頁(yè)面數(shù)據(jù)庫(kù)。其中的頁(yè)面數(shù)據(jù)與用戶瀏覽器得到的HTML是完全一樣的。搜索引擎蜘蛛在抓取頁(yè)面時(shí)，也做一定的重復(fù)內(nèi)容檢測(cè)，一旦遇到權(quán)重很低的網(wǎng)站上有大量抄襲、采集或者復(fù)制的內(nèi)容，很可能就不再爬行。第三步：預(yù)處理搜索引擎將蜘蛛抓取回來(lái)的頁(yè)面，進(jìn)行各種步驟的預(yù)處理。除了HTML 文件外，搜索引擎通常還能抓取和索引以文字為基礎(chǔ)的多種文件類型，如 PDF、Word、WPS、XLS、PPT、TXT 文件等。我們?cè)谒阉鹘Y(jié)果中也經(jīng)常會(huì)看到這些文件類型。 但搜索引擎還不能處理圖片、視頻、Flash 這類非文字內(nèi)容，也不能執(zhí)行腳本和程序。第四步：排名用戶在搜索框輸入關(guān)鍵詞后，排名程序調(diào)用索引庫(kù)數(shù)據(jù)，計(jì)算排名顯示給用戶，排名過(guò)程與用戶直接互動(dòng)的。但是，由于搜索引擎的數(shù)據(jù)量龐大，雖然能達(dá)到每日都有小的更新，但是一般情況搜索引擎的排名規(guī)則都是根據(jù)日、周、月階段性不同幅度的更新。1.2 查全率和查準(zhǔn)率查全率是指，查詢關(guān)鍵詞時(shí)，搜索引擎返回的相關(guān)網(wǎng)頁(yè)數(shù)與全部相關(guān)網(wǎng)頁(yè)數(shù)的比率。假如包含某關(guān)鍵詞的網(wǎng)頁(yè)實(shí)際上有N個(gè)，而搜索引擎真正檢索的只有M個(gè)，那么這個(gè)關(guān)鍵詞的查全率就等于MN100%。查全率是衡量搜索引擎檢索是否全面的度量指標(biāo)。查全率越高，則表示搜索引擎的全面檢索能力越強(qiáng)。查準(zhǔn)率是衡量某一檢索系統(tǒng)的信號(hào)噪聲比的一種指標(biāo)，即檢出的相關(guān)文獻(xiàn)與檢出的全部文獻(xiàn)的百分比。普遍表示為：查準(zhǔn)率=（檢索出的相關(guān)信息量/檢索出的信息總量）x100%。檢索系統(tǒng)中的匹配，分為精確匹配和模糊匹配，在文獻(xiàn)檢索時(shí)應(yīng)根據(jù)需要選用。本文在利用模糊匹配方式提高查全率的同時(shí)，還利用基于中文字主題要素的網(wǎng)頁(yè)去重方法來(lái)提高查準(zhǔn)率。1 網(wǎng)頁(yè)重復(fù)的原因和其他去重方法21 網(wǎng)頁(yè)重復(fù)的原因搜索過(guò)程中產(chǎn)生重復(fù)的原因主要有兩個(gè)，一個(gè)是由于URL本身的構(gòu)造原因產(chǎn)生搜索結(jié)果重復(fù)。例如，虛擬主機(jī)技術(shù)可能會(huì)使得多個(gè)不同域名映射到同一個(gè)IP，當(dāng)搜索系統(tǒng)用這些域名進(jìn)行搜索時(shí)，實(shí)際上搜索到的是同一個(gè)站點(diǎn)，導(dǎo)致搜索結(jié)果重復(fù)。這一類由于URL本身導(dǎo)致網(wǎng)頁(yè)重復(fù)的問(wèn)題相對(duì)來(lái)說(shuō)比較容易解決，例如，可以通過(guò)建立IP與域名的對(duì)應(yīng)表、比較網(wǎng)站前幾頁(yè)網(wǎng)頁(yè)代碼等方式解決。網(wǎng)頁(yè)重復(fù)的另一個(gè)重要原因是不同網(wǎng)站之間對(duì)相同的內(nèi)容重復(fù)引用或同一站點(diǎn)在不同物理位置的鏡像等而導(dǎo)致的，這對(duì)于一些熱點(diǎn)內(nèi)容和重要站點(diǎn)尤其如此。對(duì)于這類情況，由于大量重復(fù)網(wǎng)頁(yè)不是直接對(duì)原有網(wǎng)頁(yè)進(jìn)行復(fù)制，而是將轉(zhuǎn)載引用的內(nèi)容放到自己網(wǎng)頁(yè)的某個(gè)特定位置再提供給用戶，或者在鏡像時(shí)定制了網(wǎng)頁(yè)的內(nèi)容。這樣，新的網(wǎng)頁(yè)就可能在風(fēng)格、布局、代碼方面與原有網(wǎng)頁(yè)有很大的差別，因而不能使用網(wǎng)頁(yè)的形式特征來(lái)對(duì)網(wǎng)頁(yè)消重，消重的依據(jù)只能是根據(jù)網(wǎng)頁(yè)的內(nèi)容特征。22 其他去重方法 目前, 網(wǎng)頁(yè)去重代表性方法有3種。 1)基于聚類的方法。該方法是基于網(wǎng)頁(yè)文本內(nèi)容以6763個(gè)漢字作為向量的基, 文本中某組或某個(gè)漢字所出現(xiàn)的頻率就構(gòu)成了代表網(wǎng)頁(yè)的向量, 通過(guò)計(jì)算向量的夾角確定是否是相同的網(wǎng)頁(yè)。 2)排除相同URL方法。各種元搜索引擎去重主要采用此方法。它分析來(lái)自不同搜索引擎的網(wǎng)頁(yè)URL, URL 相同, 即被認(rèn)為是相同的網(wǎng)頁(yè), 可將其去除。 3)基于特征碼的方法。這種方法利用標(biāo)點(diǎn)符號(hào)多數(shù)出現(xiàn)在網(wǎng)頁(yè)文本的特點(diǎn), 以句號(hào)兩邊各5 個(gè)漢字作為特征碼來(lái)唯一地表示網(wǎng)頁(yè)。3 基于文字主題要素的去重方法 選擇主題詞就是把主題概念轉(zhuǎn)換成檢索語(yǔ)言。 選詞的廣度和專指度對(duì)查全率和查準(zhǔn)率起著關(guān)鍵作用, 使用規(guī)范的主題要素可以達(dá)到最佳的檢索效果。 本文針對(duì)同一網(wǎng)絡(luò)資源在不同網(wǎng)頁(yè)中的不同文字描述進(jìn)行去重, 對(duì)網(wǎng)頁(yè)內(nèi)容做出客觀的分析和學(xué)習(xí)以達(dá)到網(wǎng)頁(yè)去重的目的, 規(guī)范網(wǎng)頁(yè)中文字的主題要素, 建立時(shí)間、來(lái)自于何處(版本、格式、廠家、主要行使人、地點(diǎn)等)與目的之間的關(guān)系, 通過(guò)建立這些關(guān)系可以表明用戶按照自己的偏好查找網(wǎng)頁(yè)的大致內(nèi)容。在進(jìn)行抽取的時(shí)候, 不管是時(shí)間短語(yǔ)、 來(lái)自于何處短語(yǔ), 還是 目的短語(yǔ), 都是句子修飾的一部分, 應(yīng)盡量依照標(biāo)點(diǎn)分割的方法, 把一句話分成幾塊, 再把 塊分解成時(shí)間、 來(lái)自于何處、目的短語(yǔ), 然后依照1個(gè)名詞、1個(gè)動(dòng)詞相隔的查詢方法進(jìn)行抽取, 先在發(fā)現(xiàn)短語(yǔ)的這個(gè) 塊中查找, 找不到再去相鄰的塊查找 。對(duì)這類短語(yǔ), 在抽取的過(guò)程中規(guī)定了一些抽取的規(guī)則, 保證了所有抽取的一致性。 最后是提取核心詞的途徑, 主要有以下2種: 一是利用詞表選詞, 從所使用檢索工具提供的主題詞表查取, 如不同領(lǐng)域文摘的索引指南、名字及各類中文詞的索引庫(kù)等; 二是初查選詞, 如果在詞表中沒(méi)有查到, 先選擇課題關(guān)鍵詞在題名字段或關(guān)鍵詞字段進(jìn)行初查, 然后, 瀏覽文獻(xiàn)記錄, 在主題詞或敘詞字段得到規(guī)范核心詞, 但一定要在主題詞或敘詞字段檢索。抽取的方式可以分為以下幾種(以下加小括號(hào)的便是可根據(jù)用戶的偏好進(jìn)行抽取的)。 1) 來(lái)自于何處短語(yǔ)+ 時(shí)間短語(yǔ)+ 來(lái)自于何處短語(yǔ)+ 目的短語(yǔ)原文: 中國(guó)國(guó)務(wù)院總理溫家寶/where當(dāng)?shù)貢r(shí)間2月2日下午/ time在英國(guó)劍/where(發(fā)表演講/purpose) , 演講中/p闡述應(yīng)對(duì)全球性金融危機(jī)中國(guó)政府三點(diǎn)主張/purpose。抽取后: 溫家寶/where2 月2 日/ time 劍橋/where闡述應(yīng)對(duì)危機(jī)三點(diǎn)主張/purpose提取的核心: 溫家寶/n 劍橋/n闡述/v三點(diǎn)主張/n 2) 來(lái)自于何處短語(yǔ)+ 目的短語(yǔ)+ 名詞 原文: 鄭州市/where最便宜的/ purpose日本料理店/n 在/v 中原路與花里路交叉口向東50米/where 抽取后: 鄭州市/where最便宜的/ purpose日本料理店/n 提取的核心: 鄭州/ns 最便宜的/adj 日本/ns 料理店/n 3) 來(lái)自于何處短語(yǔ)+ 名詞+ 來(lái)自于何處 短語(yǔ)+ 動(dòng)詞+ 名詞+ 動(dòng)詞 原文: (北京市消防局/where) 今日/ time舉行/v發(fā)布會(huì)/n通報(bào)/v央視新址北配/where發(fā)生/v火災(zāi)/n因/c 業(yè)主/where 燃放/v 煙花/n 所致/c 1 /m死/v7 /m (傷/v) 抽取后: 央視新址/where 火災(zāi)/n 因/c 業(yè)主/where燃放/v煙花n所致/c1 /m死/v7 /m(傷/v) 提取的核心: 央視/n 新址/n 火災(zāi)/n 業(yè)主/n死/v 4) 時(shí)間短語(yǔ)+ 來(lái)自于何處短語(yǔ)+ 目的短語(yǔ)+ 目的短語(yǔ) 原文: 2009年/ time瑞星殺毒軟件/w here 最新更新/purpose包21。 22。 01 /n (路虎網(wǎng)/where) 提供/v免費(fèi)下載/purpose 抽取后: 2009年/ time瑞星殺毒軟件/w here最新更新/purpose免費(fèi)下載/purpose 提取的核心: 2009 /n 瑞星/n 最新更新/adj 免費(fèi)/adj 下載/v4 網(wǎng)頁(yè)去重方法的實(shí)現(xiàn) 由于是根據(jù)網(wǎng)頁(yè)中文字的主題要素去重, 所以抽取的內(nèi)容就需要采用句子的模糊匹配來(lái)進(jìn)行網(wǎng)頁(yè)重復(fù)性的度量。 算法設(shè)計(jì)如下。 1) 把要標(biāo)識(shí)的網(wǎng)頁(yè)定義為Ui, 抽取出來(lái)的短語(yǔ)分別表示為T (time), W (where), P (purpose), 相對(duì)應(yīng)短語(yǔ)抽取的句子表示為Y, 句子里面的詞分別表示為n, v, a。 也就是可以把一個(gè)網(wǎng)頁(yè)表示為U =T ( Y( ( n ) , ( v), ( a ) ) ) + W ( Y( ( n) , ( v) , ( a ) ) ) +P ( Y( ( n) , ( v) , ( a) ) ) 。 2) 計(jì)算抽取詞的短語(yǔ)相似度M sim = n + v +a /N + V+ A, 其中n 為相似的名詞的總數(shù), v 為相似的動(dòng)詞的總數(shù), a為相似的形容詞的總數(shù), N 為句子里名詞的總數(shù), V為句子里動(dòng)詞的總數(shù), P 為句子里形容詞的總數(shù)。3) 計(jì)算抽取短語(yǔ)的句子相似度Y sim = t+ w +p /T + W + P, 其中t為相似的時(shí)間短語(yǔ)的總數(shù), w為相似的來(lái)自于何處短語(yǔ)的總數(shù), p 為相似的目的短語(yǔ)的總數(shù), T 為句子里的 時(shí)間短語(yǔ)的總數(shù), W 為句子里來(lái)自于何處短語(yǔ)的總數(shù), P 為句子里目的短語(yǔ)的總數(shù)。由于抽取的不確定性, 在計(jì)算抽取的句子的相似度的時(shí)候, 不能只考慮抽取的名詞和動(dòng)詞, 在這里還加入了抽取的核心詞的比較, 并把抽取的核心詞定義為co。 4) 計(jì)算抽取的核心詞的相似度C sim = co /C, 其中co為比較以后一致的核心詞的數(shù)量, C 為抽取的核心詞的總數(shù)。5) 利用2) 3) 4) 的結(jié)果, 計(jì)算所針對(duì)句子的精確相似度為S sim = (M sim + Ysim + C sim) /3。 通過(guò)比較相似度, 得出匹配一致的句子總數(shù)為s, 抽取出來(lái)的句子總數(shù)為S。6) 由5) 的結(jié)果可計(jì)算出網(wǎng)頁(yè)中文字的相似因子U sim = s / min(S i, S j), 其中S i, S j 分別表示第i, j個(gè)網(wǎng)頁(yè)里抽取出來(lái)的句子總數(shù)。 為了能夠準(zhǔn)確地比較網(wǎng)頁(yè)內(nèi)容的真實(shí)性, 在這里考慮到了語(yǔ)言描述的誤差, 把抽取出來(lái)的短語(yǔ)總數(shù)定義為B, 通過(guò)比較短語(yǔ)相一致的短語(yǔ)總數(shù)為b, 然后比較抽取出來(lái)匹配的句子對(duì)應(yīng)的短語(yǔ)相一致的總數(shù)為B sim。7) 計(jì)算短語(yǔ)的匹配一致性B coherence =b /B sim。8) 計(jì)算短語(yǔ)的可靠因子B credibility= b /B。9) 在以上步驟的基礎(chǔ)上給出重復(fù)度的評(píng)價(jià)函數(shù)RM = (B, B coherence, B credibility, U sim), 通過(guò)預(yù)先設(shè)定的B, B coherence, B credibility, U sim 與得到的4個(gè)參數(shù)來(lái)進(jìn)行比較。 在這里把B, B credibility 這2個(gè)參數(shù)作為判斷網(wǎng)頁(yè)是否重復(fù)的標(biāo)準(zhǔn), 而通過(guò)B coherence, U sim 這2個(gè)參數(shù)來(lái)對(duì)網(wǎng)頁(yè)進(jìn)行去重, 如果大于所給定的初始的B coherence, U sim, 那么RM =1, 認(rèn)為2篇新聞內(nèi)容是重復(fù)的, 其中1篇可以被替代, 在替代的時(shí)候暫且選擇內(nèi)容少的新聞被替代;否則RM = 0, 認(rèn)為2篇新聞內(nèi)容是不重復(fù)的, 是不可以被替代的。5 結(jié)語(yǔ)本文提出的基