![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/langfa-640px-Huffman_tree_2.svg.png&w=640&q=50)
کدگذاری هافمن
From Wikipedia, the free encyclopedia
در علوم کامپیوتر و تئوری اطلاعات، کدگذاری هافمن (به انگلیسی: Huffman coding) نوع مشخصی از کد پیشوندی (به انگلیسی: Prefix code) بهینه است که کاربردی فراوان در فشردهسازی بیاتلاف اطلاعات دارد. فرایند پیدا کردن یا استفاده از این کد، با بهرهگیری از الگوریتمی انجام میشود که توسط «دیوید هافمن» (زمانی که وی دانشجوی دوره دکتری در دانشگاه MIT بود) توسعه داده شدهاست و برای اولین بار در سال ۱۹۵۲ در مقالهای با عنوان «روشی برای تولید کدی با کمترین تکرار زوائد»[1] منتشر شد.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/320px-Huffman_tree_2.svg.png)
کد | تکرار | حرف |
---|---|---|
۱۱۱ | ۷ | space |
۰۱۰ | ۴ | a |
۰۰۰ | ۴ | e |
۱۱۰۱ | ۳ | f |
۱۰۱۰ | ۲ | h |
۱۰۰۰ | ۲ | i |
۰۱۱۱ | ۲ | m |
۰۰۱۰ | ۲ | n |
۱۰۱۱ | ۲ | s |
۰۱۱۰ | ۲ | t |
۱۱۰۰۱ | ۱ | l |
۰۰۱۱۰ | ۱ | o |
۱۰۰۱۱ | ۱ | p |
۱۱۰۰۰ | ۱ | r |
۰۰۱۱۱ | ۱ | u |
۱۰۰۱۰ | ۱ | x |
میتوان به خروجی الگوریتم هافمن به عنوان یک جدول کد طول متغیر نگاه کرد که با استفاده تخمین احتمال حضور یا فراوانی تکرار حروف در فایل منبع ایجاد شدهاست و مانند هر رمزگذاری درگاشتی دیگر، حروف پرتکرار تر با تعداد بیتهای کمتری نمایش داده میشوند.
باید دقت کرد با توجه به کارایی بالای این الگوریتم، کدگذاری هافمن همواره بهینه نیست و در مواری که قصد فشردهسازی بهینهتری داشته باشیم، میتوان از الگوریتمهای کدگذاری حسابی یا سیستمهای عددی نامتقارن استفاده کرد.