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

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

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

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

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

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

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

البتالحرف
01a
10b
11c

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

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

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

من هذا نخلص إلى أنه كلما مثلنا العدد الأكثر تكراراً بأقل عدد من البتات (Bits) نكون قد وفرنا ذاكرة أكبر.

شجرة هوفمان (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. عد و كرر نفس العملية حتى تصل إلى آخر بت.

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

سامي محمد آدم

مُختص بالعلوم الرياضية قسم الرياضيات و الحاسوب أهوى البرمجة، خاصة برمجة وتطوير الويب. كما أهوى الإطلاع على كل جديد في مجال الحاسوب وكذلك التصميم بإستخدام الفوتوشوب.

مقالات ذات صلة

‫10 تعليقات

    1. مرحباً بك دوماً أخي أسامة و بورك فيك و الفخر أنتُم جُزيت خيراً.
      ما وضح لي أنك ترغب بإنشاء خوارزمية خاصة بك لضغط الملفات و لكنك تواجه مشكلة في إمتداد الملف (صيغة الضغط)، حبّذا لو أسهبت قليلاً عن المُشكلة حيث لم يتضح لي السؤال تماماً.

    1. شكراً لك أخي أمين، فعلاً هوفمان من أبسط خوارزميات الضغط. الكاتب ذكر هذه الخوارزميات استشهاداً عن برامج الضغط فقط.
      و شكراً للمعلومة الخاصة بخوارزمية LZW ?

  1. مقال جميل وومتع وشرحه سهل , وللتسهيل كان يمكن استخدام صورة لشجرة توضح المثال بالاضافة للصورة الموجود (صورة شجرة هوفمان)

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *