بیایید نگاهی به الگوریتم فشرده سازی پشت فشرده سازی یونیکس و بیشترین فشرده سازی .gif بیندازیم.
Lempel Ziv Welch [LZW] الگوریتم یک الگوریتم فشرده سازی بدون ضرر حریص است که با جایگزینی الگوهای تکراری با کدهای کوتاه تر به منظور صرفه جویی در فضا کار می کند.
Lossless نوعی فشرده سازی است که در آن هیچ داده ای از بین نمی رود.
ما الگوریتم را مرور می کنیم و نگاهی به پیاده سازی در پایتون می اندازیم.
برای سادگی ، ما بحث را به رمزگذاری کاراکترهای ASCII محدود خواهیم کرد.
رمزگذاری
اساساً ، اگر در هنگام پردازش یک پرونده متنی ، قادر به شناسایی عبارات تکراری هستیم ، می توانیم این عبارات را با کدی جایگزین کنیم که کوتاهتر از متن اصلی باشد. انجام این کار در کل سند به ما فشرده سازی می دهد که پس از آن هستیم.
LZW به دیکشنری متکی است که عبارتی را به یک کد منحصر به فرد ترسیم می کند. 256 ورودی اول در فرهنگ لغت ، تنها کاراکترهای ASCII هستند که به کد عددی آنها ترسیم شده اند.
به عنوان مثال ، در ابتدا ، فرهنگ لغت ممکن است شبیه به این باشد:
{
"A": "65",
"B": "66",
....
"a": "97",
"b": "98"
}اکنون ، ما از طریق بقیه متن تکرار خواهیم کرد – شخصیت به شخصیت – ایجاد یک عبارت / دنباله شخصیت. اگر درج کاراکتر جدید عبارتی ایجاد کند که در حال حاضر در فرهنگ لغت ما وجود ندارد ، ما این را نادیده می گیریم …