شرح ترميز هوفمان
تخزّن الحواسيب عادةً كل حرف بالعدد نفسه من البتات، ثمانية في ASCII العادي. وهذا بسيط لكنه مُهدِر، لأن بعض الحروف أشيع من غيرها بكثير. في عام 1951 وجد طالب أفضل طريقة لإعطاء كل رمز شيفرة بطول خاص به، قصيرة للرموز المتكررة وطويلة للنادرة، بطريقة بناء بسيطة إلى حد أنها تتسع في بضعة أسطر. واليوم يوجد ترميز هوفمان داخل كل ملف مضغوط وصورة وصوت تفتحه تقريبًا.
شيفرات قصيرة للرموز الشائعة
استخدمت شيفرة مورس الفكرة منذ ثلاثينيات القرن التاسع عشر: فالحرف E، وهو أشيع حرف في الإنجليزية، نقطة واحدة، بينما Q شرطة شرطة نقطة شرطة. وشيفرة كهذه توفر الوقت والمساحة كلما ظهرت بعض الرموز أكثر من غيرها. لكن الأطوال المتغيرة تطرح مشكلة حلّتها شيفرة مورس بالفواصل الزمنية: كيف تعرف أين تنتهي شيفرة وتبدأ التالية؟ وما الطول الذي ينبغي أن يأخذه كل رمز ليكون الإجمالي أصغر ما يمكن؟
الشيفرات البادئة
تختفي المشكلة الأولى إذا لم تكن أي شيفرة بدايةً لشيفرة أخرى. فبالشيفرات A = 0 وB = 10 وC = 110 وD = 111 لا يمكن قراءة البتات 0101100 إلا على أنها A B C A: فما إن تشكّل البتات المقروءة حتى الآن شيفرة حتى تكون تلك الشيفرة مكتملة. وهذه الشيفرات البادئة تقابل تمامًا الأشجار الثنائية التي تقع رموزها في الأوراق، حيث يمثل كل فرع أيسر 0 وكل فرع أيمن 1. فاختيار شيفرة هو اختيار شجرة.
طريقة هوفمان في البناء
ابدأ بورقة لكل رمز، وزنها عدد مرات ظهوره. خذ أخف شجرتين وادمجهما تحت عقدة جديدة وزنها مجموعهما، وكرّر ذلك حتى تبقى شجرة واحدة. هذه هي الخوارزمية كلها. الرموز النادرة تُدمج أولًا فينتهي بها المطاف عميقًا في الشجرة بشيفرات طويلة، والرموز الشائعة تُدمج أخيرًا فتبقى قرب القمة بشيفرات قصيرة. وباستخدام طابور أولوية يستغرق ذلك وقتًا يتناسب مع n log n لعدد n من الرموز.
لماذا هي مثلى
في أفضل شجرة ممكنة يمكن دائمًا وضع الرمزين الأندر شقيقين في أعمق مستوى: فتبديلهما بأي شيء هناك لا يمكن إلا أن يقصّر الإجمالي. ادمجهما في رمز واحد وزنه مجموع وزنيهما، فيصبح الباقي المسألة نفسها برمز أقل، ولذلك لا تسد الخطوة الجشعة الطريق إلى أفضل جواب أبدًا. والعدد الإجمالي للبتات المستخدمة يساوي مجموع أوزان كل العقد الداخلية، وهو ما يُبقيه الدمج أصغر ما يمكن.
بحث فصلي بدلًا من امتحان
في عام 1951 التحق ديفيد هوفمان، وكان طالب دراسات عليا في MIT، بمقرر روبرت فانو في نظرية المعلومات. وخيّر فانو طلابه: إما أداء الامتحان النهائي وإما كتابة بحث فصلي عن إيجاد أكفأ شيفرة ثنائية. كاد هوفمان يتخلى عن البحث، ثم أدرك أن بناء الشجرة من الأسفل إلى الأعلى، بدلًا من تقسيمها من الأعلى إلى الأسفل كما في طريقة شانون–فانو، يعطي دائمًا أفضل نتيجة. ونشرها عام 1952؛ فتفوقت طريقة الطالب على الطريقة التي وضعها أستاذه مع كلود شانون.
قريبًا من الإنتروبيا
أثبت كلود شانون أنه لا يمكن لأي شيفرة أن تستخدم في المتوسط بتات لكل رمز أقل من إنتروبيا المصدر. وتبلغ شيفرة هوفمان الإنتروبيا تمامًا حين يكون كل احتمال قوةً للنصف، ولا تزيد عليها أبدًا ببت كامل لكل رمز. وتصبح هذه الفجوة مهمة حين يكون رمز واحد شائعًا جدًا: فالرمز الذي حصته 99% يحتاج مع ذلك إلى بت كامل على الأقل، مع أنه لا يحمل سوى نحو 0.015 بت من المعلومات. ويتجنب الترميز الحسابي وأنظمة الأعداد غير المتماثلة (ANS) في برامج الضغط الأحدث هذا القيد.
شيفرات هوفمان في كل مكان
نادرًا ما يُستخدم ترميز هوفمان وحده، لكنه يشكّل المرحلة الأخيرة في صيغ كثيرة. فخوارزمية Deflate، الموجودة داخل ZIP وgzip وPNG، تستبدل التكرارات أولًا بإحالات ثم تكتب النتيجة بشيفرات هوفمان. ويستخدمها JPEG للأعداد المتبقية بعد تحويله للصورة، وMP3 لبياناته الصوتية، وأجهزة الفاكس لأطوال تتابعات الأسود والأبيض. وعادةً ما ترسل الصيغ شيفرة هوفمان قانونية لا يلزم فيها تخزين سوى أطوال الشيفرات، لأن الشيفرات نفسها يمكن إعادة بنائها منها.
استكشفها بنفسك
افتح أداة بناء شيفرة هوفمان لتبني شجرة ABRACADABRA أو MISSISSIPPI RIVER أو جملة من تأليفك أو أي نص آخر، خطوة تلو خطوة. راقب أخف شجرتين وهما تندمجان في كل خطوة، وانقر ورقةً لترى شيفرتها، وتتبّع رمزًا عبر البتات المرمَّزة، وقارن الإجمالي بشيفرة ثابتة الطول وبـUTF-8 وبالإنتروبيا.
الأسئلة المتداولة
ما الفرق بين ترميز هوفمان وترميز شانون–فانو؟
يبني ترميز شانون–فانو الشجرة من الأعلى، فيقسم الرموز مرة بعد مرة إلى مجموعتين متقاربتين في الوزن. وهو جيد في الغالب لكنه ليس أمثل دائمًا. أما هوفمان فيبني الشجرة من الأسفل بدمج أخف شجرتين، ويعطي دائمًا أقصر شيفرة بادئة ممكنة.
هل يحتاج فاك الترميز إلى الشجرة؟
نعم، فهو يحتاج إلى الشيفرة نفسها. لذلك تخزّنها الملفات المضغوطة، عادةً في صورة قائمة بأطوال الشيفرات لشيفرة قانونية، وهي لا تشغل سوى بضع عشرات من البايتات. وفي النصوص القصيرة قد تفوق هذه الإضافة مقدار التوفير؛ والأداة لا تعدّ إلا البتات المرمَّزة.
هل يمكن أن يجعل ترميز هوفمان الملف أكبر؟
الرموز المرمَّزة لا تأخذ أبدًا بتات أكثر مما تأخذه شيفرة ثابتة الطول للرموز نفسها. لكن جدول الشيفرة يجب أن يُخزَّن أيضًا، لذا قد تكون النتيجة أكبر قليلًا من الأصل في البيانات القصيرة جدًا أو شبه العشوائية.
ماذا تقول متباينة كرافت؟
تقول إن شيفرة بادئة أطوال شيفراتها l₁ وl₂ و… توجد إذا وفقط إذا كان مجموع 2 مرفوعًا إلى القوة −l على جميع الرموز لا يزيد على 1. وفي الشجرة الكاملة، مثل كل شجرة هوفمان فيها رمزان على الأقل، يساوي المجموع 1 تمامًا.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
افتح أداة بناء شيفرة هوفمان