اگوریتم هافمن

[mahdi bg]

سلام

می خواستم بدونم الگوریتم هافمن دقیقا چطوری کار میکنه
اگه بشه با یک مثال توضیح بدین عالی میشه
توی سایت گشتم
1- کد برنامه بود و نه توضیح چگونگی کار کردن الگوریتم
2- توضیحات چگونگی کار کردن الگوریتم به زبان انگلیسی بود

ممنون

[popcorn]

همان طور که می دونید یک روش فشرده سازی اطلاعات بر روی حافظه های جانبی کد گذاری کاراکتر هاست وباید به دنبال روشی گشت که یک کد دودویی ماسبی را برای فشرده سازی داده ها پیدا کرد کد گذاری هافمن یکی از این روش هاست.
آقای هافمن با استفاده از الگوریتم حریصانه الگوریتمی را طراحی کرد که از طریق ساخت یک درخت دودویی متناظر با یک کد یک کد بهینه دودویی را تولید کرد
البته باید از طریق استقرا ثابت کرد که این الگوریتم کد بهینه دودویی را تولید می کند.
شکل زیر مراحل تولید کد هافمن را نشان می دهد (به روش حریصانه

http://irapic.com/uploads/1212588098.jpg

[mahdi bg]

سلام
فقط یک سوال تو شکل بالا در مرحله اول و دوم و سوم کاراکتری که
عدد کمتری داشته به عنوان گره سمت چپ(درخت) در نظر گرفته شده اما
در مرحله آخر گره سمت راست عدد کوچکتره
نباید توی این مرحله هم این اتفاق بیفته؟

ممنون

[mahdi bg]

سلام
یک کد نوشتم می خواستم بدونم کسی نمونه ای دیگه مثل
پست شماره 2 نداره تا برنامه مو چک کنم؟
ممنون

[popcorn]

دوست عزیز شکل بالا هیچ مشکلی نداره و مربوط به سوال E مسابقات ACM امسال است.

[mahdi bg]

سلام
دوست عزیز من کی گفتم مشکل داره!!!!!!!!!!

فایل ورودی و خروجی این مسئله رو داری؟
(از کجا میتونم گیرش بیارم می خوام کدی که نوشتم تست کنم)
خیلی فوری لازم دارم.
ممنون

[popcorn]

این شکل در توضیح مختصر سوال acm که مربوط به الگوریتم هافمن بود آورده شده بود.

لگوریتم فشرده سازی هافمن الگوریتم فشرده سازی هافمن را دیوید هافمن پروفسور دانشگاه ( Technology MIT (Massachusetts Institute of آمریکا اختراع کرد. روش فشرده سازی هافمن الگوریتمی است که برای فشرده سازی متن مناسب می باشد. الگوریتم هافمن جزو خانوادهء الگوریتم هایی است که طول کد متغییری دارند. این به آن معناست که نماد های مجزا (برای نمونه کاراکترهایی در یک فایل متنی) با رشته بیت هایی که طول های مختلفی دارند تعویض می شود. بنابراین نماد هایی که زیاد در یک فایل تکرار می شوند یک رشته بیت کوتاه می گیرند در حالی که نمادهای دیگر که به ندرت دیده می شوند رشته بیت طولانی تری را می گیرند. یک مثال کاربردی اجزای کار را به شما نشان می دهد. فرض کنید می خواهید تکه اطلاعات زیر رافشرده کنید: ACDABA از آنجایی که 6 کاراکتر داریم، این متن 6 بایت یا 48 بیت می باشد. با رمز گزاری هافمن، فایل برای بیشترین تکرار ظاهر شدن نمادها (در این مثال نماد A سه بار تکرار می شود) جستجو می شود و سپس یک درخت ساخته می شود که نماد ها را با رشته بیت های کوتاه تر جایگزین می کند. در این حالت خاص الگوریتم از جدول جایگزینی زیر استفاده می کند: A=0 , B=10 , C=110 , D=111. اگر این کد برای فشرده سازی فایل استفاده شود، اطلاعات فشرده شده به صورت زیر در می آیند: 01101110100 این به این معنی است که 11 بیت به جای 48 بیت مصرف شد. در این مثال خاص نسبت فشرده سازی 4 به 1 می باشد. رمزگزاری هافمن به دو روش مختلف می تواند بهینه تر شود: 1. کد هافمن انطباقی (Adaptive Huffman code) به صورت پویا کلمات کد را با توجه به تغییر احتمال وقوع نماد ها تغییر می دهد. 2. فشرده سازی گستردهء هافمن (Extended Huffman Compression) می تواند گروهی از نماد ها را نسبت به یک نماد رمز گزاری کند. این روش می تواند بین 20% تا 90% اطلاعات را فشرده کند. این الگوریتم فشرده سازی اساسا برای فشرده سازی متون و فایل های برنامه سودمند است. برای فشرده سازی فایل های عکس از الگوریتم های دیگری استفاده می شود.

[mahdi bg]

سلام
فایل ورودی و خروجی این مسئله رو دارید؟
(این سوال رو از کدام سایت پیدا کردید؟)

[Matin_Delphi]

http://icpc.baylor.edu/icpc/Finals/2008WorldFinalsProblemSet.pdf برای mahdi bg

[Matin_Delphi]

البته problem E اونی که تو می خوای

[delfi01]

:لبخندساده:سلام
فشرده سازي داده ها با استفاده از كد Huffman
فشرده سازي داده ها يعني تبديل رشته هاي كاراكتري به رشته ديگري كه شامل همان اطلاعات باشداما طول رشته حاصل از طول رشته اوليه كوتاهتر باشد.كد گذاري و كد گشايي نيزبه ترتيب براي تبديل اوليه و نيز شناسايي و تبديل معكوس به كار مي روند.برخي تقسيم هاي رمز گذاري مانند رمز اسكي داراي طول ثابت هستند و براي هر كاراكتر تعداد ثابتي بيت در نظر مي گيرد و برخي داراي طول متغير هستند.سيستم رمز گذاري هافمن داراي مشخصات زير است:اولا طول رمز ها يكسان نمي باشد،ثانيا نيازي به جداسازنده نيست و ثالثا به تعداد تكرار هر كاراكتر توجه شده است .يعني كاراكتر هايي كه بيشتر تكرار شده اند طول كد شده كمتري دارند.نتيجه حاصل از روش هافمن يك درخت دودويي است كه هر حرف به عنوان يك برگ درخت است و رمز هر حرف درمسير ريشه درخت به آن حرف نهفته است هر گام به چپ به منزله صفر و هر گام به راست به منزله يك است.و هيچ حرفي به عنوان بخش ابتداي كد هيچ حرف ديگري نيست در نتيجه نيازي به جدا سازنده بين حروف متوالي نيست.
مثلا هرگز به جايي بر نمي خوريم كه فرضا كد حرف 01a باشد و كد حرف 011b باشد كه با ديدن رشته 01 مخير بمانيم كه شايد a باشد و شايد با توجه به ساير كدها b .چنين رمزي را رمز پيشوند آزاد گوييم prefix Free code :تشویق:


من اين توضيح رو از كتاب كنكور كارشناسي ارشد(راهيان ارشد)قسمت طراحي الگوريتم نوشتم.

[delfi01]

الگوريتم توليد

نخست هر حرف را به همراه دفعات تكرار آن(بسامد) در متن به عنوان ريشه يك درخت با تنها يك گره در نظر بگيريد.در ابتداي كار يك جنگل خواهيم داشت.از آن پس در هر مرحله دو درخت را كه بسامد ريشه آنها كمترين باشد در هم ادغام مي كنيم و درخت جديدي مي سازيم كه بسامد ريشه آن مجموع بسامد ريشه دو زير درخت تشكيل دهنده اش مي باشد.و زير درختي كه بسامد ريشه آن كمتر است در سمت چپ و زير درختي كه بسامد ريشه آن بيشتر است در سمت راست گره جديد ريشه واقع ميشود اين كار را تا جايي ادامه مي دهيم كه يك زير درخت واحد داشته باشيم.:لبخندساده:

[zo_se1386]

سلام
منم دارم برنامه ی هافمن رو با jbuilderمی نویسم.ولی سوالم با بقیه متفاوته
باید دکمه ی browsبسازم تا با استفاده از اون یه فایل رو کاربر انتخاب کنه تا بعد این فایل با الگوریتم هافمن فشرده بشه.
اگه کسی بلد که چه طور میشه دکمه ی brows روساخت،راهنماییم کنه
ممنون

[elnaz.r]

salam. mishe lotf konid va addrese site ke maghalate aghaye m.jampour dar an hast (dar morede algorithm) be man be ded.

[mehdi58]

حالا كه در اين تاپيك در مورد الگوريتم هافمن بحث شده ، من هم يه سوال مطرح مي كنم :

متني شامل 7000 حرف از حروف a و b و c‌ و d و e و f با دفعات تكرار زير موجود است .
a =1000 , b = 1200 , c = 800 , d = 1500 , e = 1800 , f = 700
چنانچه كدي بهينه براي حروف بالا انتخاب نماييم ، تعداد كل بيتهاي لازم براي تبديل متن مذكور به مجموعه اي از بيت ها چقدر است ؟
1) 14600
2) 17700
3) 24300
4) 35200

خوب ، من با درخت توليدي اون كه توي شكل ضميمه شده مشكلي ندارم . همين طور با مقادير هر كاراكتر با توجه به درخت توليدي :
a : 110
b : 111
c : 001
d : 01
e : 10
f : 000

اما در پايان نفهميدم كه عددهاي زير از كجا اومدن :
جمع كل = 3000 + 3600 + 2400 + 3000 + 3600 + 2100

[mahdi bg]

سلام
این اعداد به ترتیب ضرب تعداد کاراکتر ها در تعداد بیت های مورد نیازه
مثلا d تعداد 1500 تاست و تعداد بیت هاش 2 تاست در نتیجه میشه 3000 تا بیت
یا مثلا e 1800 تاست و دو بیت لازم داره میشه 3600 بیت
جواب تست کنکورتون هم میشه گزینه 2 (17700). یادم نیست مال چه سالی بود

[fatemeh ghasemi]

سلام خدمت دوستان عزیز
من به برنامه ای نیاز دارم که یک رشته را بگیرد و کد هافمن آن را برگرداند و بالعکس، ترجیحا به زبان ++c
اگر کمکم کنید ممنوم می شم.

[raha_hakhamanesh]

راهنما و کتابهای زیادی در این باره موجود است،
کفایت نکرده؟
لینک کتاب (http://www.adinehbook.com/gp/search/964-6949759-3732306?search-alias=books&field-keywords=%D8%B7%D8%B1%D8%A7%D8%AD%DB%8C+%D8%A7%D9% 84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85)

[skylove]

سلام دوستان، کسی توضیح ابرنامه هافمن به زبان ++c رو میدونه؟
تا امشب اگه میدونید برام بذارید لطفا،نهایتا تا فردا ظهر
ممنون از همگی

[soorena]

http://maroofi.persiangig.com/huffman/huffman.html

[taghiv]

با سلام
از عزیزان لطف می کنید بفرمایید این حل هافمن که بنده انجام دادم درست هست یا نه؟
اون قسمتی که 30 و درخت ترکیب می شن مطمئن نیستم


88005

[مسعود اقدسی فام]

با سلام
از عزیزان لطف می کنید بفرمایید این حل هافمن که بنده انجام دادم درست هست یا نه؟
اون قسمتی که 30 و درخت ترکیب می شن مطمئن نیستم


88005

30 با 39 نرکیب می‌شه و 69 رو می‌سازه و الی آخر. اون تیکه رو متوجه نشدم چرا مجددا 30 با 24 ترکیب شده.

[alireza1001]

سلام
ممنون از راهنمایی که کردید .ولی یک سوال برام پیش آمده ؟ این کدهای که نوشته شده برای حروف f,c,dاشتباه هستش اگر طبق شکل ضمیمه عمل بشود .به نظر من زمانی درست است که حرف d در درخت رسم شده سمت راست قرار بگیرد . لطفا توضیح دهید

[mehdi.piroozi nia]

سلام دوستان من دنبال راهي براي كدگشايي هافمن ميگردم.ميخوام بتونم فشرده سازي رو به حالت قبل از فشرده شدن برگردونم. ممنون ميشم راهنماييم كنيد