Created
November 19, 2020 14:01
-
-
Save Arp-G/4df11c18ef26671674df5cdc18b60433 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
defmodule GoGal.BloomFilter do | |
# Seed values for hash functions | |
@seed {9_881_409, 7_740_287, 1_822_091, 6_436_985, 6_108_165, 9_294_15, 1_815_555, 1_670_246, | |
7_190_510, 1_923_245} | |
# The number of elements to store in the bloom filter | |
@n 1024 | |
# Bloom filter bit string size (1024*4 = 4096 bit = 512 byte) | |
@m @n * 4 | |
# The number of hash functions to use given by Kernel.ceil(m / n * Math.log(Math.e(), 2)) | |
@k 6 | |
def new, do: <<0::size(@m)>> | |
def get_mask(element) do | |
mask = <<0::size(@m)>> | |
1..@k | |
|> Enum.reduce(mask, fn i, mask -> | |
index = | |
element | |
|> Murmur.hash_x86_32(elem(@seed, i)) | |
|> rem(@m) | |
set_bit(mask, index) | |
end) | |
end | |
def member?(bit_string, element) when is_bitstring(bit_string) do | |
Enum.all?(1..@k, fn i -> | |
pos = rem(Murmur.hash_x86_32(element, elem(@seed, i)), @m) | |
bit_set?(bit_string, pos) | |
end) | |
end | |
def bor( | |
<<bit_string_prefix::size(1), bit_string_rest::bits>>, | |
<<mask_prefix::size(1), mask_rest::bits>> | |
) do | |
bit = | |
if(bit_string_prefix == 1 || mask_prefix == 1, | |
do: 1, | |
else: 0 | |
) | |
<<bit::size(1), bor(bit_string_rest, mask_rest)::bits>> | |
end | |
def bor(<<>>, <<>>), do: <<>> | |
def bits(<<prefix::size(1), rest::bits>>), do: [prefix | bits(rest)] | |
def bits(<<>>), do: [] | |
def set_bit(bit_string, pos) when is_bitstring(bit_string) do | |
<<prefix::size(pos), val::size(1), rest::bits>> = bit_string | |
# set the bit only if its not set | |
if val != 1 do | |
<<prefix::size(pos), 1::size(1), rest::bits>> | |
else | |
bit_string | |
end | |
end | |
defp bit_set?(bit_string, pos) when is_bitstring(bit_string) do | |
<<_prefix::size(pos), val::size(1), _rest::bits>> = bit_string | |
val == 1 | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment