خوارزمية العد التقريبي

تتيح خوارزمية العد التقريبي عدّ عدد كبير من الأحداث باستخدام ذاكرة صغيرة. ابتكرها روبرت موريس من مختبرات بيل عام 1977 ، وتستخدم تقنيات احتمالية لزيادة العداد . خضعت الخوارزمية لتحليل شامل في أوائل ثمانينيات القرن الماضي على يد فيليب فلاجو من معهد INRIA روكوينكورت، الذي صاغ مصطلح " العد التقريبي" ، وساهم بشكل كبير في انتشارها بين أوساط الباحثين. عند التركيز على جودة التقريب العالية وانخفاض احتمالية الفشل، أظهر نيلسون ويو أن تعديلًا طفيفًا جدًا على عداد موريس يُعدّ الأمثل تقاربًا بين جميع الخوارزميات المُستخدمة لحلّ هذه المشكلة. ^{[ 1 ]} تُعتبر هذه الخوارزمية من أوائل الخوارزميات التي سبقت خوارزميات معالجة البيانات المتدفقة ، وقد شكّلت مشكلة تحديد لحظات التردد لتدفق البيانات محورًا أساسيًا في هذا المجال.

نظرية التشغيل

باستخدام خوارزمية موريس، يمثل العداد " تقديرًا تقريبيًا " للعدد الفعلي. هذا التقريب غير متحيز رياضيًا .

لزيادة العداد، يُستخدم حدث شبه عشوائي ، بحيث تكون الزيادة حدثًا احتماليًا. ولتوفير المساحة، يُحتفظ فقط بالأس. على سبيل المثال، في النظام العددي ذي الأساس 2، يمكن للعداد تقدير العدد على أنه 1، 2، 4، 8، 16، 32، وجميع قوى العدد 2. ويقتصر متطلب الذاكرة على تخزين الأس فقط .

على سبيل المثال، لزيادة العداد من 4 إلى 8، يتم توليد رقم شبه عشوائي بحيث يكون احتمال زيادة العداد 0.25. وإلا، يبقى العداد عند 4.

يوضح الجدول أدناه بعض القيم المحتملة للعداد:

القيمة الثنائية المخزنة للعداد	تقريب	نطاق القيم المحتملة للعدد الفعلي	التوقع (عدد كبير بما فيه الكفاية، توزيع منتظم)
0	1	0، أو القيمة الأولية	0
1	2	واحد أو أكثر	2
10	4	اثنان أو أكثر	6
11	8	3 أو أكثر	14
100	16	4 أو أكثر	30
101	32	5 أو أكثر	62

إذا كان العداد يحمل القيمة 101، والتي تعادل أسًا قدره 5 (القيمة العشرية المكافئة للعدد 101)، فإن العدد المُقدَّر هو $2^{5}$ أو 32. هناك احتمال ضئيل إلى حد ما أن يكون العدد الفعلي لأحداث الزيادة هو 5 ( ${\frac {1}{1024}}=1\times {\frac {1}{2}}\times {\frac {1}{4}}\times {\frac {1}{8}}\times {\frac {1}{16}}$ ). من المرجح أن يكون العدد الفعلي لأحداث الزيادة "حوالي 32"، ولكن يمكن أن يكون مرتفعًا بشكل تعسفي (مع انخفاض احتمالات الأعداد الفعلية التي تزيد عن 39).

تحديد قيم العداد

على الرغم من أن استخدام قوى العدد 2 كقيم للعداد يُعدّ فعالاً من حيث استخدام الذاكرة، إلا أن القيم العشوائية تميل إلى إنشاء نطاق خطأ ديناميكي، وستكون نسبة الخطأ في القيم الأصغر أكبر من القيم الأكبر. وتأخذ طرق أخرى لاختيار قيم العداد في الاعتبار معايير مثل توافر الذاكرة، ونسبة الخطأ المطلوبة، أو نطاق العد لتوفير مجموعة مثالية من القيم. ^{[ 2 ]}

مع ذلك، عندما تتشارك عدة عدادات نفس القيم، تُحسَّن القيم وفقًا للعداد ذي نطاق العد الأكبر، مما ينتج عنه دقة دون المستوى الأمثل للعدادات الأصغر. ويتم التخفيف من هذه المشكلة من خلال الحفاظ على مجموعات تقدير العدادات المستقلة، ^{[ 3 ]} التي تحد من تأثير العداد الأكبر على العدادات الأخرى في المجموعة.

الخوارزمية

يمكن تنفيذ الخوارزمية يدويًا. عند زيادة العداد، تُقلب قطعة نقدية عددًا من المرات يساوي قيمة العداد الحالية. إذا ظهرت الصورة في كل مرة، يُزاد العداد. وإلا، فلا يُزاد.

يمكن تحقيق ذلك بسهولة على جهاز كمبيوتر. لنفترض $c$ لتكن القيمة الحالية للعداد. توليد $c$ يتم توليد بتات شبه عشوائية، ثم يتم تطبيق عملية AND المنطقية على جميع هذه البتات، ويُضاف الناتج إلى العداد. وبما أن الناتج يساوي صفرًا إذا كانت أي من هذه البتات شبه العشوائية تساوي صفرًا، فإن احتمال الزيادة يكون 0. $2^{-c}$ يتم تنفيذ هذا الإجراء في كل مرة يتم فيها تقديم طلب لزيادة العداد.

التطبيقات

تُعدّ هذه الخوارزمية مفيدة في فحص تدفقات البيانات الضخمة بحثًا عن الأنماط. وهذا مفيد بشكل خاص في تطبيقات ضغط البيانات ، والتعرف على الصور والأصوات، وغيرها من تطبيقات الذكاء الاصطناعي .

انظر أيضاً

هايبرلوغ لوج

مراجع

↑ نيلسون، جيلاني؛ يو، هواشنغ (2020). "الحدود المثلى للعد التقريبي". arXiv : 2010.02116 .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
↑ تسيدون، إيريز، إيدو هانيل، وإسحاق كيسلاسي. "يحتاج المقدّرون أيضًا إلى قيم مشتركة للنمو معًا." وقائع مؤتمر INFOCOM، 2012، معهد مهندسي الكهرباء والإلكترونيات. معهد مهندسي الكهرباء والإلكترونيات، 2012.
↑ إينزيغر، ج.؛ فيلمان، ب.؛ كاسنر، ي. (أبريل 2015). "مجموعات تقدير العدادات المستقلة". مؤتمر IEEE للاتصالات الحاسوبية لعام 2015 (INFOCOM) . الصفحات 2560-2568 . doi : 10.1109/INFOCOM.2015.7218646 . ISBN 978-1-4799-8381-0. S2CID 15673730 .

مصادر

موريس، ر. عدّ أعداد كبيرة من الأحداث في سجلات صغيرة . اتصالات رابطة آلات الحوسبة 21، 10 (1978)، 840-842
فلاجو، ب. العد التقريبي: تحليل مفصل . BIT 25، (1985)، 113-134
فوتشز، م.، لي، س.ك.، برودينجر، هـ.، العد التقريبي باستخدام طريقة بواسون-لابلاس-ميلين

[ny2020-1] نيلسون، جيلاني؛ يو، هواشنغ (2020). "الحدود المثلى للعد التقريبي". arXiv : 2010.02116 .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=

[2] تسيدون، إيريز، إيدو هانيل، وإسحاق كيسلاسي. "يحتاج المقدّرون أيضًا إلى قيم مشتركة للنمو معًا." وقائع مؤتمر INFOCOM، 2012، معهد مهندسي الكهرباء والإلكترونيات. معهد مهندسي الكهرباء والإلكترونيات، 2012.

[3] إينزيغر، ج.؛ فيلمان، ب.؛ كاسنر، ي. (أبريل 2015). "مجموعات تقدير العدادات المستقلة". مؤتمر IEEE للاتصالات الحاسوبية لعام 2015 (INFOCOM) . الصفحات 2560-2568 . doi : 10.1109/INFOCOM.2015.7218646 . ISBN 978-1-4799-8381-0. S2CID 15673730 .

[ 1 ]

[ 2 ]

[ 3 ]