بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
فشرده سازی متن فارسی با استفاده از الگوریتم های حسابی و هافمن و مقایسه آن با
فشرده سازی متن انگلیسی
چکیده - در این مقاله فشرده سازی متن فارسی و تحلیل های آماری متن فارسی مورد بررسی قرار گرفته اند و دو الگوریتم معروف هافمن و حسابی با استفاده از انواع و مراتب مختلف مدلها برای فشرده سازی متن فارسی پیاده سازی شده و از لحاظ میزان و سرعت فشرده سازی با هم مقایسه شده اند. این بررسی ها همچنین در مورد متن انگلیسی نیز انجام شده اند و نتایج آنها باهم مقایسه شده است. نتایج بدست آمده نشان می دهد که با وجود میزان فشردهسازی کمتر الگوریتم هافمن نسبت به الگوریتم حسابی (در حد ۲-۳ درصد) سرعت اجرای آن در حدود ۴۰-۵۰ برابر بیشتر از سرعت اجرای الگوریتم حسابی می باشد. همچنین این نتایج نشان میدهد که با توجه به آنتروپی بالاتر متن فارسی نسبت به متن انگلیسی، متن فارسی دارای قابلیت فشرده پذیری کمتری نسبت به متن انگلیسی است. با استفاده از این نتایج برای الگوریتم حسابی وفقی طول بهینه ی هر بلوک برای کدگذاری متن با تقسیم بندی آن به بلوکهای با
طول ثابت، بدست آمد.
کلید واژه - انتروپی، الگوریتم حسابی، الگوریتم هافمن، فشرده سازی
۱- مقدمه
یکی از مهمترین نوع اطلاعاتی که هر روزه شاهد ارسال و دریافت و نیاز به ذخیره سازی بالاتر ان هستیم، فایلهای متنی می باشند. اصولا تئوری اطلاعات Information TheOry به طور کلی توسط کلود الوود شالینی ( Claude ElWOOd ShannOn) در سال ۱۹۴۸ در مقاله ای تحت عنوان "تئوری ریاضی ارتباطات " بر اساس این نوع اطلاعات پایه ریزی شد [ ۱]. طی سالهای اخیر الگوریتم های فشرده سازی مختلفی ابداع شده و مورد استفاده قرار گرفته اند. این الگوریتمها به دو دسته کلی باتلافی (LOSSy) و بدون اتلاف (s LOSSle) تقسیم می شوند. واضح است که در فشرده سازی متن باید از روشهای فشرده سازی بدون اتلاف استفاده کرد. گرچه می توان الگوریتم خاصی را متصور شد که مفهوم یک متن را درک کند و آن مفهوم را انتقال دهد و خود متن را کلمه به کلمه فشرده نکند. اما آنچه که در اینجا مد نظر می باشد قابلیت بازیابی کامل و بدون نقص متن
فشرده شده می باشد. برای فشرده سازی متن چندین الگوریتم وجود دارد از جمله الگوریتم هافمن (Huffman) [۲]، الگوریتم حسابی (Arithmetic) [۳، ۴، ۵]، الگوریتم لمپل - زیو (Lempell-Ziv) [۶] و غیره. در این مقاله در ابتدا در بخش ۲ به بررسی مدل احتمالاتی متن فارسی و انگلیسی می پردازیم و آنتروپی مراتب مختلف متن فارسی و انگلیسی را بررسی می کنیم. در بخش ۳ به شرح پیاده سازی الگوریتم های حسابی و هافمن می پردازیم. و در بخش ۴ نتایج پیاده سازی روشهای مختلف کدگذاری حسابی و هافمن را بر روی ۱۰ فایل فارسی و ۱۰ فایل انگلیسی، ارائه می کنیم.
۲- تحلیل آماری متن فارسی
به منظور انجام مطالعات آماری متن فارسی، با طراحی یک نرم افزار جداگانه، توزیعات اماری و احتمالات مراتب اول، دوم و سوم متن فارسی با شمارش کاراکترهای ۳۲ حرف اصلی حروف الفبای فارسی به علاوه کاراکتر فاصله از فایلهای متن فارسی که از سایتهای مختلف خبری گرفته شده بود، بدست امده است. در واقع این امار به عنوان مدل ایستا (Static) استفاده می شود. در جدول ۱ مدل مرتبه اول متن فارسی نشان داده شده است. در جدول ۲ مدل ه اول متن انگلیسی که از مرجع [۷] گرفته شده است آمده است.
بر اساس آمار استخراج شده، طول متوسط کلمات فارسی فارسی برابر با ۳/۹۱ کاراکتر و طول متوسط کلمات انگلیسی برابر با ۴/۷ کاراکتر می باشد.
۱-۲ آنتروپی اطلاعات متن فارسی و انگلیسی
شانان ثابت می کند که آنتروپی بیانگر متوسط میزان اطلاعات موجود در هر کاراکتر (برحسب بیت بر کاراکتر) می
باشد و بنابراین حد بالای نرخ فشرده سازی یک متن (برحسب بیت بر کاراکتر) برابر با آنتروپی آن میباشد [۱] بعد از بدست آوردن آمارگان مورد نیاز [۸]، با استفاده از روابط (۱) تا (۳)، آنتروپی مراتب ۱ تا ۳ مدل ایستای متن فارسی و انگلیسی محاسبه شده و در جدول ۳ نمایش داده شده است. همچنین برای مقایسه و بررسی بهتر کارایی الگوریتمهای فشرده سازی، آنتروپی مراتب مختلف هر یک از ۱۰ فایل فارسی و ۱۰ فایل انگلیسی مورد ازمحاسبه شده و در جداول ۴ و ۵ آمده است.
m تعداد کاراکترهای مجموعه الفبا و P احتمال وقوع کاراکتر می باشد.
۳- پیاده سازی الگوریتم ها
پیاده سازی الگوریتمها تحت محیط برنامه نویسی Visual 6.0 Basic و به صورت یک نرم افزار کلی شامل پیاده سازی بخش مدل کننده و پیاده سازی الگوریتمهای کدکننده و دیکدکننده هافمن و حسابی که قابل اجرا در محیط ویندوز می باشد، انجام شده است. برای پیاده سازی بخشی مدل کننده چندین روش مختلف وجود دارد: مدل ایستا (Static) : در این مدل از یک توزیع احتمالات ثابت برای تمام فایل ها استفاده می شود و در حین کدگذاری هیچ تغییری نمی کند. مدل نیمه ایستا (Semi-Static): در این مدل ابتدا با یک بار پردازش بر روی فایل توزیع احتمالات آن استخراج شده و در مرتبه دوم فایل کدگذاری می شود. مدل وفقی (Adaptive): در این مدل از یک توزیع احتمال ساده و اولیه شروع به کدگذاری می کنیم و با هر n کاراکتر جدیدی که از منبع خوانده می شود توزیع احتمالات آن به روز شده و دقیق تر می شود. هر یک از این نوع مدل ها را می توان به صورت مدل حالت محدود (Finite State Model)، مدل گرامری و یا مدل ارگادیک (ErgOdic Model) پیاده سازی کرد [۹] اما مدلی که از بیش از همه مورد استفاده قرار می گیرد مدل حالت محدود است که شکلی از مدل مارکوف ( MarkOv Model) می باشد. در مدل مرتبه n ام مارکوف، احتمال نمونه جاری (مثلاً یک کاراکتر) وابسته است بهn نمونه قبلی، در این نرم افزار، مدل های ایستا، نیمه ایستا و وفقی به صورت هر یک از مراتب ۱، ۲ و ۳ ام مارکوف پیاده سازی شده اند.
الگوریتم حسابی به دو روش استفاده از اعداد حقیقی (Real Implementation) و استفاده از اعداد صحیح (Integer Implementation) پیاده سازی شده است. در الگوریتم حسابی حقیقی، کلیه محاسبات با استفاده از اعداد حقیقی اعشاری انجام می شود که این امر نیازمند یک پردازنده قوی با توانایی انجام عملیات محاسباتی اعشاری با ممیز شناور، می باشد || ۳ || اما با پذیرفتن کاهش بسیار ناچیزی (درحد چند بیت) در کارایی الگوریتم حسابی، می توان محاسبات را با استفاده از اعداد صحیح انجام داد و هزینه های سخت افزاری را کاهش داد [۵،۴] در نرم افزار طراحی شده، با استفاده از الگوریتم حسابی می توان یک فایل را به ۳ حالت مختلف کدگذاری کرد. کل فایل به عنوان : ۱- یک بلوک، ۲- چندین بلوک با طول ثابت و ۳چندین بلوک با طول متغیر (کلمه به کلمه). بنابراین با استفاده از این نرم افزار میتوان یک فایل را به ۶×۹ =۵۴ حالت مختلف با استفاده از الگوریتم حسابی کد کرد. همچنین هر فایل را می توان با استفاده از الگوریتم هافمن در ۶ حالت مختلف شامل مراتب ۱، ۲ و ۳ مدلهای ایستا و نیمه ایستا کد کرد. در محیط این نرم افزار، گزینه های مختلفی برای تعیین نوع کدگذاری و نوع مدل و مرتبه آن قرار داده شده است. بنابراین در کل هر فایل را می توان به ۶۰ حالت مختلف کد کرده و فشرده سازی آن را مورد بررسی قرار داد. با استفاده از این نرم افزار، می توان الگوریتمها را هم بر روی متون فارسی و هم متون انگلیسی اجرا کرد. دیگر مزیت این برنامه قابلیت استفاده از ان برای کدگذاری متون عربی ( با انتخاب گزینه Far Si) می باشد.
۴- نتایج بررسی الگوریتمهای فشرده سازی
برای بررسی دقیق الگوریتمهای فشرده سازی هافمن و حسابی، در کل ۲۵۸۰ آزمایش مختلف بر روی ۲۰ فایل فارسی و انگلیسی انجام شده است. در این مقاله فقط چکیده این نتایج ارائه می شود. شرح کامل نتایج در [۸] ارائه شده به منظور هماهنگی با واحد محاسبه آنتروپی، نرخ کدگذاری بر حسب بیت بر کاراکتر محاسبه شده و نمایش داده شده است. همپنین در کنار نتایج کدگذاری هافمن و حسابی نرخ فشرده سازی حاصل از نرم افزار WinRAR (بر حسب بیت بر کاراکتر) نیز نمایش داده شده است.
۱-۴- نتایج فشرده سازی متن فارسی
نتایج کدگذاری هافمن و حسابی براساس مدل مرتبه ۳نیمه ایستا می باشد.
۴- ۲- نتایج فشرده سازی متن انگلیسی
نتایج کدگذاری هافمن و حسابی براساس مدل مرتبه ۳نیمه ایستا می باشد.
