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

اليوم نتحدث عن خوارزمية هوفمان لضغط الملفات. حيث تعتبر من أهم خوارزميات ضغط الملفات التي تعمل على مستوى البت (Bit)، على عكس خوارزميات ضغط الملفات التي تعمل على مستوى البايت (Byte) .
خوارزمية هوفمان توفر من 20% إلى 90% من حجم الملف!! وذلك إعتماداً على نوع الملف نفسه، حيث أن خورازمية هوفمان تعمل بكفاءة عالية وتوفر كثيراً من حجم الذاكرة في حالة الملفات النصية ،ولكن لها تأثيرها ليس بكبير على ملفات الصور والفديو مقارنة بالملفات النصية .
بالمثال يتضح المقال
علي سبيل المثال، إعتبر أنك تتعامل مع ملف نصي، من المعلوم لديك أن كل حرف يخزن في بايت (8 بت)، فكر في ذلك! من الممكن أن تخزن 4 بتات في 64 بت!! أوليس تبذيراً لمورد مهم جداً و هو الذاكرة؟!! الفكرة تكمن في أنه من الممكن تخزين الحرف في أقل من 8 بتات كما في المثال التالي:
ليكن لدينا النص abcabcabca
هذا النص سيخزن في ذاكرة حجمها 10*8 =80 بت، لماذا؟ لأن كل حرف يأخذ 8 بتات، و النص يتكون من 10 أحرف، و يُعد هذا إسرافاً في إستخدام الموارد، بالإمكان أن يُخزن كل حرف في 2 بت فقط كالاتي :
البت | الحرف |
---|---|
01 | a |
10 | b |
11 | c |
أي أن الملف قابل للتخزين في 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
- كوّن أوراقاً بعدد الأحرف التي لديك، أي كون 5 أوراق (عقد) و ضع في كل ورقة تكرار الحرف الذي تمثله.
- إختر عقدتان لهما أصغر تكرارين.
- إجعلمها إبنتان لعقده جديدة.
- هذه العقدة الجديدة ضع فيها مجموع التكرارين (تكراري العقدتين صاحبتا أقل تكرارين).
- طبق هذه العملية حتى تحصل على عقدة واحده وهي الجذر.
- رقّم كُل عقده وفقاً لموضعها، إذا كانت يمين عقدة أخرى تأخذ الرقم 1 وإذا كانت شمال عقدة أخرى تأخذ الرقم 0 .
بهذه الست خطوات تكون قد أنشئت شجرة هوفمان و بالإمكان تطبيق عمليتي ضغط الملفات وفك الضغط عليها.
ضغط البيانات:
بعد إنشاء شجرة هوفمان وترقيم كل عقدة، في عملية الضغط نمثل كل حرف بأرقام العقد التي نقابلها في طريقنا من العقدة التي تحوي تكرار الحرف المعني حتى الجزر. علي سبيل المثال في الشكل اعلاه رقم (a) نمثل الحرف a بالبتات 000.
والحرف e بالبتات 001 ونلاحظ أن الشجرة تعطي الحرف الأكثر تكراراً عدداً أقل من البتات، وهكذا قمنا بالضغط عن طريق خوارزمية هوفمان.
فك الضغط :
لفك الضغط، في بادئ الامر يكون لدينا سلسلة بتات ناتجة من الضغط.
- أول خطوة قف عند الجذر.
- أنظر إلى سلسلة البتات الناتجة من الضغط و انظر إلى أول بت إذا كان 0 إذهب إلى العقدة يسار الجذر و إذا كانت 1 إذهب للعقدة يمين الجذر.
- في كل تحرك يميناً أو يساراً، أنظر إلى البت الثاني إذا كان صفراً إذهب يسار العقدة التي تقف عليها وإذا كان 1 إذهب يمين العقده التي تقف عليها،.
- إستمر هكذا حتى تصل إلى ورقة و اكتب الحرف الذي تمثله.
- عد و كرر نفس العملية حتى تصل إلى آخر بت.
وهكذا تكون قد وصلت إلى النص المطلوب (أي فككت الضغط).
ختاماً:
نكون قد اوجزنا خوارزمية هوفمان وكيف تقوم بضغط الملفات وفك الضغط و فقاً لخوارزمية هوفمان. بالتأكيد أشجعك أيضاً على وضع تعليقاتك بالأسفل و استفساراتك 🙂 .
مقالات مفيدة لك:
السلام عليكم مهندس مصطفى
لوسمحت اشتي الكود البرمجي لخوارزمية هوفمان
اذا كان لدي مصفوفة فيها سبعة الوان فقط.. فما هو عدد مستويات التكميم؟
مرحبا ممكن تنزل الكود لخوارزمية هوفمان لضغط الصور وجزاك الله خيرا
انا أيضا كنت افكر في ذلك
هل هناك أحد بالفعل جرب خوارزمية هوفمان لضغط الصور ؟
مقال جميل وومتع وشرحه سهل , وللتسهيل كان يمكن استخدام صورة لشجرة توضح المثال بالاضافة للصورة الموجود (صورة شجرة هوفمان)
شكراً لجميل حديثك أخي ماجد، صدقت ما هو إلا جُهد المقل وأشكرك على هذا الاقتراح.
هذه البرامج التي ذكرتها كلها تستخدم خوارزمية LZW و ليس Huffman
شكراً لك أخي أمين، فعلاً هوفمان من أبسط خوارزميات الضغط. الكاتب ذكر هذه الخوارزميات استشهاداً عن برامج الضغط فقط.
و شكراً للمعلومة الخاصة بخوارزمية LZW ?
بارك الله فيك أدعو لكم بالتوفيق أشكرك
شُكراً لك زاهر، و بارك الله فيك و أسعدك في الدارين.
شكرا لكم
نتمنى مزيدا من الشرح بالأمثلة
ربنا يوفقك يا مهندس مصطفى الطيب…و مزيدا من التقدم. لقد كنتم دائما فخرا لنا..
سؤالي
if I want to develop my own data compressor, how can I handle file extensions and format.
مرحباً بك دوماً أخي أسامة و بورك فيك و الفخر أنتُم جُزيت خيراً.
ما وضح لي أنك ترغب بإنشاء خوارزمية خاصة بك لضغط الملفات و لكنك تواجه مشكلة في إمتداد الملف (صيغة الضغط)، حبّذا لو أسهبت قليلاً عن المُشكلة حيث لم يتضح لي السؤال تماماً.