خوارزميات الضغط-1 : خوارزمية Rle و Lz77 - نسخة قابلة للطباعة +- الفريق العربي للهندسة العكسية (https://www.at4re.net/f) +-- قسم : منتديات الهندسة العكسية - Reverse Engineering Forums (https://www.at4re.net/f/forum-4.html) +--- قسم : الهندسة العكسية المتقدمة - Advanced RCE (https://www.at4re.net/f/forum-26.html) +--- الموضوع : خوارزميات الضغط-1 : خوارزمية Rle و Lz77 (/thread-159.html)

خوارزميات الضغط-1 : خوارزمية Rle و Lz77 - dj-siba - 20-10-2018 المشاركة الأصلية كتبت بواسطة 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