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

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

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

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

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

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

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

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

السلسلة	  المحرف          الخرج               القيم المضافة
الحالية	  التالي     القيمة    البتات            للقاموس
----	  ----     ----        ----
«لا شيء»	  ح
ح         ح          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: ح ح».

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