რა არის Bloom filter და რა კომპრომისი ახდენს იგი?

Question

Accepted Answer

**Bloom filter** არის სივრცის თვალსაზრისით ეფექტური **ალბათური** სტრუქტურა, რომელიც პასუხობს სიმრავლის წევრობას ერთი მაქნიშვრით: შეიძლება ჰქონდეს **ცრუ დადებითი** შედეგი, მაგრამ **არასდროს ცრუ უარყოფითი**. "რა თქმა უნდა არ არის იქ" დაზუსტებულია; "შესაძლოა იქ არის" საჭიროებს რეალურ შემოწმებას.

## როგორ მუშაობს

`m` ბიტის და `k` hash ფუნქციის bit მასივი. ელემენტის **დასამატებლად**, დააყენეთ `k` ბიტი, რომელზეც იგი hash-ის. **გამოკითხვისთვის**, შეამოწმეთ ის `k` ბიტი — თუ რომელიმე არის 0, ელემენტი რა თქმა უნდა არ არის.

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
```

## Code

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list of hash fns
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = certain; True = maybe
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| ოპერაცია | დრო | სივრცე |
|---|---|---|
| add | O(k) | O(m) bit |
| query | O(k) | — |

ცრუ უარყოფითი არ არის; ცრუ დადებითი შედეგის მაჩვენებელი კლებულობს `m`-ის (და კორექტირებული `k`-ის) ზრდით.

## კომპრომისი

- **ძლიერი მხარეები:** ძალიან პატარა მეხსიერება სრული გასაღებების შენახვის წინააღმდეგ; მუდმივი დროის ოპერაციები.
- **სუსტი მხარეები:** ცრუ დადებითი შედეგი; **შენახვის შეუძლებელი** (სტანდარტული Bloom filter); წევრების დაონიშვნის შეუძლებელი.

## რატომ არის მნიშვნელოვანი

Bloom filter იაფად შეძლის თავიდან აიცილოს ძვირი სამუშაოები: ბაზები (მაგალითად Cassandra, HBase) იყენებენ მათ, რომ თავიდან აიცილონ დისკის წაკითხვა გასაღებებისთვის, რომლებიც **რა თქმა უნდა** დიკში არ არის.

ისინი განასახიერებენ კლასიკურ სისტემის კომპრომისს — მიმიჯოს მცირე, შეზღუდული შეცდომის სიხშირე დიდი შემცირების სანაცვლოდ მეხსიერებასა და I/O-ში.