Bloom ఫిల్టర్ అనేది ఒక స్థల-సమర్థ సంభావ్య నిర్మాణం, ఇది సెట్ సభ్యత్వ ప్రశ్నకు ఒక మలుపుతో సమాధానమిస్తుంది: ఇది తప్పుడు ధన కలిగి ఉండవచ్చు కానీ ఎప్పుడూ తప్పుడు ఋణ లేదు. "ఖచ్చితంగా ఉండదు" నిశ్చితమైనది; "బహుశా ఉంది" నిజమైన చెక్కు అవసరం.
బిట్ల నుండి బిట్ సరణి మరియు హ్యాష్ ఫంక్షన్లు. ఒక వస్తువు , అది హ్యాష్ చేసే బిట్లను సెట్ చేయండి. కోసం, ఆ బిట్లను తనిఖీ చేయండి — ఏదైనా 0 అయితే, వస్తువు ఖచ్చితంగా లేదు.
mkkkbits: [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"
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 ఫిల్టర్లు ఖరీదైన పనిని చవకగా దాటవేస్తాయి: డేటాబేస్లు (ఉదా Cassandra, HBase) అవి డిస్క్లో ఖచ్చితంగా లేని కీల కోసం డిస్క్ రీడ్లను నివారించడానికి ఉపయోగిస్తాయి.
వాటి ఒక సాధారణ సిస్టమ్ల సమన్వయం — మెమరీ మరియు I/O లో భారీ తగ్గింపుకు బదులుగా చిన్న, సరిహద్దు లోపం రేటును ఆమోదించండి.