Misra–Gries با تعداد محدودی شمارنده،نامزدهای پرتکرار یک جریان را نگه می‌دارد؛ اما هر نامزدِ باقیمانده لزوماً پرتکرارِ واقعی نیست. برای k=3،هدف یافتن نمادهایی با فراوانیِ بیشتر از n/3 است و حداکثر دو شمارنده نگه می‌داریم. این تمرین مرحلهٔ نامزدی را از شمارشِ دقیقِ دوباره جدا می‌کند.
باقی‌ماندن D چیزی را ثابت نمی‌کند
جریانِ اصیل ABCABCD را بخوانیم. با A وB،دو خانه پر می‌شوند. ورود C که نمادی تازه است،باعث لغو یک رخداد از A،B و خودِ C می‌شود؛ هر دو شمارنده صفر و حذف می‌شوند. همین اتفاق برای A،B،C بعدی تکرار می‌شود و در پایان فقط D با شمارنده۱ می‌ماند.
اما D فقط یک‌بار در هفت ورودی دیده شده است؛۱ بیشتر از۷/۳ نیست. کد این نامزدِ اضافی را واقعاً تولید می‌کند و گذرِ دوم آن را رد می‌کند. اگر فقط آخرین جدول را چاپ کنیم و نام آن را «پرتکرارهای قطعی» بگذاریم،جوابِ نادرست ساخته‌ایم.
سه شاخهٔ به‌روزرسانی
اگر نمادِ تازه از قبل در جدول باشد،شمارنده‌اش زیاد می‌شود. اگر نباشد ولی جا داشته باشیم،با شمارنده۱ وارد می‌شود. اگر جدولِ k−1 خانه‌ای پر باشد و نماد تازه متفاوت باشد،از همهٔ شمارنده‌ها یکی کم و صفرها حذف می‌شوند؛ نماد تازه هم در همان دستهٔ لغوشده حساب می‌شود و آن دور وارد جدول نمی‌شود.
دفترِ هر گام،ورودی،شمارنده‌های قبل،نوع عملیات و وضعیت بعد را ثبت می‌کند. کد کنترل می‌کند تعداد خانه‌ها از k−1 نگذرد و هیچ شمارندهٔ صفر یا منفی باقی نماند. خودِ این دفتر برای آموزش با طول جریان رشد می‌کند؛ فقط جدولِ نامزدها کران k−1 دارد.
چرا نامزدِ واقعی از دست نمی‌رود؟
لغو یک دستهٔ k نمادِ متمایز،از فراوانیِ هر نماد حداکثر یکی کم می‌کند و اندازهٔ باقیمانده را kتا پایین می‌آورد. این ایده،نامزدهای با فراوانیِ واقعاً بیشتر از n/k را در مجموعهٔ باقیمانده حفظ می‌کند. عکسِ آن برقرار نیست؛ مثال D همین تفاوت را نشان داد.
در فایل،Counter مستقل همهٔ فراوانی‌های اصلی را حساب می‌کند و بررسی می‌شود هر پرتکرارِ واقعی میان نامزدها باشد. سپس فقط نامزدهایی پذیرفته می‌شوند که count×k>n دارند. مقایسه با ضربِ صحیح انجام می‌شود تا مرزِ دقیق به گردکردن اعشاری وابسته نشود.
گذر دوم به کدام داده نیاز دارد؟
fixture یک رشتهٔ ساختگیِ قابل دوباره‌خواندن دارد؛ پس شمارشِ دقیقِ دوباره واقعاً ممکن است. در جریانِ one-shot که دیگر در دسترس نیست،همین کد نمی‌تواند از هیچ،فراوانی اصلی را بازسازی کند. شمارندهٔ باقیمانده،شمارِ رخدادهای لغونشده است،نه تعدادِ کلِ مشاهده‌شدهٔ آن نماد.
سه نمونهٔ دیگر،AAABBCDAA،AABBCC و رشتهٔ خالی‌اند. در AABBCC هر نماد دقیقاً n/3 رخ داده و هیچ‌کدام شرطِ «بیشتر از» را ندارد. در مثال AAABBCDAA،مقایسهٔ شمارندهٔ باقیمانده با شمارشِ اصلی،اثرِ لغو را آشکار می‌کند. تمام وضعیت‌ها در JSON هستند.
آزمونِ محدود ولی مستقل
همهٔ رشته‌های الفبای A،B،C با طول صفر تا۷،برای kهای۲،۳و۴ اجرا شده‌اند؛ مجموعاً۹۸۴۰حالت. نامزدها با oracle دقیق مقایسه و پاسخِ بعد از گذر دوم برابر کنترل شده است. k بولین،۱،۹ و۲٫۵ طبق قراردادِ محلی رد می‌شوند؛ این نسخه حداکثر۶۴نمادِ تک‌نویسه‌ای می‌پذیرد.
انتخاب top-k امتیازهای معلوم را رتبه‌بندی می‌کند و نمونه‌گیری مخزنی نمونه‌ای تصادفی از رخدادها می‌خواهد؛ اینجا نامزدِ فراوانی با لغوِ شمارنده ساخته می‌شود. برای ادامه به مبانی هوش مصنوعی بروید؛ هیچ شمارشِ تماس واقعی،الگوریتم داخلی اپرا یا نتیجهٔ فروش از این تمرین اعلام نمی‌شود.
فایل تمرین و منبع
کد مستقلِ تمرین و کنترل‌ها؛ Python · ورودی‌ها و تمام خروجی واقعیِ همین تمرین؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.