20-10-2018, 09:22 AM
المشاركة الأصلية كتبت بواسطة 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 كما يلي:
في كل خطوة ننسخ الحرف الحالي إلى نهاية الخرج و نزيد عداد الأحرف كما في الصورة:
![[صورة مرفقة: 4b8e021d7c.png]](http://img2.freeimagehosting.net/uploads/4b8e021d7c.png)
و بالتالي فالخرج هو AbcAbcAbcAbcAbcAbc و هو نفس النص الأصلي، لذا فالخوارزمية تعمل بشكل صحيح..
4- تمارين:
طبق الخوارزمية الأخيرة على النص التالي:
abc-dabc-reabcde
انتهى الدرس
إذا كان لديكم أي سؤال أو استفسار أنا في الخدمة..
الدرس القادم إن شاء الله سيكون عن خوارزمية ضغط Huffman.
شكراً لكم
in4matics | AT4RE
السلام عليكم و رحمة الله و بركاته
سنتكلم في هذا الدرس و عدد آخر من الدروس إن أحيانا الله عن بعض خوارزميات الضغط (شكراً للأخ مراد على اقتراحه
).و سيكون تركيزنا على خوارزمية ضغط 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
قطرة الماء تـثـقب الحجر.. لا بالعنف. لكن بتكرار المحاولة
أخي لن تنال العلم إلا بستة... ذكاء و حرص و اجتهاد و بلغة...و صحبة أستاذ و طول زمان
أخي لن تنال العلم إلا بستة... ذكاء و حرص و اجتهاد و بلغة...و صحبة أستاذ و طول زمان