شفرة بروفر: كيف تعيد المتتابعة شجرة مرقمة؟

الخلاصة السريعة

تعيد الشفرة (4,4,2,4) في مثالنا الشجرة ذات الحواف 1–4 و 3–4 و 5–2 و 2–4 و 4–6. نضيف أربع حواف أثناء قراءة الرموز، ثم حافة أخيرة بين الرأسين الباقيين؛ لا نكتب رمزًا خامسًا.

• شفرة بروفر تمثل شجرة مرقمة بمتتابعة طولها أقل من عدد الرؤوس باثنين. الورقة رأس له جار واحد في الشجرة الحالية. [1]
• عند الترميز، احذف أصغر ورقة حالية وسجل جارها، حتى يبقى رأسان. وعند الاستعادة، صل أصغر رأس باقٍ لا يظهر في بقية الشفرة بأول رمز، ثم احذفه واستهلك الرمز. أخيرًا صل الرأسين الباقيين. [1]
• في مثال الأرقام 1 إلى 6، يبين الجدول اختيار 1 ثم 3 ثم 5 ثم 2؛ والرأسان الأخيران 4 و 6. يتغير الاختيار مع بقية الشفرة، ولا نعيد رأسًا حذفناه.
• الرأس 4 يظهر ثلاث مرات في الشفرة، وله أربع حواف في رسمنا. الرأس 2 يظهر مرة وله حافتان؛ والرؤوس الأخرى لا تظهر ولها حافة واحدة.
• سجلنا الجيران (4,4,2,4)، لا الأوراق المحذوفة (1,3,5,2). الرسم والجدول يوضحان هذا الفرق، ثم نعيد الترميز للتحقق.
• يلزم عدد رؤوس لا يقل عن 2، وطول صحيح ورموز ضمن الترقيم. رسمنا بلا أوزان أو اتجاهات. [1]

ما الذي تحدده الشفرة؟

يبدأ المصدر من الصفر؛ نبدأ من 1 ونحافظ على قاعدة الأصغر. للشجرة المرقمة شفرة واحدة، والشفرة الصحيحة تستعيد شجرتها. [1]

نثبت في مثالنا ستة رؤوس مختلفة تحمل الأرقام 1 و 2 و 3 و 4 و 5 و 6. للشفرة أربعة رموز لأن 6 − 2 = 4. التكرار مسموح: ظهور 4 ثلاث مرات لا يعني أن لدينا ثلاث نسخ من الرأس 4. الأرقام أسماء للرؤوس، وليست أوزانًا للحواف.

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

ابحث في الرؤوس الباقية وفي بقية الشفرة

نبدأ بالرؤوس الستة كلها وبالشفرة (4,4,2,4). الأرقام التي لا تظهر فيها هي 1 و 3 و 5 و 6، وأصغرها 1. نصل 1 بأول رمز، وهو 4، ثم نحذف 1 من الرؤوس المتاحة ونستهلك أول 4. بقيت الشفرة (4,2,4).

الرؤوس المتاحة الآن 2 و 3 و 4 و 5 و 6. من لا يظهر في (4,2,4) هو 3 و 5 و 6؛ نختار 3 ونضيف 3–4. بعد حذفه واستهلاك الرمز، بقيت (2,4). لا يعود 1 مرشحًا رغم غيابه عن الشفرة، لأنه خرج من الرسم الجاري.

مع الرؤوس 2 و 4 و 5 و 6 وبقية الشفرة (2,4)، نختار 5 ونضيف 5–2. تصبح البقية (4)، والرؤوس 2 و 4 و 6. صار 2 غير ظاهر في البقية، وهو أصغر من 6؛ لذلك نضيف 2–4. لم يكن 2 ورقة في البداية، لكنه صار ورقة في هذه الخطوة.

نفدت الرموز وبقي 4 و 6؛ نصل بينهما بالحافة 4–6. نحصل على الحواف الخمس المبينة في الصورة الرئيسية. الصف الأخير في الجدول خطوة وصل، وليس قراءة رمز إضافي.

اعكس العمل: اكتب الجار، لا الورقة المحذوفة

انظر إلى الشجرة المكتملة. أوراقها الأولى 1 و 3 و 5 و 6، فأصغرها 1 وجاره 4: نسجل 4 ونزيل 1. ثم أصغر ورقة 3، وجارها 4 أيضًا: نسجل 4. بقيت الأوراق 5 و 6 في هذه المرحلة، فنختار 5 ونسجل جاره 2.

بعد إزالة 5 صار 2 ورقة، وهو أصغر من 6. نحذف 2 ونسجل جاره 4، ثم نتوقف عند 4 و 6. ما كتبناه هو (4,4,2,4)، مطابق للمدخل. أما (1,3,5,2) فهو تسلسل الأوراق التي حذفناها؛ الخلط بين القائمتين يبدل معنى التسجيل.

سبب كتابة 2 في الرمز الثالث هو أن الورقة المختارة حينها 5، وجارها 2. وفي الرمز الرابع نكتب 4 لأن الورقة الجديدة 2 تتصل به. قاعدة الأصغر تتعلق بالورقة التي نزيلها، لا بالرقم الذي نكتبه.

افحص تكرار الأرقام بعدد الحواف

درجة الرأس هي عدد الحواف التي تتصل به. في شفرة بروفر، درجة كل رأس تساوي عدد مرات ظهوره في الشفرة زائد 1. [1]

في رسمنا، اتصل 4 بالرؤوس 1 و 3 و 2 و 6، فدرجته 4، وقد ظهر ثلاث مرات. واتصل 2 بالرأسين 5 و 4، فدرجته 2، وقد ظهر مرة واحدة. أما 1 و 3 و 5 و 6، فلكل منها حافة واحدة ولم يظهر أي منها في الشفرة.

هذه مراجعة مستقلة لأعداد المثال: بالترتيب من 1 إلى 6 نجد الدرجات (1,2,1,4,1,1)، ومجموعها 10. الحواف الخمس تعطي طرفين لكل حافة، أي 5 × 2 = 10. تطابق الأعداد يدعم الفحص، لكننا راجعنا أيضًا كل حافة وإعادة الترميز؛ لا نكتفي بالمجموع وحده.

ثبّت الترقيم وتجنب الأخطاء الثلاثة

الخطأ الأول في مثالنا هو استعمال قائمة الأرقام الغائبة في البداية طوال العمل. عند الخطوة الرابعة يجب أن يدخل 2 قائمة المرشحين؛ عندها اختفت آخر نسخ 2 من بقية الشفرة. الخطأ الثاني هو إعادة 1 أو 3 إلى الترشيح بعد حذفهما. نبحث بين الرؤوس الباقية فقط.

والخطأ الثالث هو اختيار رقم جار الورقة على أنه معيار الأصغر. عند إزالة 5 نسجل 2، ولا نقرر إزالة 2 بدلًا منها؛ كان 2 آنذاك متصلًا بكل من 5 و 4. لا يصبح ورقة إلا بعد خروج 5.

لمثالنا أربعة رموز من 1 إلى 6؛ خمسة رموز أو 7 أو 0 لا تلائمه. لرأسين تكون الشفرة فارغة ونصلهما مباشرة؛ نستثني الرأس الواحد. [1]

غيّر مكان الدائرة 4 أو ارسم الحافة 5–2 أقصر، وستبقى بيانات المثال نفسها ما دامت الأرقام والاتصالات لم تتغير. لا تستنتج من الرسم مسافة أو كلفة أو علاقة أبوة. افحص قائمة الحواف والرؤوس، ثم أعد الترميز بالقواعد نفسها.