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 فلاجولیٹ، P. قریب قریب گنتی: ایک تفصیلی تجزیہ۔ BIT 25، (1985)، 113-134 فوکس، M.، لی، C-K.، پروڈنگر، H.، تقریبا گنتی بذریعہ پوسن-لیپلیس-میلن طریقہ بے ترتیب الگورتھم