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

◆舒遠仲 梁 濤 王 娟

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

◆舒遠仲 梁 濤 王 娟

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

本文在分析了Bloom Filter缺點的基礎上，結合天貓購物平臺網頁URL的特征，對網頁URL去重策略進行了改進，以此來提高網頁URL去重效果及減小Bloom Filter誤判率。實驗結果表明，改進后的去重策略在針對天貓購物平臺網頁URL去重時，準確度上要優于傳統的Bloom Filter。

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

0 引言

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

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

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

1 天貓網購平臺網頁URL分析

天貓采用是動態URL，即同一商品對應的網頁可能存在多個URL。通過對這些URL的分析，找出它們之間的聯系，從而可以簡化URL去重。如表1，選取多個URL實例來分析其特點。

表1 天貓網購平臺網頁URL實例

從表1中可以得出，同一店鋪同一產品可能對應多個URL；不同店鋪同一產品對應URL不同；同一店鋪不同產品對應的URL也不一樣。但對各個URL具體分析后，可以發現：每個URL中都含有參數id，對于同一店鋪同一產品，盡管對應多個URL，但參數id的值是一致的；不同店鋪同一產品URL中的參數id的值不一樣；同一店鋪不同產品URL中的參數id的值不一樣。

2 布隆過濾器

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

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

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

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

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

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

（3） 選取k個相互獨立的哈希函數h1，h2，h3，……，hk;

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

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

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

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

2.2布隆過濾器的缺點及誤判率

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

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

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

則誤判的概率為

（2）Bloom Filter無法從Bloom Filter集合中刪除一個元素。因為一個元素對應的位可能與另一個元素對應的位存在共同位。如圖3所示。

圖3 存在共同位的元素

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

圖4 Counter Bloom Filter

3 網頁URL去重

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

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

（2）提取參數id并對其進行多個哈希處理；

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

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

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

圖5 改進后的URL去重策略

4 實驗分析

由于進行的是仿真實驗，通過采集天貓網頁URL，將URL緩存于內存空間，分別使用傳統Bloom Filter與改進后的Bloom Filter對URL進行去重，比較兩者對于比較時間、準確度上的區別。結果如圖6、圖7所示。

圖6 傳統與改進后Bloom Filter去重的時間對比

圖7 傳統與改進后Bloom Filter去重的準確度對比

通過實驗結果可以看出，在準確度上，改進后的Bloom Filter要優于傳統Bloom Filter，在時間上，略慢于傳統Bloom Filter。

5 結束語

本文研究了Bloom Filter的基本工作原理，并對其在網頁URL去重中的應用進行改進，結果表明改進后的策略去重準確率提高。同時，改進后的策略在去重速度上仍有改進的空間。

[1]星圖數據.星圖數據1112：雙十一網購大數據分析報告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]黃正德.主題爬蟲關鍵技術研究[D].黑龍江：哈爾濱工程大學，2013.

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

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

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

[6]張宗華，屈英，葉志佳等.基于多特征匹配和Bloom filter的重復數據刪除算法[J].深圳大學學報(理工版)，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].計算技術與自動化，2016.