[دانه کولانه]

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


در مثال ارایه شده ، تمام كلمات تكراری انتخاب و در دیكشنری قرار گرفتند. در روش

فوق ، ساده ترین مدل برای ایجاد دیكشنری استفاده شده است . برنامه های

فشرده سازی از مدل های كاملا" متفاوت دیگر در این زمینه استفاده می

نمایند.برنامه های فوق نسبت به كلمات متمایز، از یكدیگر شناخت لازم را نداشته و

در این راستا صرفا" بدنبال "الگو" خواهند بود. این نوع برنامه ها بمنظور كاهش

ظرفیت فایل ها ، با دقت الگوها را انتخاب و آنها را در دیكشنری مستقر می نمایند.

در صورتیكه از دیدگاه فوق فرآیند فشرده سازی دنبال گردد ، در نهایت با یك

دیكشنری كاملا" متفاوت با آن چیزی كه قبلا" ایجاد شده بود ، مواجه خواهیم بود.

اگر یك برنامه فشرده سازی عبارت معروف اشاره شده در بخش قبل را بمنظور

یافتن افزونگی ، پیمایش نماید ، پس از دنبال نمودن بخشی از عبارت (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۳) ، بدلیل عدم وجود الگوهای تكرار شونده ، بخوبی

فشرده نخواهند گردید.


در صورتیكه فایلی دارای تعداد زیادی الگوی تكرار شونده باشد ، میزان افزونگی

اطلاعات موجود در فایل به طرز محسوسی ظرفیت فایل را افزایش خواهد داد. بدین

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

شونده ، ظرفیت فایل در حد قابل قبولی كاهش پیدا خواهد كرد .

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

سازی نیز بستگی دارد. بدیهی است استفاده از یك الگوریتم با كارآیی بالا ، نتایج

مثبتی را در رابطه با فشرده سازی به ارمغان خواهد آورد..jalalweb.*********.com
__________________