خوارزمية ضغط الملفات هوفمان (Huffman)

من منا لا يستخدم برامج ضغط الملفات مثل Winrar  7zip، و Power Iso. غالباً معظم الملفات التي نقوم بتحميلها عن طريق الإنترنت تكون في شكل ملفات مضغوطة لنفك ضغطها لاحقاً. لكن هل تساءلت كيف يتم ضغط الملفات؟!! كيف تمكن ملف حجمه 80 ميجا أن يتحول لملف 20 ميجا دون فقدان أي بيانات؟!!! أوليس سحراً ؟!! على حد علمي هوفمان لم يكن ساحراً 😀

خوارزمية ضغط الملفات

اليوم نتحدث عن خوارزمية هوفمان لضغط الملفات. حيث تعتبر من أهم خوارزميات ضغط الملفات التي تعمل على مستوى البت (Bit)، على عكس خوارزميات ضغط الملفات التي تعمل على مستوى البايت (Byte) .

خوارزمية هوفمان توفر من 20% إلى 90% من حجم الملف!! وذلك إعتماداً على نوع الملف نفسه، حيث أن خورازمية هوفمان تعمل بكفاءة عالية وتوفر كثيراً من حجم الذاكرة في حالة الملفات النصية ،ولكن لها تأثيرها ليس بكبير على ملفات الصور والفديو مقارنة بالملفات النصية .

بالمثال يتضح المقال

علي سبيل المثال، إعتبر أنك تتعامل مع ملف نصي، من المعلوم لديك أن كل حرف يخزن في بايت (8 بت)، فكر في ذلك! من الممكن أن تخزن 4 بتات في 64 بت!! أوليس تبذيراً لمورد مهم جداً و هو الذاكرة؟!! الفكرة تكمن في أنه من الممكن تخزين الحرف في أقل من 8 بتات كما في المثال التالي:

ليكن لدينا النص abcabcabca

هذا النص سيخزن في ذاكرة حجمها 10*8 =80 بت، لماذا؟ لأن كل حرف يأخذ 8 بتات، و النص يتكون من 10 أحرف، و يُعد هذا إسرافاً في إستخدام الموارد، بالإمكان أن يُخزن كل حرف في 2 بت فقط كالاتي :

أي أن الملف قابل للتخزين في 10*2=20 بت وهذا فرق كبير حيث قمنا بتخزين ملف كان يأخذ 80 بت في 20 بت فقط.

كذلك بالإمكان تمثيل الـ a  عن طريق بت واحد فقط وهو الـ 0، وبما أن الـ a مكررة 4 مرات، بذلك عند تمثيل الـ a عن طريق بت واحد فقط نكون قد وفرنا 4 بت أخرى ، أي أنه يمكننا حفظ الملف في ذاكرة حجمها 16 بت فقط بدلا من 20 بت.

السؤال الذي يطرح نفسه هل يشكل فرق أن مثلنا الحرف b بالبت 0 بدلاً عن الـ a؟ الجواب: نعم يُشكل فرقاً ،وذلك لأن تكرار حرف الـ b هو 3 فقط، أي أننا سنوفر 3 بت فقط وهي أقل من التي نوفرها في حالة مثلنا حرف الـ a بالـ 0.

[box type=”info” align=”aligncenter” class=”” width=””]من هذا نخلص إلى أنه كلما مثلنا العدد الأكثر تكراراً بأقل عدد من البتات (Bits) نكون قد وفرنا ذاكرة أكبر.[/box]

شجرة هوفمان (Huffman Tree) :

بدايةً قبل القيام بضغط ملف أو فك الضغط عنه يجب عليك بناء شجرة هوفمان. كيف ننشئ شجرة هوفمان؟!! هيا لتتعلم.

ليكن لدينا النص abeecbedcbaeddcbeeabea

أولاً إحسب تكرار كل حرف

a=4 ،b=5،c=3،d=3،e=7

1. كوّن أوراقاً بعدد الأحرف التي لديك، أي كون 5 أوراق (عقد) و ضع في كل ورقة تكرار الحرف الذي تمثله.
2. إختر عقدتان لهما أصغر تكرارين.
3. إجعلمها إبنتان لعقده جديدة.
4. هذه العقدة الجديدة ضع فيها مجموع التكرارين (تكراري العقدتين صاحبتا أقل تكرارين).
5. طبق هذه العملية حتى تحصل على عقدة واحده وهي الجذر.
6. رقّم كُل عقده وفقاً لموضعها، إذا كانت يمين عقدة أخرى تأخذ الرقم 1 وإذا كانت شمال عقدة أخرى تأخذ الرقم 0 .

بهذه الست خطوات تكون قد أنشئت شجرة هوفمان و بالإمكان تطبيق عمليتي ضغط الملفات وفك الضغط عليها.

ضغط البيانات:

بعد إنشاء شجرة هوفمان وترقيم كل عقدة، في عملية الضغط نمثل كل حرف بأرقام العقد التي نقابلها في طريقنا من العقدة التي تحوي تكرار الحرف المعني حتى الجزر. علي سبيل المثال في الشكل اعلاه رقم (a) نمثل الحرف a بالبتات 000.

والحرف e بالبتات 001 ونلاحظ أن الشجرة تعطي الحرف الأكثر تكراراً عدداً أقل من البتات، وهكذا قمنا بالضغط عن طريق خوارزمية هوفمان.

فك الضغط :

لفك الضغط، في بادئ الامر يكون لدينا سلسلة بتات ناتجة من الضغط.

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

وهكذا تكون قد وصلت إلى النص المطلوب (أي فككت الضغط).

ختاماً:

 نكون قد اوجزنا خوارزمية هوفمان وكيف تقوم بضغط الملفات وفك الضغط و فقاً لخوارزمية هوفمان. بالتأكيد أشجعك أيضاً على وضع تعليقاتك بالأسفل و استفساراتك 🙂 .

مقالات مفيدة لك:

الشجرة البيانية من أهم مفاهيم الخوارزميات