विकिपीडिया कहते हैं:
एक खाली ब्लूम फ़िल्टर एम बिट्स की एक बिट सरणी है,सभी को 0 पर सेट किया गया है। इसके अलग-अलग हैश फ़ंक्शंस भी परिभाषित किए जाने चाहिए, जिनमें से प्रत्येक एक समान यादृच्छिक वितरण के साथ एम सरणी पदों में से किसी एक को सेट करता है या कुछ सेट तत्व रखता है।
मैंने लेख पढ़ा, लेकिन मुझे नहीं पता कि कैसे के निर्धारित किया जाता है। क्या यह तालिका के आकार का एक कार्य है?
इसके अलावा, मैंने लिखा हैश टेबल में मैंने एक सरल उपयोग कियालेकिन हैश आकार के स्वचालित रूप से बढ़ने के लिए प्रभावी एल्गोरिदम। मूल रूप से, यदि तालिका में 50% से अधिक बाल्टी भर जाती हैं, तो मैं तालिका के आकार को दोगुना कर दूंगा। मुझे संदेह है कि आप अभी भी इसे खिलाने के साथ करना चाहते हैं झूठी सकारात्मक को कम करने के लिए फ़िल्टर करें। सही?
उत्तर:
उत्तर № 1 के लिए 39दिया हुआ:
n: आपके फ़िल्टर में कितनी वस्तुओं की अपेक्षा है (उदा। 216,553)p: आपकी स्वीकार्य झूठी सकारात्मक दर {0..1} (उदा।0.01→ 1%)
हम गणना करना चाहते हैं:
m: ब्लूम फ़िल्टर में आवश्यक बिट्स की संख्याk: हैश फ़ंक्शंस की संख्या हमें लागू करनी चाहिए
सूत्र:
m = -n*ln(p) / (ln(2)^2) बिट्स की संख्या
k = m/n * ln(2) हैश फ़ंक्शन की संख्या
हमारे मामले में:
m=-216553*ln(0.01) / (ln(2)^2)=997263 / 0.48045=2,075,686बिट्स (253 केबी)k=m/n * ln(2)=2075686/216553 * 0.693147=6.46हैश फ़ंक्शन (7 हैश फ़ंक्शन)
ध्यान दें: सार्वजनिक डोमेन में जारी कोई भी कोड। कोई विशेषता आवश्यक है।
उत्तर № 2 के लिए 17
यदि आप आगे में पढ़ते हैं ब्लूम फिल्टर के बारे में विकिपीडिया लेख, तो आपको एक अनुभाग मिल जाएगा झूठी सकारात्मक की संभावना। यह खंड बताता है कि हैश फ़ंक्शन की संख्या झूठी सकारात्मकताओं की संभावनाओं को कैसे प्रभावित करती है और आपको निर्धारित करने के लिए सूत्र प्रदान करती है कश्मीर वांछित अपेक्षित प्रोब से। झूठी सकारात्मक के।
विकिपीडिया लेख से उद्धरण:
जाहिर है, झूठी की संभावना सकारात्मकएम के रूप में घटता है (संख्या सरणी में बिट्स के) बढ़ता है, और एन के रूप में बढ़ता है (डालने की संख्या तत्व) बढ़ता है। किसी दिए गए एम के लिए और एन, के मूल्य (हैश की संख्या कार्य) जो कम करता है संभावना है
जवाब के लिए 6 № 3
और इसे एक साफ छोटी मेज में रख दिया है:
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
जवाब के लिए 0 № 4
एक उत्कृष्ट है ऑनलाइन bloomfilter कैलकुलेटर।
यह इंटरैक्टिव ब्लूम फ़िल्टर कैलक्यूलेटर आपको देता हैअनुमान लगाएं और अपने ब्लूम फ़िल्टर आवश्यकताओं के लिए गुणांक खोजें। यह आपको दृश्यों को देखने के लिए ग्राफ दिखाता है और सभी सूत्रों को प्रदान करता है उदाहरण के लिए, 216,553 के लिए गणना n संभावना के साथ आइटम p 0.01 का:
n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));