الگوریتم هافمن در ساختمان داده – آموزش 0 تا 100 الگوریتم Huffman بصورت مرحله به مرحله
مقدمهای در مورد الگوریتم هافمن
همینطور توجه کنیم که الگوریتم هافمن از جمله الگوریتمهای ابتکاری هست و ممکن است بهینهترین پاسخ را به ما ندهد ولی در سریعترین زمان نزدیکترین پاسخ به جواب بهینه را به ما خواهد داد. خوب بهتر هست نگاهی به نحوه عملکرد الگوریتم بندازیم.
نحوه عملکرد الگوریتم هافمن
برای فهم بهتر قضیه اجازه بدین مسئله را بصورت غیر رسمی به این صورت تعریف کنیم:
دادههای اولیهای که داریم مجموعهای از کاراکترها یا حروف به همراه وزن آنها یا همان تعداد تکرارهای آنها هست. که تعداد تکرارها در همان فایل ابتدایی قرار دارند. برای نگهداری فایل اولیه از صف در ساختمان داده استفاده میکنیم. هدف این الگوریتم یافتن کد دودویی بدون پیشوند با کمترین امید ریاضی برای طول کد است.
شبه کد الگوریتم هافمن
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 نوشته شده است و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است بنابراین با اطمینان کامل شروع به دانلود کنید.
انواع کد هافمن
- کد هافمن n تایی
- کد هافمن انطباقی
- الگوریتم الگوی هافمن
- کد هافمن با طول محدود
- کد هافمن با ارزش حرفی متفاوت
- کد قانونی هافمن
سخن آخر در مورد الگوریتم هافمن در ساختمان داده
الگوریتم هافمن بطور ساده با یک مثال کاربردی تعریف شد و میتوان براحتی با رابطه بازگشتی T (n) = T (n-1) + O (n) نشان داد که دارای پیچیدگی زمانی o(n۲) است که البته با روشهایی میتوان پیچیدگی آن را کاهش داد. در ادامه اگر علاقمند به مطالب بیشتری در مورد الگوریتم هافمن هستید می توانید آموزش درس ساختمان داده مهندس جلیل زاده را از همین سایت بصورت رایگان مشاهده کنید. در پایان امیدواریم مطالب فوق برای شما عزیزان مفید بوده باشد حتماً ما را از نظرات و دیدگاه های خود آگاه کنید. موفق و پیروز باشید.
درباره گلناز محرر روحانی
کارشناس ارشد مهندسی کامپیوتر، محقق و پژوهشگر در زمینه شبکه های کامپیوتری و شبکه های موردی، طراح وب، پژوهشگر در امور Cryptocurrency و مسلط به زبان انگلیسی و مدرس زبان انگلیسی
سپاسگزار بابت مطالب مفیدی که به اشتراک گذاشتین
دمت گرم عالی توضیح داده بودی
ممنون از زحماتت بابت این مطلب