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 ஐப் பயன்படுத்தி, முடிவை கவுண்டரில் சேர்க்கவும். அந்த போலி-சீரற்ற பிட்களில் ஏதேனும் பூஜ்ஜியமாக இருந்தால் இதன் விளைவாக பூஜ்ஜியமாக இருந்தது, இது அதிகரிப்பு நிகழ்தகவை அடைகிறது. கவுண்டரை அதிகரிக்க கோரிக்கை விடுக்கப்படும் ஒவ்வொரு முறையும் இந்த நடைமுறை செயல்படுத்தப்படுகிறது. பயன்பாடுகள் வடிவங்களுக்கான பெரிய தரவு நீரோடைகளை ஆராய்வதில் வழிமுறை பயனுள்ளதாக இருக்கும். தரவு சுருக்கம், பார்வை மற்றும் ஒலி அங்கீகாரம் மற்றும் பிற செயற்கை நுண்ணறிவு பயன்பாடுகளில் இது குறிப்பாக பயனுள்ளதாக இருக்கும். ஹைபர்லாக் லாக் குறிப்புகள் ஆதாரங்கள் மோரிஸ், ஆர். சிறிய பதிவேடுகளில் அதிக எண்ணிக்கையிலான நிகழ்வுகளை எண்ணுதல். ACM 21,10 (1978), 840-842 ஃபிளாஜோலெட், பி. தோராயமான எண்ணிக்கைஃ ஒரு விரிவான பகுப்பாய்வு. BIT 25, (1985), 113-134 ஃபோச்ஸ், எம்., லீ, சி. கே., ப்ரோடிங்கர், எச்., பாய்சன்-லாப்லேஸ்-மெலின் முறை மூலம் தோராயமாக எண்ணுதல் சீரற்ற வழிமுறைகள்