الگوریتم LZW

الگوریتم LZW

 

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 که یه سری از داده ها را حذف میکرد و این باعث کاهش حجم داده ها می شد.

lwz الگوریتم
lwz الگوریتم

مثالی برای الگوریتم LZW :

داده های اولیه واژه نامه کد کاراکتر ۸ بیتی با مقادیر بین ۰ تا ۲۵۵ از کد اسکی هستند. یعنی داده های واژه نامه اولیه مون از ۰ تا ۲۵۵ هستن. البته داده ۲۵۶ برای فرمان “پاک کردن واژه نامه ” و داده ۲۵۷ برای فرمان “انتها ارسال ” رزرو شده است.

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

itty bitty bit bin

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

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

در شکل زیر نحوه رمزگذاری و رمزگشایی مثال به طور کامل نشان داده شده:

دیدگاه شما:

نوشته های مرتبط

تکنولوژی های استفاده شده در netflix | Netflix TechStack

۱۴

آذر
react, SWIFT, The best startup, اخبار, استارت اپ, بازاریابی, بازاریابی محتوا, تجارت, تحقیقات بازار, جاوا اسکریپت, طراحی اپلیکیشن

تکنولوژی های استفاده شده در netflix | Netflix TechStack

در این مقاله قصد داریم تکنولوژی های مورد استفاده در Netflix رو براتون شهر بدیم . پس ادامه مطلب رو دنبال کنید 🙂 Tech stack یا پشته فناوری به مجموعه‌ای از فناوری‌ها، زبان‌ها، ابزارها و سرویس‌هایی اشاره دارد که در […]

۲۴

اردیبهشت
هوش مصنوعی

معرفی بهترین ابزار هوش مصنوعی

ابزار هوش مصنوعی (Artificial Intelligence) به دسته‌ای از تکنولوژی‌ها گفته می‌شود که به کامپیوترها اجازه می‌دهد تا به صورت خودکار، هوشمندانه و بدون نیاز به دخالت انسان، مسائل را حل کنند و تصمیم‌هایی بگیرند. در این روش، کامپیوتر با استفاده[…]

http://platinco.ir/tag/python/

۱۴

اردیبهشت
پایتون

آموزش کتابخانه pygame

انواع روش های ساخت بازی با پایتون Python یکی از زبان‌های محبوب برای توسعه بازی است و به دلیل سادگی و قابلیت استفاده آن، توسعه دهندگان بازی‌های زیادی از آن استفاده می‌کنند. در ادامه، انواع روش‌های ساخت بازی با پایتون[…]