تبلیغات
C.NA - شرح چگونگی فشرده سازی یک فایل
جمعه 23 مهر 1389

شرح چگونگی فشرده سازی یک فایل

   نوشته شده توسط: CNA G    

تا چه میزان می توان اطلاعات را فشرده کرد ؟به همراه معرفی الگوریتم هافمن

کثرفایل های کامپیوتری ( با محتویات متفاوت ) دارای افزونگی اطلاعات می باشند. این نوع فایل ها دارای اطلاعات تکراری زیادی می باشند. برنامه های فشرده سازی اطلاعات .. اطلاعات تکراری موجود در فایل ها را بر اساس الگوریتم های مربوطه حذف می نمایند. پس از تشخیص اطلاعات تکراری ..صرفااطلاعات تکراری یک بار در فایل تکرار و در سایر موارد.. از مکانیزمهای خاصی برای عدم تکرار استفاده می گردد. 
جمله زیر از 17 کلمه.. 61 حرف.. 16 فضای خالی .. یک نقطه و یک dash .. تشکیل شده است : 


"Ask not what your country can do for you -- ask what you can do for your country." 


اگر هر یک از حروف .. فضای خالی و حروف خاص .. یک واحد از حافظه را اشغال نمایند ..مجموعا 79 واحد از حافظه توسط عبارت فوق استفاده خواهد گردید (79 = 1 + 1+ 16 + 61 ) . بمنظور کاهش ظرفیت فایل می بایست افزونگی اطلاعات در فایل را بررسی کرد. با مشاهده و بررسی عبارت فوق .. نتایج زیر بدست می آید : 


کلمه " 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 
با توجه به دیکشنری ایجاد شده .. عبارت مورد نظر بصورت زیر خوانده خواهد شد : 


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


برای بازسازی مجدد عبارت فوق.. لازم است الگوی معادل آن را با توجه به دیکشنری استخراج و در محل مربوطه قرار داد. برنامه هائی نظیر WinZip از فرآیندهای مشابه برای بازسازی مجدد یک فایل و برگرداندن آن به شکل اولیه استفاده می نمایند. 
در فرآیند فشرده سازی عبارت اشاره شده در بخش قبل به شکل جدید آن چه میزان ظرفیت فایل کاهش پیدا کرده است ؟ مطمئنا عبارت فشرده شده ظرفیت کمتری نسبت به عبارت اولیه خواهد داشت . در این زمینه لازم است به این نکته مهم اشاره گردد که دیکشنری ایجاد شده نیز می بایست به همراه فایل ذخیره گردد. در مثال فوق ..عبارت اولیه برای ذخیره سازی به 79 واحد حافظه نیاز داشت . عبارت فشرده شده ( بهمراه فضای خالی ) .. 37 واحد و دیکشنری ( کلمات و اعداد ).. نیز 37 واحد حافظه را اشغال خواهند کرد. بدین ترتیب ظرفیت فایل فشرده به 74 واحد حافظه خواهد رسید . با توجه به اطلاعات فوق مشاهده می گردد که عملا در رابطه با فشرده سازی عبارت فوق به موفقیت های بزرگی نائل نشده ایم . در این زمینه لازم است به این نکته اشاره گردد که در مثال فوق .. صرفا" یک " جمله " فشرده شده است . فرض کنید جمله فوق بخشی از یک سخنرانی یک ساعته باشد .. بدیهی است که در سخنرانی فوق احتمال تکرار کلمات فوق بسیار زیاد خواهد بود . با ایجاد سیستم دیکشنری .. زمینه استفاده از آن در بخش های بعدی سخنرانی نیز وجود داشته و در ادامه قطعا میزان فشرده سازی جملات موجود در متن سخنرانی نتایج مطلوبتری را بدنبال خواهد داشت . 
----------------------------------------------------------------------------------------------------------------------------- 
جستجو برای الگوها


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

ask >what 

you 

r__country 
__can__do__for__you 

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


"1not__2345__--__12354" 

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


--------------------------------------------------------------------------------------------------------------------------- 
تا چه میزان می توان اطلاعات را فشرده کرد ؟



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

(برگرفته از سایت Srco) 
------------------------------------------------------------------------------------------------------------------ 
الگوریتم فشرده سازی هافمن


الگوریتم فشرده سازی هافمن را دیوید هافمن پروفسور دانشگاه MIT (Massachusetts Institute of Technology آمریکا اختراع کرد. روش فشرده سازی هافمن الگوریتمی است که برای فشرده سازی متن مناسب می باشد. 
الگوریتم هافمن جزو خانواده الگوریتم هایی است که طول کد متغییری دارند. این به آن معناست که نماد های مجزا (برای نمونه کاراکترهایی در یک فایل متنی) با رشته بیت هایی که طول های مختلفی دارند تعویض می شود. بنابراین نماد هایی که زیاد در یک فایل تکرار می شوند یک رشته بیت کوتاه می گیرند در حالی که نمادهای دیگر که به ندرت دیده می شوند رشته بیت طولانی تری را می گیرند. 

یک مثال کاربردی اجزای کار را به شما نشان می دهد. 

فرض کنید می خواهید تکه اطلاعات زیر رافشرده کنید: 
ACDABA 

از آنجایی که 6 کاراکتر داریم.. این متن 6 بایت یا 48 بیت می باشد. با رمز گزاری هافمن.. فایل برای بیشترین تکرار ظاهر شدن نمادها (در این مثال نماد A سه بار تکرار می شود) جستجو می شود و سپس یک درخت ساخته می شود که نماد ها را با رشته بیت های کوتاه تر جایگزین می کند. در این حالت خاص الگوریتم از جدول جایگزینی زیر استفاده می کند: 
A=0 , B=10 , C=110 , D=111. 

اگر این کد برای فشرده سازی فایل استفاده شود، اطلاعات فشرده شده به صورت زیر در می آیند: 
01101110100 

این به این معنی است که 11 بیت به جای 48 بیت مصرف شد. در این مثال خاص نسبت فشرده سازی 4 به 1 می باشد. 

رمزگزاری هافمن به دو روش مختلف می تواند بهینه تر شود: 

1. کد هافمن انطباقی (Adaptive Huffman code) به صورت پویا کلمات کد را با توجه به تغییر احتمال وقوع نماد ها تغییر می دهد. 

2. فشرده سازی گستردهء هافمن (Extended Huffman Compression) می تواند گروهی از نماد ها را نسبت به یک نماد رمز گزاری کند. 

این روش می تواند بین 20% تا 90% اطلاعات را فشرده کند. 

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