سه‌گانه (فاصله، طول، کاراکتر بعدی): پنجره لغزان LZ77 چگونه داده‌ها را بدون افت کیفیت فشرده می‌کند

لحظه دقیق کوچک شدن یک فایل در طول فشرده‌سازی بدون افت کیفیت، در مرز بین آنچه الگوریتم قبلاً دیده و آنچه قرار است بخواند رخ می‌دهد. در الگوریتم LZ77، این مرحله همان طولانی‌ترین تطابق پیشوند (longest prefix match) است. اگر می‌خواهید بدانید فایل‌های ZIP یا تصاویر PNG واقعاً چگونه در فضای ذخیره‌سازی صرفه‌جویی می‌کنند، این همان مکانیزمی است که باید یاد بگیرید.

همان‌طور که رمزگذار یک فایل را اسکن می‌کند، دائماً به داده‌های پیش‌رو در بافر پیش‌نگاه خود نگاه کرده و در بافر جستجوی خود - یک پنجره لغزان از متن‌های اخیراً پردازش‌شده - به سمت عقب جستجو می‌کند. وقتی یک توالی یکسان از کاراکترها را در آن پنجره گذشته پیدا می‌کند، نتیجه مشخص است: به‌جای نوشتن دوباره داده‌های خام، الگوریتم یک ارجاع ریاضی کوتاه به سمت عقب صادر می‌کند. همین تصمیم تطبیق ساده، مگابایت‌ها داده اضافی را به کسری از اندازه اصلی‌شان کاهش می‌دهد.[1]

پیش از آنکه آبراهام لمپل (Abraham Lempel) و جیکوب زیو (Jacob Ziv) مقاله تأثیرگذار خود را در سال ۱۹۷۷ منتشر کنند، فشرده‌سازی داده‌ها اغلب بر اختصاص کدهای کوتاه‌تر به نمادهای فردی پرکاربرد متکی بود؛ روشی که به کدگذاری هافمن (Huffman coding) معروف است. الگوریتم LZ77 از زاویه‌ای کاملاً متفاوت به افزونگی داده‌ها حمله کرد.

این الگوریتم تشخیص داد که زبان انسان، کدهای کامپیوتری و داده‌های ساختاریافته پر از عبارات تکراری هستند. با در نظر گرفتن داده‌های پردازش‌شده اخیر به‌عنوان یک دیکشنری پویا، LZ77 نیاز به ذخیره یک کتابچه کد مجزا را از بین برد. این الگوریتم به‌سادگی یک پنجره را به جلو می‌لغزاند و دائماً می‌پرسد که آیا بایت‌های پیش‌رو اخیراً ظاهر شده‌اند یا خیر.[1]

وقتی یک تطابق پیدا می‌شود، LZ77 آن را با استفاده از یک ساختار داده سه‌بخشی خاص به نام سه‌گانه (فاصله، طول، کاراکتر بعدی) کدگذاری می‌کند. همان‌طور که در مرجع ویکی‌پدیا اشاره شده است، این جفت معادل این دستورالعمل است که «هر یک از کاراکترهای بعدی به اندازه طول مشخص‌شده، برابر با کاراکترهایی هستند که دقیقاً به اندازه فاصله مشخص‌شده در پشت آن قرار دارند» در جریان داده‌های فشرده‌نشده.

«فاصله» (یا offset) دقیقاً دیکته می‌کند که رمزگشا باید چند بایت به عقب نگاه کند. «طول» مشخص می‌کند که چند بایت متوالی باید کپی شود. در نهایت، «کاراکتر بعدی» اولین بایت واقعی را ارائه می‌دهد که الگو را می‌شکند و تضمین می‌کند که الگوریتم می‌تواند به پردازش داده‌های جدید ادامه دهد.[1]

یک رشته ساده مانند "abcabcabcabc" را در نظر بگیرید. یک روش ذخیره‌سازی ساده برای نگهداری این متن به ۱۲ بایت نیاز دارد. با این حال، یک رمزگذار LZ77 اولین "abc" را به‌عنوان کاراکترهای واقعی پردازش کرده و سه‌گانه‌هایی با فاصله و طول صفر خروجی می‌دهد. وقتی به دومین "abc" می‌رسد، مرحله طولانی‌ترین تطابق پیشوند تشخیص می‌دهد که این توالی دقیق سه بایت قبل‌تر وجود دارد.

سپس سه‌گانه‌ای صادر می‌کند که به رمزگشا دستور می‌دهد ۳ بایت به عقب برگردد و ۳ بایت را به جلو کپی کند. این مکانیزم به الگوریتم اجازه می‌دهد تا کل توالی ۱۲ بایتی را تنها با استفاده از چند ارجاع به عقب بازسازی کند و فضای ذخیره‌سازی مورد نیاز را به‌شدت کاهش دهد.[3]

ظرافت سه‌گانه LZ77 در نامتقارن بودن آن نهفته است: کدگذاری از نظر محاسباتی سنگین است، اما رمزگشایی تقریباً در لحظه انجام می‌شود. رمزگذار باید جستجوهای جامعی انجام دهد یا زنجیره‌های هش پیچیده‌ای را حفظ کند تا طولانی‌ترین تطابق ممکن را در پنجره لغزان پیدا کند. با این حال، رمزگشا هیچ جستجویی انجام نمی‌دهد.

همان‌طور که در مشخصات DEFLATE بیان شده، الگوریتم خروج از حالت فشرده صرفاً فاصله و طول را می‌خواند، در بافر خروجی خود به عقب می‌رود و بایت‌ها را به جلو کپی می‌کند. به همین دلیل است که نصب نرم‌افزارها و بارگذاری صفحات وب می‌توانند داده‌ها را سریع‌تر از آنچه یک هارد دیسک یا اتصال شبکه می‌تواند ارائه دهد، از حالت فشرده خارج کنند.[2]

اندازه پنجره لغزان به‌طور دقیق میزان مصرف حافظه الگوریتم و نسبت فشرده‌سازی آن را دیکته می‌کند. یک پنجره بزرگ‌تر به رمزگذار اجازه می‌دهد تا برای یافتن تطابق‌ها به زمان‌های دورتر در گذشته نگاه کند و احتمال جایگزینی رشته‌های طولانی با سه‌گانه‌های کوتاه را افزایش دهد. با این حال، جستجو در یک پنجره عظیم به رم (RAM) و چرخه‌های پردازنده (CPU) بیشتری نیاز دارد.

الگوریتم DEFLATE که LZ77 را با کدگذاری هافمن ترکیب می‌کند تا فرمت‌هایی مانند gzip و PNG را قدرت بخشد، یک پنجره لغزان ۳۲ کیلوبایتی و حداکثر طول تطابق ۲۵۸ بایت را استاندارد کرد. این محدودیت خاص برای ایجاد تعادل بین کارایی فشرده‌سازی و حافظه محدود موجود در سخت‌افزارهای دهه ۱۹۹۰ انتخاب شد.[2][4]

در حالی که مشخصات اصلی سال ۱۹۷۷ یک جریان دقیق از سه‌گانه‌ها را خروجی می‌داد، پیاده‌سازی‌های مدرن این فرمت را برای صرفه‌جویی بیشتر در فضا بهینه‌سازی می‌کنند. الگوریتم‌هایی مانند LZSS یک پرچم ۱ بیتی (1-bit flag) را برای تمایز بین کاراکترهای واقعی و جفت‌های طول-فاصله معرفی کردند و در صورت عدم نیاز، «کاراکتر بعدی» اجباری را از سه‌گانه حذف کردند.

وقتی این روش با یک مرحله ثانویه از کدگذاری هافمن - که توالی‌های بیتی کوتاه‌تری را به رایج‌ترین فاصله‌ها و طول‌ها اختصاص می‌دهد - ترکیب می‌شود، جریان DEFLATE حاصل به نسبت‌های فشرده‌سازی متراکمی دست می‌یابد که اینترنت مدرن را امکان‌پذیر می‌کند.[1][2]

نزدیک به پنجاه سال پس از اختراع آن، مکانیزم پنجره لغزان همچنان پایه و اساس بلامنازع فشرده‌سازی بدون افت کیفیت همه‌منظوره است. در حالی که الگوریتم‌های جدیدتر مانند Brotli گوگل و Zstandard فیس‌بوک پنجره‌های بزرگ‌تر، مدل‌سازی زمینه پیشرفته و دیکشنری‌های نامتقارن را معرفی کرده‌اند، اما همچنان بر اصل هسته LZ77 متکی هستند. جهش بزرگ بعدی در نسبت فشرده‌سازی از کنار گذاشتن پنجره لغزان نخواهد آمد، بلکه از شتاب‌دهنده‌های سخت‌افزاری تعبیه‌شده مستقیماً در پردازنده‌ها ناشی می‌شود که می‌توانند بافرهای چند گیگابایتی را بدون متوقف کردن خط لوله پردازنده جستجو کنند.[1]