سلام دوستان
این سوال و از الگوریتم هافمن رفته. راه حلش و فهمیدم و جدای آخرش که ۲ رو یادش رفته تو فرمول بزاره بقیش درسته. اما سوالم اینه دقیقا چجوری فهمید از این راه باید رفت؟ من پارسه دارم شاید توش نباشه. شما بارِ اول سوال و دیدین فهمیدین الگوریتم هافمنِ؟
صفحه سوال برام باز نمیشه. اما احتمالا همون سوالیه که فکر میکنم. اگه حرف از احتمال حرف زد نرخ تولید رو براساس کاراکتر داد، باید دید کاراکتر چند بیته. به همین خاطر باید با استفاده از هافمن کاراکتر رو به بیت تبدیل کرد.
Sent from my SM-T210R using Tapatalk
(17 بهمن 1392 12:23 ب.ظ)hoomanab نوشته شده توسط: [ -> ]صفحه سوال برام باز نمیشه. اما احتمالا همون سوالیه که فکر میکنم. اگه حرف از احتمال حرف زد نرخ تولید رو براساس کاراکتر داد، باید دید کاراکتر چند بیته. به همین خاطر باید با استفاده از هافمن کاراکتر رو به بیت تبدیل کرد.
فکر کنم واسه شما مشکل داره چون عکس سوال واسه من باز میشه.
کاربرد دیگه ای هم داره واسه شبکه؟ سوال دیگه ای دیدین ازش؟ یعنی درواقع شبیه همون پارامتر هایی که تو ساختمان داده واسه الگوریتم هافمن بهمون میدن تو سوال دیدم ازین راه برم؟
هروقت صحبت از کم ترین بیت برای نسبت دهی به علائم شد از هافمن استفاده میکنیم.
(17 بهمن 1392 01:04 ب.ظ)bermoda14 نوشته شده توسط: [ -> ]هروقت صحبت از کم ترین بیت برای نسبت دهی به علائم شد از هافمن استفاده میکنیم.
نکته جالبی بود، آفرین، کاملا هم بدیهیِ دلیلش ، مرسی ;-)
Sent from my ME172V using Tapatalk
وقتی گفته حداقل سطوح یعنی کمترین تعداد بیت مورد نیاز، میتونی احتمالات رو ضربدر 100 کنی و بنویسی و درخت هافمن تشکیل بدی و بعد تعداد بیت های مورد نیاز رو بدست بیاری و ضربدر احتمالشون بعد ضربدر 100 بکنی تا کل بیت های لازم برای ارسال برای یک دوره رو بدست بیاری، حالا با توجه به دیگر ویژگی های سوال حداقل تعداد سطوحی رو بدست بیاری که بتونه این اعطلاعات رو در زمان لازم عبور بده
(17 بهمن 1392 01:10 ب.ظ)Falcon نوشته شده توسط: [ -> ]وقتی گفته حداقل سطوح یعنی کمترین تعداد بیت مورد نیاز
قبوله
(17 بهمن 1392 01:10 ب.ظ)Falcon نوشته شده توسط: [ -> ]میتونی احتمالات رو ضربدر ۱۰۰ کنی و بنویسی و درخت هافمن تشکیل بدی و بعد تعداد بیت های مورد نیاز رو بدست بیاری
میشه ۵۰ و ۲۵ و ۱۲/۵ و ۱۲/۵ که درختشم کشیدم درست بود.
(17 بهمن 1392 01:10 ب.ظ)Falcon نوشته شده توسط: [ -> ]و ضربدر احتمالشون بعد ضربدر ۱۰۰ بکنی تا کل بیت های لازم برای ارسال برای یک دوره رو بدست بیاری، حالا با توجه به دیگر ویژگی های سوال حداقل تعداد سطوحی رو بدست بیاری که بتونه این اعطلاعات رو در زمان لازم عبور بده
ها؟ :-o
یک دوره رو حساب میکنیم که چند بیت لازم داریم، مثلا اگر احتمالات 1/50 و 1/25 و 1/25 بود یعنی اینکه یک دوره ارسال میتونه بصورت 4 بیت ( 2 بیت برای 1/50 ، یک بیت برای 1/25 و یک بیت برای 1/25 بعدی ) نیاز داریم.
پس جمعا 4 بیت باید بفرستیم تا تمام احتمالات رو دربر بگیره، حالا فرض کنید که گفته 1000 علامت در ثانیه تولید میشه، یعنی 500 تا از نوع دوم و 2 تا 250 تایی از نوع اول و دوم . از روی این اطلاعات سرعت مورد نیاز رو بدست میاریم، 500 تا از نوع اول که مثلا 2 بیت میخواد، 250 تا هم از نوع دوم که مثلا 3 بیت میخواد و نوع سوم ...
بیت ریت مورد نیاز رو بدست میاریم و بعد ادامه ماجرا دیگه ...
(17 بهمن 1392 02:46 ب.ظ)Falcon نوشته شده توسط: [ -> ]یک دوره رو حساب میکنیم که چند بیت لازم داریم، مثلا اگر احتمالات ۱/۵۰ و ۱/۲۵ و ۱/۲۵ بود یعنی اینکه یک دوره ارسال میتونه بصورت ۴ بیت ( ۲ بیت برای ۱/۵۰ ، یک بیت برای ۱/۲۵ و یک بیت برای ۱/۲۵ بعدی ) نیاز داریم.
پس جمعا ۴ بیت باید بفرستیم تا تمام احتمالات رو دربر بگیره، حالا فرض کنید که گفته ۱۰۰۰ علامت در ثانیه تولید میشه، یعنی ۵۰۰ تا از نوع دوم و ۲ تا ۲۵۰ تایی از نوع اول و دوم . از روی این اطلاعات سرعت مورد نیاز رو بدست میاریم، ۵۰۰ تا از نوع اول که مثلا ۲ بیت میخواد، ۲۵۰ تا هم از نوع دوم که مثلا ۳ بیت میخواد و نوع سوم ...
بیت ریت مورد نیاز رو بدست میاریم و بعد ادامه ماجرا دیگه ...
مرسی قشنگ گفتی. من این راه حل رو یبار بداهه رو یه سوال پیاده کردم اما بعد یادم رفته بود چیکار کردم
بهترین همینه.
خوب شد این سؤالو پرسیدی....من از پایه یعنی کدینگ هافمنش مشکل دارم x_x
مثلا بگه 6 تا علامت مختلف با احتمال وقوع 2 تا از انها 0.25 و 4تاشون 0.125 چطورکی میشه ؟ نرخ تولید علائم 1000علامت در ثانیه و حداقل نرخ ارسالو خواسته
سؤالم مال 86 إ
یک درخت هافمن نیاز دارید، درخت و بکشی و علامت هارو بیت گزاری کنی مشخص میشه هرکدوم چند بیت می خوان
من هر بار حل می کنم جوابو ۱۶ بدست میارم
ولی گزینه ۲ درسته (سنجش)
مجموع سه عدد برام میشه ۱۵۰۰۰۰+۵۰۰۰۰+۵۰۰۰۰=۲۵۰۰۰۰
که در ثانیه میشه ۲۵۰۰۰۰/۶۰=۴۱۶۶
و با جاگذاری تو فرمول لگاریتم حدودای ۱۶ بدست میاد
اشتباهم می کنم کجاست؟
درخت هافمن رو رسم کنید برای 1/2 یک بیت و برای 1/4 دو بیت و برای 1/8 ها 3 بیت.
حالا برای یک ثانیه بدست میاریم :
100 هزار علامت در دقیقه میشه حدودا 1666 علامت در ثانیه
که 1/2 مش 1 بیت ، 1/4 مش 2 بیت و 2 تا 1/8 مش 3 بیت میخواد
((1666/2)*1 + (1666/4)*2 + (1666/8)*2*3) = 2915
در هر ثانیه 2915 بیت نیاز داریم
2915 = 2*1k*log2(M)
کمترین M ای هم که در این معادله صدق میکنه از توی جوابا 4 هست.