Bloom filter: cơ chế bit, false positive và ứng dụng

Giới thiệu

Bài này học bộ lọc siêu nhẹ kiểm tra tồn tại. Bạn chặn nhanh cái chắc chắn không có.

Kiến thức cần nhớ

Bài toán danh bạ

• Mỗi lần gửi mail cần hỏi có trong danh bạ không.
• Gọi kho cũ mỗi lần thì quá chậm.
• Tải cả danh bạ về máy rồi hỏi cục bộ.
• Ví dụ đời thường: danh sách đen dán ở cửa.

Mảng bit và k hàm băm

• Bắt đầu mảng toàn số 0 dài m bit.
• Lưu 1 món thì băm k lần, bật k bit lên 1.
• Hỏi 1 món thì đọc k bit đó.
• Ví dụ đời thường: đóng k dấu mực lên thẻ.
• Thiếu 1 bit 1 là chắc chắn không có.

Sai được 1 chiều

• Báo không thì luôn đúng, tin được.
• Báo có thì có thể nhầm vì bit dùng chung.
• Nhầm này gọi là dương tính giả.
• Ví dụ đời thường: thấy dấu mực nhưng nhầm chủ.
• Quy tắc: báo không thì thôi, báo có thì kiểm lại.

Các biến thể của Bloom filter

• Ghép hai bộ lọc cùng m, cùng k hàm băm: phép OR cho bộ lọc của hợp hai tập.

Ví dụ

• Input: lưu số 2 bật 2 bit, hỏi số 3 lạ mà trùng 2 bit. Output: báo có nhầm.
• Giải thích: bit không ghi tên ai nên bị trùng.

bits = [0] * 8  # mảng bit ban đầu
def add(h1, h2):  # lưu: bật 2 bit
    bits[h1] = 1
    bits[h2] = 1
def ask(h1, h2):  # hỏi: đủ 2 bit 1 mới báo có
    return bits[h1] == 1 and bits[h2] == 1

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-030/.

Bài 1: Bloom filter

class BloomFilter {
 public:
  BloomFilter(size_t m, int k);           // m bit, k hàm băm
  void add(const std::string &s);
  bool mightContain(const std::string &s) const;
  double fillRatio() const;               // tỉ lệ bit đang là 1
 private:
  std::vector<uint64_t> bits;             // tự đóng gói bit, không dùng std::vector<bool>
};

Hàm băm: double hashing. Tính h1 = FNV-1a(s), h2 = murmur-style mix(h1) | 1. Hàm thứ i là (h1 + i * h2) % m.

m=1000, k=3; add "a@x.com", "b@y.com"
mightContain("a@x.com")  -> true (luôn luôn)
bộ lọc rỗng              -> mọi truy vấn trả false

Bài 2: Đo false positive

Với n = 10000 email đã thêm, thử 100.000 email chưa thêm. In tỉ lệ dương tính giả thực tế và so với công thức:

$p \approx \left(1 - e^{-kn/m}\right)^k$

m        k    thực_tế    lý_thuyết
50000    1    ...        0.181
50000    3    ...        ...
100000   7    ...        0.008

Viết hàm optimalParams(n, p) trả m = -n ln p / (ln 2)^2 và k = (m/n) ln 2. Kiểm tra với n = 10^6, p = 0.01 ra m khoảng 9,6 triệu bit, k = 7.

Bài 3: Lọc trước khi hỏi kho chậm (nâng cao)

Giả lập kho dữ liệu chậm: SlowDB::exists(email) có sleep 1 ms.

1. Hàm checkEmail(email): hỏi Bloom trước. Bloom nói "không" thì trả false ngay. Nói "có" thì hỏi SlowDB.
2. Chạy 10.000 truy vấn, 90% là email không có. In số lần gọi SlowDB và tổng thời gian, có và không có Bloom.
3. Viết CountingBloom dùng bộ đếm 4 bit thay cho 1 bit, hỗ trợ remove. Test: thêm rồi xóa thì mightContain trả false (nếu không đụng phần tử khác).

✅ Tiêu chí hoàn thành

• Không bao giờ có âm tính giả (test 10.000 phần tử đã thêm).
• Bảng Bài 2 có số thật lệch lý thuyết không quá vài phần trăm.
• Bài 3 cho thấy số lần gọi kho chậm giảm rõ rệt.
• Giải thích được vì sao Bloom filter thường không xóa được phần tử.

❓ Câu hỏi ôn tập

• Bloom filter dùng để hỏi gì?
• Lưu và hỏi làm mấy bước băm?
• Báo không và báo có bên nào chắc chắn?
• Muốn chính xác hơn thì chỉnh gì?

🌕 Bạn đã hoàn thành ngày 30. Làm hết bài tập phía trên rồi sang ngày tiếp theo.