اگر رشته abcabbaccaabdffee را با روش کدینگ هافمن کد کنیم ، طول کد چند بیت خواهد شد؟
سلام دوست من
الگوریتم هافمنو بزن
اول که فراوانیاشونو در بیار(مثلا a 5بار تکرار شده) بعد صعودی مرتب کن بعد دوتای اولو با هم جمع کن و جمعشونو پدراین دوتا بگیر و بجای اون دوتا تولیست بذار و دوباره مرتب کن(نکتش اینه) حالا اینکارو ادامه بده،عمق درختمون جوابه که ۴ میشه
البته این نظر منه
موفق باشید
سلام .
برای حل این سوال ابتدا باید درخت هافمن رو بکشیم که به صورت زیر هستش: (البته با یکی دوبار بی دقتی و ویرایش ارسال)
[attachment=8398]
در ادامه به ازای هر تعداد کاراکتری که به یک اندازه طول بیت نیاز دارند، باید جمع فراوانی های این کاراکترها رو ضربدر تعداد بیتهای مورد نیازشان بشه و مجموع کل این اعداد میشه کل طول بیت .
[tex](d,e) \Rightarrow 4 bit \Rightarrow (1 2)*4bit=12[/tex]
[tex](f) \Rightarrow 3 bit \Rightarrow (2)*3bit=6[/tex]
[tex](b,c) \Rightarrow 3 bit \Rightarrow (4 3)*2bit=14[/tex]
[tex](a) \Rightarrow 1 bit \Rightarrow (5)*2bit=10[/tex]
[tex](f) \Rightarrow 3 bit \Rightarrow (2)*3bit=6[/tex]
[tex](b,c) \Rightarrow 3 bit \Rightarrow (4 3)*2bit=14[/tex]
[tex](a) \Rightarrow 1 bit \Rightarrow (5)*2bit=10[/tex]
و مجموع این اعداد یعنی [tex]42[/tex] میشه کل طول کد بیت .
البته توی تست فراوانی e یکی در نظر گرفته شده که جواب میشه ۳۸ ولی توی صورت سوال شما ۲ تا e دیده میشه که جواب شده ۴۲
اول از همه با استفاده از الگوریتم هافمن درخت دودوییش رو می کشیم
به فرزندان هر گره ۰ و ۱ رو نسبت می دیم ( که توی هر سطح وقتی از یکی از این ۰ ها یا ۱ ها رد میشیم یک بیت حساب میشه )
بر اساس سطحی که هر کدوم از برگ ها قرار داره می تونیم تعیین کنیم که اون برگ چند بیت نیاز داره مثلا توی این شکلa دو(۲) بیت نیاز داره و کدش میشه ۱۰ و همچنین d چهار بیت نیاز داره و کدش میشه ۱۱۱۰ و همچنین این کد رو باید در تکرارشون هم ضرب کنی مثلا ۲ بیت a رو باید در ۵ که تکرارشه ضرب کنی که میشه ۱۰ بیت پس برای a ما در کل به ۱۰ بیت نیاز داریم و در نهایت جواب کلی میشه ۴۲ بیت که طول کد ماست
شکل رو نگاه کن اگه سوالی داشتی بگو
[attachment=8397]
سلام
از پاسخهاتون ممنونم،سوتیمو فهمیدم
(۲۲ آذر ۱۳۹۱ ۱۰:۵۹ ق.ظ)jafarir نوشته شده توسط: abcabbaccaabdffeeاین سئوال یکی از کنکورها بوده.یه دونه e اضافه نوشتید.درستش اینه abcabbaccaabdffe