Bloom Filter

Kiểm tra sự tồn tại của một phần tử mà không dùng đến bất kỳ vòng lặp nào???

Bài toán

Tèo: Cho bạn một mảng các phần tử

let A = ['Teoflio', 'Tun', 'Cuden',...]

Làm thế nào để kiểm tra xem phần tử X = 'Joseph' có ở trong mảng A này hay không?

Tủn: Quá dễ! For cái vèo là xong

let x = 'Joseph';
for (let i = 0; i < A.length; i++){
    if ( A[i] == x ){
        // Tìm thấy rồi nè! hehe
        break;
    }
}

Tèo: Ok! Khá lắm, vậy bây giờ không dùng vòng lặp, bạn làm được không???

Tủn: Ummm,... chắc không được! hahaha

Tèo: Vậy đây là lúc mà Bloom Filter phát huy tác dụng!

Đôi khi, chúng ta cần kiểm tra nhanh chóng xem một phần tử có thuộc vào một tập hợp nào hay không mà không cần tốn quá nhiều chi phí tính toán (những tập hợp này có kích thước rất lớn - triệu phần tử trở lên). Bloom Filter có thể giúp được trong trường hợp này.

Thuật toán

Triển khai thuật toán Bloom Filter rất tiết kiệm về mặt bộ nhớ lưu trữ, vì bản chất Bloom Filter chỉ là một dãy các bit 0 1 (aka Mảng boolean,...).

Bloom Filter dùng để phân biệt hơn 300,000,000 phần tử riêng biệt cần dùng đến khoảng 119 MB bộ nhớ.

Bloom Filter chỉ có nhiệm vụ đơn giản là bật bit 1 tại những vị trí "Đặc trưng cho phần tử X". Những dấu hiệu đặc trưng này có thể được tính toán và tìm ra bởi những Hàm băm Phi mã hóa (Non-cryptographic hash functions).

Hàm băm phi mã hóa

Giải thích sơ lược, khi nhét một phần tử bất kỳ vô hàm băm, kết quả trả về sẽ là một con số đại diện cho phần tử đó. Hàm băm sẽ cố gắng tìm ra những con số khác nhau cho mỗi phần tử khác nhau. Nhưng đôi khi, vẫn có sự trùng lặp con số này ở những phần tử khác nhau (Collision).