تشفير هوفمان k-ary: الشرح الكامل مع خطوات بناء الشجرة
تشفير هوفمان k-ary هو تعميم لخوارزمية هوفمان الكلاسيكية تستخدم فيه أبجدية مكوّنة من k رموز بدل رمزين فقط (0 و1)، فتنتج شجرة يملك كل عقدة داخلية فيها حتى k فروع بدل فرعين. الهدف واحد: توليد شيفرة بادئة (prefix code) الأقصر في المتوسط، لكن هذه المرة عندما تكون وسيلة التخزين أو الإرسال قادرة على التعامل مع أكثر من رمزين، مثل نظام ثلاثي (0، 1، 2) أو رباعي. باختصار: الثنائي حالة خاصة من k-ary عند k = 2.
الفكرة الأساسية في جملة
الرموز الأكثر تكرارًا تحصل على أكواد أقصر، والأقل تكرارًا على أكواد أطول، لكن كل «خانة» في الكود الآن يمكن أن تأخذ أحد k قيم بدل قيمتين. هذا يقلّل عدد الخانات اللازمة، لأن كل خانة تحمل معلومات أكثر (كل رمز يحمل log₂k بت نظريًا).
الفرق بين هوفمان الثنائي وk-ary
| العنصر | هوفمان الثنائي (k = 2) | هوفمان k-ary |
|---|---|---|
| أبجدية الكود | رمزان: 0 و1 | k رمزًا: 0 … k−1 |
| فروع كل عقدة | حتى فرعين | حتى k فروع |
| عدد الدمج في كل خطوة | أصغر عقدتين | أصغر k عقد |
| شرط اكتمال الشجرة | متحقق تلقائيًا | يتطلب عقد حشو أحيانًا |
| الاستخدام | التخزين الرقمي الثنائي المعتاد | أنظمة متعددة الرموز، عتاد خاص |
خطوات بناء شجرة هوفمان k-ary
- احسب تكرار كل رمز في البيانات المراد ضغطها (كم مرة يظهر كل حرف أو بايت).
- صحّح عدد الأوراق بإضافة عقد حشو إذا لزم — وهذه أهم خطوة يغفلها كثيرون (اشرحها في القسم التالي).
- ضع كل الرموز في قائمة أولوية (min-heap) مرتّبة تصاعديًا حسب التكرار.
- اسحب أصغر k عقد من القائمة وادمجها في عقدة أب جديدة وزنها = مجموع أوزانها، ثم أعد إدخال هذه العقدة في القائمة.
- كرّر الخطوة 4 حتى تبقى عقدة واحدة هي جذر الشجرة.
- خصّص كودًا لكل رمز بقراءة المسار من الجذر إلى الورقة؛ كل فرع يحمل رقمًا من 0 إلى k−1، فيتكوّن الكود من تسلسل هذه الأرقام.
الزمن الكلي مع كومة الأولوية هو O(n log n)، حيث n عدد الرموز، تمامًا كالنسخة الثنائية.
النقطة التي يغفلها الكثيرون: عقد الحشو
لكي تكون الشجرة «مكتملة» — أي كل عقدة داخلية لها بالضبط k أبناء — يجب أن يحقق عدد الأوراق L الشرط التالي:
(L − 1) قابلة للقسمة على (k − 1).
إذا لم يتحقق هذا الشرط، فأضف عقد حشو (dummy symbols) بتكرار صفر حتى يتحقق. هذه العقد لا تظهر في البيانات ولا تؤثر على الطول المتوسط، لكن تجاهلها يجعل خطوة الدمج الأخيرة تجمع أقل من k عقد فتفسد الأمثلية (لن يكون الكود الأقصر الممكن). في النسخة الثنائية k = 2 يصبح الشرط (L − 1) قابلة للقسمة على 1، وهو متحقق دائمًا، ولذلك لا نسمع عن عقد الحشو في الشرح الثنائي.
مثال على الحساب: لديك 6 رموز وتريد k = 3. نحسب (6 − 1) mod (3 − 1) = 5 mod 2 = 1، وهي ليست صفرًا، لذا نضيف عقدة حشو واحدة ليصبح العدد 7، لأن (7 − 1) mod 2 = 0.
مثال عملي سريع (k = 3)
لنفترض الترددات: A=10، B=7، C=5، D=4، E=3، F=2. أضفنا عقدة حشو Z=0 (كما حسبنا أعلاه) فصار لدينا 7 أوراق:
- الدمج الأول: أصغر ثلاث عقد Z(0) + F(2) + E(3) = عقدة وزنها 5.
- الدمج الثاني: أصغر ثلاث عقد D(4) + C(5) + العقدة(5) = عقدة وزنها 14.
- الدمج الثالث: B(7) + A(10) + العقدة(14) = 31، وهي الجذر.
الآن الرموز الأعمق (E، F، Z) تأخذ كودين من خانتين ثلاثيتين، بينما A وB اللذان تكرارهما أعلى يجلسان أقرب للجذر ويأخذان كودًا من خانة واحدة، وهو بالضبط ما نريده.
متى تستخدم k-ary ولماذا
النسخة الثنائية هي الافتراضية لأن الحواسيب تخزّن بت 0/1. لكن k-ary مفيد عندما تكون قناة الإخراج نفسها متعددة الحالات: أنظمة اتصال ثلاثية أو رباعية، بعض ذاكرات الفلاش متعددة المستويات (MLC/TLC)، أو عندما تريد موازنة عمق الشجرة مقابل عدد الرموز في تطبيق معيّن. القاعدة العامة: كلما زاد k قصرت الشجرة وقلّ متوسط عدد الخانات، لكن كل خانة تحتاج تمثيل رمز أعرض.
الأسئلة الشائعة
هل تشفير هوفمان k-ary أفضل دائمًا من الثنائي؟ ليس بالضرورة. الأفضلية تُقاس بأبجدية الإخراج: إذا كان جهازك يخزّن بت ثنائية، فالثنائي هو الأمثل عمليًا. أما إذا كانت القناة تدعم k رموز فعليًا، فـ k-ary يعطي متوسط طول أقصر بوحدة الرموز.
ما علاقة k-ary بالإنتروبيا؟ الطول المتوسط الأمثل يقترب من إنتروبيا المصدر محسوبة بالأساس k، أي H_k = H₂ ÷ log₂k. لذلك كلما كبر k صغر عدد الرموز المتوقّع لكل حرف.
لماذا نضيف عقدًا بتكرار صفر؟ لضمان أن كل دمج يجمع بالضبط k عقد حتى الخطوة الأخيرة، وهذا شرط لازم لأمثلية الكود. حذفها قد ينتج شيفرة صحيحة لكنها ليست الأقصر.
هل ينطبق هذا على ضغط ملفات مثل ZIP أو JPEG؟ هذه الأدوات تستخدم هوفمان الثنائي (غالبًا مع خوارزميات أخرى مثل DEFLATE). النسخة k-ary موضوع أكاديمي ونظري أكثر منها معيارًا شائعًا في صيغ الملفات اليومية.