Bloom filter ਕੀ ਹੈ ਅਤੇ ਇਹ ਕਿਸ ਤਰ੍ਹਾਂ ਦਾ ਵਪਰਤ ਕਰਦਾ ਹੈ?

Question

Accepted Answer

A **Bloom filter** ਇੱਕ ਸਪੇਸ-ਦਾ ਅਸਰਦਾਰ **probabilistic** ਢਾਂਚਾ ਹੈ ਜੋ set membership ਦੇ ਪ੍ਰਸ਼ਨ ਦਾ ਜਵਾਬ ਇੱਕ ਮੋੜ ਦੇ ਨਾਲ ਦਿੰਦਾ ਹੈ: ਇਸ ਵਿੱਚ **false positives** ਹੋ ਸਕਦੇ ਹਨ ਪਰ **ਕਦੇ false negatives** ਨਹੀਂ। "ਪੱਕਾ ਨਹੀਂ ਹੈ" ਪੱਕਾ ਹੈ; "ਸੰਭਵ ਹੈ ਮੌਜੂਦ" ਨੂੰ ਅਸਲ ਜਾਂਚ ਦੀ ਲੋੜ ਹੈ।

## ਇਹ ਕਿਵੇਂ ਕੰਮ ਕਰਦਾ ਹੈ

`m` bits ਅਤੇ `k` hash functions ਦਾ bit array। ਕੋਈ item **ਜੋੜਨ** ਲਈ, `k` bits ਸੈੱਟ ਕਰੋ ਜੋ ਇਹ hash ਕਰਦਾ ਹੈ। **query** ਕਰਨ ਲਈ, ਉਹ `k` bits ਨੂੰ ਚੈੱਕ ਕਰੋ — ਜੇ ਕੋਈ 0 ਹੈ, ਤਾਂ item ਪੱਕਾ ਗੈਰ-ਮੌਜੂਦ ਹੈ।

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

| Operation | ਸਮਾਂ | Space |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

ਕੋਈ false negatives ਨਹੀਂ; false-positive rate ਘਟਦੀ ਹੈ ਜਿਵੇਂ `m` (ਅਤੇ tuned `k`) ਵਧੋ।

## ਵਪਰਤ

- **ਤਾਕਤਾਂ:** ਪੂਰੀ keys ਸਟੋਰ ਕਰਨ ਦੇ ਮੁਕਾਬਲੇ ਬਹੁਤ ਛੋਟਾ memory footprint; constant-time ops।
- **ਕਮਜ਼ੋਰੀਆਂ:** false positives; **ਮਿਟਾ ਨਹੀਂ ਸਕਦਾ** (ਇੱਕ standard Bloom filter); members ਨੂੰ ਸੂਚਬੱਧ ਨਹੀਂ ਕਰ ਸਕਦਾ।

## ਇਹ ਕਿਉਂ ਮਹੱਤਵਪੂਰਣ ਹੈ

Bloom filters ਮਹਿੰਗੇ ਕੰਮ ਨੂੰ ਸਸਤਾ ਛੱਡ ਦਿੰਦੇ ਹਨ: databases (ਜਿਵੇਂ Cassandra, HBase) ਉਨ੍ਹਾਂ ਨੂੰ disk reads ਨੂੰ ਰੋਕਣ ਲਈ ਵਰਤਦੇ ਹਨ ਉਨ੍ਹਾਂ keys ਲਈ ਜੋ **ਪੱਕਾ** disk ਤੇ ਨਹੀਂ ਹਨ।

ਉਹ ਇੱਕ ਕਲਾਸਿਕ systems trade-off ਨੂੰ ਦਰਸਾਉਂਦੇ ਹਨ — memory ਅਤੇ I/O ਵਿੱਚ ਬਹੁਤ ਘਟਾਉਂਦਿਆਂ ਇੱਕ ਛੋਟਾ, bounded error rate ਸਵੀਕਾਰ ਕਰੋ।