Khái niệm cơ bản
Bộ lọc Bloom đếm được định nghĩa là cấu trúc dữ liệu tổng quát của bộ lọc Bloom được triển khai để kiểm tra xem số đếm của một phần tử nhất định có nhỏ hơn một ngưỡng nhất định hay không khi một chuỗi các phần tử được đưa ra. Là một dạng tổng quát, bộ lọc Bloom có khả năng xuất hiện các kết quả phù hợp dương tính giả, nhưng không có khả năng âm tính giả - nói cách khác, một truy vấn trả về "có thể cao hơn hoặc bằng ngưỡng" hoặc "chắc chắn nhỏ hơn ngưỡng".
Mô tả thuật toán
- Hầu hết các tham số, được sử dụng trong bộ lọc Bloom đếm, được xác định giống với bộ lọc Bloom, chẳng hạn như n, k. m được biểu thị là số bộ đếm trong bộ lọc Đếm Bloom, là sự mở rộng của m bit trong bộ lọc Bloom.
- Một bộ lọc Nở rộ đếm trống được đặt làm m bộ đếm, tất cả đều được khởi tạo thành 0.
- Tương tự như bộ lọc Bloom, cũng phải xác định k hàm băm khác nhau, mỗi hàm trong số đó chịu trách nhiệm ánh xạ hoặc băm một số phần tử tập hợp cho một trong m vị trí mảng bộ đếm, tạo ra một phân phối ngẫu nhiên đồng nhất. Cũng giống như k là một hằng số, nhỏ hơn m rất nhiều, tỷ lệ thuận với số phần tử được thêm vào.
- Tổng quát chính của bộ lọc Bloom là thêm một phần tử. Để thêm một phần tử, hãy chèn phần tử đó vào từng hàm trong số k hàm băm để thu được k vị trí mảng và tăng số đếm 1 ở tất cả các vị trí này.
- Để truy vấn phần tử có ngưỡng θ (xác minh xem số đếm của phần tử có nhỏ hơn θ hay không), hãy chèn nó vào từng hàm trong số k hàm băm để thu được k vị trí bộ đếm.
- Nếu bất kỳ bộ đếm nào tại các vị trí này nhỏ hơn θ, số phần tử đếm chắc chắn nhỏ hơn θ - nếu nó cao hơn và bằng nhau, thì tất cả các bộ đếm tương ứng sẽ cao hơn hoặc bằng θ.
- Nếu tất cả đều cao hơn hoặc bằng θ thì số đếm thực sự cao hơn hoặc bằng θ hoặc các bộ đếm tình cờ cao hơn hoặc bằng θ.
- Nếu tất cả đều cao hơn hoặc bằng θ mặc dù số lượng nhỏ hơn θ, tình huống này được xác định là dương tính giả. Giống như bộ lọc Bloom, điều này cũng nên được giảm thiểu.