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 ஆக இருந்தால் தொகுப்பிலிருந்து எந்த ஜோடியையும் (,) அகற்றுவதற்கும் சமம். ஒரு ஏ. வி. எல் மரம் செயல்படுத்தலைப் பயன்படுத்தி, வழிமுறை ஒரு இயங்கும் நேரத்தைக் கொண்டுள்ளது. இடத் தேவையை மதிப்பிடுவதற்கு, கூறுகள் சாத்தியமான மதிப்புகளைக் கொண்டிருக்கலாம் என்று வைத்துக்கொள்வோம், எனவே ஒரு மதிப்பின் சேமிப்புக்கு பிட்கள் தேவை. ஒவ்வொரு கவுண்டருக்கும் அதிக மதிப்பு இருக்கலாம் என்பதால், அதன் சேமிப்பகத்திற்கு பிட்கள் தேவை. எனவே, மதிப்பு-கவுண்டர் ஜோடிகளுக்கு, இடத்தின் தேவை. ஸ்ட்ரீமிங் வழிமுறைகளின் துறையில், முதல் பாஸில் மிஸ்ரா-கிரைஸ் வழிமுறையின் வெளியீடு ஒரு சுருக்கம் என்று அழைக்கப்படலாம், மேலும் தரவு ஸ்ட்ரீம் மாதிரியில் அடிக்கடி வரும் கூறுகளின் சிக்கலைத் தீர்க்க அத்தகைய சுருக்கங்கள் பயன்படுத்தப்படுகின்றன. ஒரு ஸ்ட்ரீமிங் வழிமுறை ஒரு ஸ்ட்ரீம் எனப்படும் தரவு உருப்படிகளின் பட்டியலின் மீது ஒரு சிறிய, வரம்புக்குட்பட்ட எண்ணிக்கையிலான பாஸ்களை உருவாக்குகிறது. இது ஒரு பதிலை உருவாக்க பட்டியலின் அளவில் அதிகபட்ச மடக்கை கூடுதல் இடத்தைப் பயன்படுத்தி உறுப்புகளை செயலாக்குகிறது. மிஸ்ரா-கிரைஸ் சுருக்கம் என்ற சொல் கிரஹாம் கோர்மோட் என்பவரால் உருவாக்கப்பட்டதாகத் தெரிகிறது. குறிப்புகள் ஸ்ட்ரீமிங் வழிமுறைகள்