◆舒遠(yuǎn)仲 梁 濤 王 娟

一種針對天貓購物平臺的網(wǎng)頁URL去重策略研究

◆舒遠(yuǎn)仲 梁 濤 王 娟

（南昌航空大學(xué)信息工程學(xué)院 江西 330063）

本文在分析了Bloom Filter缺點(diǎn)的基礎(chǔ)上，結(jié)合天貓購物平臺網(wǎng)頁URL的特征，對網(wǎng)頁URL去重策略進(jìn)行了改進(jìn)，以此來提高網(wǎng)頁URL去重效果及減小Bloom Filter誤判率。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的去重策略在針對天貓購物平臺網(wǎng)頁URL去重時，準(zhǔn)確度上要優(yōu)于傳統(tǒng)的Bloom Filter。

布隆過濾器；網(wǎng)頁URL去重；哈希處理；誤判率；天貓

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展以及網(wǎng)絡(luò)購物平臺的興起，越來越多的人加入到“網(wǎng)購大軍”中。以2016年“雙十一”為例，據(jù)第三方數(shù)據(jù)公司星圖數(shù)據(jù)11月12日發(fā)布的《星圖數(shù)據(jù)1112：雙十一網(wǎng)購大數(shù)據(jù)分析報告》[1]顯示，2016年雙十一全網(wǎng)總銷售額為1770.4億元，其中化妝品類銷售總額為212.4億元，占全網(wǎng)銷售總額的12.0%。由此也帶來了一些的問題：部分商家銷售假冒偽劣產(chǎn)品，使得消費(fèi)者權(quán)益受到侵害。因此，相關(guān)部門需要采取相應(yīng)措施對網(wǎng)售商品進(jìn)行監(jiān)督管理。

網(wǎng)購平臺的商品具有海量 、增長迅速、更新頻繁的特點(diǎn)，在給消費(fèi)者提供更多選擇的同時，也給監(jiān)管部門帶來了巨大的挑戰(zhàn)。監(jiān)管部門需要獲取網(wǎng)售商品的信息，用于與基礎(chǔ)庫上的信息進(jìn)行比對，從而達(dá)到監(jiān)管的目的。為了獲取商品信息，需要使用網(wǎng)絡(luò)爬蟲自動抓取網(wǎng)頁并提取網(wǎng)頁內(nèi)容。通常在給定的一個或多個統(tǒng)一資源定位符URL（Uniform ResourceLocator）種子集情況下，從種子網(wǎng)頁開始采集，在抓取網(wǎng)頁的過程中，不斷將新的URL放進(jìn)待爬行的URL隊(duì)列中，直到滿足一定條件（如待爬行隊(duì)列為空、達(dá)到指定爬行數(shù)量）停止爬行[2]。如何選擇符合主題的URL，如何過濾已抓取過的信息對系統(tǒng)來說至關(guān)重要。

本文提出了針對上述問題的解決方案。以天貓網(wǎng)購平臺為例，針對其網(wǎng)頁URL的特點(diǎn)，通過對URL去重方式的改進(jìn)，使得網(wǎng)絡(luò)爬蟲能夠更準(zhǔn)確、更快速地抓取所需要的網(wǎng)頁。

1 天貓網(wǎng)購平臺網(wǎng)頁URL分析

天貓采用是動態(tài)URL，即同一商品對應(yīng)的網(wǎng)頁可能存在多個URL。通過對這些URL的分析，找出它們之間的聯(lián)系，從而可以簡化URL去重。如表1，選取多個URL實(shí)例來分析其特點(diǎn)。

表1 天貓網(wǎng)購平臺網(wǎng)頁URL實(shí)例

從表1中可以得出，同一店鋪同一產(chǎn)品可能對應(yīng)多個URL；不同店鋪同一產(chǎn)品對應(yīng)URL不同；同一店鋪不同產(chǎn)品對應(yīng)的URL也不一樣。但對各個URL具體分析后，可以發(fā)現(xiàn)：每個URL中都含有參數(shù)id，對于同一店鋪同一產(chǎn)品，盡管對應(yīng)多個URL，但參數(shù)id的值是一致的；不同店鋪同一產(chǎn)品URL中的參數(shù)id的值不一樣；同一店鋪不同產(chǎn)品URL中的參數(shù)id的值不一樣。

2 布隆過濾器

布隆過濾器（Bloom Filter）是1970年由布隆提出來的。它實(shí)際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于判斷一個元素是否存在于一個集合中。它的優(yōu)點(diǎn)是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點(diǎn)是有一定的誤識別率和刪除困難。布隆過濾器是一種空間利用率高的算法,特別適合于海量數(shù)據(jù)集的表示和查找,盡管存在一定的誤判率,但在海量信息搜集的系統(tǒng)中,不失為一種可行的解決方案[3-5]。

2.1布隆過濾器原理及判斷方法

如圖1所示，布隆過濾器原理如下：

圖1 布隆過濾器（Bloom Filter）原理

（1） 設(shè)數(shù)據(jù)集合S={S1,S2,S3,……,Sn}，含有n個元素，為待操作的集合；

（2） Bloom Filter用一個長度為m的位向量V來表示集合中元素，位向量初始化全為0；

（3） 選取k個相互獨(dú)立的哈希函數(shù)h1，h2，h3，……，hk;

（4） 用Bloom Filter表示集合S的所有元素。首先，對集合里的元素Si通過k個哈希函數(shù)產(chǎn)生k個哈希值h’1，h’2，h’3，……，h’k，將位向量V的h’1，h’2，h’3，……，h’k位上的值置為1。由于通過個哈希函數(shù)將位向量V相應(yīng)位置為1，多個集合元素進(jìn)行增加操作時，可能會出現(xiàn)向量相應(yīng)位置已經(jīng)為1，此時不對相應(yīng)位的值進(jìn)行操作。

在判斷一個元素X是否屬于該集合時，我們只需要對X使用相同的k個哈希函數(shù)得到k個哈希值，如果位向量V上對應(yīng)位置上的k個值全為1，那么我們就認(rèn)為該元素存在于該集合中；反之，我們就認(rèn)為該元素不存在于該集合。如圖2所示，元素X1是該集合的元素，X2不是該集合的元素。

圖2 判斷元素是否屬于該集合

顯然，這個判斷并不能保證結(jié)果100%的正確。當(dāng)我們判斷一個元素元素不屬于該集合時，這個判斷是100%正確的，但當(dāng)我們判斷一個元素屬于該集合時，這個判斷可能是個誤判[6-8]。

2.2布隆過濾器的缺點(diǎn)及誤判率

雖然布隆算法的空間效率及查詢時間都遠(yuǎn)遠(yuǎn)超過其他算法，但是布隆過濾器還是存在缺點(diǎn)。

（1）Bloom Filter存在一定的誤判率。對于已經(jīng)映射在集合中的元素，通過集合查找運(yùn)算一定可以判定該元素在集合中，但對于尚未映射到集合中的元素，可能存在誤判，即不在集合中的元素誤判為在集合中。

假設(shè)集合S中含有n個元素，需要使用k個哈希函數(shù)進(jìn)行處理，Bloom Filter長度為m，則某一位被置為1的概率為1/m，為0的概率為（1-1/m）。所以在集合S中的元素全部用Bloom Filter表示后，某位仍為0的概率為：

則誤判的概率為

（2）Bloom Filter無法從Bloom Filter集合中刪除一個元素。因?yàn)橐粋€元素對應(yīng)的位可能與另一個元素對應(yīng)的位存在共同位。如圖3所示。

圖3 存在共同位的元素

元素X1、X2是同一集合的元素，當(dāng)刪除元素X1，即把元素X1對應(yīng)位置為0時，X2對應(yīng)位則變?yōu)?11，此時元素X2被判斷為不在集合中。所以，一個簡單的改進(jìn)方法就是使用計數(shù)型布隆過濾器（Counter Bloom Filter），在Bloom Filter 進(jìn)行集合元素添加操作時，對相應(yīng)的向量位進(jìn)行加1操作。如圖4所示。

圖4 Counter Bloom Filter

3 網(wǎng)頁URL去重

針對天貓網(wǎng)頁URL的特點(diǎn)及Bloom Filter存在誤判率的缺點(diǎn)，本文提出一種基于Bloom Filter的改進(jìn)的URL去重的策略。如圖5所示。

（1）抓取一個URL，分析判斷URL中是否含有參數(shù)id。對于不存在參數(shù)id的URL直接舍棄；

（2）提取參數(shù)id并對其進(jìn)行多個哈希處理；

（3）判斷處理后的id是否存在于布隆過濾器中，如果不存在，則直接將此URL放入待抓取URL隊(duì)列中，并將處理后的id添加到布隆過濾中，同時將id存儲到id數(shù)組中；

（4）如果處理后的id存在于布隆過濾器中，為了避免布隆過濾器的誤判，則判斷id是否存在于id數(shù)組中，如果不存在，則將此URL放入待抓取URL隊(duì)列中，同時將id存儲到id數(shù)組中；如果存在，則說明此商品URL已存在于待抓取URL隊(duì)列中，則舍棄該URL；

（5）初始化的id數(shù)組為空，插入數(shù)據(jù)時應(yīng)有序插入。這樣，對于查找判斷一個id是否存在于該數(shù)組時可使用二分法進(jìn)行，從而可以節(jié)省查找時間。

圖5 改進(jìn)后的URL去重策略

4 實(shí)驗(yàn)分析

由于進(jìn)行的是仿真實(shí)驗(yàn)，通過采集天貓網(wǎng)頁URL，將URL緩存于內(nèi)存空間，分別使用傳統(tǒng)Bloom Filter與改進(jìn)后的Bloom Filter對URL進(jìn)行去重，比較兩者對于比較時間、準(zhǔn)確度上的區(qū)別。結(jié)果如圖6、圖7所示。

圖6 傳統(tǒng)與改進(jìn)后Bloom Filter去重的時間對比

圖7 傳統(tǒng)與改進(jìn)后Bloom Filter去重的準(zhǔn)確度對比

通過實(shí)驗(yàn)結(jié)果可以看出，在準(zhǔn)確度上，改進(jìn)后的Bloom Filter要優(yōu)于傳統(tǒng)Bloom Filter，在時間上，略慢于傳統(tǒng)Bloom Filter。

5 結(jié)束語

本文研究了Bloom Filter的基本工作原理，并對其在網(wǎng)頁URL去重中的應(yīng)用進(jìn)行改進(jìn)，結(jié)果表明改進(jìn)后的策略去重準(zhǔn)確率提高。同時，改進(jìn)后的策略在去重速度上仍有改進(jìn)的空間。

[1]星圖數(shù)據(jù).星圖數(shù)據(jù)1112：雙十一網(wǎng)購大數(shù)據(jù)分析報告EB/OL].http//www.syntun.com.cn/xing-tu-shu-ju1112- shuang-shi-yi-wang-gou-da-shu-ju-fen-xi-bao-gao.html，2016.

[2]黃正德.主題爬蟲關(guān)鍵技術(shù)研究[D].黑龍江：哈爾濱工程大學(xué)，2013.

[3]蘇國榮，楊岳湘，鄧勁生.一種去除重復(fù)URL的算法[J].廣西師范大學(xué)學(xué)報(自然科學(xué)版)，2010.

[4]黃誠.一種高速URL過濾算法的研究與應(yīng)用[J].現(xiàn)代計算機(jī)(專業(yè)版)，2016.

[5]劉佐達(dá)，張久嶺，陳茂科，李星.一種面向BBS信息檢索的主題網(wǎng)絡(luò)爬蟲算法[J].鄭州大學(xué)學(xué)報(理學(xué)版)，2010.

[6]張宗華，屈英，葉志佳等.基于多特征匹配和Bloom filter的重復(fù)數(shù)據(jù)刪除算法[J].深圳大學(xué)學(xué)報(理工版)，2016.

[7]ZHANG Guo,ZHANG Jianhui,WANG Binqiang,ZHANG Zhen.On-line Popularity Monitoring Method Based on Bloom Filters and Hash tables for Differentiated Traffic[J].中國通信，2016.

[8]趙艷紅，李洪奇，朱麗萍等.基于Bloom Filter的去重方法研究[J].計算技術(shù)與自動化，2016.