Tính toán số dân gần đúng của bộ lọc hoa

Question

Cho bộ lọc nở có kích thước N-bit và hàm băm K, trong đó M-bit (trong đó M < = N) của bộ lọc được đặt.

Có thể ước tính số phần tử được chèn vào bộ lọc nở không?

Ví dụ đơn giản

Tôi đã nghiền ngẫm ví dụ sau đây, giả sử một BF 100-bit và 5 hàm băm nơi 10-bit được thiết lập ...

trường hợp kịch bản xuất sắc nhất: Giả sử các hàm băm thực sự hoàn hảo và duy nhất ánh xạ một chút cho một số giá trị X, sau đó cho 10 bit đã được thiết lập, chúng ta có thể nói rằng chỉ có 2 phần tử được chèn vào trong trường hợp kịch bản xấu nhất: Giả sử rằng chỉ có 2 phần tử được chèn vào BF

các hàm băm là xấu và liên tục ánh xạ tới cùng một bit (độc đáo với nhau), sau đó chúng ta có thể nói 10 phần tử đã được chèn vào BF

Phạm vi này có vẻ là [2,10] trong đó khoảng trống trong phạm vi này có thể được xác định bởi xác suất dương tính giả của bộ lọc - I bị kẹt vào thời điểm này.

Answer 1

Câu hỏi này khiến tôi lo lắng một chút vì có better algorithms để tính xấp xỉ số phần tử riêng biệt với một lượng nhỏ dung lượng lưu trữ. Tuy nhiên, nếu chúng ta phải sử dụng một bộ lọc Bloom, hãy giả sử rằng hàm băm là các oracles ngẫu nhiên (tất cả các giá trị được chọn độc lập, hoặc "thực sự hoàn hảo", không bị nhầm lẫn với băm hoàn hảo). Bây giờ chúng ta có một vấn đề về quả bóng và thùng: cho rằng M của các thùng N có quả bóng trong chúng, chúng ta đã ném bao nhiêu quả bóng? Để B là số quả bóng được ném; số lượng mục là B/K, vì mỗi mục chúng tôi ném K quả bóng.

Phép tính xấp xỉ chuẩn cho các quá trình bi và thùng là mô hình từng thùng như một quá trình Poisson độc lập; thời gian trước khi một thùng rác bị chiếm đóng được phân bổ theo cấp số nhân. Để 1 là thời gian cần thiết để ném tất cả các quả bóng, khả năng tối đa ước tính λ của tỷ lệ phân phối mũ này thỏa mãn Pr(Exponential[λ] < 1) = M/N, vì vậy 1 - exp(-λ) = M/N và λ = -log(1 - M/N). Tham số λ giống như số lượng quả bóng, vì vậy ước tính cho số mục là B ≈ -N log(1 - M/N)/K.

CHỈNH SỬA: Có N thùng, vì vậy chúng tôi cần nhân với N.

Answer 2

Mục nhập tại Wikipedia cung cấp cho bạn công thức xác suất của bất kỳ bit cụ thể nào được đặt, giả sử rằng hàm băm tạo mọi thứ ngẫu nhiên. Đây là 1 - (1-1/m)^kn. Vì có m bit trong bộ lọc, điều này có nghĩa là số bit dự kiến ​​/ trung bình sẽ là m(1-(1-1/m)^kn). Vì vậy, bạn có thể đưa ra một dự đoán hợp lý hợp lý cho n bằng cách chọn số n làm cho số này tương đương với số lượng bit thực sự được đặt.

Để có được và ý tưởng về mức độ đoán chính xác như thế, có lẽ sẽ tốt hơn khi có ý tưởng về phương sai của số bit được đặt. Bạn có thể làm việc này một cách chính xác, nhưng nó là một cái gì đó của một cơn đau ở cổ. Bạn có thể sử dụng thực tế là Var(X) = E(X^2) - E(X)^2.Trong trường hợp này, E(X^2) phụ thuộc chủ yếu vào xác suất mà các cặp bit sẽ được thiết lập và bạn có thể làm việc này bằng cách xem xét xác suất của các câu lệnh như "bit 0 được đặt và bit 1 là rõ ràng và tất cả các bit khác rõ ràng" và "bit 0 rõ ràng" và "tất cả các bit ngoại trừ 0 và 1 đều trống".