تبلیغات

سرو کوهی - الگوریتم فشرده سازی هافمن
برای بهتر فهمیدن بیشتر بدانیم.
درباره وبلاگ


سخن روز

آرشیو

طبقه بندی





آخرین پستها

ساعت فلش

پیوندهای روزانه

نویسندگان

ابر برچسبها

نام شما :
ایمیل شما :
نام دوست شما:
ایمیل دوست شما:

Powered by web-abzar.ir
نظرسنجی



ابزار آپلود



آمار وبلاگ

الکسا


 ابزارهای زیبا سازی برای سایت و وبلاگ
Admin Logo
themebox


سلام.
همیشه در پشت صحنه های قواعد پیشرفته در تکنولوژی اتفاقات ساده و بعضی ناگهانی ای وجود دارند.

با اینکه شاید این داستان تکراری دیوید هافمن دیگر جذابیتی نداشته باشد...  وی در سال 1951  در کلاس درس " تئوری اطلاعات" در دانشگاه MIT ، بین دادن امتحان پایانی و یا  تحقیق درباره پیدا کردن کارآمدترین کد دودویی یکی را بایستی انتخاب می کرد .هافمن ناتوان در پیدا کردن کارآمدترین روش کد دودویی،
تصمیم گرفته بود خودش را برای امتحان پایانی آماده کند که متوجه شد چرا خود روشی را ابداع نکند؟ روش هافمن، استفاده از درخت دودویی مرتب شده با استفاده از تکرار بود. کد او در مقایسه با مبدع تئوری اطلاعات، Claude Shannon که برای ساختن کدی مشابه کار کرده بود سبقت گرفت. در روش هافمن بجای ساخته شدن از بالا به پایین ، از پایین به بالا ساخته می شد...

حالا زمان آن رسیده که باید بدانیم یک الگوریتم فشرده سازی چه می کند ؟

ساده است. فشرده سازی داده ها ! اما یک الگوریتم فشرده سازی ثابت برای هر نوع داده ای جوابگو نخواهد بود ( مگر در صورت اعمال مستقیم بر روی بیت ها ، که اینجا قصد مطرح کردن این مسئله را نداریم و در یک پست دیگر به آن خواهیم پرداخت ).
بطور مثال الگوریتم هافمن برای فشرده سازی فایلهای متنی استفاده می شود و وابسته به کاراکترهای موجود در متن می تواند از ۲۰ تا ۹۰ در صد، یک فایل را فشرده کند.‬ از آنجا این الگوریتم به شکلی حریصانه ای در مغز نفوذ کرد 
انواع مختلفی از کدگذاری هافمن به وجود آمد ؛که بعضی از آنها از الگوریتم‌هایی شبیه الگوریتم هافمن و بعضی دیگر از کد‌های بهینهٔ پیشوندی (با محدودیت‌های خاص برای خروجی)استفاه می‌کنند. در حالت اخیر، نیاز نیست که روش، شبیه روش هافمن باشد و حتی ممکن است زمان اجرایی چند‌جمله‌ای هم نداشته باشد. مانند کدهافمن با طول محدود ( این نوع هنگامی مورد استفاده قرار می‌گیرد که هدف هنوز بدست آوردن طول مسیر با کمترین وزن است اما یک شرط دیگر نیز وجود دارد و آن این است که اندازهٔ هر کد، باید کمتر از مقدار ثابت خاصی باشد) ، کد هافمن انطباقی (  احتمالاتی را که به صورت پویا و بر اساس تکرار واقعی در منبع اصلی است، محاسبه می‌کند. این به گونه‌ای مربوط به خانوادهٔ الگوریتم‌های LZ است ) و....


فرض کنید فایلی شامل صد هزار کاراکتر داریم و می خواهیم آن را با کمترین حجم ذخیره کنیم و این متن تنها شامل ۶ نوع کاراکتر بوده و حرف a به تعداد ۴۵۰۰۰ بار تکرار شده.
روش های فراوانی برای نمایش این نوع فایل ها وجود دارد، ما می خواهیم هر کاراکتر را بصورت یک کد باینری یکتا نمایش دهیم. اگر ما از کدهای هم اندازه برای نمایش استفاده کنیم، نیاز به ۳بیت احتیاج داریم تا بتوانیم ۶ کاراکتر را نمایش دهیم.
این روش نیاز مند ۳۰۰۰۰۰ بیت برای کد کردن این متن می باشد. راه های بهتری نیز وجود دارد؟


در کامپیوتر برای هر کاراکتری، یک کد با استاندارد ASCII  بین 0  تا 255 در نظر گرفته می شود.که به هفت بیت فضا نیاز دارد.مثلا برای نمایش حرف A از عدد 65  استفاده می شود.که در مبنای 2 به صورت 1000001 درخواهد آمد و در نتیجه برای ذخیره شدن به 7 بیت فضا نیاز دارد.که در این صورت رشته   AAAکه متشکل از 3 حرف A است به فضایی معادل 3*7=21 بیت نیاز دارد.

 خب ،
کلید کار اینجاست که کددهی با طول های متفادت روش بهتری از کدهای هم اندازه می باشد.
این به آن معناست که نماد های مجزا (برای نمونه کاراکترهایی در یک فایل متنی) با رشته بیت هایی که طول های مختلفی دارند تعویض می شود. بنابراین نماد هایی که زیاد در یک فایل تکرار می شوند یک رشته بیت کوتاه می گیرند در حالی که نمادهای دیگر که به ندرت دیده می شوند رشته بیت طولانی تری رامی گیرند... و صرفه جویی در مصرف بیت ها باعث کوتاه تر شدن رشته ما خواهد شد. حال فرض کنید روشی وجود داشته باشد که A را به کدی بسیار کوتاه تر مانند 1 ترجمه کنیم و مجموعا 3 بیت استفاده کنیم... هافمن کاری شبیه به این عمل را به صورت یک الگوریتم در آورده است.


در کد کذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام کد‌های بدون پیشوند(گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکتر‌های پرکاربرد تر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.

هافمن موفق شد کارآمد ترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نماد‌های اصلی با آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند. بعدها روشی برای انجام این کار پیدا شد که این کار را در زمانی خطی انجام می‌داد.

این
یک الگوریتم کد‌گذاری برای فشرده‌سازی بی‌اتلاف اطلاعات است. یعنی شما بخشی از کد اصلی داده را از دست نخواهید داد.

بر خلاف عادت این الگوریتم اجرای بسیار ساده ای دارد و به ساده ترین زبان ممکن :


( این حروف را به همراه تعداد تکرارشان را در نظر بگیرید )

1-   چگالی هر کاراکتر را محاسبه میکنیم (تعداد دفعات حضور کاراکتر در متن مورد نظر).

2-   دو کاراکتر با کمترین میزان تکرار (چگالی) را انتخاب میکنیم.

3-   کاراکتر های مرحله 2 را با کاراکتر جدیدی که دارای چگالی برابر با مجموع چگالی دو کاراکتر فوق است جایگزین میکنیم.

4-   تا زمانی که فقط یک کاراکتر باقی مانده باشد، به مرحله 2 میرویم.


( درخت حاصل از فرایند  )

5-   از عملیات فوق یک درخت حاصل می شود، بر روی این درخت هر مسیر به سمت چپ با 0 و

هر مسیر به سمت راست با 1 وزن دهی میشود.


( نتیجه کد گذاری )

6-   کد هر کاراکتر با کنار هم گذاشتن وزن ها از ریشه تا آن کاراکتر به دست می آید.



** نتیجتا داریم: (هر حرکت به چپ 0 و هر حرکت به راست 1)

در نمونه ذک شده با دنبال کردن مسیر از راس تا کاراکترها (ریشه تا برگ ها) کد های جدید به دست خواهند آمد؛ کدهای جایگزین به دست آمده برای این مثال به شکل زیر است:

E: 00

M: 0100

W: 0101

C: 0110

H: 01110

U: 01111

N: 100

I: 1010

T: 1011

_: 110

S: 111


حال با چینش کد هر کاراکتر در متن کد نهایی فشرده هافمن متن مورد نظر به دست آمده است.


درعلوم کامپیوتر و تئوری اطلاعات، کد‌گذاری هافمن یک الگوریتم کد‌گذاری برای

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

Detect language » Hungarian
Detect language » Hungarian


نوشته شده توسط :The Faludah
جمعه 18 اردیبهشت 1394-10:16 ق.ظ

Online cialis
شنبه 18 فروردین 1397 09:49 ق.ظ

Many thanks! A lot of tips.

weblink price cialis comprar cialis navarr cialis generika rezeptfrei cialis apotheke il cialis quanto costa cialis pas cher paris buy cheap cialis in uk rx cialis para comprar cialis 20 mg best price cialis 5 mg effetti collateral
Cialis pills
شنبه 4 فروردین 1397 09:36 ق.ظ

Thanks, Numerous write ups!

cialis herbs cialis sans ordonnance viagra vs cialis cialis 5mg prix generic cialis with dapoxetine acheter cialis kamagra cialis price thailand cialis kaufen bankberweisung low dose cialis blood pressure cialis generique
kimberdome.wordpress.com
دوشنبه 23 مرداد 1396 03:50 ب.ظ
I must thank you for the efforts you have put in penning this blog.

I'm hoping to view the same high-grade blog posts from you
in the future as well. In truth, your creative writing abilities has inspired me to get my
own website now ;)
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر