Misra–Gries heavy hitters algorithm
मिश्रा और ग्रिस ने हेवी-हिटर समस्या को परिभाषित किया (हालांकि उन्होंने हेवी-हिटर शब्द का परिचय नहीं दिया) और पेपर फाइंडिंग रिपीटेड एलिमेंट्स में इसके लिए पहले एल्गोरिदम का वर्णन किया। उनका एल्गोरिथ्म बोयर-मूर बहुसंख्यक खोज एल्गोरिथ्म को महत्वपूर्ण तरीके से विस्तारित करता है। हेवी-हिटर समस्या का एक संस्करण इस प्रकार हैः तत्वों का एक थैला और एक पूर्णांक दिया गया है। उन मूल्यों को ढूंढें जो एक से अधिक बार आते हैं। मिश्रा-ग्रीज़ एल्गोरिथ्म एल्गोरिथ्म के दौरान अधिकांश मूल्यों और उनकी घटनाओं की संख्या को संग्रहीत करते हुए, मूल्यों पर दो पास बनाकर समस्या का समाधान करता है। मिश्रा-ग्रीज़ सबसे शुरुआती स्ट्रीमिंग एल्गोरिदम में से एक है, और इसे नीचे अनुभाग #Summaries में उन शब्दों में वर्णित किया गया है। मिश्रा-ग्रीज़ एल्गोरिथ्म एक बैग एक सेट की तरह है जिसमें एक ही मान कई बार हो सकता है। मान लीजिए कि एक थैला तत्वों की एक श्रृंखला के रूप में उपलब्ध है। एल्गोरिथ्म के अमूर्त विवरण में, हम और उसके खंडों को भी थैले के रूप में मानते हैं। अब से, थैले का एक भारी हिटर एक ऐसा मान है जो कुछ पूर्णांक के लिए इसमें कई बार से अधिक होता है। थैले के लिए एक-कम बैग निम्नलिखित ऑपरेशन को दोहराने से प्राप्त होता है जब तक कि अब संभव न होः थैले से अलग-अलग तत्वों को हटा दें। इसकी परिभाषा के अनुसार, कम किए गए थैले में अलग-अलग मानों से कम होते हैं। निम्नलिखित प्रमेय को साबित करना आसान हैः प्रमेय 1। प्रत्येक भारी-हिटर के लिए एक कम बैग का एक तत्व है। हेवी-हिटर गणना का पहला पास एक कम बैग का निर्माण करता है। दूसरा पास एक तत्व को भारी-हिटर घोषित करता है यदि यह एक से अधिक बार होता है। प्रमेय 1 के अनुसार, यह प्रक्रिया सभी और केवल भारी-प्रहारकों को निर्धारित करती है। दूसरा पास प्रोग्राम करने में आसान है, इसलिए हम केवल पहले पास का वर्णन करते हैं। निर्माण के लिए, मानों को मनमाने क्रम में स्कैन करें, विशिष्टता के लिए निम्नलिखित एल्गोरिथ्म उन्हें बढ़ते सूचकांकों के क्रम में स्कैन करता है। एल्गोरिथम का अपरिवर्तनीय यह है कि स्कैन किए गए मूल्यों के लिए एक-कम बैग है और इसमें अलग-अलग मूल्यों की संख्या है। प्रारंभ में, कोई मूल्य स्कैन नहीं किया गया है, खाली थैला है, और शून्य है। जब भी तत्व को स्कैन किया जाता है, तो अपरिवर्तनीय को संरक्षित करने के लिएः (1) यदि नहीं है, तो इसे 1 में जोड़ें और बढ़ाएं, (2) यदि है, तो इसे जोड़ें लेकिन संशोधित न करें, और (3) यदि बराबर हो जाता है, तो उससे अलग-अलग मानों को हटाकर कम करें और उचित रूप से अद्यतन करें। एल्गोरिथ्म मिश्रा-ग्रीज़ 1 = t, d: = {}, 0 है; i के लिए 0 से n-1 तक करें यदि b [i] t तो t, d: = t ≤ {b [i]}, d + 1 और t, d: = t ≤ {b [i]} एंडिफ यदि d = k तो अपडेट एंडिफ एंड से अलग-अलग मान हटा दें। फिर इस समूह का आकार है। चरण "अलग-अलग मानों को हटाएं" प्रत्येक को 1 से कम करने और फिर सेट से किसी भी जोड़ी (,) को हटाने के बराबर है यदि 0 हो जाता है। ए. वी. एल. ट्री के कार्यान्वयन का उपयोग करते हुए, एल्गोरिथ्म का चलने का समय होता है। स्थान की आवश्यकता का आकलन करने के लिए, मान लें कि के तत्वों के संभावित मूल्य हो सकते हैं, इसलिए किसी मूल्य के भंडारण के लिए बिट्स की आवश्यकता होती है। चूँकि प्रत्येक काउंटर का मूल्य उतना ही अधिक हो सकता है जितना कि, इसके भंडारण के लिए बिट्स की आवश्यकता होती है। इसलिए, मूल्य-काउंटर जोड़े के लिए, स्थान की आवश्यकता है। सारांश स्ट्रीमिंग एल्गोरिदम के क्षेत्र में, पहले पास में मिश्रा-ग्रीज़ एल्गोरिदम के आउटपुट को सारांश कहा जा सकता है, और इस तरह के सारांश का उपयोग डेटा स्ट्रीम मॉडल में लगातार तत्वों की समस्या को हल करने के लिए किया जाता है। एक स्ट्रीमिंग एल्गोरिथ्म एक धारा नामक डेटा वस्तुओं की सूची पर एक छोटी, सीमित संख्या में पास बनाता है। यह एक उत्तर देने के लिए सूची के आकार में अतिरिक्त स्थान की अधिकतम लघुगणक मात्रा का उपयोग करके तत्वों को संसाधित करता है। ऐसा प्रतीत होता है कि मिश्रा-ग्रीज़ सारांश शब्द ग्राहम कॉर्मोड द्वारा गढ़ा गया था। संदर्भ स्ट्रीमिंग एल्गोरिदम