خوارزمية لامبل-زيف-ويلش

ليمبيل-زيف-ويلش (Lempel–Ziv–Welch)‏ أو اختصارا إل زد دبليو (LZW) هي خوارزمية مشهورة لضغط البيانات بدون ضياع تم إنشاؤها من قبل آبراهام ليمبيل وجاكوب زيف وتيري ويلش. نشرت من قبل فيلش عام 1984 تحسينا على خوارزمية إل زد 78 المنشورة من قبل ليمبيل وزيف عام 1978. الخوارزمية مصممة لتكون سريعة لكنها عادةً لا تصل للحالة الأمثلية من الضغط لأنها تقوم بتحليل محدود للبيانات.

تستخدم هذه الخوارزمية ضمن عدة تقنيات وعمليات كضغط النصوص وكمرحلة من مراحل ضغط الصور.

الخوارزمية

الفكرة

يقوم فيلش في ورقته البحثية^[1] بشرح تجربته عام 1984 حيث قام بترميز سلاسل من بيانات مرمزة على 8-بت لتصبح قيم ثابتة الطول من 12-بت. الأرقام من 0 حتى 255 تمثل سلاسل من محرف واحد موافقة للمحرف المرمز على 8-بت، أما الأرقام من 256 وحتى 4095 فيتم إنشاؤها ضمن القاموس للسلاسل التي تواججها الخوارزمية أثناء الترميز. في كل مرحلة من مراحل الغط، يتم تجميع بايتات الدخل ضمن سلسلة حتى يكون المحرف القادم سيجعل من السلسلة غير معرفة (أي أنه سيقوم بإعطاء سلسلة من المحارف غير موجودة ضمن القاموس). يقوم نظام الترميز بإرسال رقم السلسلة التي توصل لها ضمن القاموس (دون المحرف الأخير)، ويتم إنشاء مدخل ضمن القاموس للسلسلة الجديدة الناتجة (مع المحرف الأخير) وإعطاء رقم للسلسلة.

بما أن القاموس يتم إنشاؤه أثناء عملية الترميز فإن على الطرف الآخر (نظام فك الترميز) أن يقوم بتقليد عملية بناء القاموس أثناء استقباله وقراءته للبيانات.

الترميز

يتم تهيئة قاموس بالسلاسل النصية المؤلفة من محرف واحد، حيث توافق هذه السلاسل جميع سلاسل المحارف الممكنة والمؤلفة من محرف واحد (المتوقع مشاهدتها ضمن البيانات المطلوب ترميزها). الخوارزمية تعمل عن طريق فحص سلسلة الدخل بحثاً عن أكبر سلسلة من محارف الدخل لها سلسلة مقابلة ضمن القاموس وذلك من الموقع الحالي لشريط الدخل، تتم عند الحصول على أكبر سلسلة ممكنة يتم إخراج رقم المدخلة ضمن القاموس المقابلة لهذه السلسلة، ثم يتم إضافة مدخلة جديدة إلى القاموس تتألف من السلسلة التي تم الحصول عليها متبوعةً بالمحرف الذي يلي السلسلة على شريط الدخل (المحرف الذي سيجعل هذه السلسلة غير موجودة ضمن القاموس). ثم يتم تحريك مؤشر القراءة من شريط الدخل إلى المحرف الجديد (الذي تمت إضافته للسلسلة ضمن المدخلة الجديدة).

بهذه الطريقة يتم إضافة سلاسل جديدة إلى القاموس شيئاً فشيئاً مع استمرار عملية الترميز، وتصبح هذه السلاسل الجديدة متوفرة للتعرف عليها ضمن عملية الترميز أثناء التقدم في ترميز البيانات. هذه الخوارزمية تعمل بشكل أفضل على البيانات التي تحوي أنماطاً متكررة من البيانات، وبالتالي فإن أول قسم من الرسالة المرمزة سيكون قليل الضغط، لكن تزداد نسبة الضغط مع ازدياد طول الرسالة المرمزة.

فك الترميز

تكون عملية فك الترميز بقراءة قيمة من الدخل المرمز وإخراج سلسلة المحارف الموافقة لهذه القيمة على الخرج، حيث يحوي نظام فك الترميز نفس القاموس الأولي المشار إليه في فقرة الترميز والذي يحوي جميع سلاسل المحارف الممكنة والمؤلفة من محرف واحد، وفي نفس الوقت وأثناء فك الترميز يقوم نظام فك الترميز بإضافة مدخلات جديدة إلى قاموس السلاسل لديه. أثناء فك الترميز يقوم نظام فك الترميز بإضافة المدخلات الجديدة إلى القاموس عن طريق قراءة القيمة التالية على الدخل المرمز، ومن ثم إضافة سلسلة جديدة إلى القاموس وهي مؤلفة من ضم السلسلة الماضية مع أول محرف من السلسلة التالية لتشكيل سلسلة جديدة. يقوم النظام بتكرار هذه العملية حتى ينتهي شريط الدخل وعندها يتم إخراج السلسلة الأخيرة دون أي إضافة على القاموس.

بهذه الطريقة يقوم نظام فك الترميز ببناء قاموس مطابق للقاموس عند الطرف الآخر (نظام الترميز) ويستخدمه لفك ترميز القيم المرسلة له. وبالتالي فلا حاجة لإرسال القاموس كاملاً بين الطرفين، وإنما يتم إرسال القاموس الأولي فقط (وفي أغلب الأحيان يكون هذا القاموس متفق عليه مسبقاً ولا داعي لإرساله، كجدول أسكي مثلاً).

مثال

يشرح هذا المثال كيفية عمل الخوارزمية بشكل عملي، حيث يظهر ويراقب الدخل والخرج والقاموس في كل مرحلة من مراحل العمل الترميز وفك الترميز. هذا المثال معمول خصيصاً ليظهر نسبة ضغط مقبولة على نص قصير. في النصوص الحقيقية لا يظهر التكرار بهذا الشكل ولا يمكن أن تصل نسبة الضغط لهذا المستوى على نصوص بهذا الطول.

النص المراد تشفيره مأخوذ من صورة تحوي الألوان الأساسية الثلاث (الأحمر، الأخضر والأزرق) وهو:

ح ح ح خ خ خ ح ح خ خ ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز#

يشير محرف # إلى نهاية النص. بما أن هذه الرسالة مأخوذة من صورة تحوي الألوان الثلاثة فإن الرموز الممكنة هي ح وخ وز وبالتالي فإن القاموس الأولي سيحوي الرموز الثلاثة وسيحوي على رمز نهاية النص. وبالتالي سيكون القاموس المبدئي على الشكل:

# = 00 = 0 ح = 01 = 1 خ = 10 = 2 ز = 11 = 3

الترميز

يقوم المرمز بتخبئة المحارف من سلسلة الدخل ضمن السلسلة ω حتى تصبح السلسلة ω + المحرف التالي غير موجودة ضمن القاموس. يتم إخراج القيمة الموافقة للسلسلة ω ضمن القاموس ويتم إضافة السلسلة ω + المحرف التالي إلى القاموس. ومن ثم بدء التخبئة ابتداءً من المحرف التالي.

السلسلة المحرف الخرج القيم المضافة الحالية التالي القيمة البتات للقاموس ---- ---- ---- ---- «لا شيء» ح ح ح 1 0001 4: ح ح <--- القيمة 4 هي أول قيمة فارغة ضمن القاموس بما أنه يحوي مبدئياً القيم من 0 وحتى 3 ح ح ح ح خ 4 0100 5: ح ح خ خ خ 2 0010 6: خ خ خ خ خ خ ح 6 0110 7: خ خ ح ح ح ح ح خ ح ح خ خ 5 0101 8: ح ح خ خ خ ز 2 0010 9: خ ز ز ز 3 0011 10: ز ز ز ز ز ز ز 10 1010 11: ز ز ز ز ز ز ز ز ز ز ز ز 11 1011 12: ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز 12 1100 13: ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز # 13 1101 طول البيانات قبل الترميز: 25 محرف × 2 بت للمحرف = 50 بت طول البيانات بعد الترميز: 11 قيمة × 4 بت للقيمة = 44 بت

باستخدام خوارزمية إل زد دبليو تم التخلص من 6 بتات، أي أن النص قد تم ضغطه بنسبة 12%, طبعاً هذه النسبة ضئيلة هنا لأن الأبجدية المستخدمة بسيطة (4 رموز فقط) بينما في حال تم استخدام أبجدية أكبر كجدول أسكي مثلاً فإن النسبة سترتفع لأن عدد البتات اللازمة للمحرف قبل الترميز سيكون أكبر من عدد البتات اللازمة للقيمة بعد الترميز.

فك الترميز

لفك الترميز لا بد من نظام فك الترميز من معرفة القاموس الأولي المستخدم للترميز، بينما يقوم النظام بإضافة مدخلات القاموس أثناء الاستمرار في عملية فك الترميز.

الدخل سلسلة مدخلات القاموس البتات القيمة الخرج الجديدة ---- ---- ---- 0001 1 ح 4: ح ؟ <--- بانتظار المحرف الأول من السلسلة التالية 0100 4 ح ح 4: ح ح 5: ح ح ؟ 0010 2 خ 5: ح ح خ 6: خ ؟ 0110 6 خ خ 6: خ خ 7: خ خ ؟ 0101 5 ح ح خ 7: خ خ ح 8: ح ح خ ؟ 0010 2 خ 8: ح ح خ خ 9: خ ؟ 0011 3 ز 9: خ ز 10: ز ؟ 1010 10 ز ز 10: ز ز 11: ز ز ؟ 1011 11 ز ز ز 11: ز ز ز 12: ز ز ز ؟ 1100 12 ز ز ز ز 12: ز ز ز ز 13: ز ز ز ز ؟ 1101 13 ز ز ز ز ز 13: ز ز ز ز ز 14: ز ز ز ز ز ؟ 0000 0 #

في كل مرحلة يستقبل نظام فك الترميز القيمةس فيبحث عنها ضمن القاموس ويقوم بإخراج السلسلة ع المقابلة لها على الخرج، ومن ثم يقوم باعتبار السلسلة ع + ؟ على أنها قد أضيفت مؤخراً للقاموس ويعطيها قيمة مقابلة، حيث أن نظام الترميز قد لاحظ أن السلسلة غير موجودة في القاموس فأرسل القسم الموجود منها وأنشأ مدخله لديه عن السلسلة الغير موجودة، لكن لمعرفة المحرف الأخير من السلسلة يجب على النظام أن يننظر السلسلة القادمة وينظر للمحرف الأول منها، حيث أن هذا المحرف هو الذي أوقف نظام الترميز عن تشكيل سلسلة أكبر في المرة السابقة حينما أرسل القيمة س.

يبقى النظام يعمل على هذه الطريقة بنجاح ما دامت القيم المرسلة لاحقاً موجودة ضمن القاموس، لكن ماذا يحدث عندما يستقبل النظام قيمة تقابل سلسلة غير منتهية حتى الآن؟ الجواب أن النظام يهتم بأول محرف من السلسلة، فحتى لو لم تكن منتهية سينظر للمحرف الأول منها وينهي السلسلة الحالية به، كما في المثال السابق حيث عندما يستقبل النظام القيمة «4» وهي لسلسلة غير منتهية «ح ؟» يقوم بأخذ المحرف الأول منها «ح» ويكمل به السلسلة الحالية لتصبح «4: ح ح».

كما تم التنويه فالمثال السابق مأخوذ من بيانات صورة، وهي عادةً ما تؤدي للمشكلة السابقة (عدم اكتمال السلاسل بشكل بسيط)، بينما لا تظهر هذه المشكلة في النصوص العادية حيث أنها لا تحوي تكرارات متتالية بشكل كبير لنفس النمط.

المراجع

موسوعات ذات صلة :

• موسوعة علم الحاسوب
• موسوعة برمجيات
• موسوعة تقنية المعلومات