Nếu bạn là người hâm mộ lý thuyết tập hợp, bạn có thể đồng ý rằng có hai nhóm người viết chương trình máy tính: những người biết bộ lọc Bloom là gì và những người không biết. Làm thế nào bạn có thể kiểm tra một cách hiệu quả xem ai đó thuộc nhóm này hay nhóm khác? Vâng, bạn có thể sử dụng bộ lọc Bloom. [SamWho] hướng dẫn chúng ta toàn bộ vấn đề một cách tổng quát mà bạn có thể áp dụng trong mọi tình huống.

Bộ lọc Bloom thực hiện đánh đổi tốc độ của nó. Nó có thể cho kết quả dương tính giả nhưng không phải âm tính giả. Nghĩa là, nếu thuật toán bộ lọc Bloom cho bạn biết rằng X không phải là một phần của tập hợp thì điều đó đúng. Nhưng nếu nó cho bạn biết đúng như vậy, bạn có thể phải điều tra thêm để xem điều đó có đúng không.

Nếu nó không thể cho bạn biết rằng thứ gì đó chắc chắn nằm trong một bộ thì tại sao phải bận tâm? Thông thường, khi sử dụng bộ lọc Bloom, bạn muốn giảm bớt việc tìm kiếm thông qua một lượng dữ liệu khổng lồ. Ví dụ trong bài viết nói về việc có cơ sở dữ liệu 20 megabyte về các URL “xấu”. Bạn muốn cảnh báo người dùng nếu họ nhập một cơ sở dữ liệu nhưng việc tải xuống cơ sở dữ liệu đó là điều cấm. Nhưng bộ lọc Bloom có ​​thể chỉ nhỏ tới 1.8 megabyte. Tuy nhiên, xác suất dương tính giả là 1/1000.

Tăng kích thước cơ sở dữ liệu lên 3.59 megabyte và bạn có thể giảm số lượng kết quả dương tính giả xuống còn một phần triệu. Có lẽ, nếu bạn nhận được kết quả dương tính, bạn có thể chấp nhận rủi ro là kết quả đó là sai hoặc bạn có thể làm nhiều việc hơn để tìm kiếm thêm.

Ví dụ, hãy tưởng tượng một thiết bị hoặc chương trình bộ đệm web. Nhiều trang web được tải một lần và không bao giờ tải lại. Nếu bạn lưu trữ tất cả chúng vào bộ đệm, bạn sẽ lãng phí rất nhiều thời gian và đẩy những thứ khác ra khỏi bộ đệm. Nhưng nếu bạn kiểm tra URL trang bằng bộ lọc Bloom, bạn có thể cải thiện mọi thứ khá nhiều. Nếu URL có thể tồn tại trong bộ lọc Bloom thì có thể bạn đã từng thấy nó trước đây nên có thể bạn muốn lưu nó vào bộ nhớ đệm.

Nếu nó nói là chưa, bạn có thể thêm nó vào bộ lọc để nếu được truy cập lại, nó sẽ lưu vào bộ nhớ đệm. Chắc chắn, đôi khi một trang sẽ hiển thị kết quả dương tính giả. Vậy thì sao? Dù sao thì bạn cũng sẽ chỉ lưu trang vào bộ nhớ đệm trong lần đầu tiên, đó là điều bạn đã làm trước đây. Nếu điều đó chỉ xảy ra 0.1% thời gian, bạn vẫn thắng.

Nói một cách đơn giản, bộ lọc Bloom băm từng mục bằng ba thuật toán khác nhau và đặt các bit trong một mảng dựa trên kết quả. Để kiểm tra một mục, bạn tính toán các giá trị băm tương tự và xem liệu có bất kỳ bit tương ứng nào được đặt thành 0 hay không. Nếu vậy thì vật phẩm đó không thể có trong bộ này. Tất nhiên, không có gì đảm bảo rằng cả ba bit được đặt có nghĩa là tập hợp đó chứa mục đó. Ba bit đó có thể được đặt cho các mục hoàn toàn khác nhau.

Tại sao việc tăng số lượng bit lại giúp ích? Bài đăng trả lời câu hỏi đó và xem xét các tối ưu hóa khác như số lượng hàm băm và cách đếm khác nhau.

Bài đăng thực hiện rất tốt việc giải thích bộ lọc nhưng nếu bạn muốn có một ví dụ cụ thể hơn trong C, bạn có thể muốn đọc bài đăng này tiếp theo. Hoặc tìm kiếm mã bằng ngôn ngữ yêu thích của bạn. Chúng ta đã nói về Xử lý chuỗi Python với bộ lọc Bloom trước. Chúng tôi thậm chí còn thấy một đề xuất thêm chúng đến xe buýt trung chuyển.

• Phân phối nội dung và PR được hỗ trợ bởi SEO. Được khuếch đại ngay hôm nay.
• PlatoData.Network Vertical Generative Ai. Trao quyền cho chính mình. Truy cập Tại đây.
• PlatoAiStream. Thông minh Web3. Kiến thức khuếch đại. Truy cập Tại đây.
• Trung tâmESG. Than đá, công nghệ sạch, Năng lượng, Môi trường Hệ mặt trời, Quản lý chất thải. Truy cập Tại đây.
• PlatoSức khỏe. Tình báo thử nghiệm lâm sàng và công nghệ sinh học. Truy cập Tại đây.
• nguồn: https://hackaday.com/2024/02/22/filters-are-in-bloom/