مشكلة العد المميز

في علوم الحاسوب، تُعرف مسألة عدّ العناصر المميزة ^{[ 1 ]} (المعروفة أيضًا في الرياضيات التطبيقية بمسألة تقدير عدد العناصر ) بأنها مسألة إيجاد عدد العناصر المميزة في تدفق بيانات يحتوي على عناصر متكررة. هذه مسألة معروفة ولها تطبيقات عديدة. قد تمثل هذه العناصر عناوين IP لحزم البيانات التي تمر عبر جهاز توجيه ، أو زوارًا فريدين لموقع ويب، أو عناصر في قاعدة بيانات ضخمة، أو أنماطًا في تسلسل الحمض النووي ، أو عناصر شبكات RFID / المستشعرات .

مثال : لنفترض وجود سلسلة من العناصر${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$مع التكرار. دع${\displaystyle n}$يشير إلى عدد العناصر المتميزة في التدفق، مع تمثيل مجموعة العناصر المتميزة على النحو التالي:${\displaystyle \{e_{1},e_{2},\ldots ,e_{n}\}}$.

الهدف : إيجاد تقدير${\displaystyle {\widehat {n}}}$ل${\displaystyle n}$باستخدام فقط${\displaystyle m}$وحدات التخزين، حيث${\displaystyle m\ll n}$.

ومن الأمثلة على حالات مشكلة تقدير عدد العناصر هو التدفق:${\displaystyle a,b,a,c,d,b,d}$في هذه الحالة،${\displaystyle n=|\left\{{a,b,c,d}\right\}|=4}$.

الحل البسيط للمشكلة هو كما يلي:

قم بتهيئة عداد، c ، إلى الصفر.${\displaystyle c\leftarrow 0}$قم بتهيئة بنية بيانات قاموس فعالة ، D ، مثل جدول التجزئة أو شجرة البحث، حيث يمكن إجراء عمليات الإضافة والانتماء بسرعة. لكل عنصر${\displaystyle x_{i}}$يتم إصدار استعلام عن العضوية. إذا${\displaystyle x_{i}}$ليس عضواً في D (${\displaystyle x_{i}\notin D}$) يضيف${\displaystyle x_{i}}$إلى D زيادة c بمقدار واحد،${\displaystyle c\leftarrow c+1}$ خلاف ذلك (${\displaystyle x_{i}\in D}$) لا تفعل شيئًا. الإخراج${\displaystyle n=c}$.

طالما أن عدد العناصر المختلفة ليس كبيرًا جدًا، فإن المصفوفة D تتسع في الذاكرة الرئيسية ويمكن استرجاع الإجابة الدقيقة. ومع ذلك، فإن هذا الأسلوب لا يتناسب مع سعة التخزين المحدودة، أو إذا كانت العمليات الحسابية التي تُجرى لكل عنصر كبيرة.${\displaystyle x_{i}}$ينبغي تقليلها إلى الحد الأدنى. في مثل هذه الحالة، تم اقتراح العديد من خوارزميات البث التي تستخدم عددًا ثابتًا من وحدات التخزين.

لمعالجة قيود التخزين المحدودة، تستخدم خوارزميات البث عملية عشوائية لإنتاج تقدير غير دقيق لعدد العناصر المميزة.${\displaystyle n}$تقوم أحدث تقنيات التقدير بتجزئة كل عنصر${\displaystyle e_{j}}$تحويل البيانات إلى رسم تخطيطي منخفض الأبعاد باستخدام دالة تجزئة،${\displaystyle h(e_{j})}$يمكن تصنيف التقنيات المختلفة وفقًا لرسومات البيانات التي تخزنها.

دالة algorithm_d ( stream , s : int ):p = 1.0المخزن المؤقت = {}للحصول على بث مباشر :إذا كان a موجودًا في المخزن المؤقت :buffer.pop ( a )​​u = uniform ( 0 , 1 )إذا كان u < p :إذا كان طول ( المخزن المؤقت ) أقل من s :المخزن المؤقت [ أ ] = uآخر :a_p , u_p = max ( buffer.items ( ), key = lambda x : x [ 1 ] )إذا كانت u > u_p :p = uآخر :buffer.pop ( a_p )​​المخزن المؤقت [ أ ] = up = u_pإرجاع طول ( المخزن المؤقت ) / p

تهيئة${\displaystyle p\leftarrow 1}$ تهيئة الحد الأقصى لحجم المخزن المؤقت${\displaystyle s}$، أين${\displaystyle s\geq 1}$ قم بتهيئة مخزن مؤقت فارغ، B لكل عنصر${\displaystyle a_{t}}$في تدفق البيانات${\displaystyle A}$من الحجم${\displaystyle n}$افعل: إذا${\displaystyle (a_{t},u),\forall u}$إذا كان في B ، فاحذفه${\displaystyle (a_{t},u)}$من ب${\displaystyle u\leftarrow }$رقم عشوائي في${\displaystyle [0,1)}$لو${\displaystyle u<p}$ثم إذا${\displaystyle |B|<s}$ثم أدخل${\displaystyle (a_{t},u)}$في ب آخر ${\displaystyle (a',u')}$بحيث${\displaystyle u'=\max\{u'':(a'',u'')\in B,\forall a''\}}$/*${\displaystyle (a',u')}$لمن${\displaystyle u'}$أقصى قيمة في B */ لو${\displaystyle u>u'}$ثم ${\displaystyle p\leftarrow u}$ آخر يستبدل${\displaystyle (a',u')}$مع${\displaystyle (a_{t},u)}$${\displaystyle p\leftarrow u'}$نهاية حلقة الإرجاع${\displaystyle |B|/p}$.

تهيئة${\displaystyle p\leftarrow 1}$ تهيئة الحد الأقصى لحجم المخزن المؤقت${\displaystyle s}$، أين${\displaystyle s\geq 1}$ قم بتهيئة مخزن مؤقت فارغ، B لكل عنصر${\displaystyle a_{t}}$في تدفق البيانات${\displaystyle A}$من الحجم${\displaystyle n}$افعل: إذا${\displaystyle a_{t}}$إذا كان في B ، فاحذفه${\displaystyle a_{t}}$من ب${\displaystyle u\leftarrow }$رقم عشوائي في${\displaystyle [0,1)}$لو${\displaystyle u\leq p}$ثم أدخل${\displaystyle (a_{t},u)}$إلى ب بينما${\displaystyle |B|=s\wedge u<p}$ثم قم بإزالة كل عنصر من${\displaystyle (a',u')}$من B مع${\displaystyle u'>{\frac {p}{2}}}$${\displaystyle p\leftarrow {\frac {p}{2}}}$أنهِ الحلقة إذا${\displaystyle u<p}$ثم أدخل${\displaystyle (a_{t},u)}$إلى B نهاية للعودة${\displaystyle |B|/p}$.

في نسختها الموزونة، يرتبط كل عنصر بوزن، والهدف هو تقدير المجموع الكلي للأوزان. رسميًا،

مثال : سلسلة من العناصر الموزونة${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$مع التكرارات، وعدد صحيح${\displaystyle m}$. يترك${\displaystyle n}$ليكن عدد العناصر المتميزة، أي${\displaystyle n=|\left\{{x_{1},x_{2},\ldots ,x_{s}}\right\}|}$ولتكن هذه العناصر${\displaystyle \left\{{e_{1},e_{2},\ldots ,e_{n}}\right\}}$وأخيرًا، دع${\displaystyle w_{j}}$ليكن وزن${\displaystyle e_{j}}$.

الهدف : إيجاد تقدير${\displaystyle {\widehat {w}}}$ل${\displaystyle w=\sum _{j=1}^{n}w_{j}}$باستخدام فقط${\displaystyle m}$وحدات التخزين، حيث${\displaystyle m\ll n}$.

ومن الأمثلة على حالات المسألة الموزونة ما يلي:${\displaystyle a(3),b(4),a(3),c(2),d(3),b(4),d(3)}$في هذه الحالة،${\displaystyle e_{1}=a,e_{2}=b,e_{3}=c,e_{4}=d}$الأوزان هي${\displaystyle w_{1}=3,w_{2}=4,w_{3}=2,w_{4}=3}$و${\displaystyle \sum {w_{j}}=12}$.

كمثال تطبيقي،${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$قد تكون حزم بيانات IP التي يستقبلها الخادم. كل حزمة تنتمي إلى أحد${\displaystyle n}$تدفقات بروتوكول الإنترنت${\displaystyle e_{1},e_{2},\ldots ,e_{n}}$الوزن${\displaystyle w_{j}}$يمكن أن يكون الحمل الناتج عن التدفق${\displaystyle e_{j}}$على الخادم. وبالتالي،${\displaystyle \sum _{j=1}^{n}{w_{j}}}$يمثل إجمالي الحمل المفروض على الخادم من جميع التدفقات التي تستقبل الحزم${\displaystyle x_{1},x_{2},\ldots ,x_{s}}$ينتمي ل.

يمكن تعميم أي مُقدِّر إحصائي للترتيب المتطرف (رسومات الحد الأدنى/الأقصى) للمسألة غير الموزونة ليصبح مُقدِّرًا للمسألة الموزونة. ^{[ 13 ]} على سبيل المثال، يمكن الحصول على المُقدِّر الموزون الذي اقترحه كوهين وآخرون ^{[ 5 ]} عند توسيع مُقدِّر رسومات الحد الأقصى المستمر لحل المسألة الموزونة. على وجه الخصوص، يمكن توسيع خوارزمية HyperLogLog ^{[ 6 ]} لحل المسألة الموزونة. تُقدِّم خوارزمية HyperLogLog الموسعة أفضل أداء، من حيث الدقة الإحصائية واستخدام الذاكرة، مقارنةً بجميع الخوارزميات الأخرى المعروفة للمسألة الموزونة.

• رسم تخطيطي بالعد الدقائقي
• خوارزمية البث
• أقصى احتمال
• مقدر غير متحيز ذو تباين أدنى