برنامه الگوریتم کدگذاری هافمن با سی پلاس پلاس

اختصاصی از فی توو برنامه الگوریتم کدگذاری هافمن با سی پلاس پلاس دانلود با لینک مستقیم و پر سرعت .

درعلوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن یک الگوریتم کدگذاری برای فشرده‌سازی بی‌اتلاف اطلاعات است.

این تعبیر بر می‌گردد به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از نشانه‌های مبدا (مانند نویسه‌های یک پرونده). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشان‌های مبدا بدست می‌آید. این روش بوسیلهٔ دیوید هافمن توسعه یافت. وی دانشجوی دورهٔ دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.

در کدگذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام کدهای بدون پیشوند (گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک نویسه خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر نویسهٔ دیگر است، نمی‌باشد.). در این روش نویسه‌های پرکاربردتر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.

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

برای مجموعه‌ای از نمادها با توزیع احتمالی یکنواخت و تعداد عضوهایی برابر با توانی از ۲، کد گذاری هافمن هم ارز با قطعه کد سادهٔ دوجمله‌ای است. مانند کد گذاری اسکی. کد گذاری هافمن روشی متداول برای ایجاد کدهای بدون پیشوند است بطوریکه عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده می‌شود، هرچند چنین کدی با الگوریتم هافمن بدست نیامده باشد.

اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینه‌است، اما گاهی کارآمدی آن بیش از مقدار واقعی پنداشته می‌شود. برای مثال، کد کردن حسابی و کد کردن LZW، گاهی توانایی بالاتری در فشرده سازی دارند.

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

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

این مطلب از مطالب آزاد موجود در اینترنت جمع آوری شده است و در مورد الگوریتم فشرده سازی هافمن و در 9 صفحه می باشد و در زیر قسمتی از متن آورده شده است :
الگوریتم فشرده سازی هافمن را دیوید هافمن پروفسور دانشگاه MIT (Massachusetts Institute of Technology) آمریکا اختراع کرد. روش فشرده سازی هافمن الگوریتمی است که برای فشرده سازی متن مناسب می باشد.
الگوریتم هافمن جزو خانوادهء الگوریتم هایی است که طول کد متغییری دارند. این به آن معناست که نماد های مجزا (برای نمونه کاراکترهایی در یک فایل متنی) با رشته بیت هایی که طول های
مختلفی دارند تعویض می شود. بنابراین نماد هایی که زیاد در یک فایل تکرار می شوند یک رشته
بیت کوتاه می گیرند در حالی که نمادهای دیگر که به ندرت دیده می شوند رشته بیت طولانی تری را می گیرند.
تاریخچه
در سال ۱۹۵۱ David.A.Huffman و هم شاگردی‌هایش در کلاس «تئوری اطلاعات» دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا دادن امتحان پایانی را داشتند.استاد Robert M. Fano موضوع تحقیق را مسالهٔ پیدا کردن کارآمد ترین کد دودویی تعیین کرد. هافمن ناتوان در پیدا کردن کارآمد ترین، تصمیم گرفته بود خودش را برای امتحان پایانی آماده کندکه ایده‌ای به ذهنش رسید. ایدهٔ استفاده از درخت دودیی مرتب شده بر حسب تکرار(frequency) وتوانست اثبات کند که این کارآمد ترین روش است. در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، Claude Shannon برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ Shannon-Fano coding جلوگیری کرده، درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.
کد‌گذاری هافمن
یک الگوریتم کد‌گذاری برای فشرده‌سازی بی‌اتلاف اطلاعات است. این تعبیر بر می‌گردد به استفاده از جدول کد طول متغیر برای کد کردن هر کدام از نشانه‌های مبدا (مانند کاراکترهای یک فایل). جدول کد طول متغیر از روشی بخصوص مبنی بر احتمال وقوع هر کدام از نشان‌های مبدا بدست می‌آید. این روش بوسیلهٔ دیوید هافمن توسعه یافت. وی دانشجوی دورهٔ دکتری در دانشگاه MIT بود و در سال ۱۹۵۲ مقالهٔ «روشی برای تولید کدی با کمترین تکرار زوائد» را منتشر کرد.
در کد کذاری هافمن، از روشی خاص برای انتخاب نحوهٔ نمایش هر نماد استفاده می‌شود. روشی به نام کد‌های بدون پیشوند(گاهی هم روش «کدهای پیشوندی» گفته می‌شود. یعنی در این روش رشته‌ای که نشان دهندهٔ یک کاراکتر خاص است هیچ گاه پیشوند رشتهٔ دیگر که نمایانگر کاراکتری دیگر است، نمی‌باشد.).در این روش کاراکتر‌های پرکاربرد تر با رشته‌های بیتی کوتاهتری نسبت به آن‌هایی که کاربردشان کمتر است، نشان داده می‌شوند.
هافمن موفق شد کارآمد ترین روش فشرده سازی از این نوع را طراحی کند: نگاشت نکردن نشان‌های منفرد مبدا به رشته‌های بیتی یکتا، هرگاه تعداد تکرار نماد‌های اصلی با آنهایی که برای ایجاد این کد مورد استفاده قرار گرفتند مطابقت کند، خروجی‌هایی با اندازهٔ کمتر تولید می‌کند. بعدها روشی برای انجام این کار پیدا شد که این کار را در زمانی خطی انجام می‌داد.
برای مجموعه‌ای از نمادها با توزیع احتمالی یکنواخت و تعداد عضو‌هایی برابر با توانی از ۲، کد گذاری هافمن هم ارز با قطعه کد سادهٔ دوجمله‌ای است. مانند کد گذاری ASCII. کد گذاری هافمن روشی متداول برای ایجاد کد‌های بدون پیشوند است بطوریکه عبارت «کد هافمن» به گستردگی به عنوان مترادفی برای «کد بدون پیشوند» استفاده می‌شود، هرچند چنین کدی با الگوریتم هافمن بدست نیامده باشد.
اگرچه کد گذاری هافمن برای کد کردن نماد به نماد بهینه‌است، اما گاهی کارآمدی آن بیش از مقدار واقعی پنداشته می‌شود. برای مثال، کد کردن حسابی و کد کردن LZW، گاهی توانایی بالاتری در فشرده سازی دارند.
کد قانونی هافمن
اگر وزن های مربوط به ورودی های مرتب شده بر اساس الفبا، به ترتیب عددی باشند، کد هافمن طولی برابر طول کد الفبایی بهینه دارد که می‌تواند از طریق محاسبه بدست آید. ک