Bộ lọc Bloom
Bộ lọc Bloom là cấu trúc dữ liệu xác suất
để kiểm tra một phần tử có nằm trong một tập hợp hay không. Kết quả có thể là FP, không có FN tức là kết quả kiểm tra là false thì chắc chắc phần tử đó không nằm trong tập hợp, còn kết quả là true thì hên xui (càng nhiều phần tử thì FP càng cao). Nhược điểm là có thể chèn thêm phần tử mà không thể xóa (có thể khắc phục bằng một bộ lọc đếm).
Đại ý: Bộ lọc dùng k hàm băm và m bit (m >> k)
Ứng dụng chủ yếu của nó là kiểm tra sự tồn tại của một phần tử, ví dụ như: kiểm tra nhanh một link đã được crawl chưa (khi viết ứng dụng thu thập dữ liệu), kiếm tra nhanh một key đã có trong database hay chưa, kiểm tra một đoạn k-mer có trong gen hay không. Độ phức tạp của nó là O(1), nếu so với hash thì nó không chính xác bằng (hash là chắc chắn, còn bloom filter thì có thể là FP), nhưng được cái ưu điểm về mặt lưu trữ, chỉ tốn m bit so với n phần tử như trong hash. Tuy nhiên, bloom filter chỉ dùng trong các ứng dụng nhỏ. Với các ứng dụng cần kiểm tra nhanh, thì thay vì kiểm tra bằng bloom filter thì dùng bộ lọc khác (tự tìm hiểu thêm nha, wikipedia là miễn phí, viết nhiều thì các bạn lười vận động) có thể tính toán song song hay phân tán, đó là những phiên bản xuất phát từ tư tưởng của bloom filter.
Chú thích:
để kiểm tra một phần tử có nằm trong một tập hợp hay không. Kết quả có thể là FP, không có FN tức là kết quả kiểm tra là false thì chắc chắc phần tử đó không nằm trong tập hợp, còn kết quả là true thì hên xui (càng nhiều phần tử thì FP càng cao). Nhược điểm là có thể chèn thêm phần tử mà không thể xóa (có thể khắc phục bằng một bộ lọc đếm).
Đại ý: Bộ lọc dùng k hàm băm và m bit (m >> k)
- Thêm phần tử: băm phần tử đầu vào bằng k hàm băm. Gán các bit này là 1.
- Kiểm tra: băm phần tử cần kiểm tra, sau đó kiểm tra các k vị trí tương ứng có giá trị là 1 hay không.
Ứng dụng chủ yếu của nó là kiểm tra sự tồn tại của một phần tử, ví dụ như: kiểm tra nhanh một link đã được crawl chưa (khi viết ứng dụng thu thập dữ liệu), kiếm tra nhanh một key đã có trong database hay chưa, kiểm tra một đoạn k-mer có trong gen hay không. Độ phức tạp của nó là O(1), nếu so với hash thì nó không chính xác bằng (hash là chắc chắn, còn bloom filter thì có thể là FP), nhưng được cái ưu điểm về mặt lưu trữ, chỉ tốn m bit so với n phần tử như trong hash. Tuy nhiên, bloom filter chỉ dùng trong các ứng dụng nhỏ. Với các ứng dụng cần kiểm tra nhanh, thì thay vì kiểm tra bằng bloom filter thì dùng bộ lọc khác (tự tìm hiểu thêm nha, wikipedia là miễn phí, viết nhiều thì các bạn lười vận động) có thể tính toán song song hay phân tán, đó là những phiên bản xuất phát từ tư tưởng của bloom filter.
Chú thích:
- FP (false positive): nói một cách dân dã là: mình đoán nó đúng, nhưng thực ra nó sai. Ngược lại là FN: mình đoán sai, nhưng thực ra nó đúng.
- k-mer: là một thuật ngữ trong sinh học để chỉ một đoạn gen dài k nucleotide. Ví dụ: ATGCTTA là 7-mer
Comments
Post a Comment