Lempel–Ziv–Welch (LZW) الگوریتم‌های فشرده سازی زیادی وجود دارد که از یک واژه نامه استفاده می‌کنند، این واژه نامه برای رمزگذار و رمزگشا شناخته شده‌است و در طی عمل رمزگذاری و رمزگشایی تولید می‌شود. بیشتر این الگوریتم‌ها روی الگوریتم LZ بنا شده‌است. الگوریتم LZ توسط Abraham Lampel و Jacob Ziv در سال ۱۹۶۷ ارائه شد که با نام رمزگذار Lampel-Ziv شناخته شده‌است. این کدگذاری رخدادهای تکراری یک رشته را با ارجاعی به نزدیکترین رخداد جایگزین می‌کند، واژه نامه این الگوریتم فقط شامل مجموعه‌ای از این رخدادهای تکراری است. یکی از مواردی در آن از الگوریتم LZ استفاده زیادی شده‌است، الگوریتم LZW می‌باشد که توسط Terry A.Welch در سال ۱۹۸۴ ارائه شد. LZW الگوریتم مورد استفاده در بسیاری از نرم‌افزارهای عمومی فشرده سازی اطلاعات مانند pkzip و gzip می‌باشد.
الگوریتم LZW بدین منظور طراحی شده که تعداد بیت‌هایی که به دیسک فرستاده می‌شود یا از دیسک خوانده می‌شود کمتر کند. همچنین از این الگوریتم در بسیاری از زمینه‌ها مانند برنامه‌های فشرده سازی GIF برای تصاویر استفاده می‌شود که به طور میانگین حجم تصویر را به یک سوم کاهش می‌دهد. الگوریتم LZW یک الگوریتم برگشت پذیر(reversible) است، بدین معنی که الگوریتم هیچ اطلاعاتی را از دست نمی‌دهد و رمزگشا قادر خواهد بود داده اولیه را عیناً بازسازی نماید. قدرت فشرده سازی این الگوریتم از خیلی الگوریتم‌های فشرده سازی مشهور همچون الگوریتم کدگذاری هافمن بیشتر است.یه روش کدگذاری منبع ، هافمن بود که برای منابعد بدون حافظه گسسته بود که الگوریتم اصلاح شده اش تو فکس استفاده می شد. ولی در عمل منابع بدون حافظه نداریم. یعنی حروف بعدی به حروف قبلی وابسته هستند. الگوریتم LZW برای کدگذاری منابع حافظه دار استفاده می شه . این الگوریتم از یک واژه نامه استفاده میکنه که برای رمزگذاری و رمزگشا شناخته شده است. این واژه نامه در حین رمزگذاری تولید میشه.
نکته جالب در مورد این الگوریتم اینه که برگشت پذیره یعنی هیچی از اطلاعاتو از بین نمیبرد مثل الگوریتم PCA که یه سری از داده ها را حذف میکرد و این باعث کاهش حجم داده ها می شد.
مثالی برای الگوریتم LZW :
داده های اولیه واژه نامه کد کاراکتر ۸ بیتی با مقادیر بین ۰ تا ۲۵۵ از کد اسکی هستند. یعنی داده های واژه نامه اولیه مون از ۰ تا ۲۵۵ هستن. البته داده ۲۵۶ برای فرمان “پاک کردن واژه نامه ” و داده ۲۵۷ برای فرمان “انتها ارسال ” رزرو شده است.
به عنوان مثال جمله زیر را در نظر بگیرید:
itty bitty bit bin
اولین محتوای واژه نامه کدهای کاراکتری ۸ بیتی با مقادیر ۰ تا ۲۵۵ هستند که همان مقادیر کد ASCII می‌باشند. کاراکترهایی که در جمله فوق وجود دارند به همراه کد آن‌ها در جدول شماره ۱ آمده‌است.
در رمزگذاری ، الگوریتم کاراکترها را متراکم کرده و در واژه نامه به جای کاراکتر، رشته‌های متراکم شده را قرار می‌دهد تا اینکه به رشته‌ای برسد که در واژه نامه قرار دارد. هر رشته‌ای که به واژه نامه فرستاده می‌شود، آخرین کاراکتر آن به عنوان اولین کاراکتر رشته بعدی می‌باشد. وقتی که این الگوریتم روی رشته‌ای که مثال زدیم اجرا می‌شود، اولین کاراکتر “i” است و رشته فقط از کاراکترهایی تشکیل شده‌است که هم اکنون در واژه نامه هستند، بنابراین کاراکتر بعدی به انتهای “i” اضافه می‌شود و رشته متراکم “it” را تشکیل می‌دهد که این رشته در واژه نامه نمی‌باشد، پس رشته “it” به واژه نامه اضافه می‌شود واولین مقدار (شماره کد) در دسترس که ۲۵۸ است را می‌گیرد. آخرین کاراکتررشته متراکم “t” می‌باشد که درواژه نامه هست، کاراکتر بعدی(“t”) به انتهای “t” اضافه می‌شود و رشته متراکم “tt” را تشکیل می‌دهد که این رشته نیز درواژه نامه نیست، پس به واژه نامه افزوده می‌شود. فرایند به همین ترتیب تکرار می‌شود. برای مدتی در شروع کار رشته‌های اضافه شده به واژه نامه ۲ کاراکتری هستند و با هر کاراکتر جدید که برخورد می‌کنیم یک رشته به واژه نامه فرستاده می‌شود. اولین دفعه که یکی از رشته‌های دوکاراکتری تکرار شود، یک رشته ۳ کاراکتری جدید به واژه نامه فرستاده می‌شود. در این مثال این مورد با رشته “itt” اتفاق می‌افتد.(البته در اینجا مثال را طوری طراحی کرده‌ایم که این اتفاق نسبت به حالات عادی زودتر رخ دهد.) در ادامه در این مثال یک رشته ۴ کاراکتری نیز به واژه نامه فرستاده می‌شود. برای رمزگشایی از هر قلم واژه نامه کاراکتر آخر راحذف کرده و در خروجی می‌نویسیم(آخرین کاراکتر از آخرین محتوای واژه نامه نیز به خروجی فرستاده می‌شود.)
در شکل زیر نحوه رمزگذاری و رمزگشایی مثال به طور کامل نشان داده شده:
