///|
pub type BitVector = @bitvec.BitVector
///|
priv suberror BloomError {
BloomError(String)
}
///|
/// A BloomFilter is a representation of a set of _n_ items, where the main
/// requirement is to make membership queries; _i.e._, whether an item is a
/// member of a set.
pub struct BloomFilter {
m : Int32
k : Int32
b : BitVector
}
///|
/// New creates a new BloomFilter with m bits and k hashing functions.
/// We force m and k to be at least one to avoid panics.
pub fn BloomFilter::new(m : Int32, k : Int32) -> BloomFilter {
{ m: m.max(1), k: k.max(1), b: BitVector::new(m), }
}
///|
/// From creates a new Bloom filter with data.length() * 64 bits and k hashing
/// functions. The data slice is not going to be reset.
pub fn BloomFilter::from(data : Array[UInt64], k : Int32) -> BloomFilter {
{ m: data.length() * 64, k, b: BitVector::from(data), }
}
///|
/// from_with_m creates a new Bloom filter with m length, k hashing functions.
/// The data slice is not going to be reset.
pub fn BloomFilter::from_with_m(
data : Array[UInt64],
m : Int32,
k : Int32,
) -> BloomFilter {
{ m, k, b: BitVector::from(data), }
}
///|
/// Return the four hash values of data that are used to create k hashes
pub fn base_hashes(data : Bytes) -> (UInt64, UInt64, UInt64, UInt64) {
let d = Digest128::new()
// murmur hashing
d.sum256(data)
}
///|
/// Return the ith hashed location using the four base hash values
fn location(h : (UInt64, UInt64, UInt64, UInt64), i : Int32) -> UInt64 {
let hash256 = [h.0, h.1, h.2, h.3]
hash256[i % 2] + i.to_uint64() * hash256[2 + (i + i % 2) % 4 / 2]
}
///|
/// Return the ith hashed location using the four base hash values
pub fn BloomFilter::location(
self : BloomFilter,
hash256 : (UInt64, UInt64, UInt64, UInt64),
i : Int32,
) -> Int32 {
(location(hash256, i) % self.m.to_uint64()).to_int()
}
///|
/// Estimate requirements for m and k.
pub fn estimate_parameters(n : Int32, fp : Double) -> (Int32, Int32) {
let m = @math.ceil(
-1 * n.to_double() * @math.ln(fp) / @math.pow(@math.ln(2), 2),
)
let k = @math.ceil(@math.ln(2) * m / n.to_double())
(m.to_int(), k.to_int())
}
///|
/// Create a new Bloom filter for n items with fp
/// false positive rate
pub fn new_with_estimates(n : Int32, fp : Double) -> BloomFilter {
let (m, k) = estimate_parameters(n, fp)
BloomFilter::new(m, k)
}
///|
/// Returns the capacity, m, of a BloomFilter
pub fn BloomFilter::get_cap(self : BloomFilter) -> Int32 {
self.m
}
///|
/// Returns the number of hash functions used in the BloomFilter
pub fn BloomFilter::get_k(self : BloomFilter) -> Int32 {
self.k
}
///|
/// Return the underlying bitset for this BloomFilter
pub fn BloomFilter::get_bitvec(self : BloomFilter) -> BitVector {
self.b
}
///|
/// Add data to the Bloom Filter. Returns the filter (allows chaining)
pub fn BloomFilter::add(self : BloomFilter, data : Bytes) -> BloomFilter {
let hash256 = base_hashes(data)
for i in 0.. BloomFilter {
self.add(@utf8.encode(data))
}
///|
/// Merge the data from two Bloom Filters.
pub fn BloomFilter::merge(
self : BloomFilter,
other : BloomFilter,
) -> BloomFilter raise {
// Make sure the m's and k's are the same, otherwise merging has no real use.
if self.m != other.m {
raise BloomError("m's don't match")
}
if self.k != other.k {
raise BloomError("k's don't match")
}
{ ..self, b: self.b.inplace_union(other.b), }
}
///|
/// Copy creates a copy of a Bloom filter.
pub fn BloomFilter::copy(self : BloomFilter) -> BloomFilter raise {
let new_bloom = BloomFilter::new(self.m, self.k)
new_bloom.merge(self)
}
///|
/// Return true if the data is in the BloomFilter, false otherwise.
/// If true, the result might be a false positive. If false, the data
/// is definitely not in the set.
pub fn BloomFilter::check(self : BloomFilter, data : Bytes) -> Bool {
let hash256 = base_hashes(data)
for i in 0.. Bool {
self.check(@utf8.encode(data))
}
///|
/// check_locations returns true if all locations are set in the BloomFilter, false
/// otherwise.
pub fn BloomFilter::check_locations(
self : BloomFilter,
locs : Array[Int32],
) -> Bool {
for i in 0.. Bool {
let mut present = true
let hash256 = base_hashes(data)
for i in 0.. Bool {
self.check_and_add(@utf8.encode(data))
}
///|
/// If the element is already in the filter, then the filter is unchanged.
pub fn BloomFilter::check_or_add(self : BloomFilter, data : Bytes) -> Bool {
let mut present = true
let hash256 = base_hashes(data)
for i in 0.. Bool {
self.check_or_add(@utf8.encode(data))
}
///|
/// Clears all the data in a Bloom filter, removing all keys
pub fn BloomFilter::clear_all(self : BloomFilter) -> BloomFilter {
self.b.clear_all()
self
}
///|
/// estimate_false_positive_rate returns, for a BloomFilter of m bits
/// and k hash functions, an estimation of the false positive rate when
/// storing n entries. This is an empirical, relatively slow test using
/// integers as keys: each key is hashed as its 4-byte little-endian
/// encoding. This function is useful to validate the implementation.
pub fn estimate_false_positive_rate(m : Int32, k : Int32, n : Int32) -> Double {
let rounds = 100000
let bloom = BloomFilter::new(m, k)
for i in 0.. Int32 {
let x = self.b.count_ones().to_double()
let m = self.get_cap().to_double()
let k = self.get_k().to_double()
let size : Double = -1 * m / k * @math.ln(1 - x / m)
(size + 0.5).floor().to_int()
}
///|
/// Serialize from BloomFilter to Bytes
pub fn BloomFilter::marshal_bytes(self : BloomFilter) -> Bytes {
let buf = Buffer()
buf.write_int_le(self.m)
buf.write_int_le(self.k)
buf.write_bytes(self.b.marshal_bytes())
buf.to_bytes()
}
///|
/// Serialize from Bytes to BloomFilter
pub fn BloomFilter::unmarshal_bytes(bytes : Bytes) -> BloomFilter {
let m = read_int_le(bytes[0:4])
let k = read_int_le(bytes[4:8])
let bitvec = BitVector::unmarshal_bytes(bytes[8:].to_owned())
{ m, k, b: bitvec, }
}
///|
/// Equal tests for the equality of two Bloom filters
pub fn BloomFilter::equal(self : BloomFilter, other : BloomFilter) -> Bool {
self.m == other.m && self.k == other.k && self.b.equal(other.b)
}
///|
/// locations returns a list of hash locations representing a data item.
pub fn locations(data : Bytes, k : Int32) -> Array[UInt64] {
let locs = Array::make(k, 0UL)
// calculate locations
let hash256 = base_hashes(data)
for i in 0.. Int32 {
let mut value = 0
for i in 0..<4 {
value = value | (bytes[i].to_int() << (8 * i))
}
value
}
///|
/// Encodes an `Int32` as four little-endian bytes.
fn int_to_le_bytes(value : Int32) -> Bytes {
let buf = Buffer(capacity=4)
buf.write_int_le(value)
buf.to_bytes()
}
///|
/// Reads a little-endian `UInt32` from the first four bytes.
fn read_uint_le(bytes : BytesView) -> UInt32 {
let mut value : UInt32 = 0
for i in 0..<4 {
value = value | (bytes[i].to_uint() << (8 * i))
}
value
}
///|
/// Reads a little-endian `UInt64` from the first eight bytes.
fn read_uint64_le(bytes : BytesView) -> UInt64 {
let mut value : UInt64 = 0
for i in 0..<8 {
value = value | (bytes[i].to_uint64() << (8 * i))
}
value
}