Bloom filtreler, bir elementin bir set üyesi olup olmadığını test etmek için kullanılan olasılıksal veri yapılarıdır. Uzay ve hız açısından verimlidir, hızlı üyelik sorgularının kabul edilebilir bazı olumlularla gerekli olduğu uygulamalar için uygun hale getirirler.
Bloom Filtre Nasıl Çalışır
Bir Bloom filtre biraz dizi ve birden fazla hash işlevleri kullanır. Bir element eklendiğinde, her bir hash fonksiyonu haritaları seride bir pozisyona taşır, bu parçaları 1'e kadar kontrol etmek için, aynı hash işlevleri uygulanırsa, ve hepsi 1'e ayarlandığında, elementin kesinlikle uygun değilse, kesinlikle değil.
Bloom Filtreleri için Hesaplamalar
Sahte pozitif olasılık, biraz dizinin büyüklüğüne bağlıdır (m), eklenmiş elementlerin sayısı (n), ve hash işlevlerinin sayısı (k) yanlış pozitif olan olasılık (p) tarafından yaklaşık olarak tanımlanabilir:
[FONT:0]p ⁇ (1 - e-kn/m))[FLT: 4]).
K ve m için optimal değerler, verilen n. Tipik olarak verilen bir n için yanlış pozitifleri en aza indirmek için:
[0]k = (m/n) * ln 2).
Bloom Filtrelerinin Vakalarını Kullanın
Bloom filtreler de dahil olmak üzere çeşitli alanlarda kullanılır:
- Hızlı üyelik testleri için veritabanı sistemleri
- Web caching to reduce disk lookups
- Veri senkronizasyonu için Dağıtılmış sistemler
- spam filtreleme için ağ güvenliği
Bloom Filtreleri
Verimli olsa da, Bloom filtrelerinin sınırları vardır. sahte pozitifler üretebilirler ancak yanlış negatifler üretemezler.Bir kez bitler 1'e ayarlandığında, bu da zamanla hatalarına yol açabilir. Ayrıca ek veri yapıları olmadan bireysel elementleri de iyileştiremezler.