14 يناير 2025

سيولد حاسوب كمومي فائق التوصيل يعتمد على شفرة السطح مع مليون كيوبت فيزيائي بيانات قياس بمعدل حوالي 1 تيرابت في الثانية. يجب معالجة هذه البيانات على الأقل بنفس سرعة توليدها بواسطة جهاز فك التشفير، وهو البرنامج الكلاسيكي المستخدم للتنبؤ بالأخطاء التي قد تحدث، لمنع تراكم البيانات الذي ينمو بشكل أسي. -عمق البوابة في الحساب [Ter15]. علاوة على ذلك، فإن أجهزة فك التشفير السريعة مهمة ليس فقط لتشغيل الحاسوب الكمومي، ولكن أيضًا كأداة برمجية للبحث في بروتوكولات تصحيح الأخطاء الكمومية. يمكن أن يتطلب تقدير متطلبات الموارد لبروتوكول تصحيح الأخطاء الكمومية (مثل تقدير بصمة التيراقوب تحت العتبة [Gid+21]) استخدام أخذ عينات مونت كارلو المباشر لتقدير احتمال الأحداث النادرة للغاية. يمكن أن تكون هذه التحليلات مكلفة بشكل غير معقول دون الوصول إلى جهاز فك تشفير سريع، قادر على معالجة ملايين اللقطات من الدوائر التي تحتوي على البوابات في إطار زمني معقول.

تم تطوير العديد من مفككات الشيفرة لشفرة السطح، وأقدمها والأكثر شعبية هو مفكك الشيفرة ذو المطابقة المثالية ذات الوزن الأدنى (MWPM) [Den+02]، الذي هو أيضًا محور هذا العمل. يقوم مفكك الشيفرة MWPM بتحويل مشكلة فك الشيفرة إلى مشكلة رسومية من خلال تحليل نموذج الخطأ إلى -نوع و -نوع أخطاء باولي [Den+02]. يمكن حل هذه المشكلة الرسومية بمساعدة خوارزمية إدموندز للعثور على تطابق مثالي ذو وزن أدنى في رسم بياني [Edm65b; Edm65a]. إن تنفيذًا ساذجًا لمشفّر MWPM له تعقيد أسوأ حالة يعتمد على عدد العقد في الرسم البياني لـ ، مع الوقت المتوقع للتشغيل للحالات النموذجية التي تم العثور عليها تجريبيًا لتكون تقريبًا [Hig22]. أدت التقريبات والتحسينات على جهاز فك التشفير MWPM إلى تحسينات كبيرة في أوقات التشغيل المتوقعة [FWH12a; Fow15; Hig22]. على وجه الخصوص، اقترح فاولر جهاز فك التشفير MWPM بمتوسط
وقت التشغيل المتوازي [Fow15]. ومع ذلك، لم تظهر التطبيقات المنشورة لشفرة MWPM سرعات كافية للتشفير في الوقت الحقيقي على نطاق واسع.

تم اقتراح عدة بدائل لفك تشفير MWPM في الأدبيات. يتمتع فك تشفير Union-Find بوقت تشغيل أسوأ حالة شبه خطي تقريبًا [DN21؛ HNB20]، وقد تم اقتراح تنفيذات سريعة على الأجهزة. وتم تنفيذها مُفكك اتحاد-البحث أقل دقة قليلاً، ويمكن اعتباره تقريبًا لمُفكك MWPM [WLZ22]. يمكن لمفككات الاحتمالية القصوى أن تحقق دقة أعلى من مُفكك MWPM [BSV14؛ Hig+23؛ Sun+23] ولكنها تتمتع بتعقيد حسابي عالٍ، مما يجعلها غير عملية للتفكيك في الوقت الحقيقي. يمكن لمفككات أخرى، مثل MWPM المرتبطة [Fow13]، ومطابقة الاعتقاد [Hig+23]، ومفككات الشبكات العصبية [TM17؛ MPT22] أن تحقق دقة أعلى من MWPM مع زيادة متواضعة جدًا في وقت التشغيل. بينما كان هناك تقدم في تطوير حزم البرمجيات مفتوحة المصدر لتفكيك رموز السطح [Hig22؛ Tuc20]، فإن هذه الأدوات أبطأ بكثير من محاكيات دوائر المثبت [Gid21]، وبالتالي كانت عنق الزجاجة في محاكيات رموز السطح. ربما يكون هذا أحد الأسباب التي جعلت الدراسات العددية لرموز تصحيح الأخطاء تركز غالبًا على تقدير العتبات (التي تتطلب تفكيك عدد أقل من اللقطات)، بدلاً من تكاليف الموارد (التي تكون أكثر فائدة عمليًا لإجراء المقارنات).

في هذا العمل، نقدم تنفيذًا جديدًا لمفكك الشيفرة MWPM. الخوارزمية التي نقدمها، الزهرة المتناثرة، هي نوع من خوارزمية الزهرة التي تشبه من الناحية المفاهيمية النهج المتبع في المراجع [FWH12a; FWH12b; Fow15]، حيث تحل مشكلة فك الشيفرة MWPM مباشرة على رسم الكاشف، بدلاً من تقسيم المشكلة بشكل ساذج إلى خطوات متسلسلة متعددة وحل مشكلة نظرية الرسم التقليدية MWPM كروتين فرعي منفصل. هذا يتجنب عمليات البحث الشاملة باستخدام خوارزمية ديكسترا التي تُستخدم غالبًا في تنفيذات مفكك الشيفرة MWPM. تنفيذنا أسرع بمئات المرات من الأدوات البديلة المتاحة، ويمكنه فك الشيفرة لكل من و أسس دائرة شفرة السطح على بعد 17 ضجيج الدائرة) في أقل من ميكروثانية لكل جولة على نواة واحدة، مما يتطابق مع المعدل الذي يتم فيه توليد بيانات المتلازمة على معالج كمي فائق التوصيل. عند المسافة 29 بنفس نموذج الضجيج (أكثر من كافٍ لتحقيق معدلات الأخطاء المنطقية)، يستغرق PyMatching 3.5 ميكروثانية لكل جولة لفك التشفير على نواة واحدة. تشير هذه النتائج إلى أن خوارزمية الزهرة النادرة لدينا سريعة بما يكفي لفك التشفير في الوقت الحقيقي لأجهزة الكمبيوتر الكمومية الفائقة عند النطاق الكبير؛ من المحتمل تحقيق تنفيذ في الوقت الحقيقي من خلال التوازي عبر عدة نوى، ومن خلال إضافة دعم لفك تشفير تدفق، بدلاً من دفعة، من بيانات المتلازمة. تم إصدار تنفيذنا للزهرة النادرة في الإصدار 2 من حزمة PyMatching بايثون، ويمكن دمجه مع Stim [Gid21] لتشغيل المحاكاة في دقائق على جهاز كمبيوتر محمول كان سيستغرق ساعات على مجموعة حوسبة عالية الأداء.

في عمل مستقل متوازي مثير للإعجاب، طور يوي وو أيضًا تنفيذًا جديدًا لخوارزمية الزهرة يسمى الزهرة المدمجة [WZ23]، المتاحة في [Wu22]. التشابه المفهومي مع نهجنا هو أن الزهرة المدمجة تحل أيضًا مشكلة فك تشفير MWPM مباشرة على رسم الكاشف. ومع ذلك، هناك العديد من الاختلافات في تفاصيل تنفيذاتنا؛ على سبيل المثال، تستكشف الزهرة المدمجة الرسم بطريقة مشابهة لكيفية نمو المجموعات في البحث عن الاتحاد، بينما ينمو نهجنا المناطق الاستكشافية بشكل موحد، يتم إدارتها بواسطة قائمة أولويات عالمية. بينما يتمتع نهجنا بأداء أسرع على نواة واحدة، تدعم الزهرة المدمجة أيضًا التنفيذ المتوازي للخوارزمية نفسها، والتي يمكن استخدامها لتحقيق سرعات معالجة أسرع لحالات فك التشفير الفردية. عند استخدامها لمحاكاة تصحيح الأخطاء، نلاحظ أن الزهرة النادرة قابلة للتوازي بشكل تافه بالفعل من خلال تقسيم المحاكاة إلى دفعات من اللقطات، ومعالجة كل دفعة على نواة منفصلة. ومع ذلك، فإن توازي فك التشفير نفسه مهم لفك التشفير في الوقت الحقيقي، لمنع تراكم بيانات متزايد بشكل أسي داخل حساب واحد [Ter15]، أو لتجنب التباطؤ المتعدد الحدود المفروض من الاعتماد على فك التشفير من خلال النوافذ المتوازية بدلاً من ذلك. تان +23 لذلك، يمكن أن تستكشف الأعمال المستقبلية دمج الزهرة النادرة مع التقنيات الخاصة بالتوازي التي تم تقديمها في الزهرة المدمجة.

الورقة منظمة على النحو التالي. في القسم 2 نقدم خلفية عن مشكلة فك التشفير التي نهتم بها ونقدم نظرة عامة على خوارزمية الزهرة. في القسم 3 نشرح خوارزميتنا، الزهرة النادرة، قبل أن نصف الهياكل البيانية التي نستخدمها لتنفيذنا في القسم 4. في القسم 5 نقوم بتحليل زمن تشغيل الزهرة النادرة، وفي القسم 6 نقوم بتقييم زمن فك التشفير، قبل أن نختم في القسم 7.

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

نحن نعرف نموذج الخطأ المستقل بأنه مجموعة من آليات خطأ مستقلة، حيث آلية الخطأ يحدث باحتمالية (حيث هو متجه من الأولويات)، ويقوم بتغيير مجموعة من الكواشف والملاحظات. يمكن استخدام نموذج خطأ مستقل لتمثيل الضوضاء المسببة للانحلال على مستوى الدائرة بدقة، وهو تقريبي جيد للعديد من نماذج الخطأ التي يتم النظر فيها عادةً [Cha+20؛ Gid20]. يمكن أن يكون من المفيد وصف نموذج خطأ في دائرة تصحيح الأخطاء باستخدام مصفوفتين للتحقق من التماثل الثنائي: مصفوفة تحقق الكاشف ومصفوفة منطقية قابلة للملاحظة . نحن نحدد إذا كان الكاشف يتم قلبه بواسطة آلية الخطأ ، و بخلاف ذلك. بالمثل، نحن نحدد إذا كان قابلاً للملاحظة المنطقية يتم قلبه بواسطة آلية الخطأ ، و بخلاف ذلك. من خلال وصف نموذج الخطأ بهذه الطريقة، يتم تعريف كل آلية خطأ من خلال الكواشف والملاحظات التي تقوم بتغييرها، بدلاً من نوع باولي وموقعها في الدائرة. من دائرة مثبتة ونموذج ضوضاء باولي، يمكننا بناء و بكفاءة من خلال نشر أخطاء باولي عبر الدائرة لرؤية أي الكواشف والملاحظات التي تقوم بتغييرها. كل سابق ثم يتم حسابه عن طريق جمع احتمالات جميع أخطاء باولي التي تقلب نفس مجموعة الكواشف أو الملاحظات (أو بشكل أكثر دقة، فإن هذه الآليات الخطأ المعادلة مستقلة، ونحسب احتمال حدوث عدد فردي). هذا هو بالأساس ما تفعله أدوات تحليل الأخطاء في Stim، حيث يقوم نموذج خطأ الكاشف (الذي يتم إنشاؤه تلقائيًا من دائرة Stim) بالتقاط المعلومات المحتواة في و [Gid21].

يمكننا تمثيل خطأ (مجموعة من آليات الخطأ) بواسطة متجه متلازمة هو ناتج قياسات الكاشف، المعطى بـ . أحداث الكشف هي الكواشف التي تتوافق مع العناصر غير الصفرية لـ . خطأ منطقي غير قابل للاكتشاف هو خطأ في ، ومسافة الدائرة هي ، حيث هو وزن هامينغ لـ نظرًا لمتلازمة بعض الخطأ ، بالإضافة إلى المعرفة بـ و ، يقوم جهاز فك التشفير بعمل توقع خطأ يفي بـ وينجح إذا لاحظ أنه في بعض الأحيان يحتاج جهاز فك التشفير فقط إلى إخراج التوقع المنطقي (النجاح إذا تطابق )، كما سنناقش لاحقًا.

بالنسبة لدائرة معينة، فإن اختيار الكواشف ليس فريدًا. على سبيل المثال، إذا قمنا بإعادة تعريف أي كاشف كـ ثم لا يزال لدينا خيار صالح للكواشف، وهذه التغييرات تت correspond إلى إضافة صف للصف من “. منذ خطأين تكون متميزة إذا وفقط إذا يمكن لمصفوفات فحص الكاشفين التمييز بين نفس الأخطاء إذا كان لديهما نفس النواة . بينما العمليات الصفية على لا تؤثر على الأخطاء التي يمكن تمييزها، وغالبًا ما يكون من الضروري أن يكون اختيار الأساس للكواشف له هيكل معين لكي يكون خوارزمية فك التشفير المعطاة قابلة للتطبيق (كما سيتم مناقشته باختصار في القسم 2.2).

وبالمثل، فإن اختيار الملاحظات المنطقية ليس فريدًا أيضًا. نظرًا لأن نتائج الكاشف تكون صفرًا بشكل حتمي في غياب الضوضاء، يمكننا إضافة أي تركيبة خطية من الكواشف إلى ملاحظة منطقية دون التأثير على قيمتها المتوقعة لدائرة خالية من الضوضاء. من حيث مصفوفات التحقق، فإن هذا التغيير يتوافق مع تعريف بعض مصفوفات الملاحظات المنطقية الجديدة. حيث أضفنا بعض التركيبات الخطية لصفوف إلى كل صف من مصفوفة الملاحظات المنطقية الأصلية :

هنا هي مصفوفة ثنائية عشوائية بأبعاد . إذا استخدمنا جهاز فك تشفير مضمون لتقديم توقع يتماشى مع المتلازمة، أي ، ثم إضافة كواشف إلى كل ملاحظة لن يغير ما إذا كان المفسر سينجح أم لا، لأن .

في الملحق د، نوضح كيف تعمل الكواشف، والملاحظات، والمصفوفات و تم تعريفها لمثال صغير لدائرة رمز تكرار بمسافة 2.

في هذا العمل، سنقتصر اهتمامنا على نماذج الأخطاء الشبيهة بالرسوم البيانية، والتي تُعرف بأنها نماذج أخطاء مستقلة حيث يقوم كل آلية خطأ بتغيير حالة ما لا يزيد عن كاشفين. لديها وزن عمود لا يزيد عن اثنين). يمكن استخدام نماذج الأخطاء الشبيهة بالرسوم البيانية لتقريب نماذج الضوضاء الشائعة للعديد من الفئات المهمة من رموز تصحيح الأخطاء الكمومية بما في ذلك رموز السطح [Den+02]، والتي -نوع و -نوع أخطاء باولي كلاهما يشبه الرسم البياني. العديد من عائلات الأكواد ذات الصلة لديها أيضًا نماذج أخطاء تشبه الرسم البياني، مثل أكواد التكرار، أكواد الفضاء الزائد ثنائية الأبعاد [BT16]، بعض أكواد النظام الفرعي ثنائية الأبعاد [Bra+13؛ SBT11؛ Bac06؛ HB21] وأكواد فلوكيه [HH21؛ Gid+21]، من بين أمور أخرى. يمكن فك تشفير الأكواد الملونة [BM06] باستخدام خريطة إلى نموذج خطأ يشبه الرسم البياني كروتين فرعي [KD23؛ GJ23]، وتعميم هذا النهج لفك تشفير أكواد أكثر عمومية هو مجال نشط للبحث [Bro22].

يمكننا تمثيل نموذج خطأ شبيه بالرسم البياني باستخدام رسم بياني للكاشف “، يُطلق عليه أيضًا اسم الرسم البياني المطابق أو الرسم البياني لفك التشفير في الأدبيات. كل عقدة يتوافق مع كاشف (عقدة كاشف، صف من ). كل حافة هي مجموعة من عقد الكاشف بعدد واحد أو اثنين تمثل آلية خطأ تقوم بتغيير حالة هذه المجموعة من الكاشفات (عمود من يمكننا تحليل مجموعة الحواف على أنها أين و حافة منتظمة يقلب زوجًا من الكواشف بينما حافة نصفية يقلب كاشفًا واحدًا . لنصف الحافة نحن أحيانًا نقول أن مرتبط بالحدود ويستخدم الرموز ، حيث هو عقدة حدودية افتراضية (لا تتوافق مع أي كاشف). لذلك، عندما نشير إلى حافة يُفترض أن هو عقدة و إما أن يكون عقدة أو عقدة الحدود . كل حافة يتم تعيين وزن وتذكر أن هي احتمالية أن آلية الخطأ يحدث. كما نحدد متجه أوزان الحواف الذي من أجله . نحن أيضًا نضع علامة على كل حافة مع مجموعة الملاحظات المنطقية التي يتم عكسها بواسطة آلية الخطأ، والتي نشير إليها إما بـ أو . نحن نستخدم للدلالة على الفرق المتناظر للمجموعات و . على سبيل المثال، هو مجموعة الملاحظات المنطقية التي تتغير عندما يتم عكس آليتي الخطأ 1 و 2. نحن نعرف المسافة بين عقدتين و في رسم بياني للكاشف ليكون طول أقصر مسار بينهما. نقدم مثالاً على رسم بياني للكاشف لدائرة شفرة التكرار في الملحق د.

من الآن فصاعدًا، سنفترض أن لدينا نموذج خطأ مستقل يشبه الرسم البياني مع مصفوفة تحقق مصفوفة الملاحظات المنطقية متجه الأوليات بالإضافة إلى الرسم البياني للكاشف المقابل مع متجه أوزان الحواف . نظرًا لوجود خطأ ما مأخوذ من نموذج الخطأ الشبيه بالرسم البياني، مع المتلازمة الملحوظة يجد جهاز فك التشفير المطابقة المثالية ذات الوزن الأدنى (MWPM) الخطأ الفيزيائي الأكثر احتمالاً المتوافق مع المتلازمة. بعبارة أخرى، بالنسبة لنموذج الخطأ الشبيه بالرسم البياني، فإنه يجد خطأً فيزيائياً. مُرضٍ الذي لديه أقصى احتمال سابق بالنسبة لنموذج الخطأ لدينا، فإن الاحتمال السابق خطأ هو

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

على الرغم من اسم جهاز فك تشفير MWPM، إلا أن المشكلة التي يحلها، كما هو محدد أعلاه، لا تتوافق مع إيجاد MWPM في ولكن بدلاً من ذلك يتوافق مع حل نوع من مشكلة MWPM، التي نشير إليها بمشكلة المطابقة المدمجة ذات الوزن الأدنى (MWEM). دعنا أولاً نحدد مشكلة MWPM التقليدية لرسم بياني. . هنا هو رسم بياني مرجح، حيث كل حافة هي زوج من العقد وعلى عكس رسومات الكاشف، لا توجد حواف نصفية. يتم تعيين وزن لكل حافة. مطابقة مثالية هو مجموعة فرعية من الحواف بحيث يكون كل عقدة يتعلق بحافة واحدة بالضبط . لكل نقول أن يتطابق مع ، والعكس صحيح. MWPM هو تطابق مثالي له أقل وزن

. من الواضح أن ليس كل رسم بياني يحتوي على تطابق مثالي (شرط بسيط ضروري هو أن يجب أن يكون عددها زوجيًا؛ الشرط الضروري والكافي موفر من خلال نظرية توتي [Tut47]، ويمكن أن يحتوي الرسم البياني على أكثر من تطابق مثالي واحد بأقل وزن.

بالنظر إلى رسم بياني للكاشف مع مجموعة الرؤوس ومجموعة من أحداث الكشف (العقد المميزة) نحن نحدد تطابقًا مضمنًا لـ في أن تكون مجموعة من الحواف بحيث يكون كل عقدة في يتعلق بعدد فردي من الحواف في وكل عقدة في يتعلق بعدد زوجي من الحواف في المطابقة المدمجة ذات الوزن الأدنى هي مطابقة مدمجة لها أقل وزن نلاحظ أن مشكلة المطابقة المدمجة ذات الوزن الأدنى لرسم بياني قياسي (لا يحتوي على حواف نصفية) تُعرف باسم الوزن الأدنى. -مشكلة الانضمام في مجال التحسين التوافقي (لـ ) [EJ73; KV18]. الاختلافات الرئيسية بين مشكلة المطابقة المدمجة ذات الوزن الأدنى التي نهتم بها من أجل تصحيح الأخطاء، ومشكلة MWPM التقليدية، موضحة في الشكل 1.

لا يحتاج جهاز فك التشفير إلى إخراج مجموعة الحواف مباشرة، بل يخرج ، توقع أي من القياسات المنطقية القابلة للملاحظة قد تم قلبها. لقد نجح جهاز فك التشفير لدينا إذا توقع بشكل صحيح أي من الملاحظات قد تم قلبها، أي إذا . بعبارة أخرى، نحن نطبق تصحيحًا على المستوى المنطقي بدلاً من المستوى الفيزيائي، وهو ما يعادل ذلك لأن . هذه المخرجات عادة ما تكون أكثر ندرة: على سبيل المثال، في تجربة ذاكرة الشيفرة السطحية، التنبؤ هو ببساطة بت واحد، يتنبأ ما إذا كان المنطقي (أو نتيجة القياس القابلة للملاحظة تم قلبها بواسطة الخطأ. كما سنرى لاحقًا، فإن التنبؤ بالملاحظات المنطقية بدلاً من الخطأ الفيزيائي الكامل يؤدي ذلك إلى بعض التحسينات المفيدة. لاحظ أن PyMatching يدعم أيضًا إرجاع الخطأ الفيزيائي الكامل (على سبيل المثال، يمكن تعيين observable فريد لكل حافة)، ولكننا نطبق هذه التحسينات الإضافية عندما يكون عدد الملاحظات المنطقية صغيرًا (حتى 64 ملاحظة).

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

على الرغم من أن تطابقات الوزن الأدنى المضمنة والتطابقات المثالية هما مشكلتان مختلفتان، إلا أن هناك ارتباطًا وثيقًا بينهما. على وجه الخصوص، من خلال استخدام خوارزمية زمنية متعددة الحدود لحل مشكلة MWPM (مثل خوارزمية الزهرة)، يمكننا الحصول على خوارزمية زمنية متعددة الحدود لحل مشكلة MWEM من خلال تقليل. سنقوم الآن بوصف هذا التقليل لحالة أن الرسم البياني للكاشف ليس له حدود، وفي هذه الحالة تكون مشكلة MWEM مكافئة لأقل وزن -مشكلة الانضمام (انظر [EJ73؛ KV18]). تم استخدام هذا الاختزال من قبل إدموندز وجونسون لخوارزمية الوقت المتعدد الحدود الخاصة بهم لحل مشكلة ساعي البريد الصيني [EJ73]. يمكن أيضًا التعامل مع الحدود مع تعديل صغير (على سبيل المثال، انظر [Fow15]).

بالنظر إلى رسم بياني للكاشف مع أوزان حواف غير سالبة (والتي، في الوقت الحالي، نفترض أنها بلا حدود، أي )، وتم إعطاء مجموعة من أحداث الكشف نحن نحدد رسم المسار أن تكون الرسم البياني الكامل على الرؤوس لكل حافة يتم تعيين وزن يساوي المسافة بين و في . هنا المسافة هو طول أقصر مسار بين و في ، حيث هنا طول المسار هو مجموع أوزان الحواف التي يحتويها. بعبارة أخرى، رسم المسار هو الرسم البياني الفرعي للإغلاق المترى لـ المستحثة بواسطة الرؤوس . ميم من في يمكن العثور عليه بكفاءة باستخدام الخطوات الثلاث التالية:

لسوء الحظ، فإن حل هذه الخطوات الثلاث بشكل متسلسل مكلف من الناحية الحسابية؛ على سبيل المثال، فإن تكلفة تعداد الحواف في يتزايد بشكل تربيعي في عدد أحداث الكشف بينما نود في المثالي أن يكون لدينا جهاز فك تشفير بوقت تشغيل متوقع يتناسب بشكل خطي في ومع ذلك، تم استخدام هذا النهج التسلسلي على نطاق واسع من قبل باحثي QEC، على الرغم من أن أدائه بعيد جدًا عن الأمثل.

تم تقديم تحسين كبير من قبل فاولر [Fow15]. كانت الملاحظة الرئيسية التي قدمها فاولر هي أنه، بالنسبة لمشاكل QEC، عادةً ما تكون الحواف ذات الوزن المنخفض فقط في تُستخدم فعليًا بواسطة بلوسوم. استغل نهج فاولر هذه الحقيقة من خلال تحديد نصف قطر استكشاف أولي في رسم كاشف، حيث تم استخدام عمليات بحث منفصلة لبناء بعض الحواف في . تم زيادة نصف قطر الاستكشاف بشكل تكيفي حسب الحاجة بواسطة خوارزمية الزهرة. نهجنا، الزهرة النادرة، مستوحى من عمل فاولر ولكنه يختلف في العديد من التفاصيل. قبل تقديم الزهرة النادرة، سنقدم نظرة عامة على خوارزمية الزهرة القياسية.

خوارزمية الزهرة، التي قدمها جاك إدموندز [Edm65b; Edm65a]، هي خوارزمية زمنها متعدد الحدود لإيجاد تطابق مثالي ذو وزن أدنى في رسم بياني. في هذا القسم، سنستعرض بعض المفاهيم الرئيسية في خوارزمية الزهرة الأصلية. لن نشرح خوارزمية الزهرة الأصلية بالكامل، حيث يوجد تداخل كبير مع خوارزمية الزهرة النادرة التي نصفها في القسم 3. بينما يوفر هذا القسم دافعًا لخوارزمية الزهرة النادرة، إلا أنه ليس شرطًا مسبقًا لبقية الورقة، لذا قد يرغب القارئ في الانتقال مباشرة إلى القسم 3. نشير القارئ إلى المراجع [Edm65b; Edm65a; Gal83; Kol09] للحصول على نظرة أكثر اكتمالاً على خوارزمية الزهرة.

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

بالنظر إلى مسار معزز في يمكننا دائمًا زيادة عدد المطابقات واحدًا بواحد عن طريق الاستبدال مع المطابقة الجديدة . نشير إلى هذه العملية، التي تتضمن إضافة كل حافة غير متطابقة في إلى وإزالة كل حافة متطابقة في من ، كما هو الحال في تعزيز المسار المعزز (انظر الشكل 2(أ)). ينص نظرية بيرج على أن التطابق له أقصى عدد من العناصر إذا وفقط إذا لم يكن هناك مسار معزز [Ber57].

سنقدم الآن نظرة عامة على النسخة الأصلية غير الموزونة من خوارزمية الزهرة، التي تجد تطابقًا بأقصى عدد من العناصر (كما قدمها إدموندز في [Edm65b]). تُستخدم خوارزمية الزهرة غير الموزونة كروتين فرعي من قبل خوارزمية الزهرة الأكثر عمومية للعثور على تطابق مثالي بأقل وزن (التي اكتشفها أيضًا إدموندز في [Edm65a])، والتي سنستعرضها في القسم 2.5.2. تستند الخوارزمية إلى نظرية بيرج. بدءًا من تطابق تافه، تتقدم من خلال العثور على مسار معزز، وتعزيز المسار، ثم تكرار هذه العملية حتى لا يمكن العثور على مسار معزز، وفي هذه النقطة نعلم أن التطابق هو الأقصى. يتم العثور على المسارات المعززة من خلال بناء أشجار متناوبة داخل الرسم البياني. شجرة متناوبة في الرسم البياني هو شجرة فرعية من مع وجود عقدة غير متطابقة كجذر لها، ولكل مسار من الجذر إلى الورقة يتناوب بين الحواف غير المتطابقة والمتطابقة، انظر الشكل 2(b). هناك نوعان من العقد في عقد “خارجي” (موسوم بـ “+”) وعقد “داخلي” (موسوم بـ “-“). كل عقدة داخلية مفصولة عن عقدة الجذر بواسطة مسار بطول فردي، بينما كل عقدة خارجية مفصولة بواسطة مسار بطول زوجي. كل عقدة داخلية لها طفل واحد (عقدة خارجية). يمكن أن تحتوي كل عقدة خارجية على أي عدد من الأطفال (جميع العقد الداخلية). جميع العقد الورقية هي عقد خارجية.

في البداية، كل عقدة غير متطابقة هي شجرة متناوبة بسيطة (عقدة جذر). للعثور على مسار معزز، يبحث الخوارزم في العقد المجاورة في العقد الخارجية في كل شجرة . إذا، خلال هذا البحث، حافة يتم العثور عليه بحيث هو عقدة خارجية لـ و هو عقدة خارجية من شجرة أخرى ثم تم العثور على مسار معزز، يربط جذور و ، انظر الشكل 2(b). يتم توسيع هذا المسار، ويتم إزالة الشجرتين، وتستمر عملية البحث. إذا كان هناك حافة ( ) يوجد بين عقدة خارجية في وعقدة متطابقة ليس في أي شجرة (أي تمت المطابقة)، ثم وتمت إضافة مباراته إلى “. أخيرًا، إذا كان هناك حافة ( إذا وُجدت ) بين عقدتين خارجيّتين من نفس الشجرة، فإن حلقة ذات طول فردي قد وُجدت، وتشكل زهرة. كانت إحدى الرؤى الرئيسية لإدموندز هي أن الزهرة يمكن اعتبارها عقدة افتراضية، يمكن مطابقتها أو أن تنتمي إلى شجرة متناوبة مثل أي عقدة أخرى. ومع ذلك، سنشرح كيف يتم التعامل مع الزهور بمزيد من التفصيل في سياق خوارزمية الزهرة النادرة لدينا في القسم 3.

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

سنشير إلى حواف الحدود لبعض مجموعة من العقد بواسطة ، وسيسمح بـ كن مجموعة جميع المجموعات الفرعية لـ من عدد فردي لا يقل عن ثلاثة، أي نحن نحدد الحواف المتصلة بعقدة واحدة بواسطة (أي ). سنستخدم متجه الحدوث لتمثيل تطابق أين إذا و إذا . نحن نحدد وزن الحافة بواسطة يمكن بعد ذلك صياغة مشكلة المطابقة المثالية ذات الوزن الأدنى كالتالي كبرنامج عددي:

قدم إدموندز الاسترخاء البرمجي الخطي التالي للبرنامج الصحيح أعلاه:

لاحظ أن القيود في المعادلة 4c تُحقق بواسطة أي تطابق مثالي، لكن إدموندز أظهر أن إضافتها تضمن أن البرنامج الخطي لديه حل مثالي صحيح. بعبارة أخرى، يمكن استبدال قيد التكامل (المعادلة 3c) بالمتباينات في المعادلة 4c والمعادلة 4d.

كل برنامج خطي (يشار إليه بالبرنامج الخطي الأساسي، أو المشكلة الأساسية) له برنامج خطي مزدوج (أو مشكلة مزدوجة). المزدوج للمشكلة الأساسية المذكورة أعلاه هو:

حيث يتم تعريف تراجع الحافة على أنه

نقول إن الحافة مشدودة إذا كانت لديها انزلاق صفر. هنا قمنا بتعريف متغير مزدوج لكل عقدة بالإضافة إلى متغير مزدوج لكل مجموعة . بينما كل متغير مقيد بأن يكون غير سالب (المعادلة 5ج)، كل مسموح له أن يأخذ أي قيمة. على الرغم من أن لدينا عددًا أسيًا من المتغيرات، يتبين أن هذه ليست مشكلة لأن فقط غير صفر في أي مرحلة من مراحل خوارزمية الإزهار.

نسترجع الآن بعض المصطلحات والخصائص العامة للبرامج الخطية (انظر [MG07؛ KV18] لمزيد من التفاصيل). تكون حل البرنامج الخطي قابلاً للتطبيق إذا كان يلبي قيود البرنامج الخطي. دون فقدان العمومية، نفترض أن البرنامج الخطي الأساسي هو مشكلة تقليل (وفي هذه الحالة يكون ثنائيه مشكلة تعظيم). بموجب نظرية الازدواجية القوية، إذا كان لكل من البرنامج الخطي الأساسي والثنائي حل قابل للتطبيق، فإن كلاهما يمتلك أيضًا حلاً مثاليًا. علاوة على ذلك، فإن الحد الأدنى من المشكلة الأساسية يساوي الحد الأقصى من ثنائيتها، مما يوفر “دليلاً عددياً” على المثالية.

يمكننا الحصول على دليل “تركيبي” على الأمثلية لأي برنامج خطي باستخدام شروط التراخي التبادلي. كل قيد في المشكلة الأولية مرتبط بمتغير من المشكلة المزدوجة (وعكس ذلك صحيح). دعنا نربط الـ القيد الأساسي مع المتغير الثنائي (وعكس ذلك). تنص شروط التكميلية على أنه، إذا كان لدينا زوج من الحلول المثلى، فإن إذا كان إذا كانت المتغير الثنائي أكبر من الصفر، فإن يتم تحقيق القيد الأساسي بالتساوي. وبالمثل، إذا كان إذا كانت المتغير الأساسي أكبر من الصفر، فإن يتم تحقيق القيد المزدوج بالتساوي. بشكل أكثر تحديدًا، بالنسبة لزوج البرامج الخطية الأولية والثانوية المحددة التي نعتبرها، فإن شروط التراخي التكاملي هي:

تُستخدم هذه الشروط كقاعدة توقف في خوارزمية الزهرة (مع تحقيق المعادلة 7 طوال الوقت) وتوفر دليلاً على الأمثلية.

بينما من الملائم استخدام نظرية الازدواجية القوية، لأنها تنطبق على أي برنامج خطي، إلا أن صحتها ليست بديهية على الفور وإثباتها معقد للغاية (انظر [MG07؛ KV18]). لحسن الحظ، يمكننا الحصول على إثبات بسيط لجدوى مشكلة المطابقة المثالية ذات الوزن الأدنى مباشرة، دون الحاجة إلى نظرية الازدواجية القوية [Gal83]. أولاً، نلاحظ أنه بالنسبة لأي حل مزدوج قابل للتطبيق، لدينا أن أي مطابقة مثالية يُرضي

حيث هنا المساواة تأتي من تعريف وتستخدم المعادلة 5 ب والمعادلة 5 ج (أي حقيقة أن الحل المزدوج قابل للتطبيق) وحقيقة أن هو تطابق مثالي. ومع ذلك، إذا كان لدينا تطابق مثالي التي تلبي أيضًا المعادلة 7 والمعادلة 8 بدلاً من ذلك لدينا

وهكذا المطابقة المثالية يتميز بوزن خفيف جداً.
حتى الآن في هذا القسم، نظرنا فقط في الحالة التي يكون فيها كل حافة زوجًا من العقد (مجموعة ذات عدد عناصر يساوي اثنين). دعونا الآن نعتبر الحالة الأكثر عمومية (المطلوبة لفك التشفير) حيث يمكن أن يكون لدينا أيضًا حواف نصفية. بشكل أكثر تحديدًا، لدينا الآن مجموعة الحواف حيث كل هو حافة منتظمة وكل هو نصف حافة (مجموعة عقد ذات عدد واحد). نلاحظ أن المطابقة المثالية تُعرف الآن كمجموعة فرعية من هذه المجموعة العامة من الحواف، لكن تعريفها بخلاف ذلك لم يتغير (المطابقة المثالية هي مجموعة حواف). بحيث يكون كل عقدة متصلة بحافة واحدة بالضبط في ). نحن نوسع تعريفنا لـ أن يكون

مع هذا التعديل، لا يزال الدليل البسيط على الصحة أعلاه ساريًا و slack(e) لحافة نصفية محدد بشكل جيد بواسطة المعادلة 6.

يبدأ خوارزمية الإزهار لإيجاد تطابق مثالي ذو وزن أدنى بتطابق فارغ وحل ثنائي قابل للتطبيق، ويزيد بشكل تكراري من عدد عناصر التطابق وقيمة الهدف الثنائي مع ضمان بقاء قيود المشكلة الثنائية مُرضية. في النهاية، سيكون لدينا زوج من الحلول القابلة للتطبيق للمشكلة الأولية والثنائية التي تلبي شروط التراخي التبادلي (المعادلة 7 والمعادلة 8) في تلك النقطة نعلم أننا لدينا تطابق مثالي ذو وزن أدنى. تتقدم الخوارزمية على مراحل، حيث تتكون كل مرحلة من
تحديث “أساسي” و”ثنائي”. نكرر هذه التحديثات الأساسية والثنائية حتى لا يمكن تحقيق المزيد من التقدم، وفي هذه المرحلة، بشرط أن يقبل الرسم البياني تطابقًا مثاليًا، ستتحقق شروط التراخي التكميلية وبالتالي سيتم العثور على التطابق المثالي ذو الوزن الأدنى. سنقوم الآن بتفصيل التحديثات الأساسية والثنائية بمزيد من التفصيل.

في التحديث الأولي، نعتبر فقط الرسم البياني الفرعي من يتكون من حواف ضيقة ويحاول العثور على تطابق بمرتبة أعلى، أساسًا من خلال تشغيل تعديل طفيف على خوارزمية الزهرة غير الموزونة على هذه الرسم البياني الفرعي. في [Kol09]، تُشير العمليات الأربعة المسموح بها في التحديث الأساسي إلى “نمو” و”زيادة” و”انكماش” و”توسع”. تحدث الثلاثة الأولى من هذه بالفعل في النسخة غير الموزونة من الزهرة التي تم مناقشتها في القسم 2.5.1. تتكون عملية النمو من إضافة زوج متطابق من العقد إلى شجرة متناوبة. الزيادة هي عملية زيادة المسار بين جذور شجرتين عندما تصبح متصلة. الانكماش هو الاسم المستخدم لعملية تشكيل زهرة عند العثور على دورة ذات طول فردي. العملية التي تختلف قليلاً في النسخة الموزونة هي التوسع. يمكن أن تحدث هذه العملية التوسعية كلما كانت المتغير الثنائي من أجل زهرة يصبح صفرًا؛ عندما يحدث هذا، تتم إزالة الزهرة، ويتم إضافة المسار ذو الطول الفردي من خلال الزهرة إلى الشجرة المتناوبة، وتصبح العقد في المسار ذو الطول الزوجي متطابقة مع جيرانها. يختلف هذا قليلاً عن النسخة غير الموزونة كما وصفناها، حيث يتم توسيع الزهور فقط عندما يصبح المسار الذي تنتمي إليه معززًا (في هذه المرحلة، تصبح جميع العقد في دورة الزهرة متطابقة). نشير إلى القارئ إلى [Kol09] للحصول على وصف أكثر اكتمالاً لهذه العمليات في التحديث الأساسي (ومخططات مرتبطة)، على الرغم من أننا نكرر أن مفاهيم مشابهة جدًا ستتم تغطيتها بمزيد من التفصيل عندما نصف الزهرة النادرة في القسم 3.

في التحديث الثنائي، نحاول زيادة الهدف الثنائي من خلال تحديث قيمة المتغيرات الثنائية، مع ضمان بقاء الحواف في الأشجار المتناوبة والزهور مشدودة، وأيضًا ضمان بقاء المتغيرات الثنائية حلاً قابلاً للمشكلة الثنائية (يجب أن تظل المتباينات في المعادلة 5 ب والمعادلة 5 ج مُرضية). بشكل عام، الهدف من التحديث الثنائي هو زيادة الهدف الثنائي بطريقة تجعل المزيد من الحواف تصبح مشدودة، مع ضمان بقاء الأشجار المتناوبة الحالية، والزهور، والحواف المتطابقة سليمة. المتغيرات الثنائية الوحيدة التي نقوم بتحديثها هي تلك التي تنتمي إلى العقد في شجرة متناوبة. لكل شجرة متناوبة نحن نختار تغييرًا مزدوجًا ونزيد المتغير الثنائي لكل عقدة خارجية مع لكن قلل المتغير الثنائي لكل عقدة داخلية مع تذكر أن كل عقدة في إما أن يكون عقدة عادية أو زهرة، وإذا كانت العقدة زهرة، فإننا نقوم بتغيير المتغير الثنائي للزهرة (مع ترك المتغيرات الثنائية للعقد التي تحتويها دون تغيير). لاحظ أن هذا التغيير يضمن أن تظل جميع الحواف الضيقة ضمن شجرة متناوبة معينة ضيقة، ولكن نظرًا لأن المتغيرات الثنائية للعقد الخارجية تزداد، فمن الممكن أن تصبح بعض الحواف المجاورة لها (غير الضيقة) ضيقة (على أمل أن يسمح لنا ذلك بالعثور على مسار معزز بين الأشجار المتناوبة في التحديث الأولي التالي). تفرض قيود المشكلة الثنائية (المتباينات المعادلة 5ب والمعادلة 5ج) قيودًا على اختيار ؛ على وجه الخصوص، يجب أن تظل الفجوات لجميع الحواف غير سالبة، ويجب أن تظل المتغيرات الثنائية للزهور أيضًا غير سالبة.

هناك العديد من الاستراتيجيات المختلفة الصالحة التي يمكن اتخاذها للتحديث المزدوج. في نهج الشجرة الواحدة، نختار شجرة واحدة. وتحديث المتغيرات الثنائية فقط للعقد في بالحد الأقصى بحيث تظل قيود المشكلة المزدوجة مُرضية (على سبيل المثال، نقوم بتغيير المتغيرات المزدوجة حتى يصبح حافة مشدودة أو يصبح متغير الزهرة المزدوجة صفرًا). في شجرة ثابتة متعددة نقوم بتحديث المتغيرات المزدوجة لجميع الأشجار المتناوبة بنفس المقدار (مرة أخرى بأقصى قدر يضمن بقاء القيود المزدوجة مُرضية). في متغير شجرة متعددة نهج، نختار مختلفاً لكل شجرة نسختنا من خوارزمية الزهرة (زهرة متفرقة) تستخدم شجرة ثابتة متعددة النهج. هذه هي الفروق الرئيسية مع المراجع [FWH12a; FWH12b; Fow15]، التي تستخدم بدلاً من ذلك نهج الشجرة الواحدة. انظر [Kol09] لمناقشة أكثر تفصيلاً ومقارنة بين هذه الاستراتيجيات المختلفة.

في الشكل 2(c) نقدم مثالاً مع شجرتين متناوبتين، ونصور متغيراً مزدوجاً كونه نصف قطر منطقة دائرية مركزة على عقدته. من خلال تصور المتغيرات المزدوجة بهذه الطريقة، يكون الحافة بين عقدتين تافهتين مشدودة إذا كانت المناطق عند نقاط نهايتها تلامس. في هذا المثال، نقوم بتحديث المتغيرات المزدوجة (الأشعة) حتى تلامس الشجرتان المتناوبتان، في هذه النقطة تصبح الحافة التي تربط الشجرتين مشدودة، ويمكننا زيادة المسار بين جذور الشجرتين. لاحظ أنه يمكننا فقط تصور المتغيرات المزدوجة كأشعة مناطق بهذه الطريقة عندما تكون غير سالبة. بينما تكون المتغيرات المزدوجة للزهور دائماً غير سالبة (كما يفرضه المعادلة 5c)، يمكن أن تصبح المتغيرات المزدوجة للعقد العادية سالبة بشكل عام. ومع ذلك، عند تشغيل خوارزمية الزهرة
في رسم بياني على شكل مسار، فإن المتغير الثنائي لكل عقدة منتظمة يكون دائمًا غير سالب، وذلك بسبب هيكل الرسم البياني. يمكن فهم ذلك على النحو التالي. اعتبر أي عقدة داخلية منتظمة. هذا ليس زهرة، التي يجب أن تحتوي بالضرورة على عقدة خارجية واحدة فقط. في شجرتها المتناوبة (مطابقتها)، بالإضافة إلى عقدتها الخارجية الأم الواحدة تذكر أن رسم المسار هو رسم بياني كامل حيث الوزن لكل حافة ( ) هو طول أقصر مسار بين العقد و في بعض الرسوم البيانية الأخرى (على سبيل المثال، في حالتنا دائمًا رسم بياني للكاشف). لذلك هناك أيضًا حافة ( ) في رسم المسار مع الوزن ، حيث نعلم أن هناك على الأقل مسار واحد من إلى بطول ، الذي يتوافق مع اتحاد أقصر مسار من إلى وأقصر طريق من إلى . لذلك، لا يمكننا أن نملك دون أن يكون الذي سينتهك المعادلة 5 ب. بشكل أكثر تحديدًا، إذا ثم نعلم أن الحافة يجب أن تكون محكمة، مما يعني أنه يمكننا تشكيل زهرة جديدة من دورة الزهور ( يمكن أن تصبح هذه الزهرة عقدة خارجية في الشجرة المتناوبة (التي قد تكون الآن تافهة).

النسخة من خوارزمية الزهرة التي نقدمها، والتي نسميها الزهرة النادرة، تحل مباشرةً مشكلة المطابقة المدمجة ذات الوزن الأدنى المتعلقة بتصحيح أخطاء الكم. الزهرة النادرة لا تحتوي على خطوة ديكسترا منفصلة لبناء الحواف في رسم المسار. . بدلاً من ذلك، يتم استرداد معلومات أقصر مسار كجزء من نمو الأشجار المتناوبة نفسها. بعبارة أخرى، نحن نكتشف ونخزن حافة فقط في بالضبط إذا ومتى كانت مطلوبة من قبل خوارزمية بلوسوم؛ الحواف التي نتتبعها في أي نقطة في الخوارزمية تتوافق تمامًا مع مجموعة الحواف الضيقة في يتم استخدامه لتمثيل شجرة متناوبة، أو زهرة، أو مباراة. وهذا يؤدي إلى تسريع كبير جداً مقارنة بالنهج التسلسلي، حيث تكون جميع الحواف في توجد باستخدام بحث ديكسترا، على الرغم من أن الغالبية العظمى منها لا تصبح أبدًا حوافًا ضيقة في خوارزمية الزهرة. نحن نسمي الخوارزمية زهرة متناثرة، لأنها تستغل حقيقة أن نسبة صغيرة فقط من عقد الكاشف تتوافق مع أحداث الكشف لمشاكل تصحيح الأخطاء الكمية النموذجية (ويمكن ربط أحداث الكشف محليًا)، ولتلك المشاكل، تفحص طريقتنا فقط مجموعة صغيرة من العقد والحواف في رسم الكاشف.

قبل شرح الزهرة النادرة وتنفيذنا، سنقوم أولاً بتقديم وتعريف بعض المفاهيم.

منطقة تعبئة الرسم البياني نصف القطر هو منطقة استكشافية من رسم بياني للكاشف. منطقة ملء الرسم البياني تحتوي على العقد في رسم الكاشف التي تقع ضمن مسافة مصدره. مصدر منطقة تعبئة الرسم البياني هو إما حدث اكتشاف واحد، أو سطح مناطق تعبئة رسم بياني أخرى تشكل زهرة. سنقوم بتعريف الزهور لاحقًا، ومع ذلك في حالة أن منطقة تعبئة الرسم البياني لديه حدث كشف واحد كمصدره، كل عقدة تقع ضمن مسافة من محتوى في تذكر أن المسافة بين عقدتين و هو مجموع أوزان الحواف على طول أقصر مسار وزني بينهما. لاحظ أن منطقة ملء الرسم البياني في الزهرة النادرة تشبه عقدة أو زهرة في خوارزمية الزهرة القياسية، ونصف قطر منطقة ملء الرسم البياني يشبه المتغير الثنائي لعقدة أو زهرة في الزهرة القياسية. تتقدم خوارزمية الزهرة النادرة على طول خط زمني (انظر القسم 3.1.7)، ويمكن أن يكون لنصف قطر كل منطقة ملء رسم بياني واحد من ثلاثة معدلات نمو: +1 (تنمو)، -1 (تنكمش) أو 0 (مجمدة). لذلك، في أي وقت يمكننا تمثيل نصف قطر منطقة باستخدام معادلة ، حيث سنشير أحيانًا إلى منطقة ملء الرسم البياني ببساطة على أنها منطقة عندما يكون ذلك واضحًا من السياق.

نرمز بـ مجموعة أحداث الكشف في منطقة عندما تحتوي منطقة على حدث كشف واحد فقط، نحن نشير إلى ذلك على أنه منطقة تافهة. يمكن أن تحتوي المنطقة على أحداث كشف متعددة إذا كان لديها زهرة كمصدر لها. بالإضافة إلى معادلة نصف القطر الخاصة بها، قد تحتوي كل منطقة ملء رسم بياني أيضًا على أطفال زهرة ووالد زهرة (كلاهما معرف في القسم 3.1.6). كما أن لديها منطقة قشرة، مخزنة ككومة. منطقة القشرة لمنطقة ما هي مجموعة من عقد الكاشف التي تحتوي عليها، باستثناء عقد الكاشف الموجودة في أطفال الزهرة الخاصة بها. نقول إن ملء الرسم البياني

المنطقة نشطة إذا لم يكن لديها والد مزهر. سنسمح بـ تشير إلى مجموعة جميع مناطق ملء الرسم البياني.

يمثل الحافة المضغوطة مسارًا عبر رسم الكاشف بين حدثين للكشف، أو بين حدث كشف وحدود. بالنظر إلى مسار بين و ، حيث هو حدث اكتشاف و إما حدث اكتشاف أو يدل على الحدود، الحافة المضغوطة مرتبط بـ هو زوج من العقد ( ) عند نقاط النهاية لـ بالإضافة إلى مجموعة الملاحظات المنطقية مقلوب عن طريق قلب جميع الحواف في الحافة المضغوطة لذلك هو تمثيل مضغوط للمسار تحتوي على جميع المعلومات المتعلقة بتصحيح الأخطاء، ويمكن تخزينها، بالنسبة لرسم بياني للكاشف معين، باستخدام كمية ثابتة من البيانات (غير معتمدة على طول المسار). عندما يكون اختيار المسار لزوج من أحداث الكشف المعطاة ( من الواضح من السياق، يمكننا الإشارة إلى الحافة المضغوطة بدلاً من ( )، وقد تشير أيضًا إلى مجموعة الملاحظات المنطقية بواسطة نحدد طول الحافة المضغوطة بأنه المسافة بين نقطتي نهايته و .

كل حافة مضغوطة في الإزهار المتناثر يتوافق مع أقصر مسار بين و . ومع ذلك، يمكننا استخدام حافة مضغوطة لتمثيل أي مسار بين و وعند استخدامها في خوارزمية الاتحاد-البحث (انظر الملحق أ) فإن المسار لا تحتاج أن تكون بحد أدنى من الوزن. تُستخدم الحواف المضغوطة في تمثيل عدة هياكل بيانات في الزهرة النادرة (الأشجار المتناوبة، المطابقات والزهور). على وجه الخصوص، كل حافة مضغوطة ( ) يتوافق مع حافة في رسم المسار ، ولكن على عكس النهج التسلسلي القياسي لتنفيذ جهاز فك التشفير MWPM، نحن نكتشف ونبني فقط مجموعة صغيرة من الحواف في مطلوب من الزهرة النادرة.

سنسمح كن مجموعة جميع الحواف المضغوطة الممكنة التي يمكن أن تمثل أقصر المسارات بين عقد الكاشف (أي المجموعة يحتوي على حافة مضغوطة ( ) لكل حافة في ). لمنطقة نرمز بـ حواف مضغوطة على الحدود ، يُعرَّف بأنه

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

بالنسبة لأي حافة منطقة تظهر في الإزهار النادر، فإن الثوابت التالية دائمًا ما تكون صحيحة:

بعبارة أخرى، إذا كان هناك حافة منطقة ( )، ثم المناطق و يجب أن يكون مؤثراً.

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

الشجرة المتناوبة هي شجرة حيث يتوافق كل عقدة مع منطقة ملء نشطة في الرسم البياني، ويتوافق كل حافة مع حافة المنطقة. نشير إلى كل حافة منطقة في الشجرة المتناوبة باسم حافة الشجرة. يجب أن تكون المنطقتان المتصلتان بحافة الشجرة متلامستين دائمًا (نظرًا لأن كل حافة شجرة هي حافة منطقة).

تحتوي الشجرة المتناوبة على منطقة نمو واحدة على الأقل ويمكن أن تحتوي أيضًا على مناطق انكماش، وتحتوي دائمًا على منطقة نمو واحدة أكثر من منطقة انكماش. يمكن أن تحتوي كل منطقة نمو على أي عدد من الأطفال (كل منهم طفل شجرة)، يجب أن تكون جميعها مناطق انكماش، ويمكن أن يكون لها والد واحد (والد شجرة)، وهو أيضًا منطقة انكماش. تحتوي كل منطقة انكماش على طفل واحد، وهو منطقة نمو، بالإضافة إلى والد واحد، وهو أيضًا منطقة نمو. لذلك، فإن أوراق الشجرة المتناوبة هي دائمًا مناطق نمو. مثال على شجرة متناوبة موضح في الشكل 3.

عندما تصطدم منطقتان نمو من نفس الشجرة المتناوبة ببعضهما البعض، فإنهما تشكلان زهرة، وهي منطقة تحتوي على دورة ذات طول فردي من المناطق تُسمى دورة الزهرة. بشكل أكثر تحديدًا، سنشير إلى دورة الزهرة كزوج مرتب من المناطق ( ) لبعض الأعداد الفردية وكل منطقة في دورة الزهرة متصلة بكل من جيرانهما بواسطة حافة منطقة. بعبارة أخرى، تحتوي دورة الزهرة على حواف مناطق . مثال على زهرة موضح على الجانب الأيمن من الشكل 3.

تُسمى المناطق في دورة الزهرة بأطفال الزهرة. إذا كانت زهرة تحتوي على منطقة كواحد من أطفالها، فإننا نقول إن هو والد الزهرة لـ . يجب أن تكون المناطق المجاورة في دورة الزهرة متلامسة (كما يتطلب الأمر من كونها متصلة بواسطة حافة منطقة). يمكن أيضًا أن تكون الأزهار متداخلة؛ يمكن أن يكون كل طفل زهرة بنفسه زهرة، مع أطفاله الخاصين. على سبيل المثال، فإن الطفل الأيسر العلوي من الزهرة في الشكل 3 هو زهرة بنفسه، مع ثلاثة أطفال زهرة. يُعتبر سليل زهرة من زهرة منطقة إما أنها طفل زهرة لـ أو أنها بشكل متكرر سليل لأي طفل زهرة من . وبالمثل، فإن سلف زهرة من هو منطقة إما أنها والد الزهرة لـ أو (بشكل متكرر) سلف والد الزهرة لـ . نصف القطر لزهرة (متغيرها المزدوج في خوارزمية الزهرة القياسية) هو المسافة التي نمتها منذ تشكيلها (أقل مسافة بين نقطة على
سطحها وأي نقطة على مصدرها). يتم تصور ذلك على أنه المسافة عبر قشرة الزهرة في الشكل 3.

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

حيث هنا تشير إلى أن إما أنها سليل لـ أو . إذا كانت فإن عقدة الكاشف مملوكة للمنطقة ، إذا كانت فإن عقدة الكاشف ليست مملوكة لـ ، بينما إذا كانت فإن قد تكون مملوكة أو لا تكون مملوكة لـ (إنها على سطح ).

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

تنقسم زهرة متفرقة إلى مكونات مختلفة: مطابقة، ومغمر، ومتتبع. كل مكون له مسؤوليات مختلفة. المطابق مسؤول عن إدارة هيكل الأشجار المتناوبة والأزهار، دون معرفة الهيكل الأساسي لرسم الكاشف. يتعامل المغمر مع كيفية نمو مناطق ملء الرسم البياني وانكماشها في رسم الكاشف، بالإضافة إلى ملاحظة متى تصطدم منطقة بمنطقة أخرى أو الحدود. عندما يلاحظ المغمر اصطدامًا يتضمن منطقة، أو عندما تصل منطقة إلى نصف قطر صفر، يقوم المغمر بإخطار المطابق، الذي يكون مسؤولًا بعد ذلك عن تعديل هيكل الأشجار المتناوبة أو الأزهار. المتتبع مسؤول عن التعامل مع متى تحدث الأحداث المختلفة، ويضمن أن يتعامل المغمر مع الأحداث بالترتيب الصحيح، بمساعدة قائمة انتظار ذات أولوية واحدة. قائمة انتظار ذات أولوية هي نوع من قائمة الانتظار، تحتفظ بمجموعة من العناصر، مع خاصية أن العنصر الذي تمت إزالته من قائمة الانتظار (مع عملية “استخراج الحد الأدنى”) مضمون أن يكون له أعلى أولوية بين جميع العناصر في قائمة الانتظار (في حالتنا، كل عنصر هو حدث، مع أوقات الأحداث السابقة التي تتوافق مع أولوية أعلى). يستخدم المتتبع هذه القائمة ذات الأولوية لإبلاغ المغمر متى يجب التعامل مع كل حدث.

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

عندما يلاحظ المغمر أن منطقة نمو قد اصطدمت بمنطقة أخرى (نمو أو مجمدة) أو الحدود، فإنه يجد حافة الاصطدام ويعطيها للمطابق. حافة الاصطدام هي حافة منطقة بين و (أو، إذا كانت قد اصطدمت بالحدود، فإنها تكون بين والحدود). يمكن بناء حافة الاصطدام بواسطة المغمر من المعلومات المحلية في نقطة الاصطدام، كما سيتم شرحه في القسم 3.4، وتستخدم من قبل المطابق عند التعامل مع الأحداث التي تغير هيكل الشجرة المتناوبة (التي نشير إليها بأحداث الشجرة المتناوبة). المطابق مسؤول عن التعامل مع أحداث الشجرة المتناوبة، وكذلك عن استرداد أزواج أحداث الكشف المتطابقة بمجرد مطابقة جميع المناطق.

هناك سبعة أنواع مختلفة من الأحداث التي يمكن أن تغير هيكل شجرة متناوبة، والتي يتم التعامل معها من قبل المطابق، موضحة في الشكل 4:
(أ) يمكن أن تصطدم منطقة نمو في شجرة متناوبة بمنطقة التي تم مطابقتها مع منطقة أخرى . في هذه الحالة، تصبح طفلاً شجرة لـ في (وتبدأ في الانكماش)، وتصبح طفلاً شجرة لـ في (وتبدأ في النمو). تصبح حافة الاصطدام ( ) وحافة المطابقة ( ) كلاهما حواف شجرة ( هو والد الشجرة لـ ، و هو والد الشجرة لـ ).
(ب) تصطدم منطقة نمو في شجرة متناوبة بمنطقة نمو في شجرة متناوبة مختلفة . عندما يحدث ذلك، يتم مطابقة مع وتصبح المناطق المتبقية في و أيضًا متطابقة. تصبح حافة الاصطدام ( ) حافة مطابقة، وتصبح مجموعة من حواف الشجرة أيضًا حواف مطابقة. تصبح جميع المناطق في و مجمدة.
(ج) يمكن أن تصطدم منطقة نمو في شجرة متناوبة بمنطقة نمو أخرى في نفس الشجرة المتناوبة . يؤدي ذلك إلى دورة ذات طول فردي من المناطق التي تشكل دورة الزهرة لزهرة جديدة . تتشكل حواف المناطق (حواف الزهرة) في دورة الزهرة من حافة الاصطدام ( )، بالإضافة إلى حواف الشجرة على طول المسارات من و إلى سلفهما المشترك الأكثر حداثة في . تصبح الزهرة الجديدة المتكونة عقدة نمو في . عند تشكيل الدورة ، نعرف الأيتام على أنهم مجموعة من مناطق الانكماش في ولكن ليس التي كانت كل منها طفلاً لمنطقة نمو في . تصبح الأيتام أطفال شجرة لـ في . الحافة المضغوطة المرتبطة بحافة الشجرة الجديدة ( ) (التي تربط منطقة الزهرة الجديدة بوالد شجرتها ) هي فقط الحافة المضغوطة التي كانت مرتبطة بحافة الشجرة القديمة ( ). وبالمثل، تبقى الحواف المضغوطة التي تربط كل يتيم بوالده في الشجرة المتناوبة دون تغيير (حتى لو أصبحت منطقة والده ). بعبارة أخرى، إذا كان يتيم قد تم توصيله بوالده في الشجرة بواسطة حافة الشجرة قبل تشكيل الزهرة، فإن حافة الشجرة الجديدة التي تربطه بوالده الجديد في الشجرة ستكون ( ) بمجرد تشكيل الزهرة وتصبح المنطقة جزءًا من دورة الزهرة .
(د) عندما تكون زهرة في شجرة متناوبة ينكمش إلى نصف قطر صفر، بدلاً من أن يصبح نصف القطر سالبًا، يجب أن يتشقق الزهرة. عندما تتشقق الزهرة، فإن المسار ذو الطول الفردي من خلال دورة زهورها من شجرة الطفل إلى شجرة الوالدين لـ يتم إضافته إلى كمناطق متزايدة ومتقلصة. يصبح المسار ذو الطول الزوجي مطابقات. تصبح حواف الزهرة في المسار ذو الطول الفردي حواف شجرية، وبعض حواف الزهرة في المسار ذو الطول الزوجي تصبح حواف مطابقة (تُنسى حواف الزهرة المتبقية). لاحظ أن نقاط النهاية للحواف المضغوطة المرتبطة بالحواف الشجرية التي تربط يتم استخدام الشجرة الأم والشجرة الابنة لتحديد مكان وكيفية تقسيم دورة الإزهار إلى مسارين.
(هـ) عندما تكون المنطقة تافهة ينكمش إلى نصف قطر صفر، بدلاً من أن يصبح نصف القطر سالبًا، تتشكل زهرة. إذا لديه طفل والوالد في الشجرة المتناوبة عندما له نصف قطر صفر، يجب أن يكون ذلك يؤثر كأنه قد تصادم مع ). الزهرة التي تشكلت حديثًا لديه دورة الإزهار ( ). حواف الشجرة القديمة ( ) و ( تتحول حواف الزهرة في دورة الإزهار. الحافة الزهرية التي تربط مع في دورة الإزهار يتم حسابها من الحواف ( ) و ( ) و هو ( ). بعبارة أخرى، فإن حافته المضغوطة لها نقاط نهاية ( ) مع الملاحظات المنطقية .
(و) عندما تكون منطقة نامية في شجرة متناوبة يصل إلى الحدود، تتطابق مع الحدود ويصبح حافة الاصطدام هي حافة المباراة. المناطق المتبقية في أيضًا تصبح مباريات.
(ز) عندما تكون منطقة نامية في شجرة متناوبة يضرب منطقة الذي يتطابق مع الحدود، ثم بدلاً من ذلك يصبح متطابقًا مع (ويصبح حافة الاصطدام هي حافة المباراة)، والحواف المتبقية في أيضًا تصبح مباريات.
بعض هذه الأحداث تتضمن تغيير معدل نمو المناطق (على سبيل المثال، تصبح منطقتان تنموان كلتاهما مناطق متجمدة عندما تتطابقان مع بعضهما). لذلك، عند التعامل مع كل حدث شجرة متناوبة، يقوم المطابق بإبلاغ الفاضح بأي تغييرات مطلوبة في نمو المنطقة.