Approximate counting algorithm
अनुमानित गणना एल्गोरिथ्म स्मृति की एक छोटी मात्रा का उपयोग करके बड़ी संख्या में घटनाओं की गिनती की अनुमति देता है। बेल लैब्स के रॉबर्ट मॉरिस द्वारा 1977 में आविष्कार किया गया, यह काउंटर को बढ़ाने के लिए संभावित तकनीकों का उपयोग करता है। 1980 के दशक की शुरुआत में आई. एन. आर. आई. ए. रॉक्वेनकोर्ट के फिलिप फ्लैजोलेट द्वारा इसका पूरी तरह से विश्लेषण किया गया था, जिन्होंने अनुमानित गिनती नाम गढ़ा था, और अनुसंधान समुदाय के बीच इसकी मान्यता में दृढ़ता से योगदान दिया था। जब अनुमान की उच्च गुणवत्ता और विफलता की कम संभावना पर ध्यान केंद्रित किया गया, तो नेल्सन और यू ने दिखाया कि मॉरिस काउंटर में बहुत कम संशोधन समस्या के लिए सभी एल्गोरिदम के बीच स्पर्शोन्मुख रूप से इष्टतम है। एल्गोरिदम को स्ट्रीमिंग एल्गोरिदम के अग्रदूतों में से एक माना जाता है, और डेटा स्ट्रीम के आवृत्ति क्षणों को निर्धारित करने की अधिक सामान्य समस्या क्षेत्र के लिए केंद्रीय रही है। ऑपरेशन का सिद्धांत मॉरिस के एल्गोरिथ्म का उपयोग करते हुए, काउंटर वास्तविक गणना के "परिमाण अनुमान के क्रम" का प्रतिनिधित्व करता है। अनुमान गणितीय रूप से निष्पक्ष है। काउंटर को बढ़ाने के लिए, एक छद्म-यादृच्छिक घटना का उपयोग किया जाता है, जैसे कि वृद्धि एक संभावित घटना है। जगह बचाने के लिए, केवल घातांक रखा जाता है। उदाहरण के लिए, आधार 2 में, काउंटर गणना को 1,2,4,8,16,32 और दो की सभी शक्तियों का अनुमान लगा सकता है। स्मृति की आवश्यकता केवल घातांक को पकड़ने के लिए है। एक उदाहरण के रूप में, 4 से 8 तक वृद्धि करने के लिए, एक छद्म यादृच्छिक संख्या इस तरह उत्पन्न की जाएगी कि काउंटर के बढ़ने की संभावना 0.25 है। अन्यथा, काउंटर 4 पर रहता है। नीचे दी गई तालिका काउंटर के कुछ संभावित मूल्यों को दर्शाती हैः यदि काउंटर 101 का मान रखता है, जो 5 के घातांक (101 के दशमलव समकक्ष) के बराबर है, तो अनुमानित गणना, या 32 है। इस बात की काफी कम संभावना है कि वृद्धि की घटनाओं की वास्तविक गिनती 5 () थी। वृद्धि की घटनाओं की वास्तविक गिनती "लगभग 32" होने की संभावना है, लेकिन यह मनमाने ढंग से अधिक हो सकती है (39 से ऊपर की वास्तविक गिनती के लिए घटती संभावनाओं के साथ)। काउंटर मानों का चयन जबकि काउंटर मानों के रूप में 2 की शक्तियों का उपयोग करना स्मृति कुशल है, मनमाना मान एक गतिशील त्रुटि सीमा बनाते हैं, और छोटे मानों में बड़े मानों की तुलना में अधिक त्रुटि अनुपात होगा। काउंटर मानों का चयन करने के अन्य तरीके मानों का एक इष्टतम सेट प्रदान करने के लिए स्मृति उपलब्धता, वांछित त्रुटि अनुपात, या गिनती सीमा जैसे मापदंडों पर विचार करते हैं। हालांकि, जब कई काउंटर समान मान साझा करते हैं, तो सबसे बड़ी गिनती सीमा के साथ काउंटर के अनुसार मान अनुकूलित किए जाते हैं, और छोटे काउंटरों के लिए उप-इष्टतम सटीकता का उत्पादन करते हैं। स्वतंत्र काउंटर अनुमान बाल्टियों को बनाए रखते हुए शमन प्राप्त किया जाता है, जो बाल्टी में अन्य काउंटरों के लिए एक बड़े काउंटर के प्रभाव को प्रतिबंधित करता है। एल्गोरिदम एल्गोरिदम को हाथ से लागू किया जा सकता है। काउंटर को बढ़ाते समय, एक सिक्के को काउंटर के वर्तमान मूल्य के अनुरूप कई बार पलट दें। यदि यह हर बार ऊपर आता है, तो काउंटर को बढ़ाएँ। अन्यथा, इसे न बढ़ाएँ। इसे कंप्यूटर पर आसानी से प्राप्त किया जा सकता है। मान लीजिए कि काउंटर का वर्तमान मूल्य है। छद्म यादृच्छिक बिट्स उत्पन्न करना और उन सभी बिट्स के तार्किक AND का उपयोग करना और परिणाम को काउंटर में जोड़ना। चूंकि परिणाम शून्य था यदि उन छद्म-यादृच्छिक बिट्स में से कोई भी शून्य है, तो वृद्धि की संभावना प्राप्त होती है। यह प्रक्रिया हर बार काउंटर को बढ़ाने के लिए अनुरोध किए जाने पर निष्पादित की जाती है। अनुप्रयोग एल्गोरिदम पैटर्न के लिए बड़ी डेटा धाराओं की जांच करने में उपयोगी है। यह विशेष रूप से डेटा संपीड़न, दृष्टि और ध्वनि पहचान और अन्य कृत्रिम बुद्धिमत्ता अनुप्रयोगों के अनुप्रयोगों में उपयोगी है। हाइपरलॉगलॉग संदर्भ स्रोत मॉरिस, आर. को भी देखें, जो बड़ी संख्या में घटनाओं को छोटे रजिस्टरों में गिनते हैं। कम्युनिकेशंस ऑफ द एसीएम 21,10 (1978), 840-842 फ्लाजोलेट, पी. अनुमानित गणनाः एक विस्तृत विश्लेषण। बीआईटी 25, (1985), 113-134 फौच, एम., ली, सी-के., प्रोडिंगर, एच., पॉइसन-लाप्लास-मेलिन विधि यादृच्छिक एल्गोरिदम के माध्यम से अनुमानित गणना