# مهندسی نرم افزار > مباحث مرتبط با مهندسی نرم‌افزار > الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها >  اگوریتم هافمن

## mahdi bg

سلام

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

ممنون

----------


## popcorn

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

----------


## mahdi bg

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

ممنون

----------


## mahdi bg

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

----------


## popcorn

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

----------


## mahdi bg

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

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

----------


## popcorn

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

*لگوریتم فشرده سازی هافمن  الگوریتم فشرده سازی هافمن را دیوید هافمن پروفسور دانشگاه  ( * TechnologyMIT (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

راهنما و کتابهای زیادی در این باره موجود است،
کفایت نکرده؟
لینک کتاب

----------


## skylove

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

----------


## soorena

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

----------


## taghiv

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

----------


## مسعود اقدسی فام

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


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

----------


## alireza1001

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

----------


## mehdi.piroozi nia

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

----------

