موضوع مقاله: ال زد دابلیو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ال زد دابلیو | مقدمه: الگوریتم‌های فشرده سازی زیادی وجود دارد که از یک واژه نامه استفاده می‌کنند، این واژه نامه برای رمزگذار و رمزگشا شناخته شده‌است و در طی عمل رمزگذاری و رمزگشایی تولید می‌شود. | ## بخش 1: ال زد دابلیو | این کدگذاری رخدادهای تکراری یک رشته را با ارجاعی به نزدیکترین رخداد جایگزین می‌کند، واژه نامه این الگوریتم فقط شامل مجموعه‌ای از این رخدادهای تکراری است. LZW الگوریتم مورد استفاده در بسیاری از نرم‌افزارهای عمومی فشرده‌سازی اطلاعات مانند pkzip و gzip می‌باشد این الگوریتم بدین منظور طراحی شده که تعداد بیت‌هایی که به دیسک فرستاده می‌شود یا از دیسک خوانده می‌شود کمتر کند. همچنین از این الگوریتم در بسیاری از زمینه‌ها مانند برنامه‌های فشرده‌سازی GIF برای تصاویر استفاده می‌شود که به‌طور میانگین حجم تصویر را به یک سوم کاهش می‌دهد. الگوریتم LZW یک الگوریتم برگشت پذیر(reversible) است، بدین معنی که الگوریتم هیچ اطلاعاتی را از دست نمی‌دهد و رمزگشا قادر خواهد بود داده اولیه را عیناً بازسازی نماید. قدرت فشرده‌سازی این الگوریتم از خیلی الگوریتم‌های فشرده‌سازی مشهور همچون الگوریتم کدگذاری هافمن بیشتر است. کاراکترهایی که در جمله فوق وجود دارند به همراه کد آن‌ها در جدول شماره ۱ آمده‌است. | ## بخش 2: ال زد دابلیو | در طی عمل رمزگذاری و رمزگشایی فیلدهای جدید واژه نامه ساخته می‌شوند که از همه عبارات موجود در متن که در واژه نامه نیستند استفاده می‌کند. الگوریتم رمزگذاری الگوریتم کاراکترها را متراکم کرده و در واژه نامه به جای کاراکتر، رشته‌های متراکم شده را قرار می‌دهد تا اینکه به رشته‌ای برسد که در واژه نامه قرار دارد. هر رشته‌ای که به واژه نامه فرستاده می‌شود، آخرین کاراکتر آن به عنوان اولین کاراکتر رشته بعدی می‌باشد. وقتی که این الگوریتم روی رشته‌ای که مثال زدیم اجرا می‌شود، اولین کاراکتر “i” است و رشته فقط از کاراکترهایی تشکیل شده‌است که هم‌اکنون در واژه نامه هستند، بنابراین کاراکتر بعدی به انتهای “i” اضافه می‌شود و رشته متراکم “it” را تشکیل می‌دهد که این رشته در واژه نامه نمی‌باشد، پس رشته “it” به واژه نامه اضافه می‌شود و اولین مقدار (شماره کد) در دسترس که ۲۵۸ است را می‌گیرد. آخرین کاراکتر رشته متراکم “t” می‌باشد که درواژه نامه هست، کاراکتر بعدی(“t”) به انتهای “t” اضافه می‌شود و رشته متراکم “tt” را تشکیل می‌دهد که این رشته نیز درواژه نامه نیست، پس به واژه نامه افزوده می‌شود. برای مدتی در شروع کار رشته‌های اضافه شده به واژه نامه ۲ کاراکتری هستند و با هر کاراکتر جدید که برخورد می‌کنیم یک رشته به واژه نامه فرستاده می‌شود. | ## بخش 3: ال زد دابلیو | اولین دفعه که یکی از رشته‌های دو کاراکتری تکرار شود، یک رشته ۳ کاراکتری جدید به واژه نامه فرستاده می‌شود. در این مثال این مورد با رشته “itt” اتفاق می‌افتد.(البته در اینجا مثال را طوری طراحی کرده‌ایم که این اتفاق نسبت به حالات عادی زودتر رخ دهد.) در ادامه در این مثال یک رشته ۴ کاراکتری نیز به واژه نامه فرستاده می‌شود. الگوریتم رمز گشایی برا ی هر کد تبدیل یک محتوای جدید در واژه نامه تعریف می‌کنیم، برای رمزگشایی از هر قلم واژه نامه کاراکتر آخر را حذف کرده و در خروجی می‌نویسیم(آخرین کاراکتر از آخرین محتوای واژه نامه نیز به خروجی فرستاده می‌شود.) در شکل ۱ نحوه رمزگذاری و رمزگشایی مثال ۱ به‌طور کامل نشان داده شده. در پاسخ به این سؤال همانطور که در شکل ۱ مشاهده می‌کنیم ما ۱۸ کاراکتر ۸ بیتی (یعنی ۱۴۴ بیت) را به ۱۴ کاراکتر ۹ بیتی (یعنی ۱۲۶ بیت) تبدیل کرده‌ایم، یعنی حتی برای این مثال خیلی کوچک ۱۲٫۵ درصد صرفه جویی در حافظه داشته‌ایم. | ## جمع‌بندی | درعمل اغلب فایل‌های متنی بزرگ با ضریب ۲ و تصاویر با ضریبی بیشتر از این فشرده می‌شوند.