مقدمة:
إذا قمت بتحميل العديد من الملفات و البرامج عبر الانترنت فانك لابد قد واجهت الملفات المضغوطة ZIP من قبل. و نظام الضغط هذا هو اختراع مفيد جدا, خصوصا لمستخدمي الانترنت, لأنه يمكنك من تخفيض عدد البتات و البايتات في ملف ما بحيث يمكن إرساله بسرعة أكبر عبر الانترنت, أو يأخذ مساحة أقل على القرص. عندما تقوم بتحميل الملف فإنك تستخدم برنامج ما مثل WinZip لفك ضغط الملف وإعادته لحجمه الأصلي. فاذا تم كل شيء بشكل صحيح فان الملف يعود إلى ما كان عليه قبل الضغط.
من اللمحة الأولى, يبدو الأمر غامض جدا. كيف يمكن تخفيض عدد البتات و البايتات و من ثم إعادة هذه البتات و البايتات إلى ما كانت عليه سابقا؟
إيجاد الحشو:
معظم ملفات الكمبيوتر يتخللها حشو إلى حد ما, بمعنى أنها تملك نفس المعلومات التي تعاد جدولتها مرة تلو أخرى. تقوم برامج ضغط الملفات ببساطة بالتخلص من هذا الحشو. فبدلا من جدولة نفس الجزء من المعلومات مرة تلو أخرى, يقوم برنامج الضغط بجدولة هذه المعلومات المحشوة مرة واحدة فقط ومن ثم يشير إليها عندما تتكرر مرة أخرى خلال البرنامج.
على سبيل المثال, لننظر إلى نوع من المعلومات التي اعتدنا عليها وهي الكلمات. في خطاب الرئيس الأمريكي جون كينيدي في 1961, قال كلمته المشهورة:
"Ask not what your country can do for you - ask what you can do for your country."
هذه العبارة تحتوي على 17 كلمة, مؤلفة من 61 حرف, 16 فراغ, شحطة واحدة و نقطة واحدة. إذا استهلك كل حرف أو فراغ أو علامة ترقيم وحدة واحدة من الذاكرة, يكون حجم الملف الكلي 79 وحدة. ولإنقاص حجم الملف يجب البحث عن الحشو.
نلاحظ أن:
- كلمة "ask" ظهرت مرتين
- كلمة "what" ظهرت مرتين
- كلمة "your" ظهرت مرتين
- كلمة "country" ظهرت مرتين
- كلمة "can" ظهرت مرتين
- كلمة "do" ظهرت مرتين
- كلمة "for" ظهرت مرتين
- كلمة "you" ظهرت مرتين
بتجاهل الفرق بين الحروف الكبيرة و الصغيرة, يكون تقريبا نصف الجملة عبارة عن حشو. تسع كلمات (ask, not, what, your, country, can, do, for, you) تعطينا تقريبا كل شيء نحتاجه في الجملة.لإنشاء النصف الثاني من الجملة, نحتاج فقط لأن نشير إلى الكلمات الموجودة في النصف الأول ونضيف الفراغات و علامات الترقيم.
البحث عن الحشو:
معظم برامج الضغط تستخدم خوارزمية LZ adaptive dictionary-based algorithm لضغط الملفات, حيث تشير LZ الى Lempel و Ziv وهما مخترعا هذه الخوارزمية, و dictionary تشير إلى طريقة فهرسة البيانات.
يختلف نظام ترتيب القواميس لكنه يمكن أن يكون بسيط مثل قائمة مرقمة. فبالعودة لكلمات جملة كينيدي, نأخذ الكلمات المكررة ونضعها في فهرس مرقم. ومن ثم نكتب الأرقام بدلا من كتابة الكلمة بكاملها.
فإذا كان القاموس بالنسبة لهذه الجملة بالشكل:
1- ask
2- what
3- your
4- country
5- can
6- do
7- for
8- you
تكتب الجملة عندئذ بالشكل:
"1 not 2 3 4 5 6 7 8 – 1 2 8 5 6 7 3 4."
إذا كنت تعرف النظام, يكون بإمكانك إعادة بناء الجملة الأصلية باستخدام هذا القاموس فقط. وهذا ما يقوم به برنامج فك الضغط الموجود على الكمبيوتر عند فك ضغط ملف ما. و ربما صادفت أيضا ملفات مضغوطة تقوم بفك ضغطها بنفسها( ملفات تنفيذية EXE). ولإنشاء هذا النوع من الملفات يقوم المبرمج بدمج برنامج فك ضغط بسيط مع الملف المضغوط بحيث يقوم بإنشاء الملف الأصلي عند فتحه.
ولكن, كم من المساحة قمنا بالاحتفاظ بها باستخدام هذا النظام؟
"1 not 2 3 4 5 6 7 8- 1 2 8 5 6 7 3 4."
هذه الجملة هي فعليا اقصر من الجملة الاصلية "Ask not what your country can do for you; ask what you can do for your country"
ولكن تذكر أننا نحتاج لحفظ القاموس نفسه مع الملف المضغوط.
في عملية الضغط الفعلية, يكون إيجاد متطلبات الملف المختلفة هي عملية صعبة, ولكن من أجل أهدافنا, دعنا نعود إلى الفكرة التي تقول أن كل رمز أو فراغ يشغل وحدة واحدة من الذاكرة. ولقد وجدنا أن الجملة الأصلية تأخذ 79 وحدة. أما الجملة المضغوطة بالإضافة للفراغات التي تحتويها تأخذ 37 وحدة, والقاموس( بجمله و أرقامه) يأخذ 37 وحدة. وهذا يجعل حجم الملف المضغوط 74 وحدة, وبالتالي لم ننقص حجم الملف شيئا يذكر.
لكن ذلك ينطبق فقط على هذه الجملة, يمكنك تخيل أن عملية الضغط تمت على جميع خطاب الرئيس كينيدي, وبالتالي سوف يتم إيجاد هذه الكلمات و كلمات أخرى مكررة عدة مرات أخرى. وبالتالي سوف تتم إعادة إنشاء القاموس بحيث يتم تنظيم البيانات بأفضل صورة ممكنة.
البحث عن النماذج:
في مثالنا قمنا بأخذ جميع الكلمات المكررة و وضعها في القاموس. وبالنسبة لنا هذه الطريقة هي الطريقة الأكثر وضوحا لكتابة القاموس. لكن برنامج الضغط يرى ذلك بشكل مختلف, فهو لا يملك أي تصور للكلمات المنفصلة, فهو ينظر فقط إلى النماذج. ولإنقاص حجم الملف قدر الإمكان, يقوم باختيار النماذج التي سوف يحتويها القاموس بعناية.
فإذا نظرنا إلى الجملة من هذا المنظور, نحصل على قاموس مختلف تماما.
إذا قام برنامج الضغط بفحص جملة كينيدي, فان أول فائض سوف يظهر هو عبارة عن زوج من الأحرف. ففي الجزء (ask not what your) هناك تكرير لنموذج الحرف "t" متبوعا بفراغ (في not و what).
فإذا قام برنامج الضغط بكتابة هذا النموذج إلى القاموس, فانه من الممكن أن يكتب "1" في كل مرة يصادف فيها الحرف "t" متبوعا بفراغ. ولكن في هذه الجملة القصيرة, هذا النموذج لن يتكرر بشكل كاف بحيث يكون نموذج ذو قيمة, لذلك فان البرنامج سوف يستبدله في النهاية.
الشيء الثاني الذي يمكن أن يلاحظه البرنامج هو "ou", الذي يظهر في كل من "your" و "country". إذا كان الملف الذي نقوم بضغطه أطول, فإن كتابة هذا النموذج إلى القاموس يمكن أن يوفر الكثير من المساحة, حيث أن "ou" هو مزيج شائع الاستخدام في اللغة الإنكليزية. لكن عندما يعمل برنامج الضغط على هذه الجملة, يمكن أن يكتشف بسرعة خيار أفضل لوضعه في القاموس, حيث أنه ليس فقط "ou" مكررة بل إن الكلمة بكاملها "your" و "country" كلاهما مكرر,و هما فعليا مكررتان مع بعضهما, أي "your country". في هذه الحالة فإن البرنامج سوف يستبدل البند "ou" بالبند "your country".
أيضا الجملة "can do for" مكررة, مرة متبوعة بـ "your" و مرة أخرى بـ "you" بحيث تعطينا تكرار للشكل "can do for you". مما يسمح لنا بكتابة 15 رمز بما فيها الفراغات بدلالة رقم واحد, و بالتالي فإن البرنامج سوف يستبدل "your country" بـ "r country", ومن ثم كتابة بند منفصل لـ "can do for you". و يتابع البرنامج بهذه الطريقة, بحيث يأخذ جميع البتات المكررة و من ثم يحدد أي شكل يجب كتابته في القاموس. هذه القدرة على إعادة كتابة القاموس هي الجزء "adaptive" من LZ adaptive dictionary-based algorithm. لكن الطريقة التي يتبعها البرنامج معقدة بشكل أكبر.
بغض النظر عن الطريقة التي تستخدمها, فإن نظام البحث في العمق هذا يسمح لك بضغط الملف بشكل أكثر فاعلية من أن تأخذ الكلمات المكررة فقط. وباستخدام النماذج التي حصلنا عليها سابقا و بوضع "_" للفراغات, فإننا نحصل على هذا القاموس:
1-ask_
2- what_
3- you
4- r_country
5- _can_do_for_you
ونحصل بالتالي على هذه الجملة:
"1not_2345_-_12354."
وهذه الجملة تأخذ 18 وحدة من الذاكرة, و القاموس يأخذ 41 وحدة.وبالتالي قمنا بضغط حجم الملف الكلي من 79 وحدة الى 59 وحدة. وهذه فقط طريقة واحدة لضغط هذه الجملة, وليست بالضرورة الطريقة الأكثر فاعلية.
اذا, كم هو جيد هذا النظام؟
إن معدل تخفيض حجم الملف يعتمد على عدد من العوامل, مثل نوع الملف و حجمه و طريقة الضغط.
في معظم لغات العالم, تظهر حروف و كلمات محددة عادة مع بعضها في نفس النموذج. و بسبب هذه الدرجة المرتفعة من الحشو, يتم ضغط الملفات النصية بشكل جيد جدا. حيث أن تخفيض 50 % أو أكثر من حجم الملف هي نسبة نموذجية للملفات النصية ذات الحجم الكبير نسبيا.أما الملفات التي تحتوي على معلومات فريدة, مثل الصور و ملفات MP3 لا يمكن ضغطها بشكل جيد باستخدام هذا النظام لأنها لا تحتوي على نماذج مكررة بشكل كبير.
إذا احتوى الملف على العديد من النماذج المكررة, فإن معدل الانخفاض في الحجم يزداد بازدياد حجم الملف. و يمكنك رؤية ذلك بالنظر إلى مثالنا السابق, فإذا أخذنا المزيد من خطاب الرئيس كنيدي, سنكون قادرين على الإشارة إلى النماذج في قاموسنا بشكل أكبر, وبالتالي نوفر المزيد من حجم الملف. كما يمكن الحصول على نماذج أكثر فاعلية بجعل الفحص أكثر دقة, و إنشاء قاموس أكثر فاعلية.
وهذه الفاعلية تعتمد أيضا على الخوارزمية المستخدمة من قبل برنامج الضغط. بعض البرامج تتلاءم بشكل خاص مع أنواع محددة من الملفات, وبالتالي يمكن أن تقوم بضغطها بشكل أفضل. وبعضها يحتوي على قواميس داخل القواميس, التي يمكن أن تقوم بالضغط بشكل أكبر في الملفات ذات الحجم الكبير و ليس الصغير. و بينما جميع برامج الضغط تعمل بنفس الفكرة البسيطة, هناك حقيقةً اختلاف في طريقة التنفيذ. والمبرمجين يعملون دائما على بناء نظام ضغط أفضل.
الضياع و عدم الضياع:
إن نوع الضغط الذي نناقشه هنا يدعى Lossless Compression, لأنه يسمح لك بإعادة إنشاء الملف الأصلي كما كان عليه تماما من قبل. جميع أنواع الضغط التي تمنع ضياع البيانات ترتكز على فكرة تقطيع الملف إلى أجزاء أصغر من أجل إرساله عبر الانترنت أو التخزينه و من ثم تجميعه مرة أخرى بحيث يستخدم من جديد.
أما نوع الضغط المسمى Lossy Compression يعمل بشكل مختلف تماما. حيث أن البرامج العاملة بهذه الطريقة تقوم بحذف البتات الغير لازمة من المعلومات, وتعيد إنشاء الملف من جديد بحيث يصبح أصغر حجما. و يستخدم هذا النوع من الضغط كثيرا لتخفيض حجم الصور من نوع bitmap, التي تكون عادة كبيرة الحجم. ولمعرفة كيف يتم ذلك, دعنا نرى كيف يمكن للكمبيوتر أن يضغط الصورة.
إن برامج الضغط العاملة بطريقة Lossless Compression لا يمكنها ضغط هذا النوع من الملفات بشكل جيد. فعندما تبدو أجزاء كبيرة من الصورة متشابهة إلى حد كبير, مثل أن تكون السماء كلها زرقاء, تكون معظم النقاط المنفصلة مختلفة نوعا ما. ولجعل هذه الصورة أصغر بدون التأثير على دقتها, يجب عليك تغيير قيمة اللون في نقاط محددة من الصورة. فإذا احتوت الصورة على مساحة جيدة من السماء الزرقاء, يقوم البرنامج باختيار لون أزرق واحد بحيث يمكن استخدامه في كل نقطة. ومن ثم يعيد البرنامج كتابة الملف بحيث أن قيمة كل نقطة من السماء يتم الإشارة إليها باللون الذي تم اختياره. فإذا تمت عملية الضغط بشكل جيد, لن تستطيع ملاحظة الفرق في دقة الصورة, لكن حجم الملف سوف يصبح أصغر بشكل ملحوظ.
وبالطبع, في الضغط من نوع Lossy Compression, لن تستطيع الحصول على الملف الأصلي بعد القيام بعملية الضغط. و ذلك سوف يعتمد على إعادة تفسير البرنامج للملف المضغوط ليبدو مشابها للملف اللأصلي. ولهذا السبب, لا يمكنك استخدام هذا النوع من الضغط في الملفات التي يجب إعادتها لما كانت عليه تماما, مثل تطبيقات البرامج و قواعد البيانات.