پاورپوینت هافمن

بخشی از پاورپوینت

اسلاید 2 :

هافمن
.کد هافمن
.الگوریتم هافمن

اسلاید 3 :

درعلوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن یک الگوریتم کدگذاری برای فشردهسازی بیاتلاف اطلاعات است.
این تعبیر بر میگردد به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از نشانههای مبدا (مانند نویسههای یک پرونده). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشانهای مبدا بدست میآید. این روش بوسیله دیوید هافمن توسعه یافت. وی دانشجوی دوره دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقاله «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.

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

معرفی،تاریخچه

اسلاید 4 :

روش متداول نمایش فایل، کد دودیی است که در این کد، هر کاراکتر با رشته دودویی منحصر بفردی نمایش داده می شود که کدکلمه نام دارد.
[مثال]
{a,b,c}
تعداد کاراکتر = 3 22 ≥ 3 ≤ 21 پس برای هر کاراکتر به 2 بیت برای کدگذاری نیاز داریم
a: 00b: 01c: 11
.: در کد دودویی با طول ثابت، طول کد تمام کاراکتر ها ثابت است:.
ababcbbbc
000100011101010111
18 بیت
کد گذاری

اسلاید 5 :

.: در کد دودویی با طول متغیر، میتوان کدگذاری مؤثرتری پیدا کرد:.
در چنین کدی، طول کد هر کاراکتر، ممکن است متفاوت از دیگری باشد.
در مثال قبل . ( مجموعه ی {a,b,c} و رشته ی ababcbbbc) با توجه به تکرار بیشتر b داریم.:
a: 10b: 0c: 11
ababcbbbc
1001001100011
13 بیت
کد گذاریادامه.

اسلاید 6 :

نوع خاصی از کد طول متغیر است.
هیچ کلمه کد مربوط به یک کاراکتر، آغاز کلمه کد کاراکتر دیگر را نمی سازد.
هر کد پیشوندی را می توان با یک درخت دودیی نمایش داد که برگهای آن، کاراکترهایی است که باید کد شوند.
a: 10b: 0c: 11
کدهای پیشوندی

اسلاید 7 :

Bits(C1)=16*3+5*3+12*3+17*3+10*3+25*3=255
Bits(C2)=16*2+5*5+12*4+17*3+10*5+25*1=231
Bits(C3)=16*2+5*4+12*3+17*2+10*4+25*2=212

اسلاید 8 :

فرض کنیم A,B,C,D,E,F,G,H ، 8 عنصر اطلاعاتی با وزن ها ی مشخص شده هستند:
[مثال]
روش هافمن

اسلاید 14 :

Struct nodetype
{
char symbol;
int frequency;
nodetype* left;
nodetupe* right;
}
باید از صف اولویت استفاده کرد.
در صف اولویت، عنصوری با بالاترین اولویت، زودتر از همه خارج می شود.
در اینجا، اولویت بیشتر، مربوط به کاراکتریست که کمترین فراوانی را در فایل دارد.
الگوریتم هافمن

اسلاید 15 :

تعداد کاراکتر های موجود در فایل = n
بنابراین، تعداد n اشاره گر به رکوردهای nodetype را در صف اولویت PQ
به این صورت تنظیم می کنیم؛ برای هر اشاره گر مثل p داریم:
p->symbol = کاراکتری در فایل

p->frequency = فراوانی آن کاراکتر در فایل

p->left = p->right = NULL
الگوریتم هافمنادامه.

اسلاید 16 :

for(i=1;i<=n-1;i++){
remove(PQ,p);
remove(PQ,q);
r = new nodetype;
r->left = p;
r->right = q;
r->frequency = p->frequency + q->frequency;
insert(PQ,r);
}
remove(PQ,r);
Return r;
الگوریتم هافمنادامه.

اسلاید 17 :

[مثال پایانی.]
0110101010001011111100010111110100010111
0001001001001111001111001000111001101101
1110101111010001111101110101110100010
111011011000000000

اسلاید 18 :

0110101010001011111100010111110100010111
0001001001001111001111001000111001101101
1110101111010001111101110101110100010
111011011000000000
[تمرین کلاسی]

اسلاید 19 :

تشکر