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 ہو جائے۔ اے وی ایل ٹری کے نفاذ کا استعمال کرتے ہوئے، الگورتھم کا رننگ ٹائم ہوتا ہے۔ جگہ کی ضرورت کا اندازہ لگانے کے لیے، فرض کریں کہ کے عناصر کی ممکنہ اقدار ہو سکتی ہیں، اس لیے قدر کے ذخیرہ کرنے کے لیے بٹس کی ضرورت ہوتی ہے۔ چونکہ ہر کاؤنٹر کی قیمت اتنی ہی زیادہ ہو سکتی ہے، اس لیے اس کے اسٹوریج کو بٹس کی ضرورت ہوتی ہے۔ لہذا، ویلیو-کاؤنٹر جوڑوں کے لیے، جگہ کی ضرورت ہے۔ خلاصہ اسٹریمنگ الگورتھم کے میدان میں، پہلے پاس میں مشرا-گریز الگورتھم کے آؤٹ پٹ کو خلاصہ کہا جا سکتا ہے، اور اس طرح کے خلاصے کو ڈیٹا اسٹریم ماڈل میں فریکوینٹ عناصر کے مسئلے کو حل کرنے کے لیے استعمال کیا جاتا ہے۔ ایک اسٹریمنگ الگورتھم ڈیٹا آئٹمز کی فہرست پر ایک چھوٹی، محدود تعداد میں پاس بناتا ہے جسے اسٹریم کہا جاتا ہے۔ یہ جواب پیدا کرنے کے لیے فہرست کے سائز میں زیادہ سے زیادہ لوگرتھمک اضافی جگہ کا استعمال کرتے ہوئے عناصر پر کارروائی کرتا ہے۔ مشرا-گریس خلاصہ کی اصطلاح گراہم کورموڈ نے وضع کی ہے۔ حوالہ جات اسٹریمنگ الگورتھم