Bloom Filters Nasıl Çalışır ve Neden Önemlidir?

Büyük bir veri kümesinde bir şeyin var olup olmadığını kontrol etmeniz gerektiğinde, tüm veri kümesini saklamadan çözüm arıyorsanız, Bloom filtreleri imdadınıza yetişir. Bu alan tasarruflu ve olasılıksal veri yapısı, hızlı bir üyelik kontrolü sunar. Ancak küçük bir tavizi de beraberinde getirir: Yanlış pozitif sonuçlar üretebilir, ancak asla yanlış negatif sonuçlar vermez.

Bloom Filtresi Nedir?

Bloom filtresi, boyutu m olan bir bit dizisidir ve öğeleri bu diziye eşlemek için k bağımsız hash fonksiyonu kullanır. Bir öğenin bir kümenin üyesi olup olmadığını verimli bir şekilde kontrol eder. Peki ya dezavantajı? Ara sıra yanlış pozitif sonuçlarla karşılaşabilirsiniz (örneğin, bir öğe yokken var gibi görünebilir), ancak yanlış negatif sonuç almazsınız (bir öğe yok deniyorsa, gerçekten yoktur).

Gerçek Hayattaki Kullanım Alanları:

• Veritabanları: Bir kaydın varlığını sorgulamadan önce hızlıca kontrol etmek.
• Web Önbellekleme: Bir URL’nin önbellekte olup olmadığını kontrol etmek.
• E-posta Filtreleme: Daha önce spam olarak işaretlenmiş e-postaların hızlıca kontrol edilmesi.
• E-posta Filtreleme: Daha önce spam olarak işaretlenmiş e-postaların hızlıca kontrol edilmesi.

Bloom filtresinin çalışma mantığını daha detaylı inceleyelim:

Başlangıç: Bit Dizisinin Oluşturulması

Bloom filtresi, m boyutunda bir bit dizisi ile başlar. Bu bit dizisi, yalnızca 0 ve 1 değerlerini tutabilir ve başlangıçta tüm bitler 0olarak ayarlanır.

• Amaç: Bu dizi, öğelerin hash fonksiyonları tarafından eşlenen indekslerini temsil eder. Ancak burada, belirli bir öğenin tam konumu değil, sadece “var olabilir” bilgisi saklanır.

Örnek:

Dizi başlangıçta şöyle görünür:
0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Bir Öğenin Eklenmesi

1. Hashleme: Öğeyi k farklı hash fonksiyonuna göndeririz. Her hash fonksiyonu, öğeyi bit dizisinde bir indekse eşler. Hash fonksiyonlarının her biri aynı öğe için farklı bir indeks üretebilir.

2. Bitleri Ayarlama: Hash fonksiyonlarının ürettiği her indeks, bit dizisinde 1 olarak işaretlenir.

Örnek:

k = 3 , yani üç farklı hash fonksiyonu kullanıyoruz. Bit dizisinin uzunluğu m = 10 , bu yüzden hash fonksiyonlarının ürettiği değerleri dizinin boyutuna uygun hale getirmek için 10’a mod alıyoruz. Bu fonksiyonlar şunları yapar:

• Hash 1: hash1(“apple”) \% 10 → 2

• Hash 2: hash2(“apple”) \% 10 → 4

• Hash 3: hash3(“apple”) \% 10 → 7

Bu indekslerdeki bitler 1 olarak ayarlanır.

Dizi şu şekilde güncellenir:
 0, 1, 0, 1, 0, 0, 0, 1, 0, 0 

Üyelik Kontrolü

Öğeyi kontrol etmek için aynı k hash fonksiyonlarını kullanırız. Hash fonksiyonları, bit dizisinde k farklı indeks üretir. Üretilen bu indekslerdeki bitlerin 1 olup olmadığını kontrol ederiz. Eğer tüm bitler 1 ise, öğe var olabilir anlamına gelir.

Avantajlar:

• Alan Verimliliği: Çok az bellek gerektirir, büyük veri kümeleri için idealdir.
• Hız: Öğeleri eklemek ve kontrol etmek son derece hızlıdır.

Dezavantajlar:

• Yanlış Pozitifler: Bir öğe yokken var gibi görünebilir.
• Silme İşlemi Yok: Eklenen bir öğe, filtreden çıkarılamaz (ancak Counting Bloom Filter gibi varyasyonlar bu sorunu çözer).

C# ile Gerçekleştirme

using System;
using System.Collections;
using System.Security.Cryptography;
using System.Text;

public class BloomFilter
{
    private readonly int _size;
    private readonly int _hashCount;
    private readonly BitArray _bitArray;

    public BloomFilter(int size, int hashCount)
    {
        _size = size;
        _hashCount = hashCount;
        _bitArray = new BitArray(size);
    }

    private int Hash(string item, int seed)
    {
        using (var md5 = MD5.Create())
        {
            byte[] inputBytes = Encoding.UTF8.GetBytes(item + seed);
            byte[] hashBytes = md5.ComputeHash(inputBytes);
            int hash = BitConverter.ToInt32(hashBytes, 0);
            return Math.Abs(hash % _size);
        }
    }

    public void Add(string item)
    {
        for (int i = 0; i < _hashCount; i++)
        {
            int index = Hash(item, i);
            _bitArray[index] = true;
        }
    }

    public bool Check(string item)
    {
        for (int i = 0; i < _hashCount; i++)
        {
            int index = Hash(item, i);
            if (!_bitArray[index])
            {
                return false;
            }
        }
        return true;
    }
}

class Program
{
    static void Main(string[] args)
    {
        BloomFilter bloom = new BloomFilter(100, 3);
        bloom.Add("cat");

        Console.WriteLine(bloom.Check("cat"));  // Output: True
        Console.WriteLine(bloom.Check("dog"));  // Output: False
    }
}

Sonuç:

Bloom filtreleri, büyük veri kümelerinde alan verimliliği sağlayarak hızlı ve etkili üyelik testi yapabilen güçlü bir veri yapısıdır. Her ne kadar kusursuz olmasalar da, sahip oldukları avantajlar bu eksiklikleri genellikle gölgede bırakır. Ancak, uygulama alanlarına göre yanlış pozitif olasılıklarının ve silme işlemi yapılamamasının göz önünde bulundurulması önemlidir. Daha gelişmiş ihtiyaçlar için Counting Bloom Filter gibi varyasyonlar kullanılabilir.