نمایش نتایج 1 تا 24 از 24

نام تاپیک: اگوریتم هافمن

  1. #1

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

    سلام

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

    ممنون

  2. #2
    کاربر تازه وارد آواتار popcorn
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    web
    پست
    33

    Talking نقل قول: اگوریتم هافمن

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


  3. #3

    نقل قول: اگوریتم هافمن

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

    ممنون

  4. #4

    نقل قول: اگوریتم هافمن

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

  5. #5
    کاربر تازه وارد آواتار popcorn
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    web
    پست
    33

    Talking نقل قول: اگوریتم هافمن

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

  6. #6

    نقل قول: اگوریتم هافمن

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

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

  7. #7
    کاربر تازه وارد آواتار popcorn
    تاریخ عضویت
    بهمن 1386
    محل زندگی
    web
    پست
    33

    Talking نقل قول: اگوریتم هافمن

    این شکل در توضیح مختصر سوال 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% اطلاعات را فشرده کند. این الگوریتم فشرده سازی اساسا برای فشرده سازی متون و فایل های برنامه سودمند است. برای فشرده سازی فایل های عکس از الگوریتم های دیگری استفاده می شود.

  8. #8

    نقل قول: اگوریتم هافمن

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

  9. #9

    نقل قول: اگوریتم هافمن

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

  10. #10

    نقل قول: اگوریتم هافمن

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

  11. #11

    Smile نقل قول: اگوریتم هافمن

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


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

  12. #12

    نقل قول: اگوریتم هافمن

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

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

  13. #13

    نقل قول: اگوریتم هافمن

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

  14. #14

    نقل قول: اگوریتم هافمن

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

  15. #15
    کاربر دائمی آواتار mehdi58
    تاریخ عضویت
    اسفند 1384
    محل زندگی
    Utopia
    پست
    450

    نقل قول: اگوریتم هافمن

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

    متني شامل 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
    فایل های ضمیمه فایل های ضمیمه
    • نوع فایل: rar pic.rar‏ (6.2 کیلوبایت, 339 دیدار)

  16. #16

    نقل قول: اگوریتم هافمن

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

  17. #17

    نقل قول: اگوریتم هافمن

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

  18. #18
    کاربر دائمی
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    قفس فیلترینگ(ایران)
    پست
    208

    نقل قول: اگوریتم هافمن

    راهنما و کتابهای زیادی در این باره موجود است،
    کفایت نکرده؟
    لینک کتاب
    آخرین ویرایش به وسیله raha_hakhamanesh : شنبه 28 اردیبهشت 1392 در 07:28 صبح دلیل: تصحیح لینک

  19. #19
    کاربر جدید
    تاریخ عضویت
    اردیبهشت 1391
    محل زندگی
    تهران
    پست
    11

    نقل قول: اگوریتم هافمن

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

  20. #20

  21. #21

    نقل قول: اگوریتم هافمن

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


    Name:  huffman.jpg
Views: 3573
Size:  59.0 کیلوبایت

  22. #22

    نقل قول: اگوریتم هافمن

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


    Name:  huffman.jpg
Views: 3573
Size:  59.0 کیلوبایت
    30 با 39 نرکیب می‌شه و 69 رو می‌سازه و الی آخر. اون تیکه رو متوجه نشدم چرا مجددا 30 با 24 ترکیب شده.

  23. شنبه 20 خرداد 1391, 00:31 صبح

    دلیل
    زیرا

  24. #23

    نقل قول: اگوریتم هافمن

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

  25. #24
    کاربر جدید
    تاریخ عضویت
    دی 1392
    محل زندگی
    شيراز
    پست
    2

    نقل قول: اگوریتم هافمن

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

برچسب های این تاپیک

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •