> huffman | ترميز | أمثل <
// ترميز هوفمان - خوارزمية ضغط ثنائية أمثل خالية من تعارض البادئة
أكواد مثالية
تولّد أقصر طول متوسط للأكواد بناءً على تردد الرموز.
خالية من تعارض البادئة
لا يكون أي كود بادئةً لكود آخر، مما يسمح بفك ترميز وحيد وواضح.
معتمدة على التردد
تحصل الرموز الشائعة على أكواد أقصر تلقائياً لتحقيق ضغط أفضل.
>> معلومات تقنية
كيف يعمل ترميز هوفمان؟:
يبني ترميز هوفمان شجرة ثنائية من الأسفل إلى الأعلى. بدءاً من ترددات الرموز، يتم دمج أقل عقدتين في التردد في عقدة أب، وتتكرر العملية حتى يبقى الجذر فقط. الفروع اليسرى تمثل '0' واليمنى '1'. الرموز الأكثر تكراراً تحصل على أكواد أقصر، وهذا يحقق ضغطاً أمثلاً للتوزيع المعطى للترددات.
مثال على ترميز هوفمان:
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
لماذا نستخدم ترميز هوفمان؟:
- ▸نسبة ضغط مثالية تقريباً
- ▸تنفيذ بسيط وواضح
- ▸الأساس في ضغط ZIP وJPEG
- ▸لا فقدان في البيانات
- ▸فعالية مثبتة نظرياً وعملياً
>> أسئلة شائعة
ما هو ترميز هوفمان؟
ترميز هوفمان خوارزمية ضغط ثنائية مثالية وخالية من تعارض البادئة طوّرها ديفيد هوفمان عام 1952. تعطي الخوارزمية أكواداً ثنائية بطول متغيّر للرموز حسب ترددها، بحيث تحصل الرموز الأكثر شيوعاً على أكواد أقصر، وهذا يحقق أقل طول متوسط ممكن للكود.
لماذا يسمى خالياً من تعارض البادئة؟
يكون الكود خالياً من تعارض البادئة عندما لا يكون أي كود بادئةً لكود آخر. على سبيل المثال، إذا كان كود الحرف "A" هو "01" فلا يمكن لأي حرف آخر أن يبدأ بـ "01". هذا يضمن فك ترميز غير ملتبس؛ يمكنك دائماً معرفة أين ينتهي كود ويبدأ الذي يليه بدون فواصل خاصة.
ما مدى كفاءة ترميز هوفمان؟
يحقق ترميز هوفمان ضغطاً قريباً من حد الإنتروبيا النظري للتوزيع، وغالباً ما يصل إلى توفير بنسبة 60–70٪ لنصوص اللغة الإنجليزية. يكون أكثر فاعلية عندما تختلف ترددات الرموز بشكل واضح.
أين يُستخدم ترميز هوفمان؟
يُستخدم ترميز هوفمان في ضغط صور JPEG، وضغط ملفات ZIP (مع LZ77 في خوارزمية DEFLATE)، وملفات MP3 والعديد من الصيغ الأخرى. غالباً ما يُدمج مع خوارزميات أخرى؛ فمثلاً تستخدم JPEG هوفمان بعد التحويل إلى ترددات (DCT) والتكميم، بينما يستخدم ZIP هوفمان بعد ضغط LZ77.
// مثال محلول
| Symbol | Freq | Bits | Code |
|---|---|---|---|
| A | 4 | 1 | 0 |
| B | 2 | 2 | 10 |
| C | 1 | 2 | 11 |
// أمثلة برمجية
Input AAAABBC (7 symbols, 56 bits as 8-bit ASCII) Counts A=4 B=2 C=1 Merge C(1)+B(2) -> node(3); node(3)+A(4) -> root(7) Codes A=0 B=10 C=11 (0/1 on left/right branches; ties may swap) Encoded 0 0 0 0 10 10 11 = 4*1 + 2*2 + 1*2 = 10 bits
>> المزيد من الأسئلة
س: هل رمز هوفمان فريد؟
ج: ليس بالضرورة. عند تساوي التكرارات قد يختلف اختيار العقد وإسناد 0 و1. لكن أطوال الرموز والحجم الكلي مثلى ومتطابقة في أي شجرة هوفمان صحيحة.
س: ماذا تعني خاصية عدم البادئة؟
ج: لا توجد كلمة رمزية تكون بداية لأخرى، لذا يمكن فك تدفق البتات دون فواصل بتتبع البتات من الجذر حتى ورقة.
س: متى لا يكون هوفمان مثالياً؟
ج: يخصص عدداً صحيحاً من البتات لكل رمز، فتقل الكفاءة عند احتمالات شديدة التفاوت (مثل 0.99). الترميز الحسابي أقرب إلى الإنتروبيا. ويحتاج فك الترميز أيضاً إلى جدول الرموز.