Changeset 315

Show
Ignore:
Timestamp:
02/27/08 03:44:38 (9 months ago)
Author:
jake
Message:

abstracted bloom_filter

Location:
trunk/thrucommon/src
Files:
2 modified

Legend:

Unmodified
Added
Removed

  • trunk/thrucommon/src/bloom_filter.hpp

    r257 r315  
    2828 
    2929 
    30 const std::size_t bits_per_char   = 0x08;    // 8 bits in 1 char(unsigned) 
    31 const unsigned char bit_mask[bits_per_char] = { 
    32                                                 0x01,  //00000001 
    33                                                 0x02,  //00000010 
    34                                                 0x04,  //00000100 
    35                                                 0x08,  //00001000 
    36                                                 0x10,  //00010000 
    37                                                 0x20,  //00100000 
    38                                                 0x40,  //01000000 
    39                                                 0x80   //10000000 
    40                                               }; 
     30//used by default bloom impl only 
     31const unsigned char bit_mask[8] = { 
     32    0x01,  //00000001 
     33    0x02,  //00000010 
     34    0x04,  //00000100 
     35    0x08,  //00001000 
     36    0x10,  //00010000 
     37    0x20,  //00100000 
     38    0x40,  //01000000 
     39    0x80   //10000000 
     40}; 
    4141 
    4242 
    … …  
    4949   bloom_filter(const std::size_t& element_count, 
    5050                const double& false_positive_probability, 
    51                 const std::size_t& random_seed) 
     51                const std::size_t& random_seed, 
     52                std::size_t bits_per_char = 0x08 )    // 8 bits in 1 char(unsigned)) 
    5253   : hash_table_(0), 
    5354     element_count_(element_count), 
    5455     random_seed_(random_seed), 
    55      false_positive_probability_(false_positive_probability) 
     56     false_positive_probability_(false_positive_probability), 
     57     bits_per_char(bits_per_char) 
    5658   { 
    5759      find_optimal_parameters(); 
    … …  
    8486   } 
    8587 
    86   ~bloom_filter() 
     88   virtual ~bloom_filter() 
    8789   { 
    8890      delete[] hash_table_; 
    8991   } 
    9092 
    91    void insert(const std::string key) 
     93   virtual void insert(const std::string key) 
    9294   { 
    9395      for(std::vector<bloom_type>::iterator it = salt_.begin(); it != salt_.end(); ++it) 
    … …  
    98100   } 
    99101 
    100    bool contains(const std::string key) const 
     102   virtual bool contains(const std::string key) const 
    101103   { 
    102104      for(std::vector<bloom_type>::const_iterator it = salt_.begin(); it != salt_.end(); ++it) 
    … …  
    165167   } 
    166168 
    167 private: 
     169protected: 
    168170 
    169171   void generate_unique_salt() 
    … …  
    245247   std::size_t             random_seed_; 
    246248   double                  false_positive_probability_; 
     249   std::size_t             bits_per_char; 
    247250}; 
    248251 

  • trunk/thrucommon/src/counting_bloom_filter.hpp

    r314 r315  
    2727#include <limits> 
    2828 
     29#include "bloom_filter.hpp" 
    2930 
    30 class counting_bloom_filter 
     31class counting_bloom_filter : public bloom_filter 
    3132{ 
    3233public: 
    33  
    34    typedef unsigned int bloom_type; 
    3534 
    3635   counting_bloom_filter(const std::size_t& element_count, 
    3736                const double& false_positive_probability, 
    3837                const std::size_t& random_seed) 
    39    : hash_table_(0), 
    40      element_count_(element_count), 
    41      random_seed_(random_seed), 
    42      false_positive_probability_(false_positive_probability) 
    43    { 
    44       find_optimal_parameters(); 
    45       hash_table_ = new unsigned char[table_size_]; 
    46       generate_unique_salt(); 
    47       for (std::size_t i = 0; i < (table_size_); i++) 
    48       { 
    49          hash_table_[i] = static_cast<unsigned char>(0x0); 
    50       } 
    51    } 
    52  
    53    counting_bloom_filter(const counting_bloom_filter& filter) 
    54    { 
    55       this->operator =(filter); 
    56    } 
    57  
    58    counting_bloom_filter& operator = (const counting_bloom_filter& filter) 
    59    { 
    60       salt_count_          = filter.salt_count_; 
    61       table_size_          = filter.table_size_; 
    62       element_count_       = filter.element_count_; 
    63       random_seed_         = filter.random_seed_; 
    64       false_positive_probability_ = filter.false_positive_probability_; 
    65       delete[] hash_table_; 
    66       hash_table_ = new unsigned char[table_size_]; 
    67       std::copy(filter.hash_table_,filter.hash_table_ + (table_size_),hash_table_); 
    68       salt_.clear(); 
    69       std::copy(filter.salt_.begin(),filter.salt_.end(),std::back_inserter(salt_)); 
    70       return *this; 
    71    } 
    72  
    73   ~counting_bloom_filter() 
    74    { 
    75       delete[] hash_table_; 
    76    } 
     38       : bloom_filter(element_count,false_positive_probability,random_seed,0x01) 
     39   { } 
    7740 
    7841   void insert(const std::string key) 
    … …  
    11275   } 
    11376 
    114    std::size_t size() { return table_size_; } 
    115  
    116    counting_bloom_filter& operator&=(const counting_bloom_filter& filter) 
    117    { 
    118       /* intersection */ 
    119       if ( 
    120           (salt_count_  == filter.salt_count_) && 
    121           (table_size_  == filter.table_size_) && 
    122           (random_seed_ == filter.random_seed_) 
    123          ) 
    124       { 
    125          for (std::size_t i = 0; i < (table_size_); ++i) 
    126          { 
    127             hash_table_[i] &= filter.hash_table_[i]; 
    128          } 
    129       } 
    130       return *this; 
    131    } 
    132  
    133    counting_bloom_filter& operator|=(const counting_bloom_filter& filter) 
    134    { 
    135       /* union */ 
    136       if ( 
    137           (salt_count_  == filter.salt_count_) && 
    138           (table_size_  == filter.table_size_) && 
    139           (random_seed_ == filter.random_seed_) 
    140          ) 
    141       { 
    142          for (std::size_t i = 0; i < (table_size_); ++i) 
    143          { 
    144             hash_table_[i] |= filter.hash_table_[i]; 
    145          } 
    146       } 
    147       return *this; 
    148    } 
    149  
    150    counting_bloom_filter& operator^=(const counting_bloom_filter& filter) 
    151    { 
    152       /* difference */ 
    153       if ( 
    154           (salt_count_  == filter.salt_count_) && 
    155           (table_size_  == filter.table_size_) && 
    156           (random_seed_ == filter.random_seed_) 
    157          ) 
    158       { 
    159          for (std::size_t i = 0; i < (table_size_); ++i) 
    160          { 
    161             hash_table_[i] ^= filter.hash_table_[i]; 
    162          } 
    163       } 
    164       return *this; 
    165    } 
    166  
    167 private: 
    168  
    169    void generate_unique_salt() 
    170    { 
    171       const unsigned int predef_salt_count = 32; 
    172       const bloom_type predef_salt[predef_salt_count] = 
    173                        { 
    174                          0xAAAAAAAA, 0x55555555, 0x33333333, 0xCCCCCCCC, 
    175                          0x66666666, 0x99999999, 0xB5B5B5B5, 0x4B4B4B4B, 
    176                          0xAA55AA55, 0x55335533, 0x33CC33CC, 0xCC66CC66, 
    177                          0x66996699, 0x99B599B5, 0xB54BB54B, 0x4BAA4BAA, 
    178                          0xAA33AA33, 0x55CC55CC, 0x33663366, 0xCC99CC99, 
    179                          0x66B566B5, 0x994B994B, 0xB5AAB5AA, 0xAAAAAA33, 
    180                          0x555555CC, 0x33333366, 0xCCCCCC99, 0x666666B5, 
    181                          0x9999994B, 0xB5B5B5AA, 0xFFFFFFFF, 0xFFFF0000 
    182                        }; 
    183       if (salt_count_ <= predef_salt_count) 
    184       { 
    185          std::copy(predef_salt,predef_salt + salt_count_,std::back_inserter(salt_)); 
    186       } 
    187       else 
    188       { 
    189          std::copy(predef_salt,predef_salt + predef_salt_count,std::back_inserter(salt_)); 
    190          srand(static_cast<unsigned int>(0xAAAAAAAA ^ random_seed_)); 
    191          while(salt_.size() < salt_count_) 
    192          { 
    193             bloom_type current_salt = static_cast<bloom_type>(rand()) ^ static_cast<bloom_type>(rand()); 
    194             if (current_salt == 0) continue; 
    195             bool duplicate_found = false; 
    196             for(std::vector<bloom_type>::iterator it = salt_.begin(); it != salt_.end(); ++it) 
    197             { 
    198                if (current_salt == (*it)) 
    199                { 
    200                   duplicate_found = true; 
    201                   break; 
    202                } 
    203             } 
    204             if (!duplicate_found) 
    205             { 
    206                salt_.push_back(current_salt); 
    207             } 
    208          } 
    209       } 
    210    } 
    211  
    212    void find_optimal_parameters() 
    213    { 
    214       double min_m  = std::numeric_limits<double>::infinity(); 
    215       double min_k  = 0.0; 
    216       double curr_m = 0.0; 
    217       for(double k = 0; k < 1000.0; k++) 
    218       { 
    219          if ((curr_m = ((- k * element_count_) / std::log(1 - std::pow(false_positive_probability_,1 / k)))) < min_m) 
    220          { 
    221             min_m = curr_m; 
    222             min_k = k; 
    223          } 
    224       } 
    225       salt_count_  = static_cast<std::size_t>(min_k); 
    226       table_size_  = static_cast<std::size_t>(min_m); 
    227    } 
    228  
    229    bloom_type hash_ap(const std::string& str,bloom_type hash) const 
    230    { 
    231       for(std::size_t i = 0; i < str.length(); i++) 
    232       { 
    233          hash ^= ((i & 1) == 0) ? (  (hash <<  7) ^ str[i] ^ (hash >> 3)) : 
    234                                   (~((hash << 11) ^ str[i] ^ (hash >> 5))); 
    235       } 
    236       return hash; 
    237    } 
    238  
    239    std::vector<bloom_type> salt_; 
    240    unsigned char*          hash_table_; 
    241    std::size_t             salt_count_; 
    242    std::size_t             table_size_; 
    243    std::size_t             element_count_; 
    244    std::size_t             random_seed_; 
    245    double                  false_positive_probability_; 
    24677}; 
    247  
    248  
    249 counting_bloom_filter operator & (const counting_bloom_filter& a, const counting_bloom_filter& b) 
    250 { 
    251    counting_bloom_filter result = a; 
    252    result &= b; 
    253    return result; 
    254 } 
    255  
    256 counting_bloom_filter operator | (const counting_bloom_filter& a, const counting_bloom_filter& b) 
    257 { 
    258    counting_bloom_filter result = a; 
    259    result |= b; 
    260    return result; 
    261 } 
    262  
    263 counting_bloom_filter operator ^ (const counting_bloom_filter& a, const counting_bloom_filter& b) 
    264 { 
    265    counting_bloom_filter result = a; 
    266    result ^= b; 
    267    return result; 
    268 } 
    269  
    27078 
    27179#endif 
    27280 
    27381 
    274  
    275 /* 
    276    Note: 
    277    If it can be guaranteed that bits_per_char will be of the form 2^n then 
    278    the following optimization can be used: 
    279  
    280    hash_table[bit_index >> n] |= bit_mask[bit_index & (bits_per_char - 1)]; 
    281  
    282 */