همه چیز در باره کامپیوتر

“جستجو برای الگوها

در مثال ارائه شده ، تمام کلمات تکراری انتخاب و در دیکشنری قرار گرفتند. در روش فوق ، ساده ترین مدل برای ایجاد دیکشنری استفاده شده است . برنامه های فشرده سازی از مدل های کاملا" متفاوت دیگر در این زمینه استفاده می نمایند.برنامه های فوق نسبت به کلمات متمایز، از یکدیگر شناخت لازم را نداشته و در این راستا صرفا" بدنبال "الگو" خواهند بود. این نوع برنامه ها بمنظور کاهش ظرفیت فایل ها ، با دقت الگوها را انتخاب و آنها را در دیکشنری مستقر می نمایند. در صورتیکه از دیدگاه فوق فرآیند فشرده سازی دنبال گردد ، در نهایت با یک دیکشنری کاملا" متفاوت با آن چیزی که قبلا” ایجاد شده بود ، مواجه خواهیم بود.
اگر یک برنامه فشرده سازی عبارت معروف اشاره شده در بخش قبل را بمنظور یافتن افزونگی ، پیمایش نماید ، پس از دنبال نمودن بخشی از عبارت (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) ، بدلیل عدم وجود الگوهای تکرار شونده ، بخوبی فشرده نخواهند گردید.
در صورتیکه فایلی دارای تعداد زیادی الگوی تکرار شونده باشد ، میزان افزونگی اطلاعات موجود در فایل به طرز محسوسی ظرفیت فایل را افزایش خواهد داد. بدین ترتیب در زمان فشرده سازی این نوع از فایل ها با توجه به وجود الگوهای تکرار شونده ، ظرفیت فایل در حد قابل قبولی کاهش پیدا خواهد کرد .
میزان فشرده سازی اطلاعات، به الگوریتم استفاده شده توسط برنامه فشرده سازی نیز بستگی دارد. بدیهی است استفاده از یک الگوریتم با کارآئی بالا ، نتایج مثبتی را در رابطه با فشرده سازی به ارمغان خواهد آورد.