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 এর ক্ষমতা ব্যবহার করা মেমরি দক্ষ, নির্বিচারে মানগুলি একটি গতিশীল ত্রুটি পরিসীমা তৈরি করে এবং ছোট মানগুলির বড় মানের তুলনায় বৃহত্তর ত্রুটি অনুপাত থাকবে। পাল্টা মান নির্বাচন করার অন্যান্য পদ্ধতিগুলি মেমরি প্রাপ্যতা, পছন্দসই ত্রুটি অনুপাত বা গণনা পরিসরের মতো পরামিতিগুলি বিবেচনা করে মানগুলির একটি সর্বোত্তম সেট সরবরাহ করে। যাইহোক, যখন বেশ কয়েকটি কাউন্টার একই মান ভাগ করে নেয়, তখন বৃহত্তম গণনা পরিসীমা সহ কাউন্টার অনুসারে মানগুলি অনুকূলিত করা হয় এবং ছোট কাউন্টারগুলির জন্য উপ-সর্বোত্তম নির্ভুলতা তৈরি করে। স্বাধীন কাউন্টার প্রাক্কলন বালতি বজায় রেখে প্রশমন অর্জন করা হয়, যা বালতির অন্যান্য কাউন্টারে একটি বৃহত্তর কাউন্টারের প্রভাবকে সীমাবদ্ধ করে। অ্যালগরিদম অ্যালগরিদম হাতে প্রয়োগ করা যেতে পারে। কাউন্টারটি বৃদ্ধি করার সময়, কাউন্টারের বর্তমান মূল্যের সাথে সামঞ্জস্য রেখে একটি মুদ্রা বেশ কয়েকবার উল্টান। যদি এটি প্রতিবার মাথা উপরে উঠে আসে, তাহলে কাউন্টারটি বাড়ান। অন্যথায়, এটি বৃদ্ধি করবেন না। এটি কম্পিউটারে সহজেই করা যায়। কাউন্টারের বর্তমান মানটি ধরা যাক। ছদ্ম-এলোমেলো বিট তৈরি করা এবং সেই সমস্ত বিটের যৌক্তিক এবং ব্যবহার করে ফলাফলটি কাউন্টারে যোগ করা। ফলস্বরূপ শূন্য ছিল যদি সেই ছদ্ম-এলোমেলো বিটগুলির মধ্যে কোনওটি শূন্য হয়, যা বৃদ্ধির সম্ভাবনা অর্জন করে। প্রতিবার কাউন্টার বাড়ানোর অনুরোধ করার সময় এই পদ্ধতিটি কার্যকর করা হয়। অ্যাপ্লিকেশন অ্যালগরিদম প্যাটার্নের জন্য বড় ডেটা স্ট্রিম পরীক্ষা করতে কার্যকর। এটি তথ্য সংকোচন, দৃষ্টি এবং শব্দ শনাক্তকরণ এবং অন্যান্য কৃত্রিম বুদ্ধিমত্তার প্রয়োগের ক্ষেত্রে বিশেষভাবে কার্যকর। আরও দেখুন হাইপারলগলগ রেফারেন্স সোর্স মরিস, আর. ছোট রেজিস্টারে প্রচুর সংখ্যক ঘটনা গণনা করা হচ্ছে। কমিউনিকেশনস অফ দ্য এসিএম 21,10 (1978), 840-842 ফ্লাজলেট, পি. আনুমানিক গণনাঃ একটি বিস্তারিত বিশ্লেষণ। বিআইটি 25, (1985), 113-134 ফাউচস, এম., লি, সি-কে., প্রোডিঙ্গার, এইচ., পয়সন-ল্যাপলেস-মেলিন পদ্ধতির মাধ্যমে আনুমানিক গণনা এলোমেলো অ্যালগরিদম