الخوارزمية

الفكرة

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





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

الترميز

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



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

فك الترميز

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



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

مثال

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



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


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

00 0

ح 01 1


خ 10 2


ز 11 3

الترميز

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



السلسلة المحرف الخرج القيم المضافة


الحالية التالي القيمة البتات للقاموس


------ ------ ----------------- -------------


«لا شيء» ح


ح ح 1 0001 4 ح ح


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





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