در علوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن ( به انگلیسی: Huffman coding ) نوع مشخصی از کد پیشوندی ( به انگلیسی: Prefix code ) بهینه است که کاربردی فراوان در فشرده سازی بی اتلاف اطلاعات دارد. فرایند پیدا کردن یا استفاده از این کد، با بهره گیری از الگوریتمی انجام می شود که توسط «دیوید هافمن» ( زمانی که وی دانشجوی دوره دکتری در دانشگاه MIT بود ) توسعه داده شده است و برای اولین بار در سال ۱۹۵۲ در مقاله ای با عنوان «روشی برای تولید کدی با کمترین تکرار زوائد»[ ۱] منتشر شد.
می توان به خروجی الگوریتم هافمن به عنوان یک جدول کد طول متغیر نگاه کرد که با استفاده تخمین احتمال حضور یا فراوانی تکرار حروف در فایل منبع ایجاد شده است و مانند هر رمزگذاری درگاشتی دیگر، حروف پرتکرار تر با تعداد بیت های کمتری نمایش داده می شوند.
باید دقت کرد با توجه به کارایی بالای این الگوریتم، کدگذاری هافمن همواره بهینه نیست و در مواری که قصد فشرده سازی بهینه تری داشته باشیم، می توان از الگوریتم های کدگذاری حسابی یا سیستم های عددی نامتقارن استفاده کرد.
در سال ۱۹۵۱ میلادی، دیوید آ. هافمن و هم شاگردی هایش در کلاس تئوری اطلاعات در دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا شرکت در امتحان پایانی را داشتند. دکتر روبرتو فانو موضوع تحقیق را یافتن کارآمدترین کد دودویی تعیین کرد. هافمن که در ابتدا موفق به یافتن کارآمدترین کد نشده بود، تصمیم گرفت خودش را برای شرکت در امتحان پایانی آماده کند. که ایدهٔ استفاده از درخت دودیی مرتب شده برحسب فراوانی به ذهنش رسید. او در نهایت توانست اثبات کند که روش کارآمدترین روش است. [ ۲] در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، کلود شانون برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ رمزگذاری شانون - فانو جلوگیری کرد و درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.
در کدگذاری هافمن، از روشی به نام کدهای بدون پیشوند ( که به عنوان «کدهای پیشوندی» نیز شناخته می شود ) برای انتخاب نحوهٔ نمایش هر نماد استفاده می شود. در این روش نویسه های پرکاربردتر با رشته های بیتی کوتاهتری نسبت به آن هایی که کاربردشان کمتر است، نشان داده می شوند. کدگذاری هفمن به اندازه ای پرکابرد است که کلمه «کد هافمن» به صورت گسترده به عنوان مترادفی برای کدهای پیشوندی استفاده می شود.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمی توان به خروجی الگوریتم هافمن به عنوان یک جدول کد طول متغیر نگاه کرد که با استفاده تخمین احتمال حضور یا فراوانی تکرار حروف در فایل منبع ایجاد شده است و مانند هر رمزگذاری درگاشتی دیگر، حروف پرتکرار تر با تعداد بیت های کمتری نمایش داده می شوند.
باید دقت کرد با توجه به کارایی بالای این الگوریتم، کدگذاری هافمن همواره بهینه نیست و در مواری که قصد فشرده سازی بهینه تری داشته باشیم، می توان از الگوریتم های کدگذاری حسابی یا سیستم های عددی نامتقارن استفاده کرد.
در سال ۱۹۵۱ میلادی، دیوید آ. هافمن و هم شاگردی هایش در کلاس تئوری اطلاعات در دانشگاه MIT، حق انتخاب بین تحقیق در مورد یک مفهوم یا شرکت در امتحان پایانی را داشتند. دکتر روبرتو فانو موضوع تحقیق را یافتن کارآمدترین کد دودویی تعیین کرد. هافمن که در ابتدا موفق به یافتن کارآمدترین کد نشده بود، تصمیم گرفت خودش را برای شرکت در امتحان پایانی آماده کند. که ایدهٔ استفاده از درخت دودیی مرتب شده برحسب فراوانی به ذهنش رسید. او در نهایت توانست اثبات کند که روش کارآمدترین روش است. [ ۲] در انجام این کار، شاگرد از استادش که با مبدع تئوری اطلاعات، کلود شانون برای ساختن کدی مشابه کار کرده بود، پیشی گرفت. هافمن از مشکل اصلی روش کدگذاری نیم بهینهٔ رمزگذاری شانون - فانو جلوگیری کرد و درخت را به جای ساختن از بالا به پایین، از پایین به بالا ساخت.
در کدگذاری هافمن، از روشی به نام کدهای بدون پیشوند ( که به عنوان «کدهای پیشوندی» نیز شناخته می شود ) برای انتخاب نحوهٔ نمایش هر نماد استفاده می شود. در این روش نویسه های پرکاربردتر با رشته های بیتی کوتاهتری نسبت به آن هایی که کاربردشان کمتر است، نشان داده می شوند. کدگذاری هفمن به اندازه ای پرکابرد است که کلمه «کد هافمن» به صورت گسترده به عنوان مترادفی برای کدهای پیشوندی استفاده می شود.
wiki: کدگذاری هافمن