فشرده‌سازی داده‌ها

در پردازش سیگنال، فشرده‌سازی داده‌ها (به انگلیسی: Data compression) یا کُدگذاری منبع (به انگلیسی: Source Coding)، به فشرده‌سازیِ اطلاعات یک منبعِ اطلاعات می‌پردازد (با رمزگذاری اشتباه نشود). منابع اطلاعاتی طبیعی، مانند گفتار یا نوشتار، دارای افزونگی (Redundancy) یا بخش زائد هستند؛ برای مثال در جمله «من به خانه‌ام برگشتم» «من» و «ام» را می‌توان حذف کرد و چنین نوشت «به خانه برگشتم»، بی‌اینکه از مفهوم جمله کاسته شود. این را می‌توان معادل فشرده‌سازی اطلاعات یک منبع اطلاعات دانست؛ بنابراین، فشرده‌سازی اطلاعات، کاستن از حجم آن است، طوری‌که محتوای آن دچار تغییر نامناسبی نشود.

در علوم کامپیوتر و نظریه اطلاعات، فشرده‌سازی داده‌ها، در واقع کدکردن اطلاعات با استفاده از تعداد بیت‌هایی کمتر از همان اطلاعاتِ کدنَشده، و با به‌کارگرفتن روش‌های کُدکردن است.

دریافت اطلاعات فشرده‌، تنها زمانی ممکن است که هم فرستنده و هم گیرندهٔ اطلاعات، روش کدکردن را بدانند. برای نمونه، این نوشته تنها برای خواننده فارسی‌زبان مفهوم است. به همین ترتیب، دادهٔ فشرده‌ تنها زمانی قابل استفاده است که گیرنده روش کدگشایی (به انگلیسی: Decoding) آن را بداند.

اهمیت فشرده‌سازی

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

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

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

فشرده‌سازی بی‌اتلاف (بهینه) و بااتلاف

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

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

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

روش‌های فشرده‌سازی بهینه برگشت‌پذیرند، طوری‌که اطلاعات اولیه، دقیق بازیابی می‌شوند. اما روش‌های بااتلاف، از دست رفتن بخشی از اطلاعات را برای دست‌یابی به فشردگی بیشتر می‌پذیرند.

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

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

مثالی از یک الگوریتم بی اتلاف در برابر یک الگوریتم بهینه، فشرده‌سازی رشتهٔ زیر است:

۲۵٫۸۸۸۸۸۸۸۸۸

این رشته می‌تواند به روش بهینه به‌ این شکل فشرده شود:

۸[۹]۲۵

که خوانده می‌شود "بیست و پنج ممیز ۹ تا هشت"، و رشتهٔ اصلی دقیقاً بازسازی می‌شود و تنها کوتاه‌تر نوشته می‌شود. در عوض در روش بااتلاف از

۲۶

استفاده می‌شود که مقدار دقیق عدد در ازای طول کمتر از دست خواهد رفت.

الگوریتم‌ها و برنامه‌های اجرایی نمونه

نمونه بالا، نمونه ساده‌ای از کدگذاری الگو-طول (کدبندی طول اجرا، که در آن "الگو" عبارت است از رشته‌ای از عناصر که پیاپی تکرار شده‌است و "طول"، تعداد تکرار آن است) است. این روش اغلب برای بهینه‌سازی فضای دیسک در کامپیوترها یا استفادهٔ بهتر از پهنای باند در یک شبکهٔ کامپیوتری به کار می‌رود.

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

نظریه

سابقهٔ نظری فشرده‌سازی برای فشرده‌سازی‌های بهینه توسط نظریهٔ اطلاعات (که رابطه نزدیکی با نظریهٔ اطلاعات الگوریتمی دارد) و برای فشرده‌سازی‌های بااتلاف توسط نظریهٔ نرخ-اِعوِجاج (Rate–distortion theory) ارائه شده‌اند. این شاخه‌های مطالعاتی در اصل توسط کلود شانون (Claude Shannon)، که مقالاتی بنیادی در این زمینه در اواخر دهه‌ای ۱۹۴۰ و اوایل دههٔ ۱۹۵۰ به چاپ رسانده است. ایدهٔ فشرده‌سازی رابطهٔ عمیقی با آمار استنباطی دارد.

فرمت‌های فشرده‌سازی

• ZIP و RAR
• EXE
• CAB

آنتروپی (Entropy)

دو جملهٔ زیر را در نظر بگیرید؛

1. فردا خورشید از شرق طلوع می‌کند.
2. فردا باران می‌بارد.

اگرچه جملهٔ دوم کوتاه‌تر از اولی‌ست، اطلاعات بیشتری نسبت به آن دارد (محتوای اطلاعاتی بیشتری دارد)، و به این ترتیب جمله ارزشمندتری است. در واقع جمله اول از نظر اطلاعاتی هیچ ارزشی ندارد، زیرا به چیزی بدیهی اشاره می‌کند. از دیدگاه نظریۀ اطلاعات (Information Theory)، آنتروپیِ جمله دوم از جمله اول بیشتر است. در واقع آنتروپی جمله اول، صفر است، زیرا احتمال طلوع خورشید از شرق، برابر یک است.

جستارهای وابسته

• آنتروپی اطلاعات
• ویژه‌مقدار
• فشرده‌سازی تصاویر
• فشرده‌سازی متون

منابع

• Data Compression - Wikipedia
• Data Compression - Systematisation by T.Strutz

پیوند به بیرون

• [۱] * کتاب مناسب[Thomas M. Cover، Joy A. Thomas. Elements of information theory New York: Wiley، ۱۹۹۱. ISBN 0-471-06259-6 ]
• Rationale for a Large Text Compression Benchmark