[爬蟲學習筆記]基於 SimHash 的去重覆處理模塊ContentSeen的構建

Internet上的一些站點常常存在著鏡像網站（mirror），即兩個網站的內容一樣但網頁對應的功能變數名稱不同。這樣會導致對同一份網頁爬蟲重覆抓取多次。為了避免這種情況，對於每一份抓取到的網頁，它首先需要進入ContentSeen模塊。該模塊會判斷網頁的內容是否和已下載過的某個網頁的內容一致，如果一致，則... ...

Internet上的一些站點常常存在著鏡像網站（mirror），即兩個網站的內容一樣但網頁對應的功能變數名稱不同。這樣會導致對同一份網頁爬蟲重覆抓取多次。為了避免這種情況，對於每一份抓取到的網頁，它首先需要進入ContentSeen模塊。該模塊會判斷網頁的內容是否和已下載過的某個網頁的內容一致，如果一致，則該網頁不會再被送去進行下一步的處理。這樣的做法能夠顯著的降低爬蟲需要下載的網頁數。至於如果判斷兩個網頁的內容是否一致，一般的思路是這樣的：並不會去直接比較兩個網頁的內容，而是將網頁的內容經過計算生成FingerPrint（指紋），通常FingerPrint是一個固定長度的字元串，要比網頁的正文短很多。如果兩個網頁的FingerPrint一樣，則認為它們內容完全相同。

為了完成這一模塊，首先我們需要一個強大的指紋演算法，將我們的網頁內容計算成指紋存入資料庫，下次直接判斷指紋在保存前通過指紋的對比即可成功完成去重覆操作。

      首先來看一下大名鼎鼎的Google公司使用的網頁去重覆演算法SimHash吧：

      GoogleMoses Charikar發表的一篇論文“detecting near-duplicates for web crawling”中提出了simhash演算法，專門用來解決億萬級別的網頁的去重任務。

      SimHash作為locality sensitive hash（局部敏感哈希）的一種：

      其主要思想是降維，將高維的特征向量映射成低維的特征向量，通過兩個向量的Hamming Distance來確定文章是否重覆或者高度近似。

      其中，Hamming Distance，又稱漢明距離，在資訊理論中，兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數。也就是說，它就是將一個字元串變換成另外一個字元串所需要替換的字元個數。例如：1011101 與 1001001 之間的漢明距離是 2。至於我們常說的字元串編輯距離則是一般形式的漢明距離。

      如此，通過比較多個文檔的SimHash值的海明距離，可以獲取它們的相似度。

      詳情可以看這裡SimHash演算法

_______________________________________________________________________________________________

下麵我們來進行代碼實現:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Crawler.Common
{
    public class SimHashAnalyser
    {

        private const int HashSize = 32;

        public static float GetLikenessValue(string needle, string haystack, TokeniserType type = TokeniserType.Overlapping)
        {
            var needleSimHash = GetSimHash(needle, type);
            var hayStackSimHash = GetSimHash(haystack, type);
            return GetLikenessValue(needleSimHash, hayStackSimHash);
        }

        public static float GetLikenessValue(int needleSimHash, int hayStackSimHash)
        {
            return (HashSize - GetHammingDistance(needleSimHash, hayStackSimHash)) / (float)HashSize;
        }

        private static IEnumerable<int> DoHashTokens(IEnumerable<string> tokens)
        {
            return tokens.Select(token => token.GetHashCode()).ToList();
        }

        private static int GetHammingDistance(int firstValue, int secondValue)
        {
            var hammingBits = firstValue ^ secondValue;
            var hammingValue = 0;
            for (var i = 0; i < 32; i++)
                if (IsBitSet(hammingBits, i))
                    hammingValue += 1;
            return hammingValue;
        }

        private static bool IsBitSet(int b, int pos)
        {
            return (b & (1 << pos)) != 0;
        }


        public static int GetSimHash(string input)
        {
            return GetSimHash(input, TokeniserType.Overlapping);
        }

        public static int GetSimHash(string input, TokeniserType tokeniserType)
        {
            ITokeniser tokeniser;
            if (tokeniserType == TokeniserType.Overlapping)
                tokeniser = new OverlappingStringTokeniser();
            else
                tokeniser = new FixedSizeStringTokeniser();

            var hashedtokens = DoHashTokens(tokeniser.Tokenise(input));
            var vector = new int[HashSize];
            for (var i = 0; i < HashSize; i++)
                vector[i] = 0;

            foreach (var value in hashedtokens)
                for (var j = 0; j < HashSize; j++)
                    if (IsBitSet(value, j))
                        vector[j] += 1;
                    else
                        vector[j] -= 1;
            var fingerprint = 0;
            for (var i = 0; i < HashSize; i++)
                if (vector[i] > 0)
                    fingerprint += 1 << i;
            return fingerprint;
        }

    }

    public interface ITokeniser
    {
        IEnumerable<string> Tokenise(string input);
    }

    public class FixedSizeStringTokeniser : ITokeniser
    {
        private readonly ushort _tokensize;
        public FixedSizeStringTokeniser(ushort tokenSize = 5)
        {
            if (tokenSize < 2)
                throw new ArgumentException("Token 不能超出範圍");
            if (tokenSize > 127)
                throw new ArgumentException("Token 不能超出範圍");
            _tokensize = tokenSize;
        }

        public IEnumerable<string> Tokenise(string input)
        {
            var chunks = new List<string>();
            var offset = 0;
            while (offset < input.Length)
            {
                chunks.Add(new string(input.Skip(offset).Take(_tokensize).ToArray()));
                offset += _tokensize;
            }
            return chunks;
        }

    }

    public class OverlappingStringTokeniser : ITokeniser
    {

        private readonly ushort _chunkSize;
        private readonly ushort _overlapSize;

        public OverlappingStringTokeniser(ushort chunkSize = 4, ushort overlapSize = 3)
        {
            if (chunkSize <= overlapSize)
                throw new ArgumentException("Chunck 必須大於 overlap");
            _overlapSize = overlapSize;
            _chunkSize = chunkSize;
        }

        public IEnumerable<string> Tokenise(string input)
        {
            var result = new List<string>();
            var position = 0;
            while (position < input.Length - _chunkSize)
            {
                result.Add(input.Substring(position, _chunkSize));
                position += _chunkSize - _overlapSize;
            }
            return result;
        }


    }

    public enum TokeniserType
    {
        Overlapping,
        FixedSize
    }
}

調用方法如下:

var s1 = "the cat sat on the mat.";
var s2 = "the cat sat on a mat.";

var similarity = SimHashAnalyser.GetLikenessValue(s1, s2);

Console.Clear();
Console.WriteLine("相似度: {0}%", similarity * 100);
Console.ReadKey();

輸出為:

相似度: 78.125%

接下來就是對ContentSeen模塊的簡單封裝:

using Crawler.Common;

namespace Crawler.Processing
{
    /// <summary>
    /// 對於每一份抓取到的網頁，它首先需要進入Content Seen模塊。該模塊會判斷網頁的內容是否和已下載過的某個網頁的內容一致，如果一致，則該網頁不會再被送去進行下一步的處理。
    /// </summary>
    public class ContentSeen
    {
        public static int GetFingerPrint(string html)
        {
            return SimHashAnalyser.GetSimHash(html);
        }

        public static float Similarity(int print1, int print2)
        {
            return SimHashAnalyser.GetLikenessValue(print1, print2);
        }

    }
}