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

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

   
      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);
        }

    }
}