آیا فایل‌های شما نیاز قابل توجهی به صرفه‌جویی در حافظهٔ سرور دارند؟ در این مقاله ما به شما خواهیم گفت که چگونه توسط چه الگوریتم‌هایی می‌توانید اطلاعات خود را تا ۹۰٪ فشرده سازی کنید.

الگوریتم‌های فشرده سازی داده‌ها (دو نوع اصلی فشرده‌سازی داده وجود دارد)

1. فشرده‌سازی بی‌اتلاف اطلاعات (کاملاً برگشت پذیر)
2. فشرده‌سازی با اتلاف (بخش کوچکی از داده‌ها از دست می‌روند و بازسازی کامل آنها امکان پذیر نیست)

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

اجازه دهید بعضی از رایج‌ترین الگوریتم‌های فشرده‌سازی از نوع فشرده‌سازی بی‌اتلاف یا همان (lossless)  را در نظر بگیریم:

1. تکنیک کُدگذاری هافمَن (Huffman) — این امر مستلزم جایگزینی کد یکسانی برای نمادهایی با کدهای نامحدود است، بسته به تکرار وقوع یک نماد در متن هستند می‌باشد. در کد گذاری استاندارد هافمن، فرض شده‌است که هر نماد در مجموعه‌ای که کدها از آن استخراج می‌شوند، ارزشی یکسان با بقیه دارد: کد کلمه‌ای که طول آن N است ارزشی برابر N خواهد داشت، مهم نیست که چند رقم آن ۱ و چند رقم آن ۰ است. وقتی با این فرض کار می کنیم، کم کردن هزینهٔ کلی پیام، با کم کردن تعداد رقم‌های کل ۲ چیز یکسانند. کد هافمن با ارزش حرفی متفاوت به نحوی عمومیت یافته که این فرض دیگر صحیح نیست: حروف الفبای کدگذاری ممکن است طول‌های غیر همسانی داشته باشند، به خاطر خصوصیت‌های واسطهٔ انتقال. مثالی بر این ادعا، الفبای کد گذاری کد مورس است، که در آن فرستادن یک 'خط تیره' بیشتر از فرستادن یک 'نقطه' طول می‌کشد، پس ارزش خط تیره در زمان انتقال بالاتر است. درست است که هدف هنوز کم کردن میانگین طول وزنی کد است اما دیگر کم کردن تعداد نمادهای بکار برده شده در پیام، به تنهایی کافی نیست. هیچ الگوریتمی شناخته نشده است که این را به همان روش و همان کارآیی کد قراردادی هافمن انجام دهد.
2. تکنیک رمزگذاری شانون-فانو (Shannon–Fano) — این یک پیشوند است، که به عنوان یک الگوریتم کُد گذاری یکتواخت است. این تکنیک فشرده‌سازی را بر اساس احتمالات نشان می‌دهد. مانند الگوریتم هافمَن، این تکنیک بر روی افزونگی پیام است. در رمزگذاری شانون-فانو، نمادها به ترتیب احتمال از زیاد به کم مرتب شده‌اند و پس از آن به دو مجموعه که احتمال کلشان تا حد ممکن به هم نزدیک است تقسیم می‌شوند. سپس اولین رقم رمز همهٔ نمادها به آن‌ها اختصاص داده می‌شود؛ نمادها در مجموعهٔ اول "۰" و در مجموعهٔ دوم "۱" می‌گیرند. تا زمانی که مجموعه‌ای با بیش از یک عضو باقی بماند، همین فرایند برای تعیین ارقام متوالی رمزهایشان، روی آن‌ها تکرار می‌شود. وقتی یک مجموعه به یک نماد کاهش پیدا کند بدان معناست که رمز آن نماد کامل است و پیشوند هیچ رمزِ نماد دیگری را تشکیل نمی‌دهد. این الگوریتم کدگذاری‌های با طول متغیر نسبتاً کارامدی تولید می‌کند.
3. تکنیک طول اجرا (Run-length) — این تکنیک به جای مجموعه‌ای از نماد‌های مکرر با کد نماد و تعداد تکرار اشاره داد. یک شکل ساده از فشرده‌سازی داده‌ها است که در آن داده‌های یکسان پشت سر هم به صورت مقادیر تکی و تعداد تکرارشان ذخیره می‌شوند. اگرچه آسان است و می‌توان به راحتی آن را درک کرد اما هنوز کارآیی چندانی ندارد.
4. تکنیک ال زد دابلیو (Lempel–Ziv–Welch) — الگوریتم‌های فشرده‌سازی این گروه (LZ78، LZ77، و LZW) در ایدهٔ جستجو برای متن مشترک هستند. الگوریتم کاراکترها را متراکم کرده و در واژه نامه به جای کاراکتر، رشته‌های متراکم شده را قرار می‌دهد تا اینکه به رشته‌ای برسد که در واژه نامه قرار دارد.

الگوریتم ساخت کدهای نابرابر که توسط هافمَن پیشنهاد شده است یکی از مهم‌ترین دستاوردهای تئوری اطلاعات از دیدگاه‌های نظری و کاربردی است. بهتر است کدهای باینری C = {c1, ..., cm} با با طول های {l1,.. ,IM} برای پیام‌های مورد نظر بهینه باشد.

1. در صورتی که شرط به این گونه باشد pi < pj, then li > lj
2. طول مقدار در قالب lM = maxm1m از نظر کُد‌نویسی بهینه شده است
3. دو کُد lM = maxmlm که طول آن است در سمبُل آخر متفاوت خواهد بود.
4. اگر کد C دارای شرایط مطلوبی باشد، آنگاه C به عنوان کُد X مطلوب خواهد بود.

• ورودی: اندازهٔ الفبای M
• خروجی: درخت دودوییِ کد هافمَن
• مقداردهی اولیه: تعداد گِره‌ (نود‌های) پردازش شده  M0=M می‌باشد.
• با اجرای شرط While M0>1 do مراحل بعدی به صورت زیر باید انجام شوند:
  1. یافتن دو گِره (نود) با کمترین احتمال در صف از نودهای پردازش شده
  2. حذف نودها را از صف پردازش
  3. تولید یک نود جدید با دو گرده انتخاب شده به عنوان فرزند. به این ترتیب که، وزن نودها برابر است با مجموع نودهای فرزند.
  4. افزودن گِره (نود) جدید به صف. لینک کردن نودهای جدید با لبه‌های نودهای حذف شده
  5. М0 <– М <– 1.
  6. اگر بیشتر از یک نود در صف وجود داشته باشد، مراحل ۲  تا ۵ را تکرار کنید.