Có bao nhiêu hàm băm mà bộ lọc nở của tôi cần?

Question

Wikipedia nói:

Một bộ lọc Bloom rỗng là một mảng bit của m bit, tất cả các thiết lập để 0. Ngoài ra còn phải k hàm băm khác nhau xác định, mỗi trong số đó bản đồ hoặc băm một số yếu tố thiết lập để một trong những các vị trí mảng m với phân bố ngẫu nhiên đồng đều.

Tôi đã đọc bài viết, nhưng điều tôi không hiểu là cách xác định k. Nó có phải là một chức năng của kích thước bảng?

Ngoài ra, trong bảng băm tôi đã viết, tôi đã sử dụng một thuật toán đơn giản nhưng hiệu quả để tự động tăng kích thước của băm. Về cơ bản, nếu bao giờ hơn 50% các thùng trong bảng đã được lấp đầy, tôi sẽ tăng gấp đôi kích thước của bảng. Tôi nghi ngờ bạn vẫn có thể muốn làm điều này với một bộ lọc nở để giảm dương tính giả. Chính xác?

Answer 1

Nếu bạn đọc sâu hơn trong Wikipedia article about Bloom filters, thì bạn sẽ tìm thấy một phần Xác suất dương tính giả. Phần này giải thích cách số hàm băm ảnh hưởng đến xác suất dương tính giả và cung cấp cho bạn công thức để xác định k từ đầu dò mong muốn mong muốn. của dương tính giả.

---

Trích dẫn từ bài viết trên Wikipedia:

Rõ ràng, xác suất sai tích cực giảm khi m (số bit trong mảng) tăng, và tăng lên khi n (số của các phần tử chèn ) tăng lên. Đối với một m nhất định và n, giá trị của k (số băm chức năng) là giảm thiểu các xác suất là

Answer 2

Và để có nó đặt ra trong một bảng nhỏ gọn:

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

Answer 3

Given:

• n: số lượng mục bạn mong đợi có trong bộ lọc của mình (ví dụ: 216,553)
• p: tỷ lệ dương tính giả chấp nhận được của bạn {0..1} (ví dụ:0.01 → 1%)

chúng tôi muốn để tính toán:

• m: số bit cần thiết trong bộ lọc nở
• k: số hàm băm chúng ta nên áp dụng

Công thức:

m = -n*ln(p)/(ln(2)^2)số bit
k = m/n * ln(2)số hàm băm

Trong trường hợp của chúng tôi:

• m = -216553*ln(0.01)/(ln(2)^2) = 997263/0.48045 = 2,075,686 bit (253 kB)
• k = m/n * ln(2) = 2075686/216553 * 0.693147 = 6.46 hàm băm (7 hàm băm)

Note: Bất kỳ mã phát hành vào phạm vi công cộng. Không yêu cầu ghi nhận tác giả.