隨著互聯(lián)網(wǎng)的不斷發(fā)展，web已經(jīng)成為信息制造、發(fā)布、加工和處理的主要平臺(tái)，但是，互聯(lián)網(wǎng)同時(shí)也面臨著許多問題，使得互聯(lián)網(wǎng)應(yīng)用技術(shù)很難有效地應(yīng)用。大量重復(fù)的網(wǎng)頁數(shù)據(jù)就是其中的一個(gè)主要問題，如何對(duì)這些數(shù)據(jù)進(jìn)行消重呢？今天，我給大家介紹一個(gè)方法：利用MD5加密算法給數(shù)據(jù)消重。

一、MD5加密算法思想及算法描述

1、算法思想

MD5加密算法的作用是讓大容量信息在用數(shù)字簽名軟件簽署私人密鑰前被”壓縮”成一種保密的格式（就是把一個(gè)任意長度的字節(jié)串變換成一定長的大整數(shù)）。對(duì)MD5加密算法簡要的敘述為：

MD5以512位分組來處理輸入的信息，且每一分組又被劃分為16個(gè)32位子分組，經(jīng)過了一系列的處理后，算法的輸出由四個(gè)32位分組組成，將這四個(gè)32位分組級(jí)聯(lián)后將生成一個(gè)128位散列值。本文就是使用MD5加密算法將農(nóng)業(yè)供求數(shù)據(jù)不同的字段值經(jīng)過處理得到一個(gè)128位的MD5編碼存放于數(shù)據(jù)庫的表中，并對(duì)該表建立索引，然后通過比較MD5編碼迅速消除數(shù)據(jù)庫中重復(fù)及相似的供求數(shù)據(jù)。

1.1、多重MD5加密算法

北京大學(xué)的天網(wǎng)使用了多重MD5加密算法，其基于這樣一個(gè)基本思想：為每個(gè)文檔計(jì)算出一組指紋，若兩個(gè)文檔擁有一定數(shù)量的相同指紋，則認(rèn)為這兩個(gè)文檔的內(nèi)容重疊性較高，也即兩者是互為近似相似的。

假設(shè)數(shù)據(jù)集為N個(gè)網(wǎng)頁，若我們?yōu)槊總€(gè)網(wǎng)頁生成m個(gè)指紋，則對(duì)于N個(gè)網(wǎng)頁兩兩比較以檢測(cè)近似的時(shí)間代價(jià)就是0（m2N2）。這樣的計(jì)算量，對(duì)于N為上億個(gè)web頁面的數(shù)據(jù)集來說是不可能完成的。

所以，一般的全文簽名算法都會(huì)對(duì)數(shù)據(jù)作一些處理以降低算法的復(fù)雜度。有算法使用對(duì)＜文檔標(biāo)識(shí)，段標(biāo)識(shí)，指紋＞三元組排序的方法避免了對(duì)所有網(wǎng)頁作兩兩比較，使算法復(fù)雜度有所降低。但是該算法的空間復(fù)雜度和時(shí)間復(fù)雜度仍然是相當(dāng)大的，若應(yīng)用于海量的搜索引擎系統(tǒng)，仍然難以取得理想的效果。

天網(wǎng)的算法在生成每個(gè)網(wǎng)頁的指紋的時(shí)候，對(duì)于這m個(gè)指紋進(jìn)行了優(yōu)先級(jí)排序。這樣，在比較網(wǎng)頁指紋組的時(shí)候，只對(duì)于在前pre（0＜＝pre＜＝rn）個(gè)位置上存在相同指紋的網(wǎng)頁對(duì)進(jìn)行兩兩比較。由于前幾個(gè)指紋多數(shù)對(duì)應(yīng)的是網(wǎng)頁文本的標(biāo)題塊和主要正文塊。該算法可以大大降低算法的復(fù)雜度，但是對(duì)于農(nóng)業(yè)垂直搜索引擎要每天及時(shí)更新數(shù)據(jù)庫來說，這也難以滿足要求。

在考慮到農(nóng)業(yè)垂直搜索引擎數(shù)據(jù)的特點(diǎn)后，發(fā)現(xiàn)農(nóng)業(yè)數(shù)據(jù)完全重復(fù)的居多，所以本文采用單MD5指紋對(duì)完全相同的數(shù)據(jù)進(jìn)行消重后，再對(duì)消重后的數(shù)據(jù)利用多重MD5指紋消重，且定義pre＝3，因?yàn)樵诒疚脑O(shè)計(jì)的農(nóng)業(yè)垂直搜索引擎中使用的文檔數(shù)據(jù)前三個(gè)指紋對(duì)應(yīng)的是文檔標(biāo)題，聯(lián)系人以及聯(lián)系方式，只有這三個(gè)字段一樣的情況下我們才認(rèn)為供求信息可能是相似的。

2、算法描述

根據(jù)前文的描述，本文提出了單MD5和多重MD5混合使用的算法，其算法流程如下：

第一步：單MD5指紋消重　

①從數(shù)據(jù)庫供求信息表（即存放原始供求信息數(shù)據(jù)的表）中讀取供求數(shù)據(jù)各個(gè)字段值并連接生成字符串；

②對(duì)1中生成的字符串進(jìn)行MD5編碼，得到編碼值，并寫入數(shù)據(jù)庫供求信息臨時(shí)表中（該表比供求信息表多了一個(gè)字段即MD5編碼字段）;

③對(duì)數(shù)據(jù)庫中供求信息臨時(shí)表建立索引;

④按照時(shí)間段在索引文件中進(jìn)行RangeQuery查詢產(chǎn)生結(jié)果集hits1(0);

⑤取出hits1(i)的第一條記錄hits1(0)，在索引文件中進(jìn)行TermQuery查詢生生結(jié)果集hits2;

⑥如果hist2.length（）＞1，說明有重復(fù)記錄，得到重復(fù)記錄的ID，在數(shù)據(jù)中刪除，并在索引文件中同步刪除;

⑦將步驟6中重復(fù)記錄中REG—TIME值最大的記錄寫入數(shù)據(jù)庫以及索引文件中；

⑧i＋＋，返回步驟5中取下一條記錄，直到hits1(i）記錄為空結(jié)束。

第二步：多重MD5指紋消重

①從數(shù)據(jù)庫供求信息表中讀取供求數(shù)據(jù)需處理的各個(gè)字段值并連接生成字符串；

②對(duì)1中生成的字符串進(jìn)行分詞；

③對(duì)分詞結(jié)果統(tǒng)計(jì)詞頻，按照詞頻高低重新生成一個(gè)新的字符串?dāng)?shù)組；

④對(duì)字符串?dāng)?shù)組進(jìn)行MD5編碼，得到MD5編碼數(shù)組，寫入數(shù)據(jù)庫中供求信息臨時(shí)表；

⑤對(duì)數(shù)據(jù)庫中供求信息臨時(shí)表建立索引；

⑥按照時(shí)間段在索引文件中進(jìn)行RangeQuery查詢產(chǎn)生結(jié)果集hits1；

⑦取出hits1（i）的第一條記錄hits1(0)，按照MD5編碼數(shù)組中前三個(gè)元素值為關(guān)鍵字在索引文件中進(jìn)行TermQuery查詢生成結(jié)果集hits2；

⑧如果hits2.length（）＞1，說明可能有相似記錄，計(jì)算兩條數(shù)據(jù)中含有的相同MD5指紋數(shù)s；

⑨如果s＞t（t為設(shè)定的閥值），則認(rèn)為兩條數(shù)據(jù)記錄相似，得到相似記錄的ID，在數(shù)據(jù)庫中刪除，并在索引文件中同步刪除；

⑩i＋＋，返回步驟7中取下一條記錄，直到hits1（i）記錄為空結(jié)束。

二、實(shí)驗(yàn)結(jié)果及分析

本文從原始數(shù)據(jù)庫中（網(wǎng)絡(luò)爬蟲采集到的，但是沒有經(jīng)過任何處理的數(shù)據(jù)）抽取70萬條農(nóng)業(yè)供求信息數(shù)據(jù)，利用本文介紹的方法進(jìn)行試驗(yàn)，然后分別使用算法描述中的步驟一和步驟二進(jìn)行獨(dú)立實(shí)驗(yàn)，并比較這三種實(shí)驗(yàn)結(jié)果的查準(zhǔn)率和召回率（也稱查全率）以及響應(yīng)時(shí)間。

1、查準(zhǔn)率　

查準(zhǔn)率反映了的算法所發(fā)現(xiàn)的近似數(shù)據(jù)中有多少是正確的近似數(shù)據(jù)結(jié)果，假設(shè)算法檢測(cè)到了Ｓ個(gè)重復(fù)數(shù)據(jù)記錄，其中個(gè)正確結(jié)果，即符合我們對(duì)于近似數(shù)據(jù)的定義。則算法的查準(zhǔn)率為Precision=P=So/s，計(jì)算查準(zhǔn)率本文使用的方法為：在大數(shù)據(jù)的實(shí)驗(yàn)結(jié)果中進(jìn)行采樣，進(jìn)行人工評(píng)測(cè)，取樣本的準(zhǔn)確率的平均值作為算法的查準(zhǔn)率。

2、召回率　

召回率是算法所發(fā)現(xiàn)的正確的近似數(shù)據(jù)記錄占全部近似數(shù)據(jù)記錄的百分比。計(jì)算召回率方法為：由于不能確定實(shí)際全部近似數(shù)據(jù)記錄的個(gè)數(shù)，用算法發(fā)現(xiàn)的近似數(shù)據(jù)記錄集合的大小與實(shí)驗(yàn)中所有算法得到的近似數(shù)據(jù)記錄的并集的大小之比來代替查全率。假設(shè)算法檢測(cè)到了個(gè)近似數(shù)據(jù)記錄，而數(shù)據(jù)集中實(shí)際存在Ｓ個(gè)近似數(shù)據(jù)記錄，則算法的召回率為：Recall=r=S0/S0。

3、實(shí)驗(yàn)結(jié)果

運(yùn)行環(huán)境：PC機(jī)，Windows xp操作系統(tǒng)，JAVA實(shí)現(xiàn)算法。在我們的垂直搜索引擎“搜農(nóng)”上實(shí)驗(yàn)得到結(jié)果如表一所示：

方法一為使用本文提出的先使用單MD5指紋進(jìn)行完全相同數(shù)據(jù)記錄消重，然后對(duì)消重后的數(shù)據(jù)庫利用多重MD5指紋進(jìn)行相似數(shù)據(jù)消重；

方法二為單獨(dú)使用單MD5指紋進(jìn)行消重；

方法三為單獨(dú)使用多重MD5指紋進(jìn)行消重。

為了方便對(duì)比作出查準(zhǔn)率和召回率對(duì)比圖，如圖所示。

實(shí)驗(yàn)結(jié)果表明：在查準(zhǔn)率和響應(yīng)時(shí)間上，方法二最高；在召回率上，方法一最優(yōu)；考慮到方法二不能有效消除近似的數(shù)據(jù)記錄，而只能消除完全相同的數(shù)據(jù)記錄，所以我們選用方法一。

利用MD5加密算法在數(shù)據(jù)處理階段可以有效的消除冗余數(shù)據(jù)。結(jié)果表明該方法可以很好的提高檢索質(zhì)量。

admin

收藏 海報(bào)分享