خوارزميات الضغط-2 : خوارزمية Huffman

[dj-siba]

المشاركة الأصلية كتبت بواسطة in4matics في 22-02-2008 الساعة 02:51 AM:
السلام عليكم و رحمة الله
1- مقدمة
في الجزء الأول تحدثنا عن خوارزميتي RLE و LZ77 لضغط البيانات، و لاحظنا بأنهما تضغطان البيانات بتقليص عدد الأحرف قدر الإمكان، أي تقليص عدد البايتات التي تمثل نص ما.
أما اليوم فسنتحدث عن خوارزمية لضغط البيانات تعمل على مستوى البت و ليس البايت، أي تقليص عدد البتات التي تمثل حرف ما.
تذكرة
كل محرف (ASCII) نمثله في بايت Byte، و كل بايت يتألف من 8 بتات Bit.
2- الفكرة
في النص العادي (الغير مضغوط) نمثل كل محرف ببايت واحد دوماً (أي بثماني بتات)، بغض النظر عن أية عوامل أخرى. و هذا يعني أن هناك إسرافاً في تمثيل المحرف بثماني بتات، في حين يكفي لتمثيله عدد أقل منها. لنأخذ مثالاً:
مثال
ليكن لدينا النص التالي: AbcAbcAbcA
هذا النص يتألف من 10 حروف و بالتالي يتم تمثيله بـ 10 بايتات (أي 10*8 = 80 بت)، و لكن ألا يكفي أن نمثل كل حرف من النص بـ 2 بت بدلاً من 8 بت؟
لنمثل حرف A بـ 01 و b بـ 10 و c بـ 11 مثلاً حسب الجدول التالي:

التمثيل بالبتات     الحرف
A            01
b            10
c            11

عندئذ يكفي لتمثيل النص السابق 10*2 = 20 بت بدلاً من 80 بت و لم نخسر من النص شيئاً!
أي بنسبة ضغط تساوي (20 / 80 = 25%).
أكثر من ذلك يمكننا تمثيل حرف A بالبت 0 فقط، فيصبح الجدول السابق كما يلي:

التمثيل بالبتات     الحرف
A            0
b            10
c            11

و بالتالي يصبح عدد البتات الكلي الذي يمثل النص السابق هو:
(4 أحرف A) * (بت واحد) + (3 أحرف b) * (2 بت) + (3 أحرف c) * (2 بت) = 16 بت.
أي بنسبة ضغط تساوي (16 / 80 = 20%).
إذاً *ليس من الضروري تمثيل كل حرف بـ 8 بتات دوماً، بل نمثل كل حرف بالعدد اللازم فقط من البتات*.
هناك ملاحظة أخرى في هذا المثال و هي أننا مثلنا أحد الحروف (A) بتمثيل أصغري مكون من بت واحد (0)، و الحرفيين الباقيين (b, c) بتمثيل مكون من بتين (10, 11)، و لكن لماذا لم نعطي التمثيل الأصغري لحرف b أو c ؟
الجواب: لو أعطينا التمثيل الأصغري لحرف b مثلاً كما في الجدول التالي:

التمثيل بالبتات     الحرف
A            10
b            0
c            11

عندئذ يصبح عدد البتات الكلي الذي يمثل النص السابق هو:
(4 أحرف A) * (2 بت) + (3 أحرف b) * (بت واحد) + (3 أحرف c) * (2 بت) = 17 بت، إذاً زاد الحجم بتاً واحد عن طريقة التمثيل السابقة!.
لكن لماذا زاد عدد البتات اللازم للتمثيل؟ الجواب لأن الحرف A مكرر أكثر من الحرف b، لذا كان يجب أن نعطي التمثيل الأصغر له و ليس للحرف b.
إذاً *لتحقيق الضغط الأمثل نعطي التمثيل الأصغر للحرف الذي يمتلك التكرار الأكبر*.
و هذه هي الفكرة الرئيسة في خوارزمية ضغط Huffman.
3- الخوارزمية
تذكرة
الشجرة هي بنية تتكون من جذر وحيد و أغصان متفرعة و أوراق في نهاية الأغصان، نسمي المكان الذي تتفرع منه الأغصان عقدة.

خطوات الخوارزمية
ليكن لدينا النص التالي: abeecbedcbaeddcbeeabea
•    نحسب تكرار كل حرف في النص فيكون لدينا الجدول التالي:

التكرار    الحرف
a        4
b        5
c        3
d        3
e        7

•    الآن نريد أن نبني شجرة Huffman، لذا نبدأ بعدد من العقد مساوي لعدد الأحرف في النص، نكتب في كل عقدة تكرار الحرف الذي تمثله كما في الشكل التالي (نأخذ التكرارات من الجدول السابق):

•    نختار العقدتين صاحبتي أصغر رقمين، ثم نجعلهما ابنتين لعقدة جديدة نضع فيها مجموع رقمي العقدتين، كما يلي:

•    نكرر الخطوة السابقة حتى تتبقى لدينا عقدة واحدة تكون هي جذر الشجرة الناتجة:

•    بعد أن بنينا الشجرة نقوم بترقيم الأغصان، فنعطي كل غصن أيمن الرقم 1 و كل غصن أيسر الرقم 0، لتصبح الشجرة كما يلي:

•    الآن باستخدام هذه الشجرة يمكننا عمل ضغط أو فك للبيانات.
o ضغط البيانات:
من أجل كل حرف تمثله ورقة زرقاء في الشجرة، تكون سلسلة البتات الممثلة له هي الأرقام التي نصادفها في طريقنا من الجذر إلى هذه الورقة، مثلاً نحتاج للوصول إلى حرف c ابتداء بالجذر أن نمر بالعقدة edc ثم العقدة dc، و بالتالي التمثيل المقابل لهذا الحرف هي البتات الموجودة على الأغصان التي مررنا بها، أي 011، لذا يمكننا كتابة الجدول التالي:

التمثيل بالبتات     الحرف
a            11
b            10
c            011
d            010
e            00

نلاحظ من الجدول أن الحروف ذات التكرارات الأكبر (a, b, e) أخذت تمثيلاً يحوي عدداً أصغر من البتات، و هذا ما نريده.
الآن من أجل كل حرف في النص نقوم بتبديله بالبتات المقابلة له من الجدول، فنحصل على سلسلة من البتات تمثل النص المضغوط.
o فك ضغط البيانات:
لدينا الآن نص مضغوط عبارة عن سلسلة من البتات، لفك ضغطه نقوم بما يلي:
-    في البداية نقف في جذر الشجرة.
-    من أجل كل بت نقرأه من سلسلة بتات النص المضغوط لدينا حالتين:
•    إذا كانت قيمة البت 0 نختار الغصن اليساري المتفرع عن العقدة التي نقف فيها.
•    إذا كانت قيمة البت 1 نختار الغصن اليميني المتفرع عن العقدة التي نقف فيها.
-    نكرر الخطوة السابقة حتى نصل إلى ورقة، عندها نكتب الحرف المقابل لهذه الورقة في الخرج ثم نعود إلى الجذر.
-    نكرر الخطوات السابقة حتى ينتهي النص المضغوط و عندها نكون قد حصلنا على النص الأصلي في الخرج.
4- خاتمة
بهذا نكون قد انتهينا من شرحنا المبسط لخوارزمية Huffman، أرجو لكم كل الفائدة و التوفيق إن شاء الله.
........
الدرس موجود في المرفق بتنسيق PDF حسب اقتراح الأخ STRELiTZIA له كل الشكر، و يتضمن صوراً أكثر مع كامل التنسيق..
إذا كان لديكم أية أسئلة عن الدرس فأحب أن أسمعها لأني أعرف حينها أن هناك من يقرأ
تحياتي لكم
in4matics | AT4RE