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 হয়ে যায়। একটি এভিএল ট্রি বাস্তবায়ন ব্যবহার করে, অ্যালগরিদমটির একটি চলমান সময় রয়েছে। স্থানের প্রয়োজনীয়তা মূল্যায়ন করার জন্য, ধরে নিন যে এর উপাদানগুলির সম্ভাব্য মান থাকতে পারে, তাই একটি মান সংরক্ষণের জন্য বিট প্রয়োজন। যেহেতু প্রতিটি কাউন্টারের মান যতটা সম্ভব বেশি হতে পারে, তাই এর সঞ্চয়ের জন্য বিট প্রয়োজন। অতএব, ভ্যালু-কাউন্টার জুটির জন্য, জায়গার প্রয়োজনীয়তা হল। সারাংশ স্ট্রিমিং অ্যালগরিদমের ক্ষেত্রে, প্রথম পাসের মিশ্র-গ্রিজ অ্যালগরিদমের আউটপুটকে সারসংক্ষেপ বলা যেতে পারে এবং এই ধরনের সারসংক্ষেপগুলি ডেটা স্ট্রিম মডেলের ঘন ঘন উপাদানগুলির সমস্যা সমাধান করতে ব্যবহৃত হয়। একটি স্ট্রিমিং অ্যালগরিদম স্ট্রিম নামে পরিচিত ডেটা আইটেমের তালিকার উপর দিয়ে একটি ছোট, সীমাবদ্ধ সংখ্যক পাস তৈরি করে। এটি একটি উত্তর তৈরি করতে তালিকার আকারে অতিরিক্ত জায়গার সর্বাধিক লগারিদমিক পরিমাণ ব্যবহার করে উপাদানগুলিকে প্রক্রিয়া করে। মিশ্র-গ্রিস সারসংক্ষেপ শব্দটি গ্রাহাম করমোড দ্বারা উদ্ভাবিত হয়েছে বলে মনে করা হয়। রেফারেন্স স্ট্রিমিং অ্যালগরিদম