خوارزمية لامبل وزيف وويلش
المحتويات
في البداية، ليمبيل-زيف-ويلش أو اختصارا إل زد دبليو (LZW) هي خوارزمية مشهورة لضغط البيانات بدون ضياع تم إنشاؤها من قبل آبراهام ليمبيل وجاكوب زيف وتيري ويلش. نشرت من قبل فيلش عام 1984 تحسينا على خوارزمية إل زد 78 المنشورة من قبل ليمبيل وزيف عام 1978. الخوارزمية مصممة لتكون سريعة لكنها عادةً لا تصل للحالة الأمثلية من الضغط لأنها تقوم بتحليل محدود للبيانات. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
كذلك، تستعمل هذه الخوارزمية ضمن عدة تقنيات وعمليات كضغط النصوص وكمرحلة من مراحل ضغط الصور.
الخوارزمية
مثال
علاوةً على ذلك، النص المراد تشفيره مأخوذ من صورة تحوي الألوان الأساسية الثلاث (الأحمر، الأخضر والأزرق) وهو:
ومن ناحية أخرى، يشرح هذا المثال كيفية عمل الخوارزمية بشكل عملي، حيث يظهر ويراقب الدخل والخرج والقاموس في كل مرحلة من مراحل العمل الترميز وفك الترميز. هذا المثال معمول خصيصاً ليظهر نسبة ضغط مقبولة على نص قصير. في النصوص الحقيقية لا يظهر التكرار بهذا الشكل ولا يمكن أن تصل نسبة الضغط لهذا المستوى على نصوص بهذا الطول.
ح ح ح خ خ خ ح ح خ خ ز ز ز ز ز ز ز ز ز ز ز ز ز ز ز#
من جهة ثانية، يشير محرف # إلى نهاية النص. بما أن هذه الرسالة مأخوذة من صورة تحوي الألوان الثلاثة فإن الرموز الممكنة هي ح وخ وز وبالتالي فإن القاموس الأولي سيحوي الرموز الثلاثة وسيحوي على رمز نهاية النص. وبالتالي سيكون القاموس المبدئي على الشكل:
- # = 00 = 0
- ح = 01 = 1
- خ = 10 = 2
- ز = 11 = 3
الفكرة
وفي هذا السياق، يقوم فيلش في ورقته البحثية بشرح تجربته عام 1984 حيث قام بترميز سلاسل من بيانات مرمزة على 8-بت لتصبح قيم ثابتة الطول من 12-بت. الأرقام من 0 حتى 255 تمثل سلاسل من محرف واحد موافقة للمحرف المرمز على 8-بت، أما الأرقام من 256 وحتى 4095 فيتم إنشاؤها ضمن القاموس للسلاسل التي تواججها الخوارزمية أثناء الترميز. في كل مرحلة من مراحل الضغط، يتم تجميع بايتات الدخل ضمن سلسلة حتى يكون المحرف القادم سيجعل من السلسلة غير معرفة (أي أنه سيقوم بإعطاء سلسلة من المحارف غير موجودة ضمن القاموس). يقوم نظام الترميز بإرسال رقم السلسلة التي توصل لها ضمن القاموس (دون المحرف الأخير)، ويتم إنشاء مدخل ضمن القاموس للسلسلة الجديدة الناتجة (مع المحرف الأخير) وإعطاء رقم للسلسلة.
وفي هذا الصدد، بما أن القاموس يتم إنشاؤه أثناء عملية الترميز فإن على الطرف الآخر (نظام فك الترميز) أن يقوم بتقليد عملية بناء القاموس أثناء استقباله وقراءته للبيانات.
خ خ
خ خ ح 6 0110 7: خ خ ح
ح ح
ح ح خ
- ح ح خ خ 5 0101 8: ح ح خ خ
- خ ز 2 0010 9: خ ز
- ز ز 3 0011 10: ز ز
ح ح
ح ح خ 4 0100 5: ح ح خ
خ خ 2 0010 6: خ خ
ز ز ز ز ز
- ز ز ز ز ز # 13 1101
- طول البيانات قبل الترميز: 25 محرف × 2 بت للمحرف = 50 بت
- طول البيانات بعد الترميز: 11 قيمة × 4 بت للقيمة = 44 بت
وفي هذا الصدد، باستخدام خوارزمية إل زد دبليو تم التخلص من 6 بتات، أي أن النص قد تم ضغطه بنسبة 12%, طبعاً هذه النسبة ضئيلة هنا لأن الأبجدية المستعملة بسيطة (4 رموز فقط) بينما في حال تم استخدام أبجدية أكبر كجدول أسكي مثلاً فإن النسبة سترتفع لأن عدد البتات اللازمة للمحرف قبل الترميز سيكون أكبر من عدد البتات اللازمة للقيمة بعد الترميز.
ز ز ز ز
- ز ز ز ز ز 12 1100 13: ز ز ز ز ز
- ز ز
- ز ز ز
- ز ز ز ز
0000 0 #
وفي السياق ذاته، في كل مرحلة يستقبل نظام فك الترميز القيمةس فيبحث عنها ضمن القاموس ويقوم بإخراج السلسلة ع المقابلة لها على الخرج، ومن ثم يقوم باعتبار السلسلة ع + ؟ على أنها قد أضيفت مؤخراً للقاموس ويعطيها قيمة مقابلة، حيث أن نظام الترميز قد لاحظ أن السلسلة غير موجودة في القاموس فأرسل القسم الموجود منها وأنشأ مدخله لديه عن السلسلة الغير موجودة، لكن لمعرفة المحرف الأخير من السلسلة يجب على النظام أن يننظر السلسلة القادمة وينظر للمحرف الأول منها، حيث أن هذا المحرف هو الذي أوقف نظام الترميز عن تشكيل سلسلة أكبر في المرة السابقة حينما أرسل القيمة س.
وفي هذا الصدد، كما تم التنويه فالمثال السابق مأخوذ من بيانات صورة، وهي عادةً ما تؤدي للمشكلة السابقة (عدم اكتمال السلاسل بشكل بسيط)، بينما لا تظهر هذه المشكلة في النصوص العادية حيث أنها لا تحوي تكرارات متتالية إلى حدّ كبير لنفس النمط.
من جهة ثانية، يبقى النظام يعمل على هذه الطريقة بنجاح ما دامت القيم المرسلة لاحقاً موجودة ضمن القاموس، لكن ماذا يحدث عندما يستقبل النظام قيمة تقابل سلسلة غير منتهية حتى الآن؟ الجواب أن النظام يهتم بأول محرف من السلسلة، فحتى لو لم تكن منتهية سينظر للمحرف الأول منها وينهي السلسلة الحالية به، كما في المثال السابق حيث عندما يستقبل النظام القيمة «4» وهي لسلسلة غير منتهية «ح ؟» يقوم بأخذ المحرف الأول منها «ح» ويكمل به السلسلة الحالية لتصبح «4: ح ح».
الترميز
علاوةً على ذلك، بهذه الطريقة يتم إضافة سلاسل جديدة إلى القاموس شيئاً فشيئاً مع استمرار عملية الترميز، وتصبح هذه السلاسل الجديدة متوفرة للتعرف عليها ضمن عملية الترميز أثناء التقدم في ترميز البيانات. هذه الخوارزمية تعمل بشكل أفضل على البيانات التي تحوي أنماطاً متكررة من البيانات، وبالتالي فإن أول قسم من الرسالة المرمزة سيكون قليل الضغط، لكن تزداد نسبة الضغط مع ازدياد طول الرسالة المرمزة.
كذلك، يتم تهيئة قاموس بالسلاسل النصية المؤلفة من محرف واحد، حيث توافق هذه السلاسل جميع سلاسل المحارف الممكنة والمؤلفة من محرف واحد (المتوقع مشاهدتها ضمن البيانات المطلوب ترميزها). الخوارزمية تعمل عن طريق فحص سلسلة الدخل بحثاً عن أكبر سلسلة من محارف الدخل لها سلسلة مقابلة ضمن القاموس وذلك من الموقع الحالي لشريط الدخل، تتم عند الحصول على أكبر سلسلة ممكنة يتم إخراج رقم المدخلة ضمن القاموس المقابلة لهذه السلسلة، ثم يتم إضافة مدخلة جديدة إلى القاموس تتألف من السلسلة التي تم الحصول عليها متبوعةً بالمحرف الذي يلي السلسلة على شريط الدخل (المحرف الذي سيجعل هذه السلسلة غير موجودة ضمن القاموس). ثم يتم تحريك مؤشر القراءة من شريط الدخل إلى المحرف الجديد (الذي تمت إضافته للسلسلة ضمن المدخلة الجديدة).
«لا شيء» ح
في هذا الإطار، ح ح 1 0001 4: ح ح <--- القيمة 4 هي أول قيمة فارغة ضمن القاموس
بما أنه يحوي مبدئياً القيم من 0 وحتى 3
فك الترميز
إضافةً إلى ذلك، لفك الترميز لا بد من نظام فك الترميز من معرفة القاموس الأولي المستعمل للترميز، بينما يقوم النظام بإضافة مدخلات القاموس أثناء الاستمرار في عملية فك الترميز.
البتات القيمة الخرج الجديدة
الدخل سلسلة مدخلات القاموس
---- ---- ----
- 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: ز ز ز ز ز ؟
ز ز ز
- ز ز ز ز 11 1011 12: ز ز ز ز
- ز ز
- ز ز ز
الترميز
من جهة ثانية، يقوم المرمز بتخبئة المحارف من سلسلة الدخل ضمن السلسلة ω حتى تصبح السلسلة ω + المحرف التالي غير موجودة ضمن القاموس. يتم إخراج القيمة الموافقة للسلسلة ω ضمن القاموس ويتم إضافة السلسلة ω + المحرف التالي إلى القاموس. ومن ثم بدء التخبئة ابتداءً من المحرف التالي.
- السلسلة المحرف الخرج القيم المضافة
- الحالية التالي القيمة البتات للقاموس
- ---- ---- ---- ----
ز ز
ز ز ز 10 1010 11: ز ز ز
ز ز
فك الترميز
من جهة ثانية، تكون عملية فك الترميز بقراءة قيمة من الدخل المرمز وإخراج سلسلة المحارف الموافقة لهذه القيمة على الخرج، حيث يحوي نظام فك الترميز نفس القاموس الأولي المشار إليه في فقرة الترميز والذي يحوي جميع سلاسل المحارف الممكنة والمؤلفة من محرف واحد، وفي نفس الوقت وأثناء فك الترميز يقوم نظام فك الترميز بإضافة مدخلات جديدة إلى قاموس السلاسل لديه. أثناء فك الترميز يقوم نظام فك الترميز بإضافة المدخلات الجديدة إلى القاموس عن طريق قراءة القيمة التالية على الدخل المرمز، ومن ثم إضافة سلسلة جديدة إلى القاموس وهي مؤلفة من ضم السلسلة الماضية مع أول محرف من السلسلة التالية لتشكيل سلسلة جديدة. يقوم النظام بتكرار هذه العملية حتى ينتهي شريط الدخل وعندها يتم إخراج السلسلة الأخيرة دون أي إضافة على القاموس.
علاوةً على ذلك، بهذه الطريقة يقوم نظام فك الترميز ببناء قاموس مطابق للقاموس عند الطرف الآخر (نظام الترميز) ويستعمله لفك ترميز القيم المرسلة له. وبالتالي فلا حاجة لإرسال القاموس كاملاً بين الطرفين، وإنما يتم إرسال القاموس الأولي فقط (وفي أغلب الأحيان يكون هذا القاموس متفق عليه مسبقاً ولا داعي لإرساله، كجدول أسكي مثلاً).
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟