ब्लूम फ़िल्टर: क्या अवयव समुच्चय में है?
ब्लूम फ़िल्टर (Bloom filter) एक प्रायिकतात्मक संरचना है, जिससे हम कुछ हद तक प्रायिकता के साथ बता सकते हैं कि कोई अवयव x समुच्चय M में है या नहीं।
उदाहरण के लिए, हमारे सिस्टम में हमें मापना है कि उपयोगकर्ताओं ने किसी विज्ञापन बैनर पर कितनी बार क्लिक किया। प्रत्येक क्लिक के बाद हमारे पास एक HTTP GET अनुरोध आता है, जो बताता है कि उपयोगकर्ता XYZ ने विज्ञापन 123 पर क्लिक किया। कभी-कभी उपयोगकर्ता गलती से माउस से डबल-क्लिक कर देता है और हमारे पास दो अनुरोध आ जाते हैं। हम इन अनुरोधों को छाँटना चाहेंगे और डेटाबेस में उन्हें एक क्लिक के रूप में दर्ज करना चाहेंगे।
इसलिए हमें एक ऐसा एप्लिकेशन चाहिए, जो क्लिक के संदेशों वाला चैनल पढ़े और दोहराव को छाँट दे। यह हम कैसे करेंगे? प्रत्येक ऐसे संदेश का कोई ID होता है, इसलिए हमें पूरे संदेश की तुलना करने की ज़रूरत नहीं है, बस यह जानना काफ़ी है कि क्या हमने पहले कभी उसी ID वाला संदेश संसाधित किया है। संदेशों की स्ट्रीम (यहाँ सरलता के लिए सरणी) से दोहराव हटाने वाला JavaScript का सरल कोड ऐसा दिख सकता है:
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}]
var processedIds = {};
messages.forEach(function(message) {
if (!processedIds[message.id]) {
processedIds[message.id] = true;
console.log(message);
}
});
// प्रिंट करेगा: { id: "123" } { id: "456" } { id: "789" }
यह हल तब तक काम करेगा, जब तक मेमोरी ख़त्म न हो जाए — और वह एक दिन ख़त्म होगी, क्योंकि समुच्चय processedIds समय के साथ केवल बढ़ता ही जाएगा। स्वाभाविक है कि हम आँकड़ों की कोई समय-सीमा जोड़ सकते हैं — उदाहरण के लिए, हर बार एक घंटे से पुराने संदेश हटा सकते हैं या ऐसा ही कुछ।
बुरा तब है, जब यह भी पर्याप्त न हो। क्या हो, यदि हमें समुच्चय processedIds में कम से कम एक दिन के आँकड़े रखने हों और हम, मान लीजिए, प्रति सेकंड दस हज़ार संदेशों से गुज़रते हों? सबसे बुरी स्थिति में हमें 86,40,00,000 तक पहचानकर्ता सहेजने होंगे। यदि हम uuid v4 का प्रयोग करते हैं, तो प्रत्येक ID की लंबाई 36 है, जिसका अर्थ है कि एक दिन के लिए हमें कम से कम 31 GB सहेजने होंगे। यह थोड़ा ज़्यादा है। क्या मेमोरी की यह आवश्यकता घटाई नहीं जा सकती?
ब्लूम फ़िल्टर
पूरा ID सहेजने के बजाय हम केवल उसका हैश सहेज सकते हैं। हम सामान्य murmurhash का प्रयोग कर सकते हैं, जो प्रत्येक स्ट्रिंग के लिए 32-बिट पूर्णांक लौटाता है और जिसका बंटन भी अच्छा है:
var murmurhash = require("murmurhash");
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var processedHashedIds = {};
messages.forEach(function(message) {
var hashedId = murmurhash.v2(message.id);
if (!processedHashedIds[hashedId]) {
processedHashedIds[hashedId] = true;
console.log(message);
}
});
// प्रिंट करेगा: { id: "123" } { id: "456" } { id: "789" }
आगे हम बिट सरणी वाली तरकीब अपनाएँगे। यह ऐसी सरणी है, जिसमें हम केवल शून्य और 1 सहेजेंगे। यदि हमारे पास n-बिट हैश फलन है, तो हमें 2n आकार का सदिश चाहिए, ताकि हम सदिश में हैश फलन के सभी संभव आउटपुट तक पहुँच सकें। विचार यह है कि शुरुआत में सदिश में केवल शून्य होते हैं। फिर यदि इनपुट "123" के लिए हैश फलन संख्या 47 लौटाता है, तो हम बस सदिश में सूचकांक 47 पर 1 रख देते हैं। इससे हम दर्ज कर लेते हैं कि मान 47 वाला हैश हम देख चुके हैं।
var n = 8;
var numberOfValues = Math.pow(2, n);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var bitVector = new Array(numberOfValues);
messages.forEach(function(message) {
var hashedId = murmurhash.v2(message.id) % numberOfValues;
if (!bitVector[hashedId]) {
bitVector[hashedId] = true;
console.log(message);
}
});
// प्रिंट करेगा: { id: "123" } { id: "456" } { id: "789" }
कोड % numberOfValues से हमने murmurhash को बस इस तरह काटा है कि वह n-बिट हैश फलन बन जाए, और कुछ नहीं। और यही ब्लूम फ़िल्टर है। हालाँकि बहुत ही अपभ्रष्ट (degenerate) रूप में। इस तरीके की समस्या स्वाभाविक रूप से वे टकराव हैं, जो अनिवार्य रूप से होंगे। भिन्न इनपुट मानों का आउटपुट हैश एक ही हो सकता है। इसलिए टकराव की प्रायिकता घटाने के लिए हम केवल एक हैश फलन नहीं, बल्कि कई हैश फलनों का प्रयोग करेंगे। कई हैश फलन हम, उदाहरण के लिए, इनपुट मान में कोई सॉल्ट (salt) जोड़कर बना सकते हैं। भिन्न n-बिट हैश फलन बनाने वाला एक सरल फलन ऐसा दिख सकता है:
var murmurhash = require("murmurhash");
function createNBitHashFunction(n, salt) {
var upperBound = Math.pow(2, n);
return function(inputString) {
return murmurhash.v2(inputString + salt) % upperBound;
}
}
var firstHashFunction = createNBitHashFunction(8, "nejakaSul");
var secondHashFunction = createNBitHashFunction(8, "nejakaJinaSul");
console.log(firstHashFunction("123")); // 42
console.log(secondHashFunction("123")); // 174
(यहाँ “nejakaSul” और “nejakaJinaSul” चेक भाषा में “कोई सॉल्ट” और “कोई दूसरा सॉल्ट” हैं; दिखाए गए आउटपुट 42 और 174 इन्हीं स्ट्रिंगों पर निर्भर करते हैं।)
ब्लूम फ़िल्टर को निरूपित करने वाला क्लास हम इस प्रकार लिख सकते हैं:
function BloomFilter(numberOfHashFunctions, numberOfBits) {
this.reset(numberOfHashFunctions, numberOfBits);
}
BloomFilter.prototype.reset = function(numberOfHashFunctions, numberOfBits) {
this.bitVector = new Array(Math.pow(2, numberOfBits));
this.hashFunctions = [];
for (var i = 0; i < numberOfHashFunctions; i++) {
this.hashFunctions.push(createNBitHashFunction(numberOfBits, i.toString()));
}
}
BloomFilter.prototype.add = function(item) {
var checksum;
for (var i = 0; i < this.hashFunctions.length; i++) {
checksum = this.hashFunctions[i](item);
this.bitVector[checksum] = true;
}
}
BloomFilter.prototype.contains = function(item) {
var checksum;
for (var i = 0; i < this.hashFunctions.length; i++) {
checksum = this.hashFunctions[i](item);
if (!this.bitVector[checksum]) {
return false;
}
}
return true;
}
- विधि (method)
addब्लूम फ़िल्टर में अवयव जोड़ती है: यह सभी हैश फलनों से हैश परिकलित करती है और संगत सूचकांक परtrueसहेजती है। - विधि
containsयह जाँचती है कि दिया गया अवयव ब्लूम फ़िल्टर में है या नहीं।
ब्लूम फ़िल्टर का प्रयोग आसान है:
var bloomFilter = new BloomFilter(3, 8);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
messages.forEach(function(message) {
if (!bloomFilter.contains(message.id)) {
bloomFilter.add(message.id);
console.log(message);
}
});
// प्रिंट करेगा: { id: "123" } { id: "456" } { id: "789" }
और आधारभूत ब्लूम फ़िल्टर का पूरा जादू यही है। इसके ये आधारभूत गुण हैं:
- यदि विधि
containsउत्तर दे कि दिया गया अवयव ब्लूम फ़िल्टर में नहीं है, तो इसका अर्थ है कि आपने वह अवयव उसमें सचमुच कभी नहीं डाला। - यदि विधि उत्तर दे कि दिया गया अवयव ब्लूम फ़िल्टर में है, तो इसका अनिवार्य रूप से यह अर्थ नहीं कि आपने वह अवयव उसमें सचमुच डाला था — हैश फलनों का टकराव हो सकता है।
- सामान्य नियम: यदि आप गलत उत्तर की प्रायिकता घटाना चाहते हैं, तो हैश फलनों की संख्या बढ़ाइए या उनका आकार (यानी आउटपुट मान का आकार) बढ़ाइए।
- आप जितने अधिक हैश फलन प्रयोग करेंगे, ब्लूम फ़िल्टर उतना ही धीमा होगा।
- आप जितने बड़े हैश फलन प्रयोग करेंगे, ब्लूम फ़िल्टर उतनी ही अधिक जगह लेगा।
- यदि आप एक बार कोई अवयव ब्लूम फ़िल्टर में डाल दें, तो उसे हटाना संभव नहीं है।