ال زد دابلیو

الگوریتم‌های فشرده سازی زیادی وجود دارد که از یک واژه نامه استفاده می‌کنند، این واژه نامه برای رمزگذار و رمزگشا شناخته شده‌است و در طی عمل رمزگذاری و رمزگشایی تولید می‌شود. بیشتر این الگوریتم‌ها روی الگوریتم LZ بنا شده‌است. الگوریتم LZ توسط Abraham Lampel و Jacob Ziv در سال ۱۹۶۷ ارائه شد که با نام رمزگذار Lampel-Ziv شناخته شده‌است. این کدگذاری رخدادهای تکراری یک رشته را با ارجاعی به نزدیکترین رخداد جایگزین می‌کند، واژه نامه این الگوریتم فقط شامل مجموعه‌ای از این رخدادهای تکراری است. یکی از مواردی در آن از الگوریتم LZ استفاده زیادی شده‌است، الگوریتم LZW می‌باشد که توسط Terry A.Welch در سال ۱۹۸۴ ارائه شد. LZW الگوریتم مورد استفاده در بسیاری از نرم‌افزارهای عمومی فشرده‌سازی اطلاعات مانند pkzip و gzip می‌باشد این الگوریتم بدین منظور طراحی شده که تعداد بیت‌هایی که به دیسک فرستاده می‌شود یا از دیسک خوانده می‌شود کمتر کند. همچنین از این الگوریتم در بسیاری از زمینه‌ها مانند برنامه‌های فشرده‌سازی GIF برای تصاویر استفاده می‌شود که به‌طور میانگین حجم تصویر را به یک سوم کاهش می‌دهد. الگوریتم LZW یک الگوریتم برگشت پذیر(reversible) است، بدین معنی که الگوریتم هیچ اطلاعاتی را از دست نمی‌دهد و رمزگشا قادر خواهد بود داده اولیه را عیناً بازسازی نماید. قدرت فشرده‌سازی این الگوریتم از خیلی الگوریتم‌های فشرده‌سازی مشهور همچون الگوریتم کدگذاری هافمن بیشتر است.

رمزگذاری و رمزگشایی

به عنوان مثال جمله زیر را در نظر بگیرید:

itty bitty bit bin

اولین محتوای واژه نامه کدهای کاراکتری ۸ بیتی با مقادیر ۰ تا ۲۵۵ هستند که همان مقادیر کد ASCII می‌باشند. کاراکترهایی که در جمله فوق وجود دارند به همراه کد آن‌ها در جدول شماره ۱ آمده‌است.

کد	کاراکتر
۳۲	space
۹۸	b
۱۰۵	i
۱۱۰	n
۱۱۶	t
۱۲۱	y

جدول ۱: واژه نامه LZW مثال ۱

کد ۲۵۶ در واژه نامه برای دستور “Clear Dictionary” و کد ۲۵۷ برای “End of transmission”در نظر گرفته می‌شود که ثابت هستند و رشته های جدید فشرده شده از کد 258 شروع به قرار گیری در واژه نامه میکنند. در طی عمل رمزگذاری و رمزگشایی فیلدهای جدید واژه نامه ساخته می‌شوند که از همه عبارات موجود در متن که در واژه نامه نیستند استفاده می‌کند.

الگوریتم رمزگذاری

الگوریتم کاراکترها را متراکم کرده و در واژه نامه به جای کاراکتر، رشته‌های متراکم شده را قرار می‌دهد تا اینکه به رشته‌ای برسد که در واژه نامه قرار دارد. هر رشته‌ای که به واژه نامه فرستاده می‌شود، آخرین کاراکتر آن به عنوان اولین کاراکتر رشته بعدی می‌باشد. وقتی که این الگوریتم روی رشته‌ای که مثال زدیم اجرا می‌شود، اولین کاراکتر “i” است و رشته فقط از کاراکترهایی تشکیل شده‌است که هم‌اکنون در واژه نامه هستند، بنابراین کاراکتر بعدی به انتهای “i” اضافه می‌شود و رشته متراکم “it” را تشکیل می‌دهد که این رشته در واژه نامه نمی‌باشد، پس رشته “it” به واژه نامه اضافه می‌شود و اولین مقدار (شماره کد) در دسترس که ۲۵۸ است را می‌گیرد. آخرین کاراکتر رشته متراکم “t” می‌باشد که درواژه نامه هست، کاراکتر بعدی(“t”) به انتهای “t” اضافه می‌شود و رشته متراکم “tt” را تشکیل می‌دهد که این رشته نیز درواژه نامه نیست، پس به واژه نامه افزوده می‌شود. فرایند به همین ترتیب تکرار می‌شود. برای مدتی در شروع کار رشته‌های اضافه شده به واژه نامه ۲ کاراکتری هستند و با هر کاراکتر جدید که برخورد می‌کنیم یک رشته به واژه نامه فرستاده می‌شود. اولین دفعه که یکی از رشته‌های دو کاراکتری تکرار شود، یک رشته ۳ کاراکتری جدید به واژه نامه فرستاده می‌شود. در این مثال این مورد با رشته “itt” اتفاق می‌افتد.(البته در اینجا مثال را طوری طراحی کرده‌ایم که این اتفاق نسبت به حالات عادی زودتر رخ دهد.) در ادامه در این مثال یک رشته ۴ کاراکتری نیز به واژه نامه فرستاده می‌شود.

الگوریتم رمز گشایی

برا ی هر کد تبدیل یک محتوای جدید در واژه نامه تعریف می‌کنیم، برای رمزگشایی از هر قلم واژه نامه کاراکتر آخر را حذف کرده و در خروجی می‌نویسیم(آخرین کاراکتر از آخرین محتوای واژه نامه نیز به خروجی فرستاده می‌شود.) در شکل ۱ نحوه رمزگذاری و رمزگشایی مثال ۱ به‌طور کامل نشان داده شده. آیا با اعمال انجام شده تعداد بیت‌ها کاهش یافته‌است؟ در پاسخ به این سؤال همانطور که در شکل ۱ مشاهده می‌کنیم ما ۱۸ کاراکتر ۸ بیتی (یعنی ۱۴۴ بیت) را به ۱۴ کاراکتر ۹ بیتی (یعنی ۱۲۶ بیت) تبدیل کرده‌ایم، یعنی حتی برای این مثال خیلی کوچک ۱۲٫۵ درصد صرفه جویی در حافظه داشته‌ایم. برای رشته‌های زیر ۵۰۰ بایت کاهش بیشتر از این مقدار نداریم. درعمل اغلب فایل‌های متنی بزرگ با ضریب ۲ و تصاویر با ضریبی بیشتر از این فشرده می‌شوند.

منابع

• یوسفی، جواد (۱۳۸۹)، الگوریتم فشرده‌سازی LZW فرمت (PDF)