ليمبل-زيف-ويلش

يمكن وصف عملية التشفير على النحو التالي:

1. قم بتهيئة القاموس ليحتوي على جميع السلاسل النصية التي طولها واحد.
2. ابحث عن أطول سلسلة نصية W في القاموس والتي تطابق المدخلات الحالية.
3. قم بإصدار فهرس القاموس الخاص بـ W للإخراج وإزالة W من المدخلات.
4. أضف الحرف W متبوعًا بالرمز التالي في المدخلات إلى القاموس.
5. انتقل إلى الخطوة 2.

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

بهذه الطريقة، تُسجَّل السلاسل الأطول تدريجيًا في القاموس وتكون متاحة للترميز اللاحق كقيم إخراج مفردة. تعمل الخوارزمية بشكل أفضل مع البيانات ذات الأنماط المتكررة، لذا فإن الأجزاء الأولى من الرسالة لا تتعرض لضغط كبير. مع ذلك، ومع ازدياد حجم الرسالة، تميل نسبة الضغط إلى التقارب نحو الحد الأقصى (أي أن عامل الضغط أو نسبته يتحسن بشكل متزايد، وليس خطيًا، مقتربًا من الحد الأقصى النظري خلال فترة زمنية محدودة بدلًا من فترة زمنية غير محدودة). ^{[ 2 ]}

يمكن وصف عملية فك التشفير على النحو التالي:

1. قم بتهيئة القاموس ليحتوي على جميع السلاسل النصية التي طولها واحد.
2. اقرأ الرمز المشفر التالي.
3. إذا لم يكن الرمز مشفرًا في القاموس، فانتقل إلى الخطوة 7.
4. قم بإخراج السلسلة النصية W المقابلة إلى المخرجات.
5. قم بدمج السلسلة السابقة التي تم إخراجها مع الرمز الأول W ؛ أضف هذا إلى القاموس.
6. انتقل إلى الخطوة 9.
7. قم بدمج السلسلة السابقة التي تم إخراجها مع رمزها الأول؛ وسمّ هذه السلسلة V.
8. أضف V إلى القاموس وأخرج V إلى المخرجات.
9. كرر الخطوة 2 حتى نهاية المدخلات.

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

في حال استخدام رموز متغيرة العرض، يجب على المُشفِّر والمُفكِّك توخي الحذر عند تغيير العرض في نفس النقاط من البيانات المُشفَّرة لتجنب أي اختلاف في حدود الرموز الفردية في التدفق. في الإصدار القياسي، يزيد المُشفِّر العرض من p إلى p  +  1 عند مصادفة تسلسل ω  + s غير موجود في الجدول (مما يستدعي إضافة رمز له)، ولكن الرمز التالي المتاح في الجدول هو 2p ⁽ أول رمز يتطلب p + 1 بت). يُصدر المُشفِّر رمز ω بعرض p (لأن هذا الرمز لا يتطلب p + 1 بت)، ثم يزيد عرض الرمز بحيث يكون الرمز التالي المُصدر بعرض p + 1 بت.       

يكون جهاز فك التشفير دائمًا متأخرًا برمز واحد عن جهاز التشفير عند بناء الجدول، لذلك عندما يرى رمز ω، فإنه يُنشئ مدخلًا للرمز 2p ⁻ 1. وبما أن هذه هي النقطة التي يزيد فيها جهاز التشفير عرض الرمز، فيجب على جهاز فك التشفير زيادة العرض هنا أيضًا - عند النقطة التي يُنشئ فيها أكبر رمز يتناسب مع p بت.  

لسوء الحظ، تقوم بعض التطبيقات المبكرة لخوارزمية التشفير بزيادة عرض الكود ثم تُصدر قيمة ω عند العرض الجديد بدلاً من العرض القديم، مما يجعل برنامج فك التشفير يعتقد أن العرض يتغير قبل الأوان بمقدار كود واحد. يُسمى هذا "التغيير المبكر"؛ وقد تسبب في الكثير من الارتباك لدرجة أن Adobe تسمح الآن بكلا الإصدارين في ملفات PDF، ولكنها تُضيف علامة صريحة في رأس كل دفق مضغوط بتقنية LZW للإشارة إلى ما إذا كان التغيير المبكر مُستخدمًا. من بين تنسيقات ملفات الرسومات التي تدعم ضغط LZW، يستخدم TIFF التغيير المبكر، بينما لا يستخدمه GIF ومعظم التنسيقات الأخرى.

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

بما أن الرموز الصادرة لا تقع عادةً على حدود البايتات، يجب أن يتفق المُشفِّر والمُفكِّك على كيفية تجميع الرموز في البايتات. الطريقتان الشائعتان هما: LSB-first (" البت الأقل أهمية أولاً") و MSB-first (" البت الأكثر أهمية أولاً"). في طريقة LSB-first، يُحاذى الرمز الأول بحيث يقع البت الأقل أهمية فيه ضمن البت الأقل أهمية في بايت التدفق الأول، وإذا كان الرمز يحتوي على أكثر من 8 بتات، تُحاذى البتات المتبقية ذات الترتيب الأعلى مع البتات الأقل أهمية في البايت التالي؛ وتُجمَّع الرموز اللاحقة بحيث يقع البت الأقل أهمية في البت الأقل أهمية غير المستخدم في بايت التدفق الحالي، مع الاستمرار في البايتات اللاحقة حسب الحاجة. أما طريقة MSB-first، فتُحاذى الرمز الأول بحيث يقع البت الأكثر أهمية فيه ضمن البت الأكثر أهمية في بايت التدفق الأول، مع محاذاة البت الزائد مع البت الأكثر أهمية في البايت التالي؛ وتُكتب الرموز اللاحقة بحيث يقع البت الأكثر أهمية في البت الأكثر أهمية غير المستخدم في بايت التدفق الحالي.

تستخدم ملفات GIF ترتيب التعبئة LSB أولاً. بينما تستخدم ملفات TIFF وملفات PDF ترتيب التعبئة MSB أولاً.

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

قم بتخزين الأحرف المدخلة في تسلسل ω حتى يصبح الحرف ω + الحرف التالي غير موجود في القاموس. ثم قم بإصدار رمز ω، وأضف الحرف ω + الحرف التالي إلى القاموس. ابدأ التخزين المؤقت مرة أخرى مع الحرف التالي. (السلسلة المراد ترميزها هي "TOBEORNOTTOBEORTOBEORNOT#").

الطول غير المشفر = 25 رمزًا × 5 بتات/رمز = 125 بتًا

الطول المشفر = (6 رموز × 5 بتات/رمز) + (11 رمزًا × 6 بتات/رمز) = 96 بت.

ساهم استخدام خوارزمية LZW في توفير 29 بت من أصل 125، مما قلل حجم الرسالة بأكثر من 23%. لو كانت الرسالة أطول، لكانت كلمات القاموس ستمثل مقاطع نصية أطول فأطول، مما يؤدي إلى إرسال الكلمات المتكررة بشكل مضغوط للغاية.

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

في كل مرحلة، يستقبل المُفكِّك رمزًا X؛ يبحث عن X في الجدول ويُخرج التسلسل χ الذي يُشفِّره، ويفترض أن χ +  ؟ هو المدخل الذي أضافه المُشفِّر للتو - لأن المُشفِّر أصدر X لـ χ تحديدًا لأن χ +  ؟ لم يكن موجودًا في الجدول، ثم يُضيفه. ولكن ما هو الحرف المفقود؟ إنه الحرف الأول في التسلسل الذي يُشفِّره الرمز التالي Z الذي يستقبله المُفكِّك. لذا يبحث المُفكِّك عن Z، ويُفكِّكه إلى التسلسل ω، ويأخذ الحرف الأول z ويُلحقه بنهاية χ كمدخل القاموس التالي.

تنجح هذه الطريقة طالما أن الرموز المستلمة موجودة في قاموس المُفكِّك، بحيث يمكن فك تشفيرها إلى متواليات. ماذا يحدث إذا استلم المُفكِّك رمزًا Z غير موجود في قاموسه؟ بما أن المُفكِّك دائمًا ما يكون متأخرًا برمز واحد فقط عن المُشفِّر، فلا يمكن أن يكون Z في قاموس المُشفِّر إلا إذا كان المُشفِّر قد أنشأه للتو ، عند إرسال الرمز السابق X للرمز χ. وبالتالي، يُشفِّر Z حرفًا ما ω وهو χ +  ؟، ويمكن للمُفكِّك تحديد الحرف المجهول كما يلي:

1. يرى جهاز فك التشفير X ثم Z، حيث يقوم X بتشفير التسلسل χ ويقوم Z بتشفير تسلسل غير معروف ω.
2. يعرف جهاز فك التشفير أن جهاز التشفير قد أضاف Z كرمز لـ χ + حرف غير معروف c ، لذا فإن ω = χ + c .
3. بما أن c هو الحرف الأول في دفق الإدخال بعد χ، وبما أن ω هي السلسلة التي تظهر مباشرة بعد χ، فيجب أن يكون c هو الحرف الأول من التسلسل ω.
4. بما أن χ هي سلسلة فرعية أولية من ω، فيجب أن يكون c أيضًا الحرف الأول من χ.
5. لذلك على الرغم من أن رمز Z ليس موجودًا في الجدول، إلا أن جهاز فك التشفير قادر على استنتاج التسلسل غير المعروف ويضيف χ + (الحرف الأول من χ) إلى الجدول كقيمة لـ Z.

تحدث هذه الحالة عندما يواجه المُشفِّر مُدخلات على شكل cScSc ، حيث c حرف واحد، وS سلسلة نصية، و cS موجودة بالفعل في القاموس، بينما cSc غير موجودة. يُصدر المُشفِّر رمز cS ، ويضع رمزًا جديدًا لـ cSc في القاموس. ثم يرى cSc في المُدخلات (بدءًا من الحرف c الثاني في cScSc ) ويُصدر الرمز الجديد الذي أضافه للتو. تُبين الحجة أعلاه أنه عندما يتلقى المُفكِّك رمزًا غير موجود في قاموسه، يجب أن تكون الحالة على هذا النحو.

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

تعتمد خوارزمية LZMW (1985)، من تطوير فيكتور ميلر ومارك ويغمان ، ^{[ 5 ]} على البحث في المدخلات عن أطول سلسلة نصية موجودة مسبقًا في القاموس (التطابق "الحالي")، ثم تضيف دمج التطابق السابق مع التطابق الحالي إلى القاموس. وبالتالي، تنمو مدخلات القاموس بسرعة أكبر، إلا أن هذه الطريقة أكثر تعقيدًا في التنفيذ. ويقترح ميلر وويغمان حذف المدخلات ذات التكرار المنخفض من القاموس عند امتلائه.

يُعدّ LZAP (1988)، من تطوير جيمس ستورر، ^{[ 6 ]} تعديلًا لـ LZMW. فبدلًا من إضافة سلسلة التطابق السابقة مع سلسلة التطابق الحالية إلى القاموس، يُضيف LZAP سلاسل التطابق السابقة مع كل سلسلة فرعية أولية من سلسلة التطابق الحالية ("AP" اختصارًا لـ "جميع البادئات"). على سبيل المثال، إذا كانت سلسلة التطابق السابقة هي "wiki" وسلسلة التطابق الحالية هي "pedia"، فإن مُشفّر LZAP يُضيف 5 سلاسل جديدة إلى القاموس: "wikip" و"wikipe" و"wikiped" و"wikipedi" و"wikipedia"، بينما يُضيف مُشفّر LZMW السلسلة "wikipedia" فقط. يُقلّل هذا من تعقيد LZMW، على حساب إضافة المزيد من مدخلات القاموس.

LZWL هو شكل مختلف من LZW يعتمد على المقاطع الصوتية.