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

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

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

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

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

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

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

• پاورپوینت الگوریتم هافمن (Huffman coding) — کلیک کنید.

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

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

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 را وارد صف می‌کنیم.

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

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

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

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

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

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

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

در این مقاله در مورد الگوریتم هافمن به عنوان روشی برای فشرده سازی داده به نحوی که هیچ قسمتی از داده از دست نرود صحبت کردیم. می‌توان به خروجی الگوریتم هافمن را به عنوان یک جدول کد طول متغیر نگاه کرد که همانطور که مشاهده کردید از فراوانی تکرار کاراکترها در فایل منبع ایجاد شد.
الگوریتم هافمن بطور ساده با یک مثال کاربردی تعریف شد و می‌توان براحتی با رابطه بازگشتی T (n) = T (n-1) + O (n) نشان داد که دارای پیچیدگی زمانی o(n^۲) است که البته با روش‌هایی می‌توان پیچیدگی آن را کاهش داد. در ادامه اگر علاقمند به مطالب بیشتری در مورد الگوریتم هافمن هستید می‌توانید آموزش درس ساختمان داده مهندس جلیل زاده را از همین سایت بصورت رایگان مشاهده کنید. در پایان امیدواریم مطالب فوق برای شما عزیزان مفید بوده باشد حتماً ما را از نظرات و دیدگاه‌های خود آگاه کنید. موفق و پیروز باشید.

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

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

کلیک کنید