اختبار المجموعة

توجد تصنيفات مستقلة لمشاكل اختبار المجموعات؛ فكل مشكلة اختبار مجموعة إما تكيفية أو غير تكيفية، وإما احتمالية أو توافقية. ^{[ 3 ]}

في النماذج الاحتمالية، يُفترض أن العناصر المعيبة تتبع توزيعًا احتماليًا معينًا ، والهدف هو تقليل العدد المتوقع للاختبارات اللازمة لتحديد عيب كل عنصر. من ناحية أخرى، في اختبار المجموعات التوافقي، يكون الهدف هو تقليل عدد الاختبارات اللازمة في أسوأ سيناريو ممكن - أي إنشاء خوارزمية minmax - ولا يُفترض معرفة توزيع العناصر المعيبة. ^{[ 3 ]}

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

توجد طرق عديدة لتوسيع نطاق مشكلة اختبار المجموعات. إحدى أهم هذه الطرق تُسمى اختبار المجموعات الضوضائي ، وتتناول افتراضًا أساسيًا في المشكلة الأصلية: وهو أن الاختبار خالٍ من الأخطاء. تُسمى مشكلة اختبار المجموعات ضوضائية عندما يكون هناك احتمال أن تكون نتيجة اختبار المجموعة خاطئة (مثلًا، أن تكون النتيجة إيجابية بينما لم يحتوي الاختبار على أي منتجات معيبة). يفترض نموذج ضوضاء برنولي أن هذا الاحتمال ثابت.${\displaystyle q}$لكن بشكل عام، قد يعتمد ذلك على العدد الحقيقي للعناصر المعيبة في الاختبار وعدد العناصر المختبرة. ^{[ 6 ]} على سبيل المثال، يمكن نمذجة تأثير التخفيف بالقول إن النتيجة الإيجابية أكثر احتمالًا عند وجود عدد أكبر من العناصر المعيبة (أو نسبة أكبر من العناصر المعيبة إلى عدد العناصر المختبرة) في الاختبار. ^{[ 7 ]} دائمًا ما يكون للخوارزمية المشوشة احتمال غير صفري لارتكاب خطأ (أي، تصنيف عنصر بشكل خاطئ). ^{[ 6 ]}

يمكن توسيع نطاق الاختبارات الجماعية من خلال النظر في سيناريوهات يكون فيها أكثر من نتيجتين محتملتين للاختبار. على سبيل المثال، قد يكون للاختبار النتائج التالية:${\displaystyle 0,1}$و${\displaystyle 2^{+}}$، وهو ما يتوافق مع عدم وجود أي عيوب، أو وجود عيب واحد، أو عدد غير معروف من العيوب أكبر من واحد. وبشكل أعم، يمكن اعتبار مجموعة نتائج الاختبار على أنها${\displaystyle {0,1,\ldots ,k^{+}}}$بالنسبة للبعض${\displaystyle k\in \mathbb {N} }$[ ^{8 ]​}

ثمة امتداد آخر يتمثل في النظر في القيود الهندسية المفروضة على المجموعات التي يمكن اختبارها. تُعدّ مسألة المصباح الكهربائي المذكورة أعلاه مثالًا على هذا النوع من القيود: إذ لا يمكن اختبار سوى المصابيح التي تظهر متتالية. وبالمثل، يمكن ترتيب العناصر في دائرة، أو بشكل عام، في شبكة، حيث تمثل الاختبارات المسارات المتاحة على الرسم البياني. ومن أنواع القيود الهندسية الأخرى تحديد الحد الأقصى لعدد العناصر التي يمكن اختبارها في مجموعة، ^{أو قد يكون من الضروري أن تكون أحجام المجموعات زوجية ، وهكذا . وبالمثل، قد يكون من المفيد النظر في القيد الذي ينص على أن أي عنصر معين لا يمكن} أن يظهر إلا في عدد محدد من الاختبارات.

توجد طرق لا حصر لها لتطوير الصيغة الأساسية لاختبار المجموعات. ستوضح التفاصيل التالية بعضًا من أكثر المتغيرات غرابة. في نموذج "جيد-متوسط-سيئ"، يُصنف كل عنصر على أنه "جيد" أو "متوسط" أو "سيئ"، وتكون نتيجة الاختبار هي نوع العنصر "الأسوأ" في المجموعة. في اختبار المجموعات العتبية، تكون نتيجة الاختبار إيجابية إذا كان عدد العناصر المعيبة في المجموعة أكبر من قيمة عتبة أو نسبة معينة. ^{[ 9 ]} يُعد اختبار المجموعات مع المثبطات أحد المتغيرات المستخدمة في البيولوجيا الجزيئية. هنا، توجد فئة ثالثة من العناصر تُسمى المثبطات، وتكون نتيجة الاختبار إيجابية إذا احتوى على عنصر معيب واحد على الأقل ولم يحتوِ على أي مثبطات. ^{[ 10 ]}

طُرح مفهوم الاختبار الجماعي لأول مرة من قِبل روبرت دورفمان عام 1943 في تقرير موجز ^{[ 2 ]} نُشر في قسم الملاحظات من حوليات الإحصاء الرياضي . ^{[ 8 ] [ ب ]} ركز تقرير دورفمان - كما هو الحال مع جميع الأعمال المبكرة حول الاختبار الجماعي - على المشكلة الاحتمالية، وهدف إلى استخدام فكرة الاختبار الجماعي الجديدة لتقليل العدد المتوقع للاختبارات اللازمة لاستبعاد جميع الرجال المصابين بالزهري في مجموعة معينة من الجنود. كانت الطريقة بسيطة: تقسيم الجنود إلى مجموعات ذات حجم محدد، واستخدام الاختبار الفردي (اختبار العناصر في مجموعات من عنصر واحد) على المجموعات الإيجابية لتحديد المصابين. قام دورفمان بجدولة أحجام المجموعات المثلى لهذه الاستراتيجية مقابل معدل انتشار المرض في المجتمع. ^{[ 2 ]} وجد ستيفن صامويلز حلاً مغلقًا لحجم المجموعة الأمثل كدالة لمعدل الانتشار. ^{[ 12 ]}

بعد عام 1943، ظل اختبار المجموعات دون تغيير يُذكر لعدة سنوات. ثم في عام 1957، أدخل ستيريت تحسينًا على إجراء دورفمان. تبدأ هذه العملية الجديدة بإجراء اختبار فردي على المجموعات الإيجابية، ولكنها تتوقف بمجرد تحديد عنصر معيب. بعد ذلك، تُختبر العناصر المتبقية في المجموعة معًا، نظرًا لاحتمالية عدم وجود أي عنصر معيب فيها. ^{[ 13 ]}

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

تُظهر النتيجة الأساسية التي توصل إليها بيتر أونجار في عام 1960 أنه إذا كان معدل الانتشار${\displaystyle p>p_{u}}$، أين${\displaystyle p_{u}=(3-{\sqrt {5}})/2\approx 0.38}$إذاً، يُعد الاختبار الفردي هو الإجراء الأمثل لاختبار المجموعة فيما يتعلق بالعدد المتوقع للاختبارات، وإذا${\displaystyle p<p_{u}}$إذا كان الأمر كذلك، فهو ليس الأمثل. ومع ذلك، من المهم ملاحظة أنه على الرغم من ثمانين عامًا من الجهود البحثية، فإن الإجراء الأمثل لا يزال غير معروف بالنسبة لـ${\displaystyle p<p_{u}}$وحجم السكان العام${\displaystyle n>2}$[ ^{15 ]​}

تمت دراسة اختبار المجموعات لأول مرة في السياق التوافقي بواسطة لي في عام 1962، ^{[ 16 ]} مع تقديم لي لـ${\displaystyle s}$خوارزمية من مرحلتين . ^{[ 8 ]} اقترح لي توسيعًا لخوارزمية دورفمان "ذات المرحلتين" لتشمل عددًا عشوائيًا من المراحل لا يتطلب أكثر من${\textstyle t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)}$الاختبارات التي تضمن العثور على${\displaystyle d}$أو عدد أقل من المنتجات المعيبة بين${\displaystyle n}$كانت الفكرة هي إزالة جميع العناصر في الاختبارات السلبية، وتقسيم العناصر المتبقية إلى مجموعات كما تم مع المجموعة الأولية. وكان من المقرر القيام بذلك.${\displaystyle s-1}$^{[ 16 ]} مرات قبل إجراء الاختبارات الفردية.

تمت دراسة اختبار المجموعات التوافقي بشكل عام بشكل أكثر شمولاً لاحقًا بواسطة كاتونا في عام 1973. قدم كاتونا التمثيل المصفوفي لاختبار المجموعات غير التكيفي، ووضع إجراءً لإيجاد المعيب في حالة المعيب الواحد غير التكيفي في مدة لا تتجاوز${\displaystyle t=\lceil \log _{2}(n)\rceil }$الاختبارات، والتي أثبت أيضاً أنها مثالية. ^{[ 17 ]}

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

في الحالات التي يوجد فيها عيبان أو أكثر، لا تزال خوارزمية التقسيم الثنائي المعممة تُنتج نتائج شبه مثالية، وتتطلب على الأكثر${\displaystyle d-1}$الاختبارات التي تتجاوز الحد الأدنى للمعلومات حيث${\displaystyle d}$يمثل عدد الوحدات المعيبة. ^{[ 18 ]} وقد أدخلت شركة أليمان تحسينات كبيرة على هذا الأمر في عام 2013، مما أدى إلى خفض عدد الاختبارات المطلوبة إلى أقل من${\displaystyle 0.187d+0.5\log _{2}(d)+5.5}$أعلى من الحد الأدنى للمعلومات عندما${\displaystyle n/d\geq 38}$و${\displaystyle d\geq 10}$وقد تحقق ذلك بتغيير البحث الثنائي في خوارزمية التقسيم الثنائي إلى مجموعة معقدة من الخوارزميات الفرعية ذات مجموعات اختبار متداخلة. وبذلك، تم حل مشكلة اختبار المجموعات التوافقي التكيفي - مع وجود عدد معروف أو حد أعلى لعدد المنتجات المعيبة - بشكل أساسي، مع مجال ضئيل لمزيد من التحسين. ^{[ 19 ]}

لا يزال السؤال مطروحًا حول متى يكون الاختبار الفردي في حالة minmax . وقد أظهر هو وهوانغ ووانغ في عام 1981 أن الاختبار الفردي يكون في حالة minmax عندما${\displaystyle n\leq \lfloor (5d+1)/2\rfloor }$وأنه ليس minmax عندما${\displaystyle n>3d}$[ ^{20 ]} يُفترض حاليًا أن هذا الحد دقيق: أي أن الاختبار الفردي يكون في أدنى قيمة قصوى إذا وفقط ^إذا${\displaystyle n\leq 3d}$[ ^{21 ] [ ج ]} أُحرز بعض التقدم في عام 2000 على يد ريتشيو وكولبورن، اللذين أظهرا أنه بالنسبة للأحجام ^{الكبيرة}${\displaystyle n}$الاختبار الفردي يكون في أدنى حد أقصى عندما${\displaystyle d\geq n/\log _{3/2}(3)\approx 0.369n}$[ ^{22 ]​}

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

وفي هذا السياق، قدم تشان وآخرون (2011) خوارزمية COMP ، وهي خوارزمية احتمالية لا تتطلب أكثر من${\displaystyle t=ed(1+\delta )\ln(n)}$اختبارات للكشف عن ما يصل إلى${\displaystyle d}$معيب في${\displaystyle n}$العناصر التي لا تتجاوز احتمالية الخطأ فيها${\displaystyle n^{-\delta }}$[ ^{6 ] هذا ضمن} عامل ثابت من${\displaystyle t=O(d\log _{2}n)}$الحد الأدنى. ^{[ 4 ]}

قدّم تشان وآخرون (2011) تعميمًا لنموذج COMP ليشمل نموذجًا بسيطًا مشوّشًا، وقدّموا بالمثل حدًا صريحًا للأداء، والذي كان ثابتًا (يعتمد على احتمالية فشل الاختبار) أعلى من الحد الأدنى المقابل. ^{[ 4 ] [ 6 ]} بشكل عام، يكون عدد الاختبارات المطلوبة في حالة ضوضاء برنولي أكبر بمعامل ثابت من عددها في حالة انعدام الضوضاء. ^{[ 6 ]}

قدّم ألدريدج وبالداسيني وجونسون (2014) امتدادًا لخوارزمية COMP أضاف خطوات معالجة لاحقة إضافية. ^{[ 23 ]} وأظهروا أن أداء هذه الخوارزمية الجديدة، المسماة DD ، يتجاوز أداء COMP بشكل ملحوظ، وأن DD تُعدّ "مثالية بشكل أساسي" في السيناريوهات التي${\displaystyle d^{2}\geq n}$وذلك بمقارنتها بخوارزمية افتراضية تحدد قيمة مثلى معقولة. ويشير أداء هذه الخوارزمية الافتراضية إلى وجود مجال للتحسين عندما${\displaystyle d^{2}<n}$وكذلك اقتراح مدى التحسن الذي قد يحدث. ^{[ 23 ]}

بما أنه من الممكن دائمًا اللجوء إلى الاختبار الفردي عن طريق الإعداد${\displaystyle S_{j}=\{j\}}$لكل${\displaystyle 1\leq j\leq n}$لا بد أن يكون ذلك${\displaystyle {\bar {t}}(d,n)\leq n}$كذلك، بما أن أي إجراء اختبار غير تكيفي يمكن كتابته كخوارزمية تكيفية ببساطة عن طريق إجراء جميع الاختبارات دون النظر إلى نتائجها،${\displaystyle t(d,n)\leq {\bar {t}}(d,n)}$وأخيرًا، عندما${\displaystyle 0\neq d\neq n}$يوجد عنصر واحد على الأقل يجب تحديد عيبه (عن طريق اختبار واحد على الأقل)، ولذا${\displaystyle 1\leq t(d,n)}$.

باختصار (عند افتراض${\displaystyle 0\neq d\neq n}$)${\displaystyle 1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n}$. ^{[ f ]}

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

• لنفترض إجراء اختبار جماعي غير تكيفي لـ${\displaystyle n}$تتضمن العناصر الاختبارات${\displaystyle S_{1},S_{2},\dots ,S_{t}}$بالنسبة للبعض${\displaystyle t\in \mathbb {N} _{\geq 0}}$مصفوفة الاختبار لهذا المخطط هي${\displaystyle t\times n}$المصفوفة الثنائية،${\displaystyle M}$، أين${\displaystyle (M)_{ij}=1}$إذا وفقط إذا${\displaystyle j\in S_{i}}$(وتكون قيمتها صفرًا فيما عدا ذلك).

وبالتالي كل عمود من${\displaystyle M}$يمثل كل صف عنصرًا، ويمثل كل صف اختبارًا، مع${\displaystyle 1}$في${\displaystyle (i,j){\textrm {-th}}}$مدخل يشير إلى أن${\displaystyle i{\textrm {-th}}}$تضمن الاختبار ما يلي:${\displaystyle j{\textrm {-th}}}$عنصر و أ${\displaystyle 0}$مما يشير إلى خلاف ذلك.

بالإضافة إلى المتجه${\displaystyle \mathbf {x} }$(طول)${\displaystyle n}$) التي تصف المجموعة المعيبة غير المعروفة، من الشائع إدخال متجه النتائج، الذي يصف نتائج كل اختبار.

• يترك${\displaystyle t}$ليكن عدد الاختبارات التي تُجريها خوارزمية غير تكيفية. متجه النتائج ،${\displaystyle \mathbf {y} =(y_{1},y_{2},\dots ,y_{t})}$، هو متجه ثنائي طوله${\displaystyle t}$(إنه،${\displaystyle \mathbf {y} \in \{0,1\}^{t}}$) بحيث${\displaystyle y_{i}=1}$إذا وفقط إذا كانت نتيجة${\displaystyle i{\textrm {-th}}}$كانت نتيجة الاختبار إيجابية (أي احتوى على عنصر واحد معيب على الأقل). ^{[ g ]}

بناءً على هذه التعريفات، يمكن إعادة صياغة المشكلة غير التكيفية على النحو التالي: أولاً، يتم اختيار مصفوفة اختبار،${\displaystyle M}$وبعد ذلك المتجه${\displaystyle \mathbf {y} }$يتم إرجاعها. ثم تكمن المشكلة في التحليل.${\displaystyle \mathbf {y} }$لإيجاد تقدير ما لـ${\displaystyle \mathbf {x} }$.

في أبسط الحالات الضوضائية، حيث يكون الاحتمال ثابتًا،${\displaystyle q}$إذا افترضنا أن اختبار المجموعة سيؤدي إلى نتيجة خاطئة، فإننا نعتبر متجهًا ثنائيًا عشوائيًا.${\displaystyle \mathbf {v} }$حيث يكون لكل إدخال احتمال${\displaystyle q}$من كونه${\displaystyle 1}$وهو${\displaystyle 0}$وإلا، فإن المتجه الذي يتم إرجاعه هو${\displaystyle {\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v} }$مع الإضافة المعتادة على${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$(بمعنى آخر، هذه هي عملية XOR العنصرية ). يجب على الخوارزمية المشوشة أن تُقدِّر${\displaystyle \mathbf {x} }$استخدام${\displaystyle {\hat {\mathbf {y} }}}$(أي بدون معرفة مباشرة بـ)${\displaystyle \mathbf {y} }$). ^{[ 6 ]}

يُتيح تمثيل المصفوفة إمكانية إثبات بعض الحدود على اختبار المجموعة غير التكيفي. ويُحاكي هذا النهج نهج العديد من التصاميم الحتمية، حيث${\displaystyle d}$تُعتبر المصفوفات القابلة للفصل، كما هو مُعرّف أدناه. ^{[ 8 ]}

• مصفوفة ثنائية،${\displaystyle M}$يُطلق عليه اسم${\displaystyle d}$- قابلة للفصل إذا كان كل مجموع منطقي (أو منطقي) لأي${\displaystyle d}$تتميز أعمدتها بخصائص فريدة. بالإضافة إلى ذلك، فإن الترميز${\displaystyle {\bar {d}}}$يشير -separable إلى أن كل مجموع لأي من العناصر يصل إلى${\displaystyle d}$ل${\displaystyle M}$أعمدة 's مميزة. (هذا ليس هو نفسه${\displaystyle M}$كون${\displaystyle k}$- قابلة للفصل لكل${\displaystyle k\leq d}$.)

متى${\displaystyle M}$هي مصفوفة اختبار، وهي خاصية كونها${\displaystyle d}$قابل للفصل (${\displaystyle {\bar {d}}}$(قابل للفصل) يعادل القدرة على التمييز بين (حتى)${\displaystyle d}$معيبة. ومع ذلك، لا يضمن ذلك أن يكون الأمر بسيطًا. هناك خاصية أقوى، تُسمى الانفصال، تضمن ذلك.

• مصفوفة ثنائية،${\displaystyle M}$يُطلق عليه اسم${\displaystyle d}$- غير منفصل إذا كان المجموع المنطقي لأي${\displaystyle d}$لا يحتوي العمود A على أي عمود آخر. (في هذا السياق، يُقال إن العمود A يحتوي على العمود B إذا كان لكل فهرس يحتوي فيه B على 1، يحتوي A أيضًا على 1.)

خاصية مفيدة لـ${\displaystyle d}$مصفوفات الاختبار المنفصلة هي تلك التي تصل إلى${\displaystyle d}$بالنسبة للعناصر المعيبة، سيظهر كل عنصر غير معيب في اختبار واحد على الأقل تكون نتيجته سلبية. وهذا يعني وجود إجراء بسيط للعثور على العناصر المعيبة: ببساطة قم بإزالة كل عنصر يظهر في اختبار سلبي.

باستخدام خصائص${\displaystyle d}$-قابلة للفصل و${\displaystyle d}$يمكن إثبات ما يلي فيما يتعلق بمشكلة تحديد المصفوفات المنفصلة.${\displaystyle d}$العيوب بين${\displaystyle n}$إجمالي العناصر. ^{[ 4 ]}

1. يتناسب عدد الاختبارات اللازمة للحصول على احتمال خطأ متوسط ​​صغير تقاربياً مع${\displaystyle O(d\log _{2}n)}$.
2. يتناسب عدد الاختبارات اللازمة للحصول على احتمال خطأ أقصى صغير تقاربياً مع${\displaystyle O(d^{2}\log _{2}n)}$.
3. يتناسب عدد الاختبارات اللازمة لتحقيق احتمال خطأ صفري طرديًا مع${\displaystyle O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)}$.

خوارزمية البحث عن المطابقة المتعامدة التوافقية ، أو COMP، هي خوارزمية اختبار جماعي بسيطة غير تكيفية تشكل الأساس للخوارزميات الأكثر تعقيدًا التي تليها في هذا القسم.

أولاً، يتم اختيار كل عنصر من عناصر مصفوفة الاختبار بشكل مستقل ومتطابق .${\displaystyle 1}$باحتمال${\displaystyle 1/d}$و${\displaystyle 0}$خلاف ذلك.

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

لا تتطلب خوارزمية COMP أكثر من${\displaystyle ed(1+\delta )\ln(n)}$الاختبارات التي يكون احتمال الخطأ فيها أقل من أو يساوي${\displaystyle n^{-\delta }}$[ ^{6 ]} هذا يقع ضمن عامل ثابت للحد الأدنى لمتوسط ​​احتمال الخطأ أعلاه ^.

في حالة الضوضاء، يتم تخفيف الشرط الوارد في خوارزمية COMP الأصلية بأن مجموعة مواقع الواحدات في أي عمود من${\displaystyle M}$يجب أن يكون العنصر المقابل لقيمة موجبة محصورًا بالكامل في مجموعة مواقع الآحاد في متجه النتيجة. بدلاً من ذلك، يُسمح بعدد معين من "حالات عدم التطابق" - يعتمد هذا العدد من حالات عدم التطابق على كل من عدد الآحاد في كل عمود، وكذلك على معامل التشويش.${\displaystyle q}$لا تتطلب خوارزمية COMP الضوضائية هذه أكثر من${\displaystyle 4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}}$اختبارات لتحقيق احتمال خطأ لا يتجاوز${\displaystyle n^{-\delta }}$[ ^{6 ]​}

تُعدّ طريقة العيوب المؤكدة (DD) امتدادًا لخوارزمية COMP، وهي تسعى إلى إزالة أي نتائج إيجابية خاطئة. وقد ثبت أن ضمانات الأداء لطريقة DD تتجاوز بشكل كبير ضمانات الأداء لخوارزمية COMP. ^{[ 23 ]}

تعتمد خطوة فك التشفير على خاصية مفيدة لخوارزمية COMP، وهي أن كل عنصر تُعلن عنه COMP بأنه غير معيب هو بالتأكيد غير معيب (أي لا توجد نتائج سلبية خاطئة). وتتم هذه الخطوة على النحو التالي.

1. أولاً، يتم تشغيل خوارزمية COMP، ويتم استبعاد أي منتجات غير معيبة يتم اكتشافها. أما جميع المنتجات المتبقية فتُعتبر الآن "معيبة على الأرجح".
2. بعد ذلك، تنظر الخوارزمية في جميع الاختبارات الإيجابية. إذا ظهر عنصر ما باعتباره العنصر "المحتمل أن يكون معيبًا" الوحيد في الاختبار، فإنه يجب أن يكون معيبًا، وبالتالي تعلن الخوارزمية أنه معيب.
3. يُفترض أن جميع العناصر الأخرى غير معيبة. ويستند هذا الإجراء الأخير إلى افتراض أن عدد العناصر المعيبة أقل بكثير من العدد الإجمالي للعناصر.

لاحظ أن الخطوتين 1 و2 لا تخطئان أبدًا، لذا لا يمكن للخوارزمية أن تخطئ إلا إذا صنّفت عنصرًا معيبًا على أنه غير معيب. وبالتالي، فإن خوارزمية DD لا تُنتج إلا نتائج سلبية خاطئة.

خوارزمية SCOMP (المقارنة التسلسلية) هي خوارزمية تستفيد من حقيقة أن خوارزمية DD لا ترتكب أخطاءً حتى الخطوة الأخيرة، حيث يُفترض أن العناصر المتبقية غير معيبة. لنفترض أن مجموعة العناصر المعيبة المعلنة هي${\displaystyle K}$يُفسر الاختبار الإيجابي بـ${\displaystyle K}$إذا كان يحتوي على عنصر واحد على الأقل في${\displaystyle K}$. الملاحظة الرئيسية المتعلقة بـ SCOMP هي أن مجموعة العيوب التي تم العثور عليها بواسطة DD قد لا تفسر كل اختبار إيجابي، وأن كل اختبار غير مفسر يجب أن يحتوي على عيب خفي.

تتم الخوارزمية على النحو التالي.

1. نفّذ الخطوتين 1 و2 من خوارزمية DD للحصول على${\displaystyle K}$، تقدير أولي لمجموعة المنتجات المعيبة.
2. لو${\displaystyle K}$يشرح كل اختبار إيجابي، وينهي الخوارزمية:${\displaystyle K}$هذا هو التقدير النهائي لمجموعة المنتجات المعيبة.
3. إذا كانت هناك أي اختبارات غير مفسرة، فابحث عن "الاختبار المعيب المحتمل" الذي يظهر في أكبر عدد من الاختبارات غير المفسرة، وأعلن أنه معيب (أي أضفه إلى المجموعة).${\displaystyle K}$انتقل إلى الخطوة 2.

أظهرت عمليات المحاكاة أن أداء SCOMP يقترب من الأداء الأمثل. ^{[ 23 ]}

تُعدّ خوارزمية تجميع الحدود المتعددة الحدود (PP) خوارزمية حتمية تضمن تحديدًا دقيقًا يصل إلى${\displaystyle d}$الإيجابيات. ^{[ 26 ]} الخوارزمية مخصصة لإنشاء مصفوفة التجميع${\displaystyle M}$والتي يمكن استخدامها مباشرة لفك تشفير الملاحظات في${\displaystyle y}$على غرار COMP، يتم فك تشفير العينة وفقًا للعلاقة التالية: ${\displaystyle x_{i}=1~~{\text{ if }}~~M(:,i)~.*~y=M(:,i)}$، أين${\displaystyle .*}$يمثل الضرب العنصري و${\displaystyle M(:,i)}$هو${\displaystyle i}$العمود رقم 1 من${\displaystyle M}$بما أن خطوة فك التشفير ليست صعبة، فإن PP متخصص في توليد${\displaystyle M}$.

تشكيل المجموعات

مجموعة / مسبح${\displaystyle \ell }$يتم توليدها باستخدام علاقة متعددة الحدود تحدد مؤشرات العينات الموجودة في كل مجموعة. تحدد مجموعة من معلمات الإدخال الخوارزمية. بالنسبة لعدد أولي${\displaystyle p>1}$وعدد صحيح${\displaystyle n\geq 1}$أي قوة أولية تُعرَّف بواسطة${\displaystyle q=p^{n}}$. لمعامل بُعد${\displaystyle c\geq 2}$إجمالي عدد العينات هو${\displaystyle n=q^{c}}$وعدد العينات لكل مجموعة هو${\displaystyle q^{c-1}}$علاوة على ذلك، فإن الحقل المنتهي من الرتبة${\displaystyle q}$يُرمز إليه بـ${\displaystyle \mathbb {F} _{q}}$ (أي الأعداد الصحيحة)${\displaystyle \{0,1,2,\ldots ,q-1\}}$تُعرَّف هذه العمليات بعمليات حسابية خاصة تضمن أن الجمع والضرب في${\displaystyle \mathbb {F} _{q}}$لا يزال في${\displaystyle \mathbb {F} _{q}}$تقوم هذه الطريقة بترتيب كل عينة في شبكة وتمثيلها بالإحداثيات.${\displaystyle x=(u,v)}$يتم حساب الإحداثيات وفقًا لعلاقة متعددة الحدود باستخدام الأعداد الصحيحة ${\displaystyle 1\leq l\leq c-1}$،${\displaystyle 0\leq u_{i_{l}}\leq q-1}$

${\displaystyle v~=~a^{c-1}~u_{i_{c-1}}+\cdots +a~u_{i_{1}}+b,\quad a,b,u_{i_{l}}\in \mathbb {F} _{q}.}$

مزيج من التكرار عبر${\displaystyle u_{i_{l}}}$يتم تمثيل القيم بمجموعة تحتوي على${\displaystyle q^{c-1}}$عناصر من سلسلة${\displaystyle d-1}$الأعداد الصحيحة، أي ${\displaystyle u_{i_{1}}\times \cdots \times u_{i_{c-1}}=\{(i_{1},\ldots ,i_{c-1})\}}$، أين ${\displaystyle 0\leq i_{l}\leq q-1}$وبدون فقدان للعمومية ، فإن التركيبة تكون بحيث ${\displaystyle i_{d-1}}$دورات كل${\displaystyle q}$مرات،${\displaystyle i_{d-2}}$دورات كل${\displaystyle q^{2}}$أوقات حتى ${\displaystyle i_{1}}$تُكرر الدورة مرة واحدة فقط. صيغ لحساب مؤشرات العينة، وبالتالي المجموعات المقابلة، لقيم ثابتة${\displaystyle a}$و${\displaystyle b}$يتم تقديمها بواسطة

${\displaystyle {\begin{aligned}u_{i}&=\sum _{l=1}^{c-1}~q^{d-1-l}~i_{l}\\v_{u_{i}}&=\sum _{l=1}^{c-1}~a^{l}~i_{l}+b\quad ({\text{computed in }}\mathbb {F} _{q})\\x_{qu_{i}+v_{u_{i}}}&=(u_{i},v_{u_{i}})\end{aligned}}}$

الحسابات في${\displaystyle \mathbb {F} _{q}}$يمكن تنفيذ ذلك باستخدام مكتبات برمجية متاحة للعموم للحقول المنتهية، عندما${\displaystyle q}$هي قوة رئيسية. عندما${\displaystyle q}$إذا كان عددًا أوليًا، فإن العمليات الحسابية في${\displaystyle \mathbb {F} _{q}}$تبسيط إلى حساب المعامل، أي${\displaystyle v_{u_{i}}=(\sum _{l=1}^{c-1}a^{l}i_{l}+b)~{\text{mod}}~q}$مثال على كيفية إنشاء مجموعة واحدة${\displaystyle \ell }$متى ${\displaystyle a=1,b=0,c=2}$يتم عرضها في الجدول أدناه، بينما يتم عرض مجموعة العينات المقابلة في الشكل أعلاه.

حساب مجموعة واحدة${\displaystyle \ell }$استخدام PP مع${\displaystyle c=3}$،${\displaystyle q=3}$،${\displaystyle a=1}$،${\displaystyle b=0}$

${\displaystyle i_{1}}$	${\displaystyle i_{2}}$	${\displaystyle u_{i}}$	${\displaystyle v_{u_{i}}}$	${\displaystyle qu_{i}+v_{u_{i}}}$	${\displaystyle \ell }$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle x_{0}}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 4}$	${\displaystyle x_{4}}$
${\displaystyle 0}$	${\displaystyle 2}$	${\displaystyle 2}$	${\displaystyle 2}$	${\displaystyle 8}$	${\displaystyle x_{8}}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 3}$	${\displaystyle 1}$	${\displaystyle 10}$	${\displaystyle x_{10}}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 4}$	${\displaystyle 2}$	${\displaystyle 14}$	${\displaystyle x_{14}}$
${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 5}$	${\displaystyle 0}$	${\displaystyle 15}$	${\displaystyle x_{15}}$
${\displaystyle 2}$	${\displaystyle 0}$	${\displaystyle 6}$	${\displaystyle 2}$	${\displaystyle 20}$	${\displaystyle x_{20}}$
${\displaystyle 2}$	${\displaystyle 1}$	${\displaystyle 7}$	${\displaystyle 0}$	${\displaystyle 21}$	${\displaystyle x_{21}}$
${\displaystyle 2}$	${\displaystyle 2}$	${\displaystyle 8}$	${\displaystyle 1}$	${\displaystyle 25}$	${\displaystyle x_{25}}$

تستخدم هذه الطريقة${\displaystyle q(c-1)(d+1)}$اختبارات لتحديد ما يصل إلى${\displaystyle d}$الإيجابيات بين${\displaystyle n=q^{c}}$العينات. ولهذا السبب، فإن PP فعال بشكل خاص لأحجام العينات الكبيرة، حيث ينمو عدد الاختبارات بشكل خطي فقط بالنسبة لـ${\displaystyle c}$بينما تنمو العينات بشكل أُسّي مع هذا المعامل. ومع ذلك، يمكن أن يكون PP فعالاً أيضاً لأحجام العينات الصغيرة. ^{[ 26 ]}

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

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

في سياق اختبار المجموعات، تُعالج هذه المشكلة عادةً بتقسيم الوقت إلى "حقب" على النحو التالي. ^{[ 8 ]} يُعتبر المستخدم "نشطًا" إذا كان لديه رسالة في بداية كل حقبة. (إذا تم إنشاء رسالة خلال حقبة، يصبح المستخدم نشطًا فقط في بداية الحقبة التالية). تنتهي الحقبة عندما يُرسل كل مستخدم نشط رسالته بنجاح. تكمن المشكلة حينها في إيجاد جميع المستخدمين النشطين في حقبة معينة، وتحديد وقت لهم للإرسال (إذا لم يكونوا قد أرسلوا بنجاح من قبل). هنا، يُمثل الاختبار على مجموعة من المستخدمين أولئك المستخدمين الذين يحاولون الإرسال. نتائج الاختبار هي عدد المستخدمين الذين حاولوا الإرسال.${\displaystyle 0,1,}$و${\displaystyle 2^{+}}$، وهو ما يتوافق على التوالي مع عدم وجود مستخدمين نشطين، أو مستخدم نشط واحد فقط (نجاح إرسال الرسالة)، أو أكثر من مستخدم نشط واحد (تصادم الرسائل). لذلك، يتم استخدام خوارزمية اختبار جماعية تكيفية مع النتائج${\displaystyle \{0,1,2^{+}\}}$يمكن تحديد المستخدمين الذين يرغبون في الإرسال خلال الفترة الزمنية المحددة. بعد ذلك، يمكن تخصيص وقت للإرسال لأي مستخدم لم يقم بإرسال ناجح حتى الآن، دون إهدار الوقت على المستخدمين غير النشطين.

يُعدّ التعلّم الآلي أحد فروع علوم الحاسوب، وله تطبيقات برمجية عديدة، مثل تصنيف الحمض النووي، وكشف الاحتيال، والإعلانات الموجّهة . ومن أهم فروع التعلّم الآلي مشكلة "التعلّم بالأمثلة"، حيث تتمثل المهمة في تقريب دالة غير معروفة عند معرفة قيمتها عند عدد من النقاط المحددة. ^{[ 8 ]} وكما هو موضح في هذا القسم، يمكن معالجة مشكلة تعلّم هذه الدالة باستخدام أسلوب اختبار المجموعات.

في نسخة مبسطة من المسألة، توجد دالة غير معروفة،${\displaystyle f:\{0,1\}^{N}\to \{0,1\}}$أين${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$، و${\displaystyle {\textbf {a}}\in \{0,1\}^{N}}$(باستخدام الحساب المنطقي: الجمع هو عملية "أو" المنطقية والضرب هو عملية "و" المنطقية). هنا${\displaystyle {\textbf {a}}}$يكون '${\displaystyle d}$"متفرق"، مما يعني أنه على الأكثر${\displaystyle d\ll N}$من بين مدخلاتها${\displaystyle 1}$الهدف هو بناء تقريب لـ${\displaystyle f}$استخدام${\displaystyle t}$تقييمات النقاط، حيث${\displaystyle t}$أصغر ما يمكن. ^{[ 4 ]} (استعادة بالضبط)${\displaystyle f}$يتوافق مع خوارزميات خالية من الأخطاء، بينما${\displaystyle f}$يتم تقريبها بواسطة خوارزميات لها احتمال خطأ غير صفري.

في هذه المشكلة، الاستعادة${\displaystyle f}$يُعادل إيجاد${\displaystyle {\textbf {a}}}$. علاوة على ذلك،${\displaystyle f({\textbf {p}})=1}$إذا وفقط إذا كان هناك فهرس ما،${\displaystyle n}$، أين${\displaystyle {\textbf {a}}_{n}={\textbf {p}}_{n}=1}$وبالتالي، فإن هذه المشكلة مماثلة لمشكلة اختبار المجموعة مع${\displaystyle d}$معيبة و${\displaystyle n}$إجمالي العناصر. إدخالات${\displaystyle {\textbf {a}}}$هي العناصر التي تعتبر معيبة إذا كانت${\displaystyle 1}$،${\displaystyle {\textbf {p}}}$يحدد الاختبار، ويكون الاختبار إيجابياً إذا وفقط إذا${\displaystyle f({\textbf {p}})=1}$[ ^{4 ]​}

في الواقع، غالباً ما يهتم المرء بالوظائف الأكثر تعقيداً، مثل${\displaystyle f:\mathbb {C} ^{N}\to \mathbb {C} }$، مرة أخرى حيث${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$يمكن استخدام تقنية الاستشعار المضغوط ، المرتبطة ارتباطًا وثيقًا بالاختبار الجماعي، لحل هذه المشكلة. ^{[ 4 ]}

في الاستشعار المضغوط، يتمثل الهدف في إعادة بناء الإشارة.${\displaystyle {\textbf {v}}\in \mathbb {C} ^{N}}$، وذلك بأخذ عدد من القياسات. يتم نمذجة هذه القياسات على أنها عملية الضرب النقطي لـ${\displaystyle {\textbf {v}}}$باستخدام متجه مُختار. ^{[ h ]} الهدف هو استخدام عدد قليل من القياسات، على الرغم من أن هذا غير ممكن عادةً إلا إذا تم افتراض شيء ما حول الإشارة. أحد هذه الافتراضات (وهو شائع ^{[ 35 ] [ 36 ]} ) هو أن عددًا صغيرًا فقط من إدخالات${\displaystyle {\textbf {v}}}$وهي ذات أهمية ، أي أنها ذات قيمة كبيرة. وبما أن القياسات هي حاصل ضرب نقطي لـ${\displaystyle {\textbf {v}}}$المعادلة${\displaystyle M{\textbf {v}}={\textbf {q}}}$يحجز، حيث${\displaystyle M}$هو${\displaystyle t\times N}$مصفوفة تصف مجموعة القياسات التي تم اختيارها و${\displaystyle \mathbf {q} }$هي مجموعة نتائج القياس. يوضح هذا التركيب أن الاستشعار المضغوط هو نوع من أنواع اختبار المجموعة "المستمر".

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

توجد بنى حتمية صريحة لهذا النوع من خوارزميات البحث التوافقي ، مما يتطلب${\displaystyle d2^{(\log _{2}\log _{2}N)^{O(1)}}}$القياسات. ^{[ 38 ]} ومع ذلك، كما هو الحال مع اختبار المجموعة، فإن هذه القياسات ليست مثالية، ويمكن للتركيبات العشوائية (مثل COMP) أن تعوض ذلك في كثير من الأحيان${\displaystyle f}$بشكل شبه خطي في${\displaystyle N}$[ ^{37 ]​}

خلال جائحة مثل تفشي كوفيد-19 في عام 2020، تُجرى أحيانًا اختبارات الكشف عن الفيروس باستخدام تصميمات اختبار جماعية غير تكيفية. ^{[ 39 ] [ 40 ] [ 41 ]} وقدّم مشروع Origami Assays مثالًا على ذلك، حيث أصدر تصميمات اختبار جماعية مفتوحة المصدر لتشغيلها على صفيحة اختبار قياسية معملية ذات 96 بئرًا. ^{[ 42 ]}

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

باستخدام تصميمات اختبار المجموعة الأكبر (XL3)، أمكن اختبار 1120 عينة من المرضى في 94 بئرًا للاختبار. إذا كان معدل النتائج الإيجابية الحقيقية منخفضًا بدرجة كافية، فلا حاجة إلى إجراء اختبارات إضافية.

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

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

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

في الواقع، عدد التجزئات المطلوبة منخفض للغاية لدرجة أنه يمكن تخزينها، إلى جانب مصفوفة الاختبار التي تشير إليها، ضمن البنية التنظيمية للبيانات نفسها. وهذا يعني أنه فيما يتعلق بالذاكرة، يمكن إجراء الاختبار "مجانًا". (ينطبق هذا باستثناء المفتاح الرئيسي/كلمة المرور المستخدمة لتحديد دالة التجزئة سرًا). ^{[ 31 ]}

• دينغ-تشو، دو؛ هوانغ، فرانك ك. (2000). اختبار المجموعات التوافقية وتطبيقاته (  الطبعة الثانية). سنغافورة: وورلد ساينتيفيك. ISBN 978-9810241070.
• دورة أتري رودرا حول رموز تصحيح الأخطاء: التوافقية والخوارزميات والتطبيقات (ربيع 2007)، المحاضرات 7 .
• دورة أتري رودرا حول رموز تصحيح الأخطاء: التوافقية والخوارزميات والتطبيقات (ربيع 2010)، المحاضرات 10 و 11 و 28 و 29
• دو، د.؛ هوانغ، ف. (2006). تصميمات التجميع واختبار المجموعات غير التكيفي . وورلد ساينتيفيك. ISBN 9789814477864.
• ألدريج، م.؛ جونسون، أ.؛ سكارليت، ج. (2019). "الاختبار الجماعي: منظور نظرية المعلومات" (ملف PDF) . أسس واتجاهات في الاتصالات ونظرية المعلومات . 15 ( 3-4 ): 196-392 . arXiv : 1902.06002 . doi : 10.1561/0100000099 . S2CID 62841593 . 
• بورات، إي.؛ روتشيلد، أ. (2011). "مخططات اختبار المجموعات التوافقية غير التكيفية الصريحة". معاملات IEEE في نظرية المعلومات . 57 (12): 7982-89 . arXiv : 0712.3876 . Bibcode : 2011ITIT...57.7982P . doi : 10.1109/TIT.2011.2163296 . S2CID 8815474 . 
• كاجان، يوجين؛ بنغال، إيراد (2014)، "خوارزمية اختبار جماعي مع التعلم المعلوماتي عبر الإنترنت"، معاملات معهد مهندسي الصناعة ، 46 (2): 164-184 ، doi : 10.1080/0740817X.2013.803639 ، ISSN 0740-817X ، S2CID 18588494