الگوریتم هافمن در ساختمان داده – آموزش 0 تا 100 الگوریتم Huffman بصورت مرحله به مرحله

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

الگوریتم هافمن huffman در ابتدا توسط دیوید هافمن در سال ۱۹۵۲ طی یک مقاله ارائه شد. در این مورد جالب است بدانید که آقای دیوید هافمن و هم کلاسی‌هایش در کلاس تئوری اطلاعات در دانشگاه MIT حق انتخاب بین امتحان پایانی دادن و یا انجام تحقیقی در مورد یک مفهومی را داشتند. استاد هافمن موضوع تحقیق را پیدا کردن کارآمدترین کد دودویی تعیین کرد. جالب است که هافمن در ابتدا موفق نشد کارآمدترین را پیدا کند و به فکر این افتاد که خودش را برای امتحان پایانی آماده کند. تا اینکه ایده‌‌ای در مورد استفاده از درخت دودویی که بر حسب تعداد فراوانی مرتب شده باشد به ذهنش خطور کرد.

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

داده‌های فشرده شده موجب می‌شوند ۲۰٪ الی ۹۰٪ در حافظه صرفه‌جویی شود. در ادامه که الگوریتم هافمن را توضیح دادیم متوجه خواهید شد که این مطالب در حقیقت به چه معنایی هستند. خروجی الگوریتم هافمن در واقع کد طول متغیر است که با استفاده از تخمین احتمال موجود بودن یک حرف یا فراوانی تکرار حروف در فایل منبع تولید می‌شود. توجه کنیم که مانند هر رمزگذار فشرده‌سازی اطلاعات بدون تلفات دیگری، حروف پر تکرار تعداد بیت‌های بیشتری دارند که در ادامه خواهیم دید.

همینطور توجه کنیم که الگوریتم هافمن از جمله الگوریتم‌های ابتکاری هست و ممکن است بهینه‌ترین پاسخ را به ما ندهد ولی در سریع‌ترین زمان نزدیکترین پاسخ به جواب بهینه را به ما خواهد داد. خوب بهتر هست نگاهی به نحوه عملکرد الگوریتم بندازیم.

نحوه عملکرد الگوریتم هافمن

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

N=|C|
Q=C
For i = 1 to n-1
  Allocate a new node z
  Z.left = x = Extract - Min(Q)
  Z.right = y = Extract - Min(Q)
  Z.freq = x.freg + y.freg
  Insert(Q,z)
Return Extract - Min(Q)

• خط ۱: C یک مجموعه از N  کاراکتر است. که بسامد و تکرار هر کدام لحاظ شده است.
• خط ۲: کل c را وارد Q صف می‌کنیم. بر مبنای اولویتشان در صف مرتب می‌شوند بدین شکل که کاراکتر با تعداد تکرار کمتر در ابتدای صف و دومین تعداد تکرار کمتر در دومین جایگاه و به همین ترتیب ادامه دارد.
• خط ۳: وارد یک حلقه for می‌شویم و این حلقه تا بررسی تمام کاراکترها ادامه دارد. در ادامه یگ گره جدید می‌سازیم به نام z، این گره از ترکیب دو کاراکتر با تکرار بسامد کمتر بوجود می‌آید.
• خط ۴: گره z ایجاد می‌شود.
• خط ۵: فرزند چپ گره z‌‌ای را که ساختیم x نام گذاری می‌کنیم. یعنی گره‌‌ای که اولویتش بالاتر است در نتیجه بسامدش یا همان تکرارش از همه کمتر است را از صف خارج می‌کنیم. که اینجا کاراکتر g با تکرار ۱۰ را به عنوان فرزند چپ z در نظر  می‌گیریم.
• خط ۶: دوباره در صف گره بعدی با کمترین بسامد یعنی گره r انتخاب می‌شود فرزند راست گره  z یعنی y می‌شود و از صف خارج می‌شود.
• خط ۷: بسامد گره جدید از ترکیب بسامد گره‌های چپ و راست بدست می‌آیند.
• خط ۸: گره جدید g r را وارد صف می‌کنیم.

و این حلقه به همین ترتیب ادامه پیدا می‌کند تا دیگر گرهی در صف نباشد. اجازه بدین این الگوریتم را به شکل گرافیکی بررسی کنیم.

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

توجه کنید روی یال‌ها مقادیر ۰ و ۱ نوشته می‌شوند. وزن‌های کمتر با عدد ۰ و وزن‌های بیشتر با عدد ۱ مقداردهی شده اند. به این ترتیب که فرزندان چپ شماره ۰ و فرزندان راست شماره ۱ خواهند گرفت.

در نهایت از سمت ریشه به سمت برگ‌ها حرکت می‌کنیم و با یادداشت ۰ و ۱‌ها طبق مسیر موجود به کد با طول متغیر آن کاراکتر می‌رسیم و به این ترتیب رشته دی کد می‌شود و کد دودویی معادل رشته بدست می‌آید. همانطور که در ابتدا اشاره کرده بودیم این کد برای دی کد کردن رشته کد شده است و رشته همراه درخت ارسال می‌شود.

الگوریتم هافمن HUFFMAN در سی شارپ #C

سورس کد الگوریتم هافمن HUFFMAN در سی شارپ #C با استفاده از Microsoft Visual Studio 2013 نوشته شده است و دارای گزارش کار 5 صفحه ای در Word است.

همین الان کلیک کنید

استفاده از صف برای پیاده سازی الگوریتم هافمن

فرض کنید یک مجموعه کاراکتر با فراوانی g=10 , r= 18 , y=20 , I=22, e= 30 را داریم. در ابتدا این فراوانی ها را بصورت صعودی طبق شکل زیر مرتب می کنیم:

 

اکنون دو گره در صف باقی مانده gre و yI این دو انتخاب شده و نتیجه گره yIgre به عنوان گره ریشه حاصل می‌شود. اکنون برای استفاده از درخت برای دی کد کردن از سمت ریشه به سمت برگ‌ها درخت را پیمایش می‌کنیم.

شما می توانید کد آماده الگوریتم هافمن در زبان سی پلاس پلاس را با هزینه جزئی از فروشگاه ما تهیه و دانلود کنید. برای دانلود می توانید روی لینک زیر کلیک کنید.

سورس کد الگوریتم هافمن (Huffman) در سی پلاس پلاس ++C

سورس کد الگوریتم هافمن در سی پلاس پلاس با استفاده از Borland ++c نوشته شده است و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است بنابراین با اطمینان کامل شروع به دانلود کنید.

همین الان کلیک کنید

انواع کد هافمن