Bloom Filter

Türkçe karşılığı: bloom filtresi
Okunuşu: blum filtır

Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.

Güncellendi 30 Eylül 20263 dk okuma

Kısaca

Bloom filter, çok az bellek kullanarak bir öğenin kümede kesinlikle olmadığını ya da büyük olasılıkla olduğunu söyleyen kompakt, olasılıksal bir veri yapısıdır.

Bloom filter nedir?

Bloom filter, bir öğenin bir kümeye ait olup olmadığını sınamak için kullanılan, bellek açısından verimli bir veri yapısıdır. Bir öğenin kümede olmadığını kesin olarak söyleyebilir; ancak bir öğenin var olduğunu söylediğinde yanılma ihtimali küçüktür ve buna yanlış pozitif (false positive) denir. Bu belirsizliğin karşılığında, öğelerin kendisini hiç saklamadığı için tam bir hash set'in ihtiyaç duyacağı belleğin çok küçük bir kısmını kullanır. Burton Howard Bloom tarafından 1970'te icat edilmiştir.

Bloom filter, hepsi 0 ile başlayan m bitlik bir dizi ve k farklı hash fonksiyonundan oluşur. Bir öğe eklemek için onu k kez hash'ler ve ortaya çıkan her konumdaki biti 1 yaparsınız. Bir öğeyi kontrol etmek için aynı şekilde hash'lersiniz: bu bitlerden herhangi biri 0 ise öğe kesinlikle hiç eklenmemiştir; hepsi 1 ise büyük olasılıkla eklenmiştir, ancak aynı bitleri başka öğeler de ayarlamış olabilir. Yanlış pozitif oranı dizi boyutuna, hash fonksiyonu sayısına ve saklanan öğe sayısına bağlıdır; öğe başına yaklaşık 10 bit ve 7 hash fonksiyonuyla bu oran yüzde 1'in hemen altındadır.

Yüzleri belirsiz hatırlayan bir kapı görevlisi gibidir: sizin gibi birini hiç görmediyse kesinlikle listede değilsiniz, ama tanıdık görünüyorsanız yine de gerçek misafir listesine bakar. Bloom filter'lar pahalı bir şeyin önünde ucuz bir ilk kontrol işlevi görür. LSM ağaçları üzerine kurulu veritabanları, bir anahtarı içeremeyecek dosyaları atlamak için her veri dosyası başına bir tane tutar; önbellekler yalnızca bir kez istenmiş öğeleri saklamaktan kaçınmak için onları kullanır; servisler ise URL'leri ya da parolaları devasa engelleme listelerine karşı, listenin tamamını indirmeden kontrol etmek için kullanmıştır.

Bloom filter sıklıkla hash set ile karıştırılır. Hash set gerçek öğeleri saklar; bu yüzden kesin yanıt verir ve onları listelemenize ya da silmenize izin verir. Bloom filter ise yalnızca bit saklar; bu yüzden içeriğini listeleyemez ve bazı yanlış pozitifler verir, ancak asla yanlış negatif vermez. Standart bir Bloom filter ayrıca öğe silemez, çünkü bir biti temizlemek başka öğeleri de silebilir; counting Bloom filter ve cuckoo filter, silmeyi destekleyen varyantlardır.

Önemli noktalar

Bloom filter küme üyeliği için ya kesinlikle hayır ya da büyük olasılıkla evet yanıtını verir.
Asla yanlış negatif vermez ama yanlış pozitif verebilir.
Öğeleri değil yalnızca bir bit dizisi sakladığı için çok az bellek kullanır.
Bir öğeyi eklemek ve kontrol etmek O(k) sürer; k hash fonksiyonu sayısıdır.
Pahalı disk okumalarından, ağ çağrılarından ya da veritabanı aramalarından kaçınan ucuz bir ilk kontroldür.

Örnek

Python'da asgari bir Bloom filterpython

SIZE, HASHES = 1000, 5
bits = [0] * SIZE

def positions(item):  # k bit positions per item, one from each seeded hash
    return [hash((seed, item)) % SIZE for seed in range(HASHES)]

def add(item):
    for p in positions(item):
        bits[p] = 1

def might_contain(item):
    return all(bits[p] for p in positions(item))  # any 0 bit means definitely absent

add("alice@example.com")
print(might_contain("alice@example.com"), might_contain("bob@example.com"))  # True False (almost always)

Sık sorulan sorular

Bloom filter yanlış negatif verebilir mi?

Hayır. Bir öğe eklendiyse tüm bitleri 1 olarak ayarlanmıştır; bu yüzden filtre onu her zaman olası var olarak bildirir. Yalnızca, başka öğelerin tesadüfen aynı bitlerin hepsini ayarlamış olması durumunda yanlış pozitifler mümkündür.

Bloom filter ne kadar büyük olmalı?

Kaç öğe beklediğinize ve hangi yanlış pozitif oranını kabul edebileceğinize bağlıdır. Genel bir kural olarak öğe başına yaklaşık 10 bit ve 7 hash fonksiyonu yüzde 1'in hemen altında bir oran verir ve öğe başına eklenen her 5 bit bu oranı yaklaşık on kat düşürür.

Bloom filter ile hash set arasındaki fark nedir?

Hash set her öğeyi saklar ve üyeliği kesin olarak yanıtlar, ancak tüm öğeler için bellek ister. Bloom filter yalnızca bit sakladığı için çok daha küçüktür, ancak yanlış pozitif döndürebilir ve temel biçimiyle öğeleri listeleyemez ya da silemez.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin