Kas yra Bloom filtras ir kokį kompromisą jis daro?

Question

Accepted Answer

**Bloom filtras** yra erdvės atžvilgiu efektyvus **probabilinis** paieškos saityne narystės nustatymo paieškos rezultatas su viena išlyga: gali turėti **klaidingus teigiamus** rezultatus, tačiau **niekada neturi klaidingų neigiamų** rezultatų. "Tikrai nėra" yra tikra; "galbūt yra" reikalinga reali patikra.

## Kaip tai veikia

Bitų masyvas iš `m` bitų ir `k` hash funkcijų. Norėdami **pridėti** elementą, nustatykite `k` bitų, į kuriuos jis grąžina hash. Norėdami **daryti užklausą**, patikrinkite tuos `k` bitus — jei kuris nors yra 0, elementas tikrai nėra.

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

| Operacija | Laikas | Vieta |
|---|---|---|
| add | O(k) | O(m) bitų |
| query | O(k) | — |

Nėra klaidingų neigiamų rezultatų; klaidingų teigiamų rezultatų dažnis mažėja didėjant `m` (ir nustatytas `k`).

## Kompromisai

- **Stiprybės:** labai mažas atminties žemėlapis palyginti su visų raktų saugojimu; pastovaus laiko operacijos.
- **Silpnybės:** klaidingi teigiami rezultatai; **negali ištrinti** (standartinis Bloom filtras); negali išvardinti narių.

## Kodėl tai svarbu

Bloom filtrai pigiai išvengti brangių darbų: duomenų bazės (pvz., Cassandra, HBase) jas naudoja, kad išvengtų disko skaitymų raktams, kurių **tikrai** nėra diske.

Jie įkūnija klasikinį sistemų kompromisą — priimti mažą, ribotą klaidų dažnį, siekiant žymiai sumažinti atmintį ir I/O.