Çfarë është një filtër Bloom dhe çfarë kompromisi bën ai?

Question

Accepted Answer

Një **filtër Bloom** është një strukturë **probabilistike** të efishme në hapësirë që përgjigjet kërkesës për anëtarësinë në një bashkësi me një kthesë: mund të ketë **pozitiva të rreme** por **kurrë negative të rreme**. "Definitivisht nuk është i pranishëm" është i sigurt; "ndoshta është i pranishëm" ka nevojë për një kontroll të vërtetë.

## Si funksionon

Një grup bitesh me `m` bite dhe `k` funksione hash. Për të **shtuar** një element, vendosni `k` bitet në të cilat ai e hash-on. Për **kërkime**, kontrolloni ato `k` bite — nëse ndonjë është 0, elementi definitivisht mungon.

```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"
```

## Kodi

```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)
```

| Operacioni | Koha | Hapësira |
|---|---|---|
| add | O(k) | O(m) bite |
| query | O(k) | — |

Nuk ka negative të rreme; shkalla e pozitivave të rreme bie ndërsa `m` (dhe `k` i akorduar) rriten.

## Kompromisët

- **Forcat:** shenjë shumë e vogël e kujtesës krahasuar me ruajtjen e çelësave të plotë; operacione në kohë konstante.
- **Dobësitë:** pozitiva të rreme; **nuk mund të fshini** (një filtër Bloom standard); nuk mund të renditni anëtarë.

## Pse është i rëndësishëm

Filtrat Bloom më lirë anashkalon punën e shtrenjtë: bazat e të dhënave (p.sh. Cassandra, HBase) i përdorin ato për të shmangur leximet nga disku për çelësat që **definitivisht** nuk janë në disk.

Ata përmbajnë një kompromis klasik të sistemeve — pranoni një shkallë të vogël, të kufizuar të gabimit në këmbim të një reduktimi të madh në kujtesë dhe I/O.