大数据量的过滤 (用于爬虫,蜘蛛) Bloom Filter 布隆过滤器

大数据量的过滤 (用于爬虫,蜘蛛) Bloom Filter 布隆过滤器

原文:Bloom Filters in C#
http://www.devsource.com/article2/0,1895,2113495,00.asp


想像一下.如果你有一个非常大的无序的数据(url连接) 并且你要保证同样的一条连接不会在其它地方再次出现
你实时的收集哪些数据,你没有办法来预防两个相同的url出现,再不断增加的数据当中.

当这些数据是少的时候你可以轻松的创建一个list(dictonary or hashtable 或者你自已的数据结构)然后遍历它们,看它是不是已经存在在这个list当中,
遍历所花的时间是非常多的,
但是 当这些数据的长度超过可用的内存的时候? hashtable可以帮我加快速度,但是存...

上面的比较多的费话..看起来累 呦口继续不下去了.

得出的方案是用 bit数组来节省空间
a hash table capable of holding M items will take m/8 bytes of memory
接下来是实际的解决方法
net 里面有一个类 BitArray它可以帮我们很容易的创建出一个hashtabel

创建一个简单的 HashingTable

public class SimpleHashTable
    {
        private BitArray hashbits = null;

        public SimpleHashTable(int tableSize)
        {
            hashbits = new BitArray(tableSize, false);
        }

        public bool Test(string str)
        {
            int hash = Math.Abs(str.GetHashCode()) % hashbits.Count;
            return hashbits[hash];
        }

        public bool Add(string str)
        {
            int hash = Math.Abs(str.GetHashCode()) % hashbits.Count;
            bool rslt = hashbits[hash];
            if (!rslt)
                hashbits[hash] = true;
            return rslt;
        }
    }

Add 里面没有这个值的时候是返回 false ,
Test 里面有值的话是返回 true;

 class Program
    {
        static void Main(string[] args)
        {
            int urlsRead = 0;
            int collisions = 0;

            SimpleHashTable hashTable = new SimpleHashTable(1000000);
            using (StreamReader sr = new StreamReader("urls.txt"))
            {
                string url;
                while ((url = sr.ReadLine()) != null)
                {
                    urlsRead++;
                    bool rslt = hashTable.Add(url);
                    if (rslt)
                        collisions++;
                    if ((urlsRead % 10000) == 0)
                    {
                        Console.WriteLine("{0}  {1}  {2}%", 
                            urlsRead, collisions, 100*
                                (double)collisions / urlsRead);
                    }
                }
            }
            Console.WriteLine("{0} urls read", urlsRead);
            Console.WriteLine("{0} collisions", collisions);
            Console.WriteLine("False positive rate = {0}%", 
                100*(double)collisions / urlsRead);
        }
    }

The output from that program, run against the 100,000 unique URLs in my file, is:

10000  44  0.44%
20000  187  0.935%
30000  423  1.41%
40000  753  1.8825%
50000  1200  2.4%
60000  1753  2.92166666666667%
70000  2375  3.39285714285714%
80000  3123  3.90375%
90000  3946  4.38444444444444%
100000  4834  4.834%
100000 urls read
4834 collisions
False positive rate = 4.834%

然后写了一个简单的测试类,我们可以看到它的碰撞(冲突)还是比较明显的

接下来就是如何继续去解决这样的问题
创建一个新的 Hash算法函数 HashString
hi(x) = (f1(x) + if2(x)) mod m

然后提供了一个 防止碰撞的结构. hashkeys 保存这个hash的三个位置

 public class BloomFilter
    {
        private BitArray hashbits;
        private int numKeys;
        private int[] hashKeys;

        public BloomFilter(int tableSize, int nKeys)
        {
            numKeys = nKeys;
            hashKeys = new int[numKeys];
            hashbits = new BitArray(tableSize);
        }

        private int HashString(string s)
        {
            int hash = 0;

            for (int i = 0; i < s.Length; i++)
            {
                hash += s[i];
                hash += (hash << 10);
                hash ^= (hash >> 6);
            }
            hash += (hash << 3);
            hash ^= (hash >> 11);
            hash += (hash << 15);
            return hash;
        }

        private void CreateHashes(string str)
        {
            int hash1 = str.GetHashCode();
            int hash2 = HashString(str);

            hashKeys[0] = Math.Abs(hash1 % hashbits.Count);
            if (numKeys > 1)
            {
                for (int i = 1; i < numKeys; i++)
                {
                    hashKeys[i] = Math.Abs((hash1 + (i * hash2))
                        % hashbits.Count);
                }
            }
        }

        public bool Test(string str)
        {
            CreateHashes(str);
            // Test each hash key.  Return false if any 
            //  one of the bits is not set.
            foreach (int hash in hashKeys)
            {
                if (!hashbits[hash])
                    return false;
            }
            // All bits set.  The item is there.
            return true;
        }

        public bool Add(string str)
        {
            // Initially assume that the item is in the table
            bool rslt = true;
            CreateHashes(str);
            foreach (int hash in hashKeys)
            {
                if (!hashbits[hash])
                {
                    // One of the bits wasn't set, so show that
                    // the item wasn't in the table, and set that bit.
                    rslt = false;
                    hashbits[hash] = true;
                }
            }
            return rslt;
        }
    }

测试: