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