Bộ lọc Bloom

Bộ lọc Bloom, phát minh bởi Burton Howard Bloom năm 1970,^[1] là một cấu trúc dữ liệu xác suất để kiểm tra xem một phần tử có nằm trong một tập hợp hay không. Có thể có lỗi dương tính sai, nhưng không bao giờ có âm tính sai; nghĩa là kết quả thu được luôn là "nằm trong tập hợp (có thể sai)" hoặc "không nằm trong tập hợp". Có thể chèn thêm phần tử nhưng không thể xóa (nhược điểm này có thể được khắc phục bằng một bộ lọc đếm). Càng chèn nhiều phần tử thì xác suất dương tính sai càng cao.

Mô tả thuật toán

Một ví dụ của bộ lọc Bloom cho tập hợp {x, y, z}. Các mũi tên màu chỉ ra các vị trí mỗi phần tử ánh xạ đến. Phần tử w không nằm trong tập hợp {x, y, z}, bởi một trong các vị trí nó ánh xạ đến có giá trị 0. Trong ví dụ này, m=18 và k=3.

Một bộ lọc Bloom rỗng là một mảng m bit, tất cả đều bằng 0. Giả sử có k hàm băm khác nhau, mỗi hàm ánh xạ từ không gian các phần tử tới m vị trí trong bảng với xác suất như nhau. Thông thường k là một hằng số và nhỏ hơn nhiều so với m

Để chèn một phần tử, áp dụng k hàm băm để tính ra mảng k vị trí và gán cho các bit này giá trị 1.

Để kiểm tra một phần tử có nằm trong tập hợp hay không, áp dụng k hàm băm để tính ra k vị trí trong mảng và kiểm tra xem tất cả các bit đó có giá trị 1 hay không. Nếu có một bit nào đó bằng 0 thì phần tử cần kiểm tra chắc chắn không nằm trong mảng. Nếu tất cả chúng đều bằng 1 thì phần tử đó có thể nằm trong mảng.

Xác suất dương tính sai

Xác suất dương tính sai ${\displaystyle p}$ dưới dạng hàm số của số phần tử ${\displaystyle n}$ và kích thước ${\displaystyle m}$ của bộ lọc. Giả sử sử dụng ${\displaystyle k=(m/n)\ln 2}$ hàm băm

Giả sử các hàm băm lựa chọn các vị trí trong bảng với xác suất như nhau và hoàn toàn ngẫu nhiên và độc lập. Nếu m là số bit trong mảng thì xác suất một bit không được gán giá trị 1 khi ta băm một phần tử bằng một hàm băm là

${\displaystyle 1-{\frac {1}{m}}.}$

Xác suất nó không được gán giá trị 1 bởi bất kì hàm băm nào là

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}.}$

Nếu chèn n phần tử, thì xác suất bit đó vẫn bằng 0 là

${\displaystyle \left(1-{\frac {1}{m}}\right)^{kn};}$

nên xác suất nó bằng 1 là

${\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}.}$

Ta xét quá trình kiểm tra liệu một phần tử có nằm trong tập hay không. Thuật toán kiểm tra k vị trí trong mảng xem chúng có bằng 1 hay không. Xác suất tất cả chúng đều bằng 1 là

${\displaystyle \left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.}$

Chứng minh này không toàn toàn đúng do nó giả sử xác suất mỗi bit trong mảng được gán giá trị 1 là độc lập với nhau. Tuy nhiên, giả sử đây là một xấp xỉ tốt, thì giá trị ${\displaystyle k}$ tối ưu để xác suất trên là nhỏ nhất là

${\displaystyle {\frac {m}{n}}\ln 2\approx 0.7{\frac {m}{n}},}$

cho giá trị xác suất dương tính sai là

${\displaystyle 2^{-k}\approx {0.6185}^{m/n}.}$

Có thể tính kích thước ${\displaystyle m}$ của mảng theo số phần tử ${\displaystyle n}$ và xác suất dương tính sai ${\displaystyle p}$ bằng cách thay giá trị tối ưu của ${\displaystyle k}$ vào biểu thức trên:

${\displaystyle p=\left(1-e^{-(m/n\ln 2)n/m}\right)^{(m/n\ln 2)}}$

Đơn giản hóa biểu thức trên, ta thu được:

${\displaystyle \ln p=-{\frac {m}{n}}\left(\ln 2\right)^{2}.}$

từ đó thu được:

${\displaystyle m=-{\frac {n\ln p}{(\ln 2)^{2}}}.}$

Nghĩa là để xác suất sai là hằng số cố định, kích thước của mảng là tuyến tính với số phần tử của tập hợp.