شیوه فشرده سازی فایل ها

شیوه فشرده سازی فایل ها
اكثر فایل های موجود بر روی اینترنت با استفاده از نرم افزارهایی نظیر WinZip فشرده و بر روی سرویس دهندگان FTP مستقر هستند تا كاربران بتوانند با سرعت مناسب اقدام به دریافت آنها نمایند. فایل های فشرده ZIP یكی از متداولترین و سهل الوصول ترین نوع فایل های فشرده می باشند. با فشرده نمودن فایل ها امكان ارسال سریعتر آنها بر روی اینترنت خصوصا" در مواردیكه سرعت خط ارتباطی كاربران بالا نباشد ، فراهم می گردد. پس از دریافت فایل های فشرده با استفاده از نرم افزارهای مربوطه نظیر WinZip می بایست آنها را به حالت اولیه تبدیل ( از حالت فشرده خارج گردند ) كرد.

هدف از فشرده نمودن فایل ها كاهش ظرفیت فایل ها بوده و در زمان استفاده از فایل می بایست مجددا" فایل به حالت اولیه برگردانده شود. در فرآیند فوق بیت هایی از فایل با استفاده از الگوریتم هایی خاص ، از فایل حذف و زمینه كاهش ظرفیت فایل فراهم خواهد شد. در زمان استفاده از فایل با استفاده از الگوریتم فشرده سازی عملیات معكوس انجام و فایل به حالت اولیه خود برگردانده خواهد شد. در ادامه به برخی از روش های فشرده سازی اطلاعات اشاره خواهد شد.

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

اكثرفایل های كامپیوتری ( با محتویات متفاوت ) دارای افزونگی اطلاعات می باشند. این نوع فایل ها دارای اطلاعات تكراری زیادی می باشند. برنامه های فشرده سازی اطلاعات ، اطلاعات تكراری موجود در فایل ها را بر اساس الگوریتم های مربوطه حذف می نمایند. پس از تشخیص اطلاعات تكراری ، صرفا" اطلاعات تكراری یك بار در فایل تكرار و و در سایر موارد، از مكانیزمهای خاصی برای عدم تكرار استفاده می گردد.
جمله زیر از ۱۷ كلمه ، ۶۱ حرف ، ۱۶ فضای خالی ، یك نقطه و یك dash ، تشكیل شده است :


"Ask not what your country can do for you — ask what you can do for your country."
اگر هر یك از حروف ، فضای خالی و حروف خاص ، یك واحد از حافظه را اشغال نمایند ، مجموعا" ۷۹ واحد از حافظه توسط عبارت فوق استفاده خواهد گردید (۷۹ = ۱ + ۱+ ۱۶ + ۶۱ ) . بمنظور كاهش ظرفیت فایل می بایست افزونگی اطلاعات در فایل را بررسی كرد. با مشاهده و بررسی عبارت فوق ، نتایج زیر بدست می آید :


§ كلمه " ask" ، دو مرتبه تكرار شده است . § كلمه " what" ، دو مرتبه تكرار شده است .
§ كلمه " your" ، دو مرتبه تكرار شده است .
§ كلمه "country" ، دو مرتبه تكرار شده است .
§ كلمه "can" ، دو مرتبه تكرار شده است .
§ كلمه " do" ، دو مرتبه تكرار شده است .
§ كلمه " for" ، دو مرتبه تكرار شده است .
§ كلمه "you" ، دو مرتبه تكرار شده است .

با عدم لحاظ نمودن حروف بزرگ و كوچك درعبارت فوق ، مشاهده می گردد كه نیمی از اطلاعات موجود در عبارت فوق ، زاید و تكراری می باشند. با دقت در عبارت فوق و نحوه افزونگی اطلاعات مشاهده می گردد كه با دارا بودن نه كلمه ask,not,what,your,country,can ،do ،for و you می توان پالایشی مناسبی از عبارت فوق را انجام و در صورت لزوم و با استفاده از نه كلمه فوق ، مجددا" عبارت اولیه را ایجاد نمود. در این راستا و بمنظور ایجاد عبارت فوق كافی است به كلمات موجود در بخش اول ( نصف عبارت ) اشاره و جایگاه و تعداد تكرار هر یك از آنها را در بخش دوم مشخص نمود. در ادامه نحوه فشرده سازی اطلاعات و بازسازی مجدد آنها بررسی می گردد.

فشرده سازی اطلاعات

اكثر برنامه های فشرده سازی از مدل ها ی متفاوت الگوریتم مبتنی بر دیكشنری ایجاد شده توسط "Lempel و Ziv" ، بمنظور كاهش ظرفیت فایل ها ، استفاده می نمایند. منظور از دیكشنری در الگوریتم فوق ، روش های كاتولوگ نمودن بخش هایی از داده است . سیستم استفاده شده برای سازماندهی دیكشنری متفاوت و در ساده ترین حالت می تواند شامل یك لیست عددی باشد. با مراجعه مجدد به عبارت اشاره شده در بخش قبل ، كلمات تكراری را انتخاب و آنها را در لیست مرتب شده ای بصورت زیر ایندكس می نماییم . پس از ایجاد لیست فوق ، می توان در مواردیكه از كلمات در عبارت استفاده می شود ، از اعداد نسبت داده شده و متناظر با آنها استفاده كرد.
دیكشنری ایجاد شده برای عبارت اشاره شده در بخش قبل بصورت زیر است :

ask

what

your

country

can

do

for

you
با توجه به دیكشنری ایجاد شده ، عبارت مورد نظر بصورت زیر خوانده خواهد شد :

"۱ not ۲ ۳ ۴ ۵ ۶ ۷ ۸ — ۱ ۲ ۸ ۵ ۶ ۷ ۳ ۴"
برای بازسازی مجدد عبارت فوق ، لازم است الگوی معادل آن را با توجه به دیكشنری استخراج و در محل مربوطه قرار داد. برنامه هایی نظیر WinZip از فرآیندهای مشابه برای بازسازی مجدد یك فایل و برگرداندن آن به شكل اولیه استفاده می نمایند.
در فرآیند فشرده سازی عبارت اشاره شده در بخش قبل به شكل جدید آن ( مطابق جدول بالا ) چه میزان ظرفیت فایل كاهش پیدا كرده است ؟ مطمینا" عبارت فشرده شده ظرفیت كمتری نسبت به عبارت اولیه خواهد داشت . در این زمینه لازم است به این نكته مهم اشاره گردد كه دیكشنری ایجاد شده نیز می بایست به همراه فایل ذخیره گردد. در مثال فوق ، عبارت اولیه برای ذخیره سازی به ۷۹ واحد حافظه نیاز داشت . عبارت فشرده شده ( بهمراه فضای خالی ) ، ۳۷ واحد و دیكشنری ( كلمات و اعداد ) ، نیز ۳۷ واحد حافظه را اشغال خواهند كرد. بدین ترتیب ظرفیت فایل فشرده به ۷۴ واحد حافظه خواهد رسید . با توجه به اطلاعات فوق مشاهده می گردد كه عملا" در رابطه با فشرده سازی عبارت فوق به موفقیت های بزرگی نایل نشده ایم . در این زمینه لازم است به این نكته اشاره گردد كه در مثال فوق ، صرفا" یك " جمله " فشرده شده است . فرض كنید جمله فوق بخشی از یك سخنرانی یك ساعته باشد ، بدیهی است كه در سخنرانی فوق احتمال تكرار كلمات فوق بسیار زیاد خواهد بود . با ایجاد سیستم دیكشنری ، زمینه استفاده از آن در بخش های بعدی سخنرانی نیز وجود داشته و در ادامه قطعا" میزان فشرده سازی جملات موجود در متن سخنرانی نتایج مطلوبتری را بدنبال خواهد داشت .

جستجو برای الگوها
در مثال ارایه شده ، تمام كلمات تكراری انتخاب و در دیكشنری قرار گرفتند. در روش فوق ، ساده ترین مدل برای ایجاد دیكشنری استفاده شده است . برنامه های فشرده سازی از مدل های كاملا" متفاوت دیگر در این زمینه استفاده می نمایند.برنامه های فوق نسبت به كلمات متمایز، از یكدیگر شناخت لازم را نداشته و در این راستا صرفا" بدنبال "الگو" خواهند بود. این نوع برنامه ها بمنظور كاهش ظرفیت فایل ها ، با دقت الگوها را انتخاب و آنها را در دیكشنری مستقر می نمایند. در صورتیكه از دیدگاه فوق فرآیند فشرده سازی دنبال گردد ، در نهایت با یك دیكشنری كاملا" متفاوت با آن چیزی كه قبلا" ایجاد شده بود ، مواجه خواهیم بود.
اگر یك برنامه فشرده سازی عبارت معروف اشاره شده در بخش قبل را بمنظور یافتن افزونگی ، پیمایش نماید ، پس از دنبال نمودن بخشی از عبارت (ask not what your) ، الگویی جدید را تشخیص خواهد داد. الگوی فوق حرف "t" بوده كه بدنبال آن یك فضای خالی نیز قرار دارد. ( در كلمات "not" و "what" ) . در صورتیكه برنامه فشرده سازی الگوی فوق را در دیكشنری مستقر نماید ، می بایست یك عدد "۱" را در هر زمان كه با حرف "t" و یك فضای خالی بدنبال آن برخورد می نماید ، در دیكشنری ثبت نماید. با ادامه پیمایش عبارت فوق توسط برنامه فشرده سازی ، مشاهده می گردد كه الگوی تشخیص داده شده ( حرف t و فضای خالی بدنبال آن ) به میزان قابل ملاحظه ای در عبارت تكرار نشده و برای ثبت در دیكشنری واجد شرایط مناسب نخواهد بود ، بدین تزتیب الگوی تشخیص داده شده نادیده گرفته شده و عملیات یافتن الگویی دیگر ، دنبال خواهد گردید.
در ادامه برنامه فشرده سازی متوجه الگوی "ou" می گردد ، الگوی فوق در كلمات "your" و "country" ، تكرار شده است . در صورتیكه عبارت مورد نظر یك فایل طولانی بود ، ثبت و نوشتن الگوی فوق در دیكشنری می توانست به میزان قابل توجه ای از ظرفیت فایل را كاهش دهد. "ou" ، یكی از تركیبات متداول استفاده شده در زبان انگلیسی است . معیار برنامه فشرده سازی عبارتی است كه در حال پیمایش آن است . در ادامه پیمایش عبارت فوق ، یك الگوی مناسبتر تشخیص داده خواهد شد. الگوهای فوق "your" و "country" بوده كه هر یك بدفعات تكرار شده اند. تكرار هر یك از كلمات فوق در عبارت معادل تركیب كلمات "your country" است . در چنین حالتی برنامه قشرده سازی entry موجود در دیكشنری برای الگوی "ou" را با الگوی "your country" ، جایگزین می نماید. عبارت تركیبی "can do for" ، نیز در عبارت اصلی تكرار شده است . ( یك مرتبه پس از "your" و یك مرتبه پس از "you" ) . بدین ترتیب الگوی "can do for you" نیز تكراری خواهد بود. بنابراین می توان در عوض نوشتن ۱۵ حرف ( بهمراه قضای خالی ) ، از یك عدد استفاده كرد. در صورت استفاده از الگوی "your country" ، برای ۱۳ حرف از یك عدد معادل استفاده می گردد ، بدیهی است كه الگوی فوق نادیده گرفته شده در عوض الگوی "r country" و الگوی جدید "can do fo you" ، در دیكشنری ثبت می گردند. برنامه فشرده سازی فرآیند فوق را دنبال و پس از یافتن یك الگو ، محاسبات مربوطه را انجام و الگوی واجدالشرایط را در دیكشنری ثبت خواهد كرد. مهمترین ویژگی "الگوریتم مبتنی بر دیكشنری " ، قابلیت تغییر الگوها در زمان فرآیند فشرده سازی است .
با توجه به الگوهایی تشخیص داده شده ، دیكشنری مربوطه بشكل زیر خواهد بود . در دیكشنری زیر الگوهای تشخیص داده شده ثبت و برای فضای خالی از كاراكتر "__" استفاده شده است .

ask >what

you

r__country
__can__do__for__you

با توجه به دیكشنری فوق ، عبارت اشاره شده در بخش قبل بصورت زیر فشرده می گردد.


"۱not__۲۳۴۵__–__۱۲۳۵۴"
عبارت فوق ۱۸ و دیكشنری ۴۱ ، واحد حافظه را اشغال خواهند كرد. بدین ترتیب فایل حاوی عبارت اولیه فوق از ۷۹ واحد حافظه به ۵۹ واحد حافظه كاهش پیدا كرده است . روش استفاده شده بمنظور فشرده سازی عبارت فوق یكی از امكانات موجود بوده و می توان در این راستا از روش های دیگر نیز استفاده كرد.

تا چه میزان می توان اطلاعات را فشرده كرد ؟
میزان ( نسبت ) كاهش ظرفیت یك فایل ، به عوامل متعددی نظیر : نوع فایل ، اندازه فایل و روش فشرده سازی بستگی دارد. در اكثر زبانهای طبیعی ، حروف و كلمات الگوهای مناسبی را بصورت جداگانه و یا تركیبی ایجاد می نمایند. بدین ترتیب فشرده سازی فایل های متنی نتایج بسیار مطلوبی را بدنبال خواهد داشت . فایل های متنی اغلب پس از فشرده سازی به میزان پنجاه درصد و یا بیشتر ، كاهش ظرفیت را خواهند داشت . اكثر زبانهای برنامه نویسی ( مصنوعی ) نیز بدلیل استفاده از مجموعه ای از دستورات كه بصورت تكراری استفاده می شوند ، دارای افزونگی اطلاعات بوده و پس از فشرده سازی نتایج رضایت بخشی را بدنبال خواهد داشت . فایل هایی كه دارای حجم بالایی از اطلاعات منحصر بفرد بوده ( نظیر فایل های گرافیك و یا فایل های mp۳) ، بدلیل عدم وجود الگوهای تكرار شونده ، بخوبی فشرده نخواهند گردید.
در صورتیكه فایلی دارای تعداد زیادی الگوی تكرار شونده باشد ، میزان افزونگی اطلاعات موجود در فایل به طرز محسوسی ظرفیت فایل را افزایش خواهد داد. بدین ترتیب در زمان فشرده سازی این نوع از فایل ها با توجه به وجود الگوهای تكرار شونده ، ظرفیت فایل در حد قابل قبولی كاهش پیدا خواهد كرد .
میزان فشرده سازی اطلاعات، به الگوریتم استفاده شده توسط برنامه فشرده سازی نیز بستگی دارد. بدیهی است استفاده از یك الگوریتم با كارآیی بالا ، نتایج مثبتی را در رابطه با فشرده سازی به ارمغان خواهد آورد.