سلام
من یک مقاله با عنوان الگوریتم های فشرده سازی می خوام.من هیچ چیز درباره ی این موضوع نمی دونم لطفا مقاله طوری باشد که بتونم خودم یاد بگیرم و کنفرانس بدم.
ممنون
Printable View
سلام
من یک مقاله با عنوان الگوریتم های فشرده سازی می خوام.من هیچ چیز درباره ی این موضوع نمی دونم لطفا مقاله طوری باشد که بتونم خودم یاد بگیرم و کنفرانس بدم.
ممنون
سلام...
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
اكثر فايل هاي موجود بر روي اينترنت با استفاده از نرم افزارهايي نظير 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?) ، بدليل عدم وجود الگوهاي تكرار شونده ، بخوبي فشرده نخواهند گرديد.
در صورتيكه فايلي داراي تعداد زيادي الگوي تكرار شونده باشد ، ميزان افزونگي اطلاعات موجود در فايل به طرز محسوسي ظرفيت فايل را افزايش خواهد داد. بدين ترتيب در زمان فشرده سازي اين نوع از فايل ها با توجه به وجود الگوهاي تكرار شونده ، ظرفيت فايل در حد قابل قبولي كاهش پيدا خواهد كرد .
ميزان فشرده سازي اطلاعات، به الگوريتم استفاده شده توسط برنامه فشرده سازي نيز بستگي دارد. بديهي است استفاده از يك الگوريتم با كارآيي بالا ، نتايج مثبتي را در رابطه با فشرده سازي به ارمغان خواهد آورد.
----------------------------------------------
الگوریتم های فشرده سازی تصاویر
کد:
http://atlc.sourceforge.net/bmp.html
http://www.fortunecity.com/skyscrape.../bmpffrmt.html
http://www.qzx.com/pc-gpe/pcx.txt
http://www.fileformat.info/format/pcx