اکثر فايل های موجود بر روی اينترنت با استفاده از نرم افزارهائی نظير WinZip فشرده و بر روی سرويس دهندگان FTP مستقر تا کاربران بتوانند با سرعت مناسب اقدام به دريافت آنها نمايند. فايل های فشرده ZIP يکی از متداولترين و سهل الوصول ترين نوع فايل های فشرده می باشند. با فشرده نمودن فايل ها امکان ارسال سريعتر آنها بر روی اينترنت خصوصا" در موارديکه سرعت خط ارتباطی کاربران بالا نباشد ، فراهم می گردد. پس از دريافت فايل های فشرده با استفاده از نرم افزارهای مربوطه نظير WinZip می بايست آنها را به حالت اوليه تبديل ( از حالت فشرده خارج گردند ) کرد.
هدف از فشرده نمودن فايل ها کاهش ظرفيت فايل ها بوده و در زمان استفاده از فايل می بايست مجددا" فايل به حالت اوليه برگردانده شود. در فرآيند فوق بيت هائی از فايل با استفاده از الگوريتم هائی خاص ، از فايل حذف و زمينه کاهش ظرفيت فايل فراهم خواهد شد. در زمان استفاده از فايل با استفاده از الگوريتم فشرده سازی عمليات معکوس انجام و فايل به حالت اوليه خود برگردانده خواهد شد. در ادامه به برخی از روش های فشرده سازی اطلاعات اشاره خواهد شد.
يافتن افزونگی در فايل
اکثرفايل های کامپيوتری ( با محتويات متفاوت ) دارای افزونگی اطلاعات می باشند. اين نوع فايل ها دارای اطلاعات تکراری زيادی می باشند. برنامه های فشرده سازی اطلاعات ، اطلاعات تکراری موجود در فايل ها را بر اساس الگوريتم های مربوطه حذف می نمايند. پس از تشخيص اطلاعات تکراری ، صرفا" اطلاعات تکراری يک بار در فايل تکرار و و در ساير موارد، از مکانيزمهای خاصی برای عدم تکرار استفاده می گردد.
جمله زير از 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" ، به منظور کاهش ظرفيت فايل ها ، استفاده می نمايند. منظور از ديکشنری در الگوريتم فوق ، روش های کاتولوگ نمودن بخش هائی از داده است . سيستم استفاده شده برای سازماندهی ديکشنری متفاوت و در ساده ترين حالت می تواند شامل يک ليست عددی باشد. با مراجعه مجدد به عبارت اشاره شده در بخش قبل ، کلمات تکراری را انتخاب و آنها را در ليست مرتب شده ای بصورت زير ايندکس می نمائيم . پس از ايجاد ليست فوق ، می توان در موارديکه از کلمات در عبارت استفاده می شود ، از اعداد نسبت داده شده و متناظر با آنها استفاده کرد. ديکشنری ايجاد شده برای عبارت اشاره شده در بخش قبل بصورت زير است :
|
با توجه به ديکشنری ايجاد شده ، عبارت مورد نظر بصورت زير خوانده خواهد شد :
"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" ، در ديکشنری ثبت می گردند. برنامه فشرده سازی فرآيند فوق را دنبال و پس از يافتن يک الگو ، محاسبات مربوطه را انجام و الگوی واجدالشرايط را در ديکشنری ثبت خواهد کرد. مهمترين ويژگی "الگوريتم مبتنی بر ديکشنری " ، قابليت تغيير الگوها در زمان فرآيند فشرده سازی است .
با توجه به الگوهائی تشخيص داده شده ، ديکشنری مربوطه بشکل زير خواهد بود . در ديکشنری زير الگوهای تشخيص داده شده ثبت و برای فضای خالی از کاراکتر "__" استفاده شده است .
|
با توجه به ديکشنری فوق ، عبارت اشاره شده در بخش قبل بصورت زير فشرده می گردد.
"1not__2345__--__12354" |
عبارت فوق 18 و ديکشنری 41 ، واحد حافظه را اشغال خواهند کرد. بدين ترتيب فايل حاوی عبارت اوليه فوق از 79 واحد حافظه به 59 واحد حافظه کاهش پيدا کرده است . روش استفاده شده به منظور فشرده سازی عبارت فوق يکی از امکانات موجود بوده و می توان در اين راستا از روش های ديگر نيز استفاده کرد.
تا چه ميزان می توان اطلاعات را فشرده کرد ؟
ميزان ( نسبت ) کاهش ظرفيت يک فايل ، به عوامل متعددی نظير : نوع فايل ، اندازه فايل و روش فشرده سازی بستگی دارد. در اکثر زبانهای طبيعی ، حروف و کلمات الگوهای مناسبی را بصورت جداگانه و يا ترکيبی ايجاد می نمايند. بدين ترتيب فشرده سازی فايل های متنی نتايج بسيار مطلوبی را بدنبال خواهد داشت . فايل های متنی اغلب پس از فشرده سازی به ميزان پنجاه درصد و يا بيشتر ، کاهش ظرفيت را خواهند داشت . اکثر زبانهای برنامه نويسی ( مصنوعی ) نيز بدليل استفاده از مجموعه ای از دستورات که بصورت تکراری استفاده می شوند ، دارای افزونگی اطلاعات بوده و پس از فشرده سازی نتايج رضايتبخشی را بدنبال خواهد داشت . فايل هائی که دارای حجم بالائی از اطلاعات منحصر بفرد بوده ( نظير فايل های گرافيک و يا فايل های mp3) ، بدليل عدم وجود الگوهای تکرار شونده ، بخوبی فشرده نخواهند گرديد.
در صورتی که فايلی دارای تعداد زيادی الگوی تکرار شونده باشد ، ميزان افزونگی اطلاعات موجود در فايل بطرز محسوسی ظرفيت فايل را افزايش خواهد داد. بدين ترتيب در زمان فشرده سازی اين نوع از فايل ها با توجه به وجود الگوهای تکرار شونده ، ظرفيت فايل در حد قابل قبولی کاهش پيدا خواهد کرد .
ميزان فشرده سازی اطلاعات، به الگوريتم استفاده شده توسط برنامه فشرده سازی نيز بستگی دارد. بديهی است استفاده از يک الگوريتم با کارآئی بالا ، نتايج مثبتی را در رابطه با فشرده سازی به ارمغان خواهد آورد.