ضغط الملفات النصية باستخدام طريقة HUFFMAN

Text files compression using HUFFMAN method

     من المعروف أن كل حرف في الملفات النصية -Text Files- يتم تخزينه في حيز مقداره 8 بت أي 1 بايت وهو عدد الBits التي يحتاجها كود الASCII الخاص بالحرف , مثلا حرف ال A كود ال ASCII الخاص به هو 65 بالنظام العشري و هو ما يكافئ 1000001 بالنظام الثنائي.

     طريقه Huffman التي ابتكرها العالم David Huffman تعتمد علي إعطاء الحرف-أو كلمة (رمز) - كود خاص به بحيث لا يكون هناك تكرار في المعلومات اللازمة للتفرقة بين الحروف و بعضها البعض –كود الASCII - بحيث يأخذ الحرف –أو الرمز- الأكثر تكرارا في الملف المراد ضغطه أقل كود ممكن مثل بت واحد أو 2 بت والحروف الأقل تكرارا تأخذ كود أطول.

      أي أن طول الكود الخاص بكل رمز هو طول متغير Variable و ليس طول ثابت Fixed (8 بت) كما كان الوضع في نظام ال ASCII و لكن يجب أن يظل من الممكن التفرقة بين كود كل حرف عند الحاجة لقراءة الملف المضغوط أو عند عملية فك الضغط , ويتم استخدام شجرة ثنائيه Binary Tree من أجل توليد هذه الأكواد للحروف -أو الرموز-.

• كيفية ضغط الملفات بطريقة Huffman

       يمكن تلخيص خطوات إنشاء أكواد Huffman كما يلي:

1 إيجاد عدد مرات تكرار كل حرف في الملف النصي.

2 يتم تكوين قائمة من العناصر كل عنصر يحتوي علي الرمز و عدد مرات تكراره وهذه العناصر ستكون الأوراق - Leafs - للشجرة الثنائية.

3 اختر العنصرين من القائمة الذين لديهم أقل عدد مرات تكرار و اجمع أرقام التكرار لكل منهم لتحصل علي عنصر جديد يحتوي علي المجموع و يكون الابن –child- الأيمن لهذا العنصر الجديد هو العنصر الأقل تكرارا في القائمة و الابن الأيسر له هو العنصر الأقل الذي يليله , ثم احذف العنصران اللذان تم اختيارهما من القائمة و أضف العنصر الجديد في القائمة بترتيبه.

4 يتم تكرار الخطوة رقم 3 لحين الحصول علي عنصر واحد في القائمة هذا العنصر سيكون ال root للشجرة الثنائية التي سيتم توليد الأكواد بواسطتها.

5 نقوم بزيارة كل leaf (العنصر الذي ليس له أبناء في الشجرة) بداية من الroot , بحيث إذا انعطفنا يمينا يتم إضافة (0) للكود و إذا انعطفنا يسارا نضيف ( 1) للكود الخاص بالحرف الموجود في ال leaf التي سنزورها والكود الضي سينتج من الأصفار والوحياد التي كوناها عبر المسار من الroot إلي ال Leaf سيكون هو كود الحرف الموجود في الleaf التي تم زيارتها.

قد يبدو الأمر غامضا قليلا, لكن هذا المثال سيوضح الأمر بإذن الله:

لنفترض أن لدينا النص التالي : "SHE-SELLS-SEA-SHELLS"

نطبق الخطوة رقم 1 وهي إيجاد عدد مرات تكرار كل حرف في الملف أو النص المراد ضغطه

إذن هذه هي العناصر الأساسيه التي ستكون الأوراق - Leafs - للشجرة الثنائية.

ننتقل للخطوة الثانية و نكون فيها القائمة (مرتبة تصاعديا وفي حالة التساوي سنتعبر أن العنصر الداخلي هو الأكبر):

ننتقل الآن لتنفيذ الخطوة الثالثة : و نختر أقل عنصرين و هما A و H ونكون عنصر جديد يضمهما

الآن نحذفهما من القائمة و ندخل العنصر الجديد فتصبح القائمة بالشكل الآتي:

لم يصل عدد العناصر إلي 1 , لذلك سنكرر الخطوة الثالثة مرة أخري و هكذا حتى نصل لأن يكون هناك عنصر واحد في القائمة :

وتصبح القائمة بالشكل الآتي :

 نختار أقل عنصرين تكراراً :

 وتصبح القائمة بالشكل الآتي :

نختار أقل عنصرين تكراراً :

وتصبح القائمة بالشكل الآتي :

نختار أقل عنصرين تكراراً :

أصبح لدينا عنصر واحد , إذن الآن انتهينا من تكوين الشجرة الثنائية , فننتقل للمرحلة التالية.

وهي الخطوة رقم 5 توليد الأكواد للرموز –أو الأحرف- المكونة للنص الأصلي ,

وفيها نقوم بزيارة كل ورقة –Leaf- بداية من root الشجرة الثنائية و عند الانتقال للابن الأيمن –Child- نضع صفر و للأيسر واحد , ونكرر ذلك مع كل Leaf.

فتصبح الأكواد للحروف كالآتي :

وكملخص للخطوتين السابقتين:

    نلاحظ أنه لكل حرف هناك كود مميز له – لأن هذا الكود يعبر عن المسار بين العنصر الذي يحتوي علي ذلك الحرف و بين ال root في الشجرة الثنائية لذلك من المستحيل أن تتشابه الأكواد لحرفين أو أكثرر لأن المسار لكل عنصر هو مسار وحيد - و في نفس الوقت نلحظ أن الحروف ذات مرات التكرار الأكثر أخذت كود طوله صغير, و بذلك نكون قد حققنا الهدف المطلوب.

     الآن و بعد الانتهاء من عملية توليد الأكواد ننتقل لمرحلة كتابة الملف المضغوط بحيث نعوض عن كل حرف بالكود الذي نتج من الشجرة , مع مراعاة أن الكتابة في الملف المضغوط تكون بالبت –Bit- .

    أي أن النص: "SHE-SELLS-SEA-SHELLS" سيخزن في الملف المضغوط بالشكل الآتي :

1110010010111000101111011100100010111100100010111

    وهذا يحتاج منا مساحة تخزينية بمقدار : 49 بت فقط بدلا من 160 بت كما كان يتطلب التخزين بنظام الASCII , إذن التوفير- Saving - يساوي 111 بت ونسبة الضغط -compression ratio- تكون 69.375% .

   يجب ملاحظة أن نسبة الضغط و مدي التوفير يعتمد علي طبيعة النص و شكل تكرار الحروف فيه, أي أن النسبة ستتخلف من ملف لآخر.

    ويلزم أيضا أن وضع المعلومات الموجودة في أول جدول –الحرف و عدد مرات تكراره- داخل الملف المضغوط حتى نتمكن من تكوين الشجرة الثنائية مرة أخري عند قراءة الملف المضغوط , وتكون هذه المعلومات بمثابة الHeader للملف المضغوط , وهذا يعتبر overhead علي حجم الملف المضغوط لكن مع الملفات الكبيرة لن يمثل حجم الHeader مشكلة لأنه يمكن إهماله عندها.

• العملية العكسية (فك الضغط ) :

        كما أسلفنا سيحتوي الملف المضغوط داخل قسم الHeader علي المعلومات الأساسية عن كل حرف –الحرف و عدد مرات تكراره- وهذه المعلومات يتم قراءتها عند بداية قراءة الملف المضغوط ثم يتم تكوين الشجرة الثنائية مرة أخري داخل الذاكرة كما سبق تماما.

         ثم نبدأ بقراءة الملف المضغوط بالبت Bit by Bit و نقف عند root الشجرة الثنائية, فإذا ما كانت البت المقروءة "1" ننتقل لليسار أو "0" فننتقل لليمين داخل الشجرة, ثم نختبر ما إذا كان العنصر الذي نقف عليه الآن داخل الشجرة هل هو ورقة –Leaf - أم لا؟ (أي ليس له أبناء-Childs-) :

• فإذا كان Leaf نقرأ الحرف الموجود بداخله مثلا S و نكتبه في الملف الخرج (فك الضغط) , ثم نعود مرة أخري إلي الroot و نتابع القراءة من الملف المضغوط.
• أما إذا لم يكن Leaf نتابع قراءة البت التالية من الملف المضغوط وننتقل داخل الشجرة مرة أخري علي حسب قيمة البت المقروءة ثم نختبر ما إذا كانت Leaf أم لا ..

وهكذا حتى ننتهي من قراءة كل الBits الموجودة داخل الملف المضغوط.

• Static Huffman و عيوبها.

         تسمي الطريقة التي شرحناها هنا ب Static Huffman لأنه بمجرد بناء الشجرة الثنائية –Binary Tree- لم يعد من الممكن التعديل فيها, وهذه الطريقة لها عدة عيوب منها:

• أنه لابد من أن يكون لدي كل من الطرفين( الطرف الذي يقوم بضغط الملف و الطرف الذي يقوم بفك الضغط ) معلومات عن ال Huffman Tree و هذه تعتبر overhead علي حجم الملف المضغوط.
• العيب الثاني يتمثل في أنه لابد من قراءة الملف المراد ضغطه مرتين , مرة لإيجاد تكرار كل حرف داخل النص و المرة الثانية عند إنشاء الملف المضغوط بعد توليد الأكواد للحروف , وفي حالة الملفات الكبيرة الحجم هذا يعد مشكلة لأن العملية ستسغرق وقت طويل.
• و في تطبيق آخر لطريقة Huffman مثل إرسال البيانات عبر الشبكات, نجد أن الطرف المستقبل لابد أن ينظر حتى ينتهي المرسل من عمله كاملا ثم يرسل له معلومات الشجرة الثنائية و البيانات المضغوطة , وهذا يعد إهدار للوقت و المصادر- Resources -لأن أحد الطرفين يظل بلا عمل( Idle )حتى ينتهي الآخر من عمله.

          لذلك تم تعديل ال Static Huffman إلي ما يسمي ب Adaptive Huffman وهي التي سنتناولها بالشرح في الدرس القادم بإذن الله تعالي.

• Static Huffman implementation with C++

     هذا implementation لخوارزم Huffman كتبته بلغة C++ باستخدام Microsoft Visual C++ 6 , يمكن تنزيل مصدر-source- البرنامج من هنا -رايت كلك وsave target as- واستخدامه شريطة ذكر المصدر و ألا تضع عليه أسمك.

    البرنامج يتكون من 2 Class الأول HuffTree و هو مسئول عن تكوين الشجرة و توليد الأكواد , و يتم إدخال الحرف و عدد مرات تكراره لها .

     الثاني إسمه Huffman  و هذا يعتبر الواجهة بين الClass الأول والمستخدم -user- و يحتوي علي object من الclass HuffTree يستخدمه في العمليات- methods - التي يوفرها للمستخدم مثل فك و ضغط الملفات , و بداخله أيضا ال-methods-التي تقوم بقراءة و كتابة الBits في عمليات كتابة و فك ضغط الملفات المضغوطة.

      للأسف لم أجهز واجهة visual  للبرنامج حتى الآن لكني بصدد عملها و حتى ذلك الحين يمكن تجربة البرنامج من الconsole .

و إذا كان هناك أي شئ غير واضح أو أي تعديل أو تصحيح في الكود أرجو منكم مراسلتي.

وهذه لقطة من البرنامج :