optimize_bloom_filter.py

from math import e


# Compute k (optimal number of hash functions)
# n - the number of elements
# m - the bloom filter size
def compute_k(n, m):
    ln2 = 0.69314718056
    k = ln2 * m / n
    return round(k)


# Compute the prob. of false positive
# n - the number of elements
# m - the bloom filter size
# k - the number of hash functions
# false_positive = (1 - e ^ (-k * n / m)) ^ k
def compute_error_rate(n, m, k):
    false_positive = (1 - e ** (-k * n / m)) ** k
    return false_positive


# Input n
n = int(input("Enter n: "))

# Input some reasonable m (bloom filter size):
m = int(input("Enter m: "))

k = compute_k(n, m)
error_rate = compute_error_rate(n, m, k)

print('[Bloom filter: m = %2d, k = %d]\n\terror rate = %.5f' % (m, k, error_rate))

desired_error_rate = float(input("Enter your desired error rate: "))

print("\nOptimizing the bloom filter size ...")
while error_rate > desired_error_rate:
    # Increase m
    m += 1
    k = compute_k(n, m)
    error_rate = compute_error_rate(n, m, k)
    print('[Bloom filter: m = %2d, k = %d]\terror rate = %.5f' % (m, k, error_rate))

print("\nOptimization results:")
print('[Bloom filter: m = %2d, k = %d]\terror rate = %.5f' % (m, k, error_rate))