فایل های فشرده شده چگونه کار می کنند ؟

اگر شما دانلود می کنید برنامه ها و فایل های زیادی رو از اینترنت, شاید شما برخورد کرده باشید با فایل ها ی زیپ شده . این سیستم فشرده سازی هست یک ابتکار سودمند بویژه برای کاربران وب , زیرا به شما اجازه می دهد کاهش دهید تعداد بیت ها و بایت ها در یک فایل را پس می تونه با سرعت بیشتری انتقال پیدا کنه با ارتباطات اینترنت بسیار اهسته , یا کاهش می ده فضای اشغال شده برای اون رو بر روی دیسک سخت . شما برنامه ایی را دانلود می کنید و شما استفاده می کنید از یک برنامه در کامپیوترتان مانند :WinZip یا Stuffitبرای برگردانندن فایل به اندازه ی اصلی .اگر همه چیز به درستی انجام شود , فایل باز شده هست همانند فایل اصلی پیش از فشرده شدن .

در اولین مشاهده , به نظر می رسه این بسیار مرموز باشه . چگونه شما می تونید کاهش بدید تعدادی از بیت ها و بایت ها و سپس اضافه کنید این بیت و بیت ها رو پس از خارج کردن از حالت فشرده شده ؟

در این مقاله , ما بررسی می کنیم نمونه ی ساده ایی از فشرده سازی یک فایل بسیار کوچک را .

اکثر نوع های فایل های کامپیوتری تا انداز ه ایی دارای افزونگی هستند – انها اطلاعات فهرست شده یکسانی دارند که بارها وبارها تکرار می شوند . نمونه برنامه های فشرده سازی این افزونگی ها را از بین می برند. در عوض فهرست نویسی یک قطعه از اطلاعات بارها و بارها , فهرست های یک فایل فشرده شده که این اطلاعات یکبار نوشته و سپس ارجاع داده می شه به اونها هر وقتی که این ظاهر بشه در برنامه اصلی .

به عنوان یک نمونه , اجازه بدید در نظر بگیریم نوعی از اطلاعات که ما با انها اشنا هستیم : کلمات

در 1961 , F.Kennedy’s در سخنرانی افتتاحیه خطاب قرار داد حاضران را , او ایراد کرد این جمله ی معروف را :

“Ask not what your country can do for you — ask what you can do for your country.”

نقل قول فوق 17کاراکتر دارد ساخته شده از 61 کاراکتر و 16 فضای خالی و یک خط تیره و یک نقطه برای مشخص کردن پایان جمله . اگر هر کلمه فضای خالی یا علایم نشانه گذاری اشغال کند یک واحد از حافظه را, ما داریم فایلی به اندازه ی 79 واحد . برای کاهش اندازه ی فایل ما نیاز داریم در نظر بگیریم افزونگی ها رو .

بلافاصله ما تشخیص می دیم که :

· “asK” ظاهر شده دو بار

· “what” ظاهر شده دوبار

· “your” ظاهر شده دو بار

· “Country” ظاهرشده دو بار

· “Can” ظاهر شده دو بار

· “do” ظاهر شده دو بار

· “For” ظاهر شده دو بار

· “You” ظاهر شده دو بار

نادیده می گیریم تفاوت بین حروف بزرگ و حروف کوچک رو , تقریبا نیمی از عبارات هستند اضافی . 9 کلمه ی – ask,not,what,your,country,can,do ,for,you – به ما می دن هر چیزی که ما نیاز داریم برای وارد کردن به نقل قول . برای ساختن دومین نیمه از عبارت , ما تنها اشاره می دیم به کلماتی در نیمه اول و تکمیل کردن فضاهای خالی و علایم نشانه گذاری .

ما مشاهده خواهیم کرد چگونه سیستم های فشرده کردن فایل کار می کنن با افزونگی در قسمت بعد جزییات بیشتری رو بیان می کنیم .

افزونگی و الگوریتم

اکثر برنامه های فشرده سازی استفاده می کنند روشهای گوناگونی ازLZ adaptive dictionary-based algorithmبه منظور کاهش اندازه ی فایل ها . “LZ” ارجاع دارد به Lempel And Ziv , ایجاد کردن الگوریتم , و “dictionary” استفاده کرده از روش دسته بندی قطعاتی از داده , و دیکشنری اشاره داره به روشی از دسته بندی قطعاتی از داده .

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

پس اگر این دیکشنری داده های ما باشه :

جمله ما حالا به این صورت می شه :

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

اما چه مقدار فضا مادر حقیقت صرفه جویی می کنیم با این سیستم ؟

“1 not 2 3 4 5 6 7 8 — 1 2 8 5 6 7 3 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” وبدنبال ان یک فاصله در “Not” و “What”, به شرطی که برنامه فشرده ساز بنویسد ان را در دیکشنری.این می تونست نوشته بشه “1″ هرگاه یک “t” به دنبالش یک فاصله بود .اما در این عبارت کوتاه این انتخاب به تنهایی سودمند نیست پس برنامه سر انجام بازنویسی می کنه این رو . چیز دیگری که شاید برنامه مورد توجه قرار بده هست “ou” ,که ظاهر شده در هر دو کلمه ی “Your” و “Country” . اگر این یک سند بزرگتر بود, نوشتن این الگو در دیکشنری می تونه صرفه جویی کنه فضای زیادی رو . “Ou” هست ترکیبی کاملا معمول در زبان انگلیسی . اما همانطور که برنامه فشرده ساز عمل می کنه بر روی این عبارت , می تونه به سرعت کشف کنه الگوهای بهتری رو برای وارد کردن به دیکشنری : تنها “ou” تکرار نشده در عبارت , از طرف دیگر کلمات “your” و “Country” دو بار تکرار شده اند , و انها در حقیقت با هم تکرار شده اند , همچون عبارت “Your Country” .در این حالت , برنامه فشرده ساز می تونه باز نویسی کنه ورودی “ou” رو با ورودی برای “Your Country”.

عبارت “Can do for you” همچنین تکرار شده , پیش تر در نظر گرفتم “You” و “Your,” را , به ما می ده یک الگوی تکرار شده از “Can do for You.” که به ما اجازه می ده بنویسیم 15 کاراکتر را (همراه فاصله ) با یک عدد, در صورتیکه “Your Country” به ما اجازه نوشتن 13 کاراکتر (همراه با فاصله )با یک ارزش عددی رو می ده , پس برنامه می تونه بازنویس کنه “your Country” با ورودی “r Country” و بعد نوشته می شه یک ورودی مجزا برای “can do for you.” برنامه به این نحو پیش می ره .به دست می یاره تمام بیت های تکرار شده از اطلاعات را و بعد محاسبه می کنه کدام الگو می تونه در دیکشنری نوشته بشه. این قابلیت نوشتن دردیکشنری هست“Adaptive” قسمتی از LZ adaptive dictionary-based algorithm . روش کار یک برنامه فشرده ساز واقعی می تونه واقعا پیچیده باشه .

اهمیت نداره روش ویژه ای که شما استفاده می کنید عمق جستجوی سیستم است که به شما اجازه می دهد فشرده کنید فایل رو بسیار موثر و کارامد پس شما می تونستید به تنهایی کلمات را انتخاب کنید . الگوهایی که ما در بالا استفاده کردیم , و اضافه کردیم “__” برای فاصله ها

ما به کار گرفتیم دیکشنری بزرگتری را :

و این جمله ی کوتاهتر را :

این جمله حالا اشغال می کنه 18 واحد از حافظه را , و دیکشنری ما 41 واحد از حافظه را اشغال می کند.پس ما فشرده کردیم اندازه ی کامل فایل را از 79 واحد به 59 واحد ! این تنها یک روش از فشرده سازی عبارت بود , و لزوما کارامد ترین روش نیست .

پس چگونه این سیستم فشرده سازی خوب است ؟ نرخ کاهش فایل وابسته است روی تعدادی فاکتورها, شامل نوع فایل , اندازه ی فایل و الگوی فشر ده سازی .

در اکثر زبان های جهانی , حرف ها و کلمات خاصی اغلب ظاهر می شوند در کنار یکدیگر در الگویی مشابه .

به علت این نرخ بالا از افزونگی , فایل ها متنی به خوبی فشرده می شوند . یک کاهش 50% یا بیشتر هست معمول و خوبی برای فایل متنی . زبان های برنامه نویسی افزونگی زیادی دارند زیرا انها استفاده می کنند یک مجموعه ی نسبتا کوچکی از دستورات را , که به طور تکرار شونده در کنار هم در یک مجموعه الگو قرار می گیرند .

فایل هایی که شامل تعداد زیادی اطلاعات منحصر به فرد هستند همچون فایل های گرافیکی و MP3 با این سیستم نمی توان انها را بسیار فشرده کرد زیرا انها الگو های تکرار شونده زیادی ندارند(اطلاعات بیشتر در مورد این موضوع در قسمت بعد ).

اگر فایلی الگو ها ی تکرار شونده زیادی داشته باشد , نرخ کاهش معمول افزایش پیدا می کنه با افزایش اندازه ی فایل . شما می تونید پی ببرید به این موضوع تنها با در نظر گرفتن نمونه ما – اگر ما سخنان بیشتری از کندی رو داشتیم , ما می تونستیم ارجاع بدیم عبارات بیشتری رو به الگوها در دیکشنری , در نتیجه صرفه جویی بیشتری در حافظه رو داشتیم . همچنین الگوهای فراگیرتر و جامع تری ممکن بود پدیدار شوند در فعالیت بیشتر , اجازه بدید ما ایجاد کنیم یک دیکشنری بسیار کارامد را .

این کارامدی همچنین وابسته است روی الگوریتم ویژه ی استفاده شده در برنامه فشرده ساز. بعضی برنامه هاد سازگار شده اند برای برگزیدن الگوهایی برای نوع های خاصی از فایل ها, و شاید قادر باشند انها را بسیار فشرده کنند . داشتن دیکشنری های دیگری در دیکشنری ها, که شاید فشرده سازی کارامدتری داشته باشه برای فایل های بزرگ اما نه برای یک فایل بسیار کوچک . تمامی برنامه های فشرده سازی با این عملکرد تفکر پایه ایی مشابهی دارند, انها حقیقتا هستند یک کارگزار خوب از تنوع و گوناگونی در روش اجرا.برنامه نویسان همیشه سعی می کنند روش بهتری رو برای این منظور ایجاد کنند .

Lossy and Lossless Compression(فشرده سازی پراتلاف و کم ضرر)

این نوع ازفشرده سازی که ما صحبت می کنیم درباره ی ان نامیده می شه lossless compression,زیرابه شما اجازه می دهددوباره ایجاد کنید فایل اصلی را به طور کامل . همه ی lossless compression هستند بر مبنای عقیده ی شکستن فایل به قسمت های کوچکتر برای انتقال یا ذخیره سازی و سپس جمع کردن ان برای استفاده دوباره .

lossless compression بسیار متفاوت عمل می کنه.این برنامه ها به راحتی حذف می کنند بیت ها و اطلاعات غیر ضروری را , و کاهش اندازی فایل تا حدی که مناسب باشه .این نوع از فشرده سازی برای کاهش اندازه ی عکس های نقشه بیتی استفاده می شه (BitMap) , که کاملا مد نظر قرار می ده بزرگی اون رو .ببینیم چگونه عمل میکنه این سیستم,اجازه بدید ببینیم که چگونه کامپیوتر شما فشرده می کند یک عکس اسکن شده را .

یک برنامه فشرده سازی lossless compression نمی تونه کار کنه به خوبی با این نوع از فایل ها .چونکه قسمت های زیادی از عکس شاید یکسان به نظر برسند – تمام اسمان هست ابی , برای نمونه—اکثر پیکسل های مجزا از هم هستند, یک بیت متفاوت کوچک .که تصاویر کوچکتری رو ایجاد می کنند بدون فشرده سازی وضوع تصویر.شما تغییر می دید ارزش رنگ رو برای پیکسل های خاصی .اگر تصویر شما داشته باشه مقدار زیادی اسمان ابی

, برنامه انتخاب می کنه رنگی از ابی رو که می تونه استفاده بشه به جای همه ی اون پیکسل ها . سپس برنامه بازنویسی می کنه فایل رو به نحوی که هر ارزش برای رنگ ابی ارجاع داده بشه به این اطلاعات . اگر الگوی فشرده سازی بسیار خوب عمل کنه , شما به اختلاف پی نخواهید برد , اما اندازه ی فایل می تونه تاثیر گذار باشه در کاهش اون . البته با lossless compression, شما نمی تونید برگردانید تصویراصلی رو بعد از عمل فشرده سازی. شما ثابت کردید تغییرات برنامه فشرد ساز رو برای فایل اصلی . به همین علت شما نمی تونیداستفاده کنید از این روش برای فشرده سازی هر چیزی که نیاز دارید به کاهش پیدا کنه , شامل نرم افزار ها ی کاربردی , پایگاه های داده و سخنرانی ها ی ریاست جمهوری را .

مشاهده منبع مقاله

استفاده از متن فارسی مقاله با ذکر منبع http://w2kir.wordpress.com بلامانع است