مشاهده

Report
1
‫‪.‬‬
‫‪.‬‬
‫کد هافمن‬
‫الگوریتم هافمن‬
‫‪2‬‬
‫معرفی‪،‬تاریخچه‬
‫‪][ .‬‬
‫درع لوم کامپیوتر و ت ئوری اطال عات‪ ،‬کد گذاری هافمن یک ال گوریتم کد گذاری برای ف شرده سازی بیا تالف‬
‫اطالعات است‪.‬‬
‫ا ین تعب یر بر می گردد به ا ستفاده از جدول کد طول متغ یر برای کد کردن هر کدام از ن شانه های م بدا‬
‫(مانند نویسه های یک پرونده)‪ .‬جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشان های‬
‫مبدا بدست میآید‪ .‬این روش بوسیله دیوید هافمن توسعه یافت‪ .‬وی دانشجوی دوره دکتری در دانشگاه ‪MIT‬بود و در‬
‫سال ‪ ۱۹۵۲‬مقاله «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد‪.‬‬
‫در کدگذاری هافمن‪ ،‬از روشی خاص برای انتخاب نحوه نمایش هر نماد استفاده می شود‪ .‬روشی به نام کدهای بدون‬
‫پیشوند(گاهی هم روش «کدهای پیشوندی» گفته میشود‪ .‬یعنی در این روش رشتهای که نشان دهنده یک نویسه خاص‬
‫است هیچ گاه پیشوند رشته دیگر که نمایانگر نویسه دیگر است‪ ،‬نمیباشد‪ .).‬در این روش نویسه های پرکاربردتر با‬
‫رشتههای بیتی کوتاهتری نسبت به آنهایی که کاربردشان کمتر است‪ ،‬نشان داده میشوند‪.‬‬
‫هافمن موفق شد کارآمدترین روش فشرده سازی از این نوع را طراحی کند‪ :‬نگاشت نکردن نشان های منفرد م بدا به‬
‫رشته های بیتی یکتا‪ ،‬هر گاه تعداد تکرار نمادهای ا صلی با آن هایی که برای ایجاد ا ین کد مورد استفاده قرار گرفت ند‬
‫مطابقت کند‪ ،‬خروجیهایی با اندازه کمتر تولید میکند‪.‬‬
‫‪3‬‬
‫‪ .‬کد []گذاری‬
‫روش متداول نمایش فایل‪ ،‬کد دودیی است که در این کد‪ ،‬هر کاراکتر با رشته دودویی منحصر بفردی نمایش داده می‬
‫شود که کدکلمه نام دارد‪.‬‬
‫[مثال]‬
‫تعداد کاراکتر = ‪3‬‬
‫}‪{a,b,c‬‬
‫‪۲۱ ≤ 3 ≥ ۲۲‬‬
‫پس برای هر کاراکتر به ‪ ۲‬بیت برای کدگذاری نیاز داریم‬
‫‪ :.‬در کد دودویی با طول ثابت‪ ،‬طول کد تمام کاراکتر ها ثابت است‪.:‬‬
‫‪ ۱8‬بیت‬
‫‪4‬‬
‫‪c: 11‬‬
‫‪000100011101010111‬‬
‫‪b: 01‬‬
‫‪a: 00‬‬
‫‪ababcbbbc‬‬
‫کد گذاریادامه‪...‬‬
‫[]‬
‫‪.‬‬
‫‪ :.‬در کد دودویی با طول متغیر‪ ،‬میتوان کدگذاری مؤثرتری پیدا کرد‪.:‬‬
‫در چنین کدی‪ ،‬طول کد هر کاراکتر‪ ،‬ممکن است متفاوت از دیگری باشد‪.‬‬
‫در مثال قبل ‪ ( ...‬مجموعه ی }‪ {a,b,c‬و رشته ی ‪ )ababcbbbc‬با توجه به تکرار بیشتر ‪ b‬داریم‪:...‬‬
‫‪c: 11‬‬
‫‪ ۱3‬بیت‬
‫‪5‬‬
‫‪1001001100011‬‬
‫‪b: 0‬‬
‫‪a: 10‬‬
‫‪ababcbbbc‬‬
‫کدهای پیشوندی‬
‫‪][ .‬‬
‫• نوع خاصی از کد طول متغیر است‪.‬‬
‫• هیچ کلمه کد مربوط به یک کاراکتر‪ ،‬آغاز کلمه کد کاراکتر دیگر را نمی سازد‪.‬‬
‫• هر کد پیشوندی را می توان با یک درخت دودیی نمایش داد که برگهای آن‪ ،‬کاراکترهایی است که باید کد شوند‪.‬‬
‫‪c: 11‬‬
‫‪b: 0‬‬
‫‪a: 10‬‬
‫‪0‬‬
‫‪1‬‬
‫‪b‬‬
‫‪1‬‬
‫‪c‬‬
‫‪6‬‬
‫‪0‬‬
‫‪a‬‬
‫هافمن(‪)C3‬‬
‫‪C2‬‬
‫(طول ثابت)‪C1‬‬
‫فراوانی‬
‫کاراکتر‬
‫‪00‬‬
‫‪10‬‬
‫‪000‬‬
‫‪۱6‬‬
‫‪a‬‬
‫‪1110‬‬
‫‪11110‬‬
‫‪001‬‬
‫‪۵‬‬
‫‪b‬‬
‫‪110‬‬
‫‪1110‬‬
‫‪010‬‬
‫‪۱۲‬‬
‫‪c‬‬
‫‪01‬‬
‫‪110‬‬
‫‪011‬‬
‫‪۱7‬‬
‫‪d‬‬
‫‪1111‬‬
‫‪11111‬‬
‫‪100‬‬
‫‪۱0‬‬
‫‪e‬‬
‫‪10‬‬
‫‪0‬‬
‫‪101‬‬
‫‪۲۵‬‬
‫‪f‬‬
‫‪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‬‬
‫‪7‬‬
‫روش هافمن‬
‫‪][ .‬‬
‫[مثال]‬
‫فرض کنیم ‪ 8 ، A,B,C,D,E,F,G,H‬عنصر اطالعاتی با وزن ها ی مشخص شده هستند‪:‬‬
‫‪8‬‬
9
10
11
...
12
13
‫الگوریتم هافمن‬
‫‪][ .‬‬
‫• باید از صف اولویت استفاده کرد‪.‬‬
‫• در صف اولویت‪ ،‬عنصوری با باالترین اولویت‪ ،‬زودتر از همه خارج می شود‪.‬‬
‫‪Struct nodetype‬‬
‫• در اینجا‪ ،‬اولویت بیشتر‪ ،‬مربوط به کاراکتریست که کمترین فراوانی را در فایل دارد‪.‬‬
‫{‬
‫;‪char symbol‬‬
‫;‪int frequency‬‬
‫;‪nodetype* left‬‬
‫;‪nodetupe* right‬‬
‫}‬
‫‪14‬‬
‫الگوریتم هافمنادامه‪...‬‬
‫[]‬
‫‪.‬‬
‫تعداد کاراکتر های موجود در فایل = ‪n‬‬
‫بنابراین‪ ،‬تعداد ‪ n‬اشاره گر به رکوردهای ‪ nodetype‬را در صف اولویت‪PQ‬‬
‫به این صورت تنظیم می کنیم؛ برای هر اشاره گر مثل ‪ p‬داریم‪:‬‬
‫کاراکتری در فایل = ‪p->symbol‬‬
‫فراوانی آن کاراکتر در فایل = ‪p->frequency‬‬
‫‪p->left = p->right = NULL‬‬
‫‪15‬‬
...‫الگوریتم هافمنادامه‬
][
.
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;
16
‫حرف‬
x
u
r
p
o
l
t
s
n
m
i
h
f
e
a
space
‫تکرار‬
۱
۱
۱
۱
۱
۱
۲
۲
۲
۲
۲
۲
۳
۴
۴
۷
]...‫[مثال پایانی‬
0110101010001011111100010111110100010111
0001001001001111001111001000111001101101
1110101111010001111101110101110100010
111011011000000000
17
‫[تمرین کالسی]‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪1‬‬
‫‪1‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪1‬‬
‫‪0‬‬
‫‪1‬‬
‫‪0‬‬
‫‪1‬‬
‫‪0‬‬
‫‪1‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0‬‬
‫‪0110101010001011111100010111110100010111‬‬
‫‪0001001001001111001111001000111001101101‬‬
‫‪1110101111010001111101110101110100010‬‬
‫‪111011011000000000‬‬
‫‪18‬‬
‫‪][ .‬‬
‫تشکر‬
‫‪19‬‬

similar documents