فایل‌های فشرده

وقتی یک فایل فشرده شده را دانلود می‌کنید، رایانه با استفاده از یک نرم افزار مانند WinZip فایل را به حالت اولیه باز می‌گرداند. اگر همه چیز درست پیش برود، فایل بسط داده شده دقیقا همان فایل اصلی قبل از فشرده شدن است.

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

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

بیشتر برنامه‌های فشرده سازی موجود از نمونه‌ای از الگوریتم تطبیقی LZ که بر اساس یک جدول داده کار می‌کند، استفاده می‌کنند. LZ مخفف اسم طراحان این الگوریتم یعنی Lempel و Ziv است.

یکی از مهم‌ترین و تأثیرگذارترین مراحل الگوریتم، تولید جدول داده است و در برنامه‌های مختلف روش‌های آن متفاوت است. اما یک نمونه ساده آن می‌تواند یک فهرست شماره‌گذاری شده باشد. برای مثال فرض می‌کنیم در فایل متن که یک جمله است، فهرست کلمات به صورت زیر است:

1. ask 2. what 3. your 4. country 5. can 6. do 7. for 8. you

حالا به جای استفاده از کلمات، از شماره آنها استفاده می‌کنیم:

1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4

اگر شما این جدول و جمله شماره‌بندی شده را در اختیار داشته باشید، براحتی می‌توانید این جمله را به حالت اولیه بازگردانید. این همان کاری است که رایانه هنگام بسط دادن یک فایل فشرده شده انجام می‌دهد. ممکن است با فایل‌های فشرده که خود به خود باز می‌شوند نیز برخورد کرده باشید. برای تولید چنین فایلی، برنامه نویس یک برنامه بسط‌دهنده ساده در فایل فشرده شده قرار می‌دهد و این برنامه به صورت خودکار فایل اصلی را تولید می‌کند. اکنون ببینیم این فشرده سازی چقدر حجم متن را کاهش می‌دهد. عبارت:

1 not 12856734-- -- 2345678 4

کوتاه تر از

Ask not what your country can do for you; ask what you can do for your country;

است، اما به خاطر داشته باشید که شما فهرست و جدول داده‌ها را نیز باید به فایل فشرده شده ضمیمه کنید.

در فشرده سازی واقعی یک فایل، با در نظر گرفتن همه جزئیات، کار پیچیده می‌شود. اما برای درک بیشتر این مثال، فرض می‌کنیم هر کاراکتر یک واحد حافظه را اشغال می‌کند. در این مثال عبارت ما 79 واحد است و عبارت فشرده شده 37 واحد و فهرست کلمات 37 واحد. پس حجم فایل فشرده شده ما 74 واحد حافظه می‌شود. بنابراین در فشرده‌سازی حجم چندانی از فایل اصلی کم نکردیم.

اما توجه داشته باشید که ما در این فرآیند فقط یک جمله را فشرده کردیم. می‌توانید تصور کنید اگر همین کار را برای یک مقاله یا کتاب انجام می‌دادیم، تعداد کلمات تکرار شده بسیار بیشتر از این می‌شد و در نتیجه نسبت فشردگی فایل افزایش می‌یافت.

در مثال قبل، ما کلمات تکراری را در یک جدول قرار دادیم. برای ما این کار واضح‌ترین روش برای نوشتن یک جدول است. اما یک برنامه فشرده‌سازی نگاهی کاملا متفاوت به این موضوع دارد. در الگوریتم برنامه مفهوم کلمه تعریف نشده، در عوض برنامه به دنبال الگوهای مشابه می‌گردد و برای این که حجم فایل را تا جای ممکن کاهش دهد، با دقت الگوهایی را که باید در جدول ذخیره کند، انتخاب می‌کند. اگر با این دیدگاه عبارت مثال را بررسی کنیم، جدول کاملا متفاوتی به دست خواهیم آورد.

در عبارت قبل، اولین الگوی تکراری در قسمت ask not what your، دیده می‌شود که حرف t است که بعد از آن یک space (در کلمه not و what) است. اگر این الگو وارد جدول می‌شد، هر جا که این الگو مشاهده می‌شد عدد یک نوشته می‌شد. اما در این عبارت کوتاه این الگو به اندازه کافی تکرار نمی‌شود که ارزش نوشته شدن در جدول را داشته باشد، پس برنامه خود به خود الگوی باارزش‌تری را جایگزین آن می‌کند. الگوی بعدی که برنامه مشاهده می‌کند، دو حرف ou در کلمات you و country است. اگر این متن کمی طولانی‌تر بود، نوشتن این دو حرف در جدول کمک زیادی به فشرده‌سازی می‌کرد؛ چرا که این دو حرف در کلمات زیادی در زبان انگلیسی تکرار می‌شوند. اما وقتی برنامه این جمله را بیشتر مورد بررسی قرار می‌دهد ، انتخاب بهتری برای وارد کردن به جدول پیدا می‌کند. نه تنها دو حرف ou تکرار شده‌اند، بلکه دو کلمه your و country پشت سر هم تکرار شده‌اند و الگوی جدید your country به جای ou وارد جدول می‌شود.

عبارت can do for هم تکرار شده است، که یک بار بعد از آن کلمه your آمده و یک بار کلمه you که الگوی can do for you را برای ما می‌سازد. این به ما 15 کاراکتر می‌دهد که می‌توانیم آن را با یک عدد جایگزین کنیم، در حالی که your country فقط 13 کاراکتر به ما می‌دهد. بنابراین برنامه به جای your country فقط r country را می‌نویسد و بعد در یک خط جدا در جدول can do for you را اضافه می‌کند. برنامه به همین ترتیب پیش می‌رود و همه داده‌های تکراری را در فایل شناسایی و محاسبه می‌کند که چه الگوهایی را باید در جدول بنویسد. این قابلیت بازنویسی جدول، به همان قسمت تطبیقی الگوریتم LZ اشاره دارد. روش‌هایی که برنامه برای انجام این کار دارند بسیار پیچیده است و در این مقاله نمی‌گنجد.

در بیشتر زبان‌ها، حرف‌ها و کلمات در الگو‌های مشابه تکرار می‌شوند. به همین دلیل فایل‌های متنی بخوبی فشرده می‌شوند(اکثر آنها بیش از 50 درصد فشرده می‌شوند.) کدهای برنامه‌نویسی نیز به دلیل محدودیت فرمان‌ها تکرار زیادی در آنها رخ می‌دهد که الگوهای مشابهی دارند. فایل‌هایی که داده‌های تکراری ندارند، مانند فایل‌های گرافیکی و صوتی، با این روش بخوبی فشرده نمی‌شوند. برای فشرده‌کردن این فایل‌ها معمولا از روش‌هایی استفاده می‌کنند که کیفیت را کاهش می‌دهد و فایل بسط داده شده با فایل اصلی فرق دارد؛ اما فرق این دو فایل ناچیز است و معمولا به چشم نمی‌آید.

محمدعلی زارعی‌فر

منبع: moc.computer.howstuffworks