خوارزميات الضغط-1 : خوارزمية Rle و Lz77

[dj-siba]

المشاركة الأصلية كتبت بواسطة in4matics في 15-02-2008 الساعة 03:49 PM:
السلام عليكم و رحمة الله و بركاته
سنتكلم في هذا الدرس و عدد آخر من الدروس إن أحيانا الله عن بعض خوارزميات الضغط (شكراً للأخ مراد على اقتراحه ).
و سيكون تركيزنا على خوارزمية ضغط GZip التي يعتمد عليها تنسيق الملفات Zip.
لن أطيل في المقدمات، إلى الدرس:
1- خوارزمية RLE (اختصار لـ Run-Length Encoding):
فكرتها بسيطة جداً و أظنها خطرت على بال الكثيرين ممن فكروا باختراع خوارزمية ضغط
سنأخذ مثالاُ مباشرة، ليكن لدينا النص التالي و الذي طوله 26 حرفاً:
aaaaaaaaaaaattrrrreeeeeeee
لو قلت لك اقرأ لي هذا النص، فعلى الأغلب لن تقرأ لي النص هكذا: a a a a a a a . . . t t r r r r e e
بل ستقول لي: 12 حرف a، و حرفي t، و 4 حروف r، و 8 حروف e، و هذه هي فكرة الخوارزمية!
سنكتب بدل كل سلسلة أحرف متشابهة الحرف و تكراره فقط، مثلاً يصبح النص السابق:
12a2t4r8e
لاحظ أن طول النص الجديد هو 8 بايتات (الرقم 12 نكتبه في بايت واحد).
و بالتالي اختصرنا 26 - 8 = 18 بايت، و نسبة الضغط:
(8 / 26) * 100 = 30%
2- خوارزمية LZ77 (اختصار لـ Lempel-Ziv 1977):
لنفكر بتطوير الخوارزمية السابقة، ماذا لو كان لدي النص التالي:
at4re-at4re-abc4re-bat4rest
لاحظوا الآن أن هناك كلمات تتكرر مثل "at4re" التي تكررت 3 مرات، و "-at4re" تكررت مرتين، و "4re" تكررت 4 مرات.
لماذا لا نستعيص عن الكلمتين المكررتين من كلمة "at4re" الأولى بمؤشر إلى بداية الكلمة و طولها، أي يصبح النص:
at4re-[1,5]-abc4re-b[1,5]st
حيث الرقم 1 يعني الحرف الأول، و الرقم 5 يعني 5 أحرف، أي أننا نقول: اذهب إلى الحرف الذي ترتيبه 1 و قص 5 أحرف تحصل على الكلمة المطلوبة، ثم ضعها مكان [1,5].
و لكن لاحظوا معي، ألم يكن من الأفضل أن نبدل كلمة "-at4re" بـ [1,6] لنحصل على ضغط أفضل (أي أننا نختار التكرار الأكبر من الأحرف)؟ أي يصبح النص المضغوط:
at4re-[1,6]abc4re-b[1,5]st
هل يمكننا الضغط أيضاً؟.. نعم لنبدل "-4re" بـ [3,4]، فيصبح النص المضغوط:
at4re-[1,6]abc[3,4]b[1,5]st
الآن كيف نفك ضغط النص السابق؟
الحل بسيط، نبدأ بقراءة أحرف النص المضغوط:
* إذا وجدنا حرفاً عادياً نكتبه في الخرج.
* إذا وجدنا زوجاً من الشكل [x,y] نذهب إلى *الخرج* و نقص منه كلمة بطول y ابتداء من الموقع x، ثم نكتبها في نهاية الخرج.
و نتابع... حتى نصل إلى نهاية النص المشفر و عندها يكون الخرج هو النص الأصلي
3- مثال يظهر قوة خوارزمية LZ77:
بفرض لدينا النص التالي:
AbcAbcAbcAbcAbcAbc
دعونا نطبق الخوارزمية عليه، سنجد أن هناك كلمة متكررة و هي Abc و لذا يصبح شكل النص المضغوط:
[Abc[1,3][1,3][1,3][1,3][1,3
و لكننا ذكرنا في الدرس ما يلي "نختار التكرار الأكبر من الأحرف"، إذاً ركزوا معي..
ألا يمكننا اعتبار آخر 5 كلمات Abc هي تكرار لأول خمس كلمات Abc ؟!
أي الجزء المحدد بين قوسين
[Abc[AbcAbcAbcAbcAbc
هو تكرار للجزءالتالي المحدد بين قوسين
AbcAbcAbcAbcAbc]Abc]
و بالتالي يكون ناتج الضغط هو:
[Abc[1,15
يبدو ذلك غريباً أليس كذلك؟
للتأكد من صحة العمل لنقم بفك ضغط النص الأخير:
- من أجل الحروف الثلاثة الأولى سنضعها كما هي في الخرج.
- من أجل الزوج [1,15] نبدأ بالموضع 1 من الخرج أي بأول حرف، و ننسخ الحروف حرفاً حرفاً و نضعها في آخر الخرج حتى يصبح مجموع الحروف المنسوخة 15 كما يلي:
في كل خطوة ننسخ الحرف الحالي إلى نهاية الخرج و نزيد عداد الأحرف كما في الصورة:

و بالتالي فالخرج هو AbcAbcAbcAbcAbcAbc و هو نفس النص الأصلي، لذا فالخوارزمية تعمل بشكل صحيح..
4- تمارين:
طبق الخوارزمية الأخيرة على النص التالي:
abc-dabc-reabcde
انتهى الدرس
إذا كان لديكم أي سؤال أو استفسار أنا في الخدمة..
الدرس القادم إن شاء الله سيكون عن خوارزمية ضغط Huffman.
شكراً لكم
in4matics | AT4RE