Bloom வடிப்பி என்றால் என்ன மற்றும் அது என்ன சமரசம் செய்கிறது?

Question

Accepted Answer

**Bloom வடிப்பி** என்பது ஒரு இடத்தை சேமிக்கும் **நிகழ்தகவு** கட்டமைப்பு ஆகும், இது தொகுப்பு உறுப்பினத்துடன் ஒரு திருப்புடன் பதிலளிக்கிறது: இது **தவறான நேர்மறை** கொண்டிருக்கலாம் ஆனால் **ஒருபோதும் தவறான எதிர்மறை** இல்லை. "நிச்சயமாக இல்லை" உறுதியானது; "ஒருவேளை உள்ளது" ஒரு உண்மையான சரிபார்ப்பு தேவைப்படுகிறது.

## அது எப்படி செயல்படுகிறது

`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 வடிப்பி); உறுப்பினர்களை பட்டியலிட முடியாது.

## ஏன் முக்கியமாக இருக்கிறது

Bloom வடிப்பிகள் விலையுயர்ந்த வேலை மலிவாக தவிர்க்கின்றன: தரவுத்தளங்கள் (மி.கா. Cassandra, HBase) அவை நিச்சயமாக வட்டில் **இல்லாத** விசைகளுக்கான வட்டு வாசனைகளைத் தவிர்க்க பயன்படுத்துகின்றன.

அவை ஒரு சாதாரண அமைப்பு சமரசத்தைப் பிரதிபலிக்கின்றன — நினைவக மற்றும் I/O இல் பெரிய குறைப்பின் பதிலாக ஒரு சிறிய, வரம்பற்ற பிழை விகிதத்தை ஏற்றுக்கொள்ளுங்கள்.