تالار گفتمان مانشت
با عناصر تکراری در درخت هافمن چه می کنید؟ - نسخه‌ی قابل چاپ

با عناصر تکراری در درخت هافمن چه می کنید؟ - bijibuji - 03 بهمن ۱۳۸۹ ۰۵:۵۱ ب.ظ

حتما به مشکلی که من برخوردم شما هم برخورد کردید در درخت هافمن

اگر حاصل محاسبه دو مقدار برابر بشه مثلا به ۱۰ و ما دو مقدار اولیه ۱۰ رو هم داشته باشیم
(یعنی در کل سه مقدار برابر که یکی از اش محاسبه به دست اومده و دوتاش مقدار اولیه هستند)
با چه ترتیبی باید این سه رو ترکیب کنیم؟
حتما متوجه شدید که درخت حاصل یکسان نخواهد بود

با عناصر تکراری در درخت هافمن چه می کنید؟ - ف.ش - ۰۳ بهمن ۱۳۸۹ ۰۷:۱۲ ب.ظ

آره ولی اون مجموع حافظه استفاده شده فرقی نمیکنه.
فقط کدها هست که فرق میکنه.

با عناصر تکراری در درخت هافمن چه می کنید؟ - javadjj - 03 بهمن ۱۳۸۹ ۰۷:۵۱ ب.ظ

متاسفانه من عینا با این موضوع برخورد داشتم و مهم نظر طراح هستش و اونچه اون حل کرده و در ضمن هر دو نوع رو هم تو گزینه‌ها میزارن و نظر هم نظر خودشون اما من اگه گره جدید باشه میدم سمت راست و گرهی هم که حاصل جمع وزن های قبلی هستش رو سمت چپ

RE: با عناصر تکراری در درخت هافمن چه می کنید؟ - bijibuji - 03 بهمن ۱۳۸۹ ۱۰:۲۳ ب.ظ

(۰۳ بهمن ۱۳۸۹ ۰۷:۱۲ ب.ظ)afagh1389 نوشته شده توسط:  آره ولی اون مجموع حافظه استفاده شده فرقی نمیکنه.
فقط کدها هست که فرق میکنه.

خوب حالا به هر حای یه چیزی فرق می کنه دیگه.
بحث من هم سر همین تفاوت هست

(۰۳ بهمن ۱۳۸۹ ۰۷:۵۱ ب.ظ)javadjj نوشته شده توسط:  متاسفانه من عینا با این موضوع برخورد داشتم و مهم نظر طراح هستش و اونچه اون حل کرده و در ضمن هر دو نوع رو هم تو گزینه‌ها میزارن و نظر هم نظر خودشون اما من اگه گره جدید باشه میدم سمت راست و گرهی هم که حاصل جمع وزن های قبلی هستش رو سمت چپ

یعنی اگر درست متوجه شده باشم، یکی از دوتا گره مقدار اولیه رو با اون گره حاصل محاسبه قبلی می گیری آقا جواد؟
یا دوتا جدید‌ها رو جدا با هم حساب می کنی؟

با عناصر تکراری در درخت هافمن چه می کنید؟ - grayman - 04 بهمن ۱۳۸۹ ۰۲:۰۲ ب.ظ

در کتاب بالاکرشتاین روش جالبی برای این الگوریتم گفته. به صورت مجموعه با همون ترتیب باهاش برخورد می کنید. یعنی اولیویت از چپ به راست در نظر می گیری. اگر ۳ تا عنصر یکسان داشتی از سمت چپ دو تای اول رو با هم میگیری. من هرچی تست زدم با این روش درست بوده و همونی بوده که در پاسخ تشریحی بود.

با عناصر تکراری در درخت هافمن چه می کنید؟ - zr2358 - 04 بهمن ۱۳۸۹ ۰۲:۴۲ ب.ظ

خب نتیجه ای که از جمع دو تا نود بدست میاد چه الویتی نسبت به اعدادی که توی لیست موجود هستند داره کمتر از اوناست یا بیشتر؟
شما میگید به ترتیب، عددی که تازه بدست اومده کجا قرار میگیره بخصوص اگه اعداد مرتب نباشند

RE: با عناصر تکراری در درخت هافمن چه می کنید؟ - grayman - 04 بهمن ۱۳۸۹ ۰۲:۴۷ ب.ظ

(۰۴ بهمن ۱۳۸۹ ۰۲:۴۲ ب.ظ)zr2358 نوشته شده توسط:  خب نتیجه ای که از جمع دو تا نود بدست میاد چه الویتی نسبت به اعدادی که توی لیست موجود هستند داره کمتر از اوناست یا بیشتر؟
شما میگید به ترتیب، عددی که تازه بدست اومده کجا قرار میگیره بخصوص اگه اعداد مرتب نباشند
من جایی نگفتم مرتب باشن. بیبنید اگر ۳ تا ۱۰ توی یک مجموعه باشن از چپ به راست بدون در نظر گرفتن ترتیب بزگتر یا کوچکتر ۲ تا ۱۰ سمت چپ رو با هم جمع می کنی حاصل میشه ۲۰/ باز هم از چپ دنبال دو تا عدد کوچکتر میگردی مثلا ۱۳ که قاعدتا با اون ۱۰ باقیمونده جمع میشه میشه ۲۳ . حالا تو مجموعه دنبال دوتا کوچکتر میگردیم که شاید اون ۲۳ و ۲۰ باشن یا شاید مثلا ۱۵ با ۲۰ باشه. اگر عدد تکراری داشت که مثل شیوه ای گه گفتم عمل می کنیم و اگر نبود که شیوه معمولی رو اجرا می کنیم و دو تا عدد جدید اضافه می کنیم.

RE: با عناصر تکراری در درخت هافمن چه می کنید؟ - zr2358 - 04 بهمن ۱۳۸۹ ۰۳:۰۱ ب.ظ

(۰۴ بهمن ۱۳۸۹ ۰۲:۴۷ ب.ظ)grayman نوشته شده توسط:  
(04 بهمن ۱۳۸۹ ۰۲:۴۲ ب.ظ)zr2358 نوشته شده توسط:  خب نتیجه ای که از جمع دو تا نود بدست میاد چه الویتی نسبت به اعدادی که توی لیست موجود هستند داره کمتر از اوناست یا بیشتر؟
شما میگید به ترتیب، عددی که تازه بدست اومده کجا قرار میگیره بخصوص اگه اعداد مرتب نباشند
من جایی نگفتم مرتب باشن. بیبنید اگر ۳ تا ۱۰ توی یک مجموعه باشن از چپ به راست بدون در نظر گرفتن ترتیب بزگتر یا کوچکتر ۲ تا ۱۰ سمت چپ رو با هم جمع می کنی حاصل میشه ۲۰/ باز هم از چپ دنبال دو تا عدد کوچکتر میگردی مثلا ۱۳ که قاعدتا با اون ۱۰ باقیمونده جمع میشه میشه ۲۳ . حالا تو مجموعه دنبال دوتا کوچکتر میگردیم که شاید اون ۲۳ و ۲۰ باشن یا شاید مثلا ۱۵ با ۲۰ باشه. اگر عدد تکراری داشت که مثل شیوه ای گه گفتم عمل می کنیم و اگر نبود که شیوه معمولی رو اجرا می کنیم و دو تا عدد جدید اضافه می کنیم.

می دونم، متوجه منظورتون شدم
بحث این تاپیک اینه که مثلا اعداد زیر رو داریم
۱۰ ۵ ۱۰ ۵ ...
دو تا ۵ رو که با هم جمع کردیم جواب میشه ۱۰
بعد دو تا ۱۰ که توی اعداد اولیه هستند رو با هم جمع می کنید یا یکی از اونا رو با ۱۰ی که الان با جمع ۵ها بدست آوردی؟
شما میگید به ترتیب از چپ، حالا این ۱۰ی که داریم قبل از ایناست یا بعدش یا ...

با عناصر تکراری در درخت هافمن چه می کنید؟ - bijibuji - 04 بهمن ۱۳۸۹ ۰۹:۲۹ ب.ظ

zr2358 جان
من به نتیجه ای که رسیدم این هست که باید حاصل اون دو تا ۵ رو( که شده یک ۱۰) با یکی از ۱۰‌ها بگیریم
با اینکه این حالت درخت هافمن بدتری می ده‌، اما در تست های سال های قبل گویا این درخت بد مورد نظر بوده.

با عناصر تکراری در درخت هافمن چه می کنید؟ - grayman - 05 بهمن ۱۳۸۹ ۱۲:۳۵ ق.ظ

اون ۱۰ که از مجموع دو تا ۵ بدست آمده اولویتش پایین‌تر از ۱۰ هایی است که تو مجموعه هست. البته من تا حالا ندیدم که این طوری باشه ولی طبق همون روشی که در کتاب بالاکرشتاین دیدم اولویت با عناصر قدیمی‌تر توی مجموعه است. منظور از قدیمی‌تر این که هنوز وارد درخت هافمن نشدن. اینجا ۲ تا ۱۰ باقیونده اولویت دارن نسبت به ۱۰ که حاصل ۲ تا ۵ هست.
اگر بعد از جمع کردن هم نتایج بدست اومده یکسان بود دوباره باز اولویت با اونیه که از قبل تو مجموعه بوجو اومده نسبت به این عنصر مشابه جدید.

با عناصر تکراری در درخت هافمن چه می کنید؟ - ف.ش - ۰۵ بهمن ۱۳۸۹ ۰۱:۳۱ ق.ظ

اینو که کدومشون اولویت دارن رو نمیدونم اما طبق کتاب مقسمی اگه خواستیم ۲ تا که حاصل مساوی دارن رو جمع بزنیم اونی که خودش حاصل جمع هست سمت راست قرار میگیره و اونی که خودش یه حرفه سمت چپ.

RE: با عناصر تکراری در درخت هافمن چه می کنید؟ - bijibuji - 05 بهمن ۱۳۸۹ ۰۹:۱۲ ق.ظ

(۰۵ بهمن ۱۳۸۹ ۱۲:۳۵ ق.ظ)grayman نوشته شده توسط:  اون ۱۰ که از مجموع دو تا ۵ بدست آمده اولویتش پایین‌تر از ۱۰ هایی است که تو مجموعه هست. البته من تا حالا ندیدم که این طوری باشه ولی طبق همون روشی که در کتاب بالاکرشتاین دیدم اولویت با عناصر قدیمی‌تر توی مجموعه است. منظور از قدیمی‌تر این که هنوز وارد درخت هافمن نشدن. اینجا ۲ تا ۱۰ باقیونده اولویت دارن نسبت به ۱۰ که حاصل ۲ تا ۵ هست.
اگر بعد از جمع کردن هم نتایج بدست اومده یکسان بود دوباره باز اولویت با اونیه که از قبل تو مجموعه بوجو اومده نسبت به این عنصر مشابه جدید.

دقیقا منم همینو می گم. این حالت بهینه رو می ده
اما در بسیاری از تست‌ها حالت غیر بهینه پاسخ بوده
دلیل اش هم واضح نیست

با عناصر تکراری در درخت هافمن چه می کنید؟ - admin - 05 بهمن ۱۳۸۹ ۰۴:۱۲ ب.ظ

الگوریتم هافمن باید نتیجه بهینه رو بده، در صورتی که جواب غیر بهینه پاسخ باشه طراح اشتباه کرده و می‍شه اعتراض کرد. دوستان منطقی فکر کنید!. در ضمن الگوریتم هافمن هیچ اجباری به چپ یا راست بودن مجموع در ترکیب جدید نداره .در واقع اینکه چپ باشه یا راست تفاوتی نداره. چون که ضرب فراوانی در کدهای ایجاد شده در این دو درخت مثل هم می‍شه.
این الگوریتم خیلی پیچیده نیست و می‍شه حالت‍های مختلف رو به راحتی آزمایش کرد و یکی از هنرهای شما سرجلسه آزمودن روش‍های مختلف هست که باید به سرعت انجام بدین.

RE: با عناصر تکراری در درخت هافمن چه می کنید؟ - Masoud05 - 08 تیر ۱۳۹۱ ۰۶:۲۵ ق.ظ

در ادامه صحبت های جناب دکتر در این تاپیک زیر خاکی باید گفت :

الگوریتم هافمن بهینه است پس در بدترین حالت نباید مصرف حافظه ای بیشتر از حالت معمول داشته باشیم .
در الگوریتم هافمن اگر تعداد بیشترین تکرار یک حرف از کمترین تعداد تکرار حرفی ، کمتر باشد آنگاه الگوریتم هافمن مزیتی ندارد .

یه نکته جالب ، ارسال های بالا رو ببینید ( بغیر از خود جناب دکتر ) الان همه بچه هایی که یه موقع اینجا در بحث علمی شرکت داشتن ؛ تمامی اونها الان دارن ارشد میخونن، مانشت در سال ۸۹ خیلی قوی بود علتش هم همین بحث های علمی بود و اینکه کمتر به حاشیه میرفتن بچه ها . الان مانشت یکم تو حاشیه ها زیاد میره