سلام دوستان
این سوال و از الگوریتم هافمن رفته. راه حلش و فهمیدم و جدای آخرش که ۲ رو یادش رفته تو فرمول بزاره بقیش درسته. اما سوالم اینه دقیقا چجوری فهمید از این راه باید رفت؟ من پارسه دارم شاید توش نباشه. شما بارِ اول سوال و دیدین فهمیدین الگوریتم هافمنِ؟
صفحه سوال برام باز نمیشه. اما احتمالا همون سوالیه که فکر میکنم. اگه حرف از احتمال حرف زد نرخ تولید رو براساس کاراکتر داد، باید دید کاراکتر چند بیته. به همین خاطر باید با استفاده از هافمن کاراکتر رو به بیت تبدیل کرد.
Sent from my SM-T210R using Tapatalk
(۱۷ بهمن ۱۳۹۲ ۱۲:۲۳ ب.ظ)hoomanab نوشته شده توسط: صفحه سوال برام باز نمیشه. اما احتمالا همون سوالیه که فکر میکنم. اگه حرف از احتمال حرف زد نرخ تولید رو براساس کاراکتر داد، باید دید کاراکتر چند بیته. به همین خاطر باید با استفاده از هافمن کاراکتر رو به بیت تبدیل کرد.
فکر کنم واسه شما مشکل داره چون عکس سوال واسه من باز میشه.
کاربرد دیگه ای هم داره واسه شبکه؟ سوال دیگه ای دیدین ازش؟ یعنی درواقع شبیه همون پارامتر هایی که تو ساختمان داده واسه الگوریتم هافمن بهمون میدن تو سوال دیدم ازین راه برم؟
هروقت صحبت از کم ترین بیت برای نسبت دهی به علائم شد از هافمن استفاده میکنیم.
(۱۷ بهمن ۱۳۹۲ ۰۱:۰۴ ب.ظ)bermoda14 نوشته شده توسط: هروقت صحبت از کم ترین بیت برای نسبت دهی به علائم شد از هافمن استفاده میکنیم.
نکته جالبی بود، آفرین، کاملا هم بدیهیِ دلیلش ، مرسی ;-)
Sent from my ME172V using Tapatalk
وقتی گفته حداقل سطوح یعنی کمترین تعداد بیت مورد نیاز، میتونی احتمالات رو ضربدر ۱۰۰ کنی و بنویسی و درخت هافمن تشکیل بدی و بعد تعداد بیت های مورد نیاز رو بدست بیاری و ضربدر احتمالشون بعد ضربدر ۱۰۰ بکنی تا کل بیت های لازم برای ارسال برای یک دوره رو بدست بیاری، حالا با توجه به دیگر ویژگی های سوال حداقل تعداد سطوحی رو بدست بیاری که بتونه این اعطلاعات رو در زمان لازم عبور بده
(۱۷ بهمن ۱۳۹۲ ۰۱:۱۰ ب.ظ)Falcon نوشته شده توسط: وقتی گفته حداقل سطوح یعنی کمترین تعداد بیت مورد نیازقبوله
(۱۷ بهمن ۱۳۹۲ ۰۱:۱۰ ب.ظ)Falcon نوشته شده توسط: میتونی احتمالات رو ضربدر ۱۰۰ کنی و بنویسی و درخت هافمن تشکیل بدی و بعد تعداد بیت های مورد نیاز رو بدست بیاریمیشه ۵۰ و ۲۵ و ۱۲/۵ و ۱۲/۵ که درختشم کشیدم درست بود.
(۱۷ بهمن ۱۳۹۲ ۰۱:۱۰ ب.ظ)Falcon نوشته شده توسط: و ضربدر احتمالشون بعد ضربدر ۱۰۰ بکنی تا کل بیت های لازم برای ارسال برای یک دوره رو بدست بیاری، حالا با توجه به دیگر ویژگی های سوال حداقل تعداد سطوحی رو بدست بیاری که بتونه این اعطلاعات رو در زمان لازم عبور بدهها؟ :-o
یک دوره رو حساب میکنیم که چند بیت لازم داریم، مثلا اگر احتمالات ۱/۵۰ و ۱/۲۵ و ۱/۲۵ بود یعنی اینکه یک دوره ارسال میتونه بصورت ۴ بیت ( ۲ بیت برای ۱/۵۰ ، یک بیت برای ۱/۲۵ و یک بیت برای ۱/۲۵ بعدی ) نیاز داریم.
پس جمعا ۴ بیت باید بفرستیم تا تمام احتمالات رو دربر بگیره، حالا فرض کنید که گفته ۱۰۰۰ علامت در ثانیه تولید میشه، یعنی ۵۰۰ تا از نوع دوم و ۲ تا ۲۵۰ تایی از نوع اول و دوم . از روی این اطلاعات سرعت مورد نیاز رو بدست میاریم، ۵۰۰ تا از نوع اول که مثلا ۲ بیت میخواد، ۲۵۰ تا هم از نوع دوم که مثلا ۳ بیت میخواد و نوع سوم ...
بیت ریت مورد نیاز رو بدست میاریم و بعد ادامه ماجرا دیگه ...
(۱۷ بهمن ۱۳۹۲ ۰۲:۴۶ ب.ظ)Falcon نوشته شده توسط: یک دوره رو حساب میکنیم که چند بیت لازم داریم، مثلا اگر احتمالات ۱/۵۰ و ۱/۲۵ و ۱/۲۵ بود یعنی اینکه یک دوره ارسال میتونه بصورت ۴ بیت ( ۲ بیت برای ۱/۵۰ ، یک بیت برای ۱/۲۵ و یک بیت برای ۱/۲۵ بعدی ) نیاز داریم.
پس جمعا ۴ بیت باید بفرستیم تا تمام احتمالات رو دربر بگیره، حالا فرض کنید که گفته ۱۰۰۰ علامت در ثانیه تولید میشه، یعنی ۵۰۰ تا از نوع دوم و ۲ تا ۲۵۰ تایی از نوع اول و دوم . از روی این اطلاعات سرعت مورد نیاز رو بدست میاریم، ۵۰۰ تا از نوع اول که مثلا ۲ بیت میخواد، ۲۵۰ تا هم از نوع دوم که مثلا ۳ بیت میخواد و نوع سوم ...
بیت ریت مورد نیاز رو بدست میاریم و بعد ادامه ماجرا دیگه ...
مرسی قشنگ گفتی. من این راه حل رو یبار بداهه رو یه سوال پیاده کردم اما بعد یادم رفته بود چیکار کردم
بهترین همینه.
خوب شد این سؤالو پرسیدی....من از پایه یعنی کدینگ هافمنش مشکل دارم x_x
مثلا بگه ۶ تا علامت مختلف با احتمال وقوع ۲ تا از انها ۰/۲۵ و ۴تاشون ۰/۱۲۵ چطورکی میشه ؟ نرخ تولید علائم ۱۰۰۰علامت در ثانیه و حداقل نرخ ارسالو خواسته
سؤالم مال ۸۶ إ
یک درخت هافمن نیاز دارید، درخت و بکشی و علامت هارو بیت گزاری کنی مشخص میشه هرکدوم چند بیت می خوان
من هر بار حل می کنم جوابو ۱۶ بدست میارم
ولی گزینه ۲ درسته (سنجش)
مجموع سه عدد برام میشه ۱۵۰۰۰۰+۵۰۰۰۰+۵۰۰۰۰=۲۵۰۰۰۰
که در ثانیه میشه ۲۵۰۰۰۰/۶۰=۴۱۶۶
و با جاگذاری تو فرمول لگاریتم حدودای ۱۶ بدست میاد
اشتباهم می کنم کجاست؟
درخت هافمن رو رسم کنید برای ۱/۲ یک بیت و برای ۱/۴ دو بیت و برای ۱/۸ ها ۳ بیت.
حالا برای یک ثانیه بدست میاریم :
۱۰۰ هزار علامت در دقیقه میشه حدودا ۱۶۶۶ علامت در ثانیه
که ۱/۲ مش ۱ بیت ، ۱/۴ مش ۲ بیت و ۲ تا ۱/۸ مش ۳ بیت میخواد
((۱۶۶۶/۲)*۱ + (۱۶۶۶/۴)*۲ + (۱۶۶۶/۸)*۲*۳) = ۲۹۱۵
در هر ثانیه ۲۹۱۵ بیت نیاز داریم
۲۹۱۵ = ۲*۱k*log2(M)
کمترین M ای هم که در این معادله صدق میکنه از توی جوابا ۴ هست.