財神娛樂首存即享優惠回饋唷~詳情請進👉

【數據布局】布隆百家發過濾器

布隆過濾器(Bloom Filter)是由布隆(Burton Howard Bloom)在1970年提出的。
它現實上是由一個很長的二進制向量以及一系列隨機映照函數構成,布隆過濾器可以用于檢索一個元素是否在一個聚攏中。它的優點是空間效率以及查問時間都遙遙跨越一般的算法,錯誤謬誤是有肯定的誤辨認率以及刪除難題,然則沒有辨認過錯的景遇。

在一樣平常生涯中,包含在設計計算機軟件時,咱們常常要判定一個元素是否在一個聚攏中。譬如在字處置軟件中,必要反省一個英語單詞是否拼寫精確(也便是要判定 它是否在已經知的字典中);在 FBI,一個懷疑人的名字是否已經經在懷疑名單上;在收集爬蟲里,一個網址是否被走訪過等等。最間接的要領便是將聚攏中掃數的元素存在計算機中,碰到一個新元素時,將它以及聚攏中的元素間接比較即可。一般來講,計算機中的聚攏是用哈希表(hash table)來存儲的。它的利益是疾速準確,錯誤謬誤是費存儲空間。當聚攏比較小時,這個成績不顯著,然則當聚攏偉大時,哈希表存儲效率低的成績就閃現進去 了。譬今彩539開獎號碼預測如說,一個象 Yahoo,Hotmail 以及 Gmai 那樣的”大眾電子郵件(email)供應商,老是必要過濾來自發送渣滓郵件的人(spamer)的渣滓郵件。一個設施便是記載下那些發渣滓郵件的 email 地址。因為那些發送者不絕地在注冊新的地址,全世界少說也有幾十億個發渣滓郵件的地址,將他們都存起來則必要大批的收集服務器。若是用哈希表,每存儲一億 個 email 地址, 就必要 1.6GB 的內存(用哈希表完成的詳細設施是將每一個 email 地址對應成一個八字節的信息指紋(詳見:googlechinablog.com/2006/08/blog-post.html), 然后將這些信息指紋存入哈希表,因為哈希表的存儲效率一般只有 50%,是以一個 email 地址必要占用十六個字節。一億個地址約莫要 1.6GB, 即十六億字節的內存)。是以存貯幾十億個郵件地址可能必要上百 GB 的內存。除非是超等計算機,一般服務器是沒法存儲的。

根本觀點

若是想判定一個元素是否是在一個聚攏里,一般想到的是將一切元素保管起來,然后經由過程比較確定。鏈表,樹等等數據布局都是這類思緒. 然則跟著聚攏中元素的增長,咱們必要的存儲空間愈來愈大,檢索速率也愈來愈慢。無非世界上還有一種鳴作散列表(又鳴哈希表,Hash table)的數據布局。它可以經由過程一個Hash函數將一個元素映照成一個位陣列(Bit Array)中的一個點。如許一來,咱們只需望望這個點是否是 1 就曉得可以聚攏中有無它了。這便是布隆過濾器的根本思惟。

Hash面對的成績便是沖突。假定 Hash 函數是優秀的,若是咱們的位陣列長度為 m 個點,那末若是咱們想將沖突率下降到例如 1%,這個散列表就只能包容 m/100 個元素。顯然這就不鳴空間有用了(Space-efficient)。辦理要領也簡略,便是使用多個 Hash,若是它們有一個說元素不在聚攏中,那一定就不在。若是它們都說在,固然也有肯定可能性它們在撒謊,無非直覺上判定這類工作的幾率是比較低的。

優點

相比于別的的數據布局,布隆過濾器在空間以及時間方面都有偉大的上風。布隆過濾器存儲空間以及拔出/查問時間都是常數。另外,Hash 函數互相之間沒無關系,便利由硬件并行完成。布隆過濾器不必要存儲元素自身,在某些對失密要求特別很是嚴厲的場所有上風。

布隆過濾器可以透露表現選集,別的任何數據布局都不克不及;

k 以及 m 雷同,使用統一組 Hash 函數的兩個布隆過濾器的交并差運算可以使用位操作進行。

錯誤謬誤

然則布隆過偏財運生肖濾器的錯誤謬誤以及優點同樣明明。誤算率(False Positive)是個中之一。跟著存入的元素數目增長,誤算率隨之增長。然則若是元素數目太少,則使用散列表足矣。

另外,一般環境下不克不及從布隆過濾器中刪除元素. 咱們很輕易想到把位排陣釀成整數數組,每拔出一個元素響應的計數器加1,如許刪除元素時將計數器減失就可以了。然而要保障寧靜的刪除元素并非云云簡略。起首咱們必需保障刪除的元素切實其實在布隆過濾器內里. 這一點單憑這個過濾器是沒法保障的。另外計數器歸繞也會形成成績。

#pragma once 

#include"大眾bitmap.hpp"大眾 

size_t BKDRHash(const char *str)  
{  
    unsigned int seed = 131; // 31 131 1313 13131 131313 
    unsigned int hash = 0;  
    while (*str)  
    {  
        hash = hash * seed + (*str++);  
    }  

    return (hash & 0x7FFFFFFF);  
 }  

size_t SDBMHash(const char *str)  
{  
    register size_t hash = 0;  
    while (size_t ch = (size_t)*str++)  
    {  
        hash = 65599 * hash + ch;  
        //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash; 
    }  
        return hash;  
}  

si六合彩二星三星ze_t RSHash(const char *str)  
{  
    register size_t hash = 0;  
    size_t magic = 63689;  
    while (size_t ch = (size_t)*str++)  
    {  
        hash = hash * magic + ch;  
        magic *= 378551;  
    }  
    return hash;  
}  

size_t APHash(const char *str)  
{  
    register size_t hash = 0;  
    size_t ch;  
    for (long i = 0; ch = (size_t)*str++; i++)  
    {  
        if ((i & 1) == 0)  
        {  
            hash ^= ((hash << 7) ^ ch ^ (hash >> 3));  
        }  
        else  
        {  
            hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));  
        }  
    }  
    return hash;  
}  

size_t JSHash(const char *str)  
{  
    if (!*str)  
        return 0;  

    register size_t hash = 1315423911;  
    while (size_t ch = (size_t)*str++)  
    {  
        hash ^= ((hash << 5) + ch + (hash >> 2));  
    }  
    return hash;  
}  

template<class K>  
struct __HashFunc1  
{  
    size_t ope539必中法rator()(const K& key)  
    {  
        return BKDRHash(key.c_str());  
    }  
};  

template<class K>  
struct __HashFunc2  
{  
    size_t operator()(const K& key)  
    {  
        return SDBMHash(key.c_str());  
    }  
};  

template<class K>  
struct __HashFunc3  
{  
    size_t operator()(const K& key)  
    {  
        return RSHash(key.c_str());  
    }  
};  

template<class K>  
struct __HashFunc4  
{  
    size_t operator()(const K& key)  
    {  
        return APHash(key.c_str());  
    }  
};  

template<class K>  
struct __HashFunc5  
{  
    size_t operator()(const K& key)  
    {  
        return JSHash(key.c_str());  
    }  
};  

template<class K = string,class HashFunc1 = __HashFunc1<K>,class HashFunc2 = __HashFunc2<K>,class HashFunc3 = __HashFunc3<K>,class HashFunc4 = __HashFunc4<K>,class HashFunc5 = __HashFunc5<K>>  
class BloomFilter  
{  
妞妞鐵支public:  
    BloomFilter(size_t size) 
        : _capacity(_GetNextPrime(size)),_bitmap(_capacity)
    {}  

    void Set(const K& key)  
    {  
        size_t index1 = HashFunc1()(key);  
        size_t index2 = HashFunc2()(key);  
        size_t index3 = HashFunc3()(key);  
        size_t index4 = HashFunc4()(key);  
        size_t index5 = HashFunc5()(key);  

        _bitmap.Set(index1%_capacity);  
        _bitmap.Set(index2%_capacity);  
        _bitmap.Set(index3%_capacity);  
        _bitmap.Set(index4%_capacity);  
        _bitmap.Set(index5%_capacity);  
    }  

    bool IsIn(const K& key)  
    {  
        size_t index1 = HashFunc1()(key);  
        if (!_bitmap.Test(index1%_capacity))  
        {  
            return false;  
        }  
        size_t index2 = HashFunc2()(key);  
        if (!_bitmap.Test(index2%_capacity))  
        {  
            return false;  
        }  
        size_t index3 = HashFunc3()(key);  
        if (!_bitmap.Test(index3%_capacity))  
        {  
            return false;  
        }  
        size_t index4 = HashFunc4()(key);  
        if (!_bitmap.Test(index4%_capacity))  
        {  
            return false;  
        }  
        size_t index5 = HashFunc5()(key);  
        if (!_bitmap.Test(index5%_capacity))  
        {  
            return false;  
        }  

        return true;  
    }  

protected:  

    unsigned long _GetNextPrime(unsigned long num)  
    {  
        const int _PrimeSize = 28;  
        static const unsigned long _PrimeList[_PrimeSize] =  
        {  
            53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,196613ul,393241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,4294967291ul  
        };  
        size_t pos = 0;  
        while (pos < _PrimeSize)  
        {  
            if (_PrimeList[pos] > num)  
            {  
                break;  
            }  
            ++pos;  
        }  
        return _PrimeList[pos];  
    }  

private:  

    size_t _capacity;  
    Bitmap _bitmap;
};  

void Test()  
{  
    BloomFilter<> b1(30);  
    b1.Set(公眾www.baidu.com公眾);  
    b1.Set(公眾www.sina.con"大眾);  
    b1.Set(公眾www.taobao.com"大眾);  

    cout << b1.IsIn("大眾www.baidu.com"大眾) << endl;  
    cout << b1.IsIn("大眾dnsjdasjkdsjakdjas"大眾) << endl;  
}

【免責聲明】本站內容轉載自互聯網,其相關談吐僅代表作者小我私家概念盡非權勢巨子,不代表本站態度。如您發明內容存在版權成績,請提交相關鏈接至郵箱:,咱們將實時予以處置。