Bloom filter કયું છે અને તે કયો સમાધાન કરે છે?

Question

Accepted Answer

**Bloom filter** એક અવકાશ-કાર્યક્ષમ **સંભાવનાત્મક** માળખું છે જે સમૂહની સભ્યપદ સાથે એક વળાંક જવાબ આપે છે: તેમાં **ખોટા હકારાત્મક** હોઈ શકે છે પરંતુ **ક્યારેય ખોટા નકારાત્મક** નહીં. "નિશ્ચિતપણે હાજર નથી" નિશ્ચિત છે; "સંભવતઃ હાજર" ને વાસ્તવિક તપાસની જરૂર છે.

## તે કેવી રીતે કામ કરે છે

`m` બિટ્સ અને `k` હેશ ફંક્શન્સની બીટ એરે. આઇટમ **ઉમેરવા માટે**, તે જે `k` બિટ્સને હેશ કરે છે તેને સેટ કરો. **ક્વેરી** કરવા માટે, તે `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"
```

## કોડ

```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) બિટ્સ |
| query | O(k) | — |

કોઈ ખોટા નકારાત્મક નહીં; ખોટી હકારાત્મક દર `m` તરીકે ઘટે છે (અને ટ્યુન્ડ `k`) વધે.

## સમાધાન

- **શક્તિઓ:** સંપૂર્ણ કીઝ સંગ્રહ કરવા કરતાં ખૂબ નાની મેમરી ફૂટપ્રિન્ટ; સતત-સમય ઑપરેશન્સ.
- **નબળાઈઓ:** ખોટા હકારાત્મક; **કાઢી નાખી શકાતા નથી** (એક માનક Bloom filter); સભ્યોને સૂચિબદ્ધ કરી શકાતા નથી.

## શા માટે તે મહત્વપૂર્ણ છે

Bloom filters સસ્તો મોંઘું કામ છોડી દે છે: ડેટાબેસ (દા.ત. Cassandra, HBase) તેનો ઉપયોગ કર્યો ડિસ્ક રીડ્સ ટાળવા માટે કે જે કીઓ **નિશ્ચિતપણે** ડિસ્ક પર નથી.

તેઓ સિસ્ટમ સમાધાનનો એક ક્લાસિક રજૂ કરે છે — મેમરી અને I/O માં વિશાળ ઘટાડોના બદલે નાના, સીમાબદ્ધ ભૂલ દરને સ્વીકાર કરો.