CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Huffman coding - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"096ac2fb-8b72-4008-a3eb-919afec2506a","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Huffman_coding","wgTitle":"Huffman coding","wgCurRevisionId":1271869873,"wgRevisionId":1271869873,"wgArticleId":13883,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 location test","Articles with short description","Short description is different from Wikidata","Use dmy dates from May 2019","Articles needing additional references from December 2021","All articles needing additional references","Wikipedia articles needing clarification from September 2023","All articles with unsourced statements","Articles with unsourced statements from December 2021","Commons category link is on Wikidata","1952 in computing","Lossless compression algorithms", "Binary trees","Data compression"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Huffman_coding","wgRelevantArticleId":13883,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":40000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q2647", "wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.tablesorter.styles":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready", "jquery.tablesorter","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cjquery.tablesorter.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.15"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/1200px-Huffman_tree_2.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="772"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/800px-Huffman_tree_2.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="515"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/640px-Huffman_tree_2.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="412"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Huffman coding - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Huffman_coding"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Huffman_coding&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Huffman_coding"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Huffman_coding rootpage-Huffman_coding skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Huffman+coding" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Huffman+coding" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Huffman+coding" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Huffman+coding" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-History" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#History"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>History</span> </div> </a> <ul id="toc-History-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Terminology" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Terminology"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Terminology</span> </div> </a> <ul id="toc-Terminology-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Problem_definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Problem_definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Problem definition</span> </div> </a> <button aria-controls="toc-Problem_definition-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Problem definition subsection</span> </button> <ul id="toc-Problem_definition-sublist" class="vector-toc-list"> <li id="toc-Informal_description" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Informal_description"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Informal description</span> </div> </a> <ul id="toc-Informal_description-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Formalized_description" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Formalized_description"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Formalized description</span> </div> </a> <ul id="toc-Formalized_description-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Example" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Example"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Example</span> </div> </a> <ul id="toc-Example-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Basic_technique" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Basic_technique"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Basic technique</span> </div> </a> <button aria-controls="toc-Basic_technique-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Basic technique subsection</span> </button> <ul id="toc-Basic_technique-sublist" class="vector-toc-list"> <li id="toc-Compression" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Compression"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Compression</span> </div> </a> <ul id="toc-Compression-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Decompression" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Decompression"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Decompression</span> </div> </a> <ul id="toc-Decompression-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Main_properties" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Main_properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Main properties</span> </div> </a> <button aria-controls="toc-Main_properties-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Main properties subsection</span> </button> <ul id="toc-Main_properties-sublist" class="vector-toc-list"> <li id="toc-Optimality" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Optimality"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Optimality</span> </div> </a> <ul id="toc-Optimality-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Variations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Variations"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Variations</span> </div> </a> <button aria-controls="toc-Variations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Variations subsection</span> </button> <ul id="toc-Variations-sublist" class="vector-toc-list"> <li id="toc-n-ary_Huffman_coding" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#n-ary_Huffman_coding"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.1</span> <span><i>n</i>-ary Huffman coding</span> </div> </a> <ul id="toc-n-ary_Huffman_coding-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Adaptive_Huffman_coding" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Adaptive_Huffman_coding"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2</span> <span>Adaptive Huffman coding</span> </div> </a> <ul id="toc-Adaptive_Huffman_coding-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Huffman_template_algorithm" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Huffman_template_algorithm"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3</span> <span>Huffman template algorithm</span> </div> </a> <ul id="toc-Huffman_template_algorithm-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Length-limited_Huffman_coding/minimum_variance_Huffman_coding" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Length-limited_Huffman_coding/minimum_variance_Huffman_coding"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.4</span> <span>Length-limited Huffman coding/minimum variance Huffman coding</span> </div> </a> <ul id="toc-Length-limited_Huffman_coding/minimum_variance_Huffman_coding-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Huffman_coding_with_unequal_letter_costs" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Huffman_coding_with_unequal_letter_costs"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.5</span> <span>Huffman coding with unequal letter costs</span> </div> </a> <ul id="toc-Huffman_coding_with_unequal_letter_costs-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Optimal_alphabetic_binary_trees_(Hu–Tucker_coding)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Optimal_alphabetic_binary_trees_(Hu–Tucker_coding)"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.6</span> <span>Optimal alphabetic binary trees (Hu–Tucker coding)</span> </div> </a> <ul id="toc-Optimal_alphabetic_binary_trees_(Hu–Tucker_coding)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_canonical_Huffman_code" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#The_canonical_Huffman_code"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.7</span> <span>The canonical Huffman code</span> </div> </a> <ul id="toc-The_canonical_Huffman_code-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Applications</span> </div> </a> <ul id="toc-Applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bibliography" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bibliography"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Bibliography</span> </div> </a> <ul id="toc-Bibliography-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Huffman coding</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 36 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-36" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">36 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%AA%D8%B1%D9%85%D9%8A%D8%B2_%D9%87%D9%88%D9%81%D9%85%D8%A7%D9%86" title="ترميز هوفمان – Arabic" lang="ar" hreflang="ar" data-title="ترميز هوفمان" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Haffman_kodla%C5%9Fd%C4%B1rmas%C4%B1" title="Haffman kodlaşdırması – Azerbaijani" lang="az" hreflang="az" data-title="Haffman kodlaşdırması" data-language-autonym="Azərbaycanca" data-language-local-name="Azerbaijani" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Codificaci%C3%B3_de_Huffman" title="Codificació de Huffman – Catalan" lang="ca" hreflang="ca" data-title="Codificació de Huffman" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Huffmanovo_k%C3%B3dov%C3%A1n%C3%AD" title="Huffmanovo kódování – Czech" lang="cs" hreflang="cs" data-title="Huffmanovo kódování" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Huffman-kodning" title="Huffman-kodning – Danish" lang="da" hreflang="da" data-title="Huffman-kodning" data-language-autonym="Dansk" data-language-local-name="Danish" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Huffman-Kodierung" title="Huffman-Kodierung – German" lang="de" hreflang="de" data-title="Huffman-Kodierung" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Huffmani_kodeerimine" title="Huffmani kodeerimine – Estonian" lang="et" hreflang="et" data-title="Huffmani kodeerimine" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%9A%CF%89%CE%B4%CE%B9%CE%BA%CE%BF%CF%80%CE%BF%CE%AF%CE%B7%CF%83%CE%B7_%CE%A7%CE%BF%CF%8D%CF%86%CE%BC%CE%B1%CE%BD" title="Κωδικοποίηση Χούφμαν – Greek" lang="el" hreflang="el" data-title="Κωδικοποίηση Χούφμαν" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman" title="Codificación Huffman – Spanish" lang="es" hreflang="es" data-title="Codificación Huffman" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Kodado_de_Huffman" title="Kodado de Huffman – Esperanto" lang="eo" hreflang="eo" data-title="Kodado de Huffman" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Huffman_kodifikazio" title="Huffman kodifikazio – Basque" lang="eu" hreflang="eu" data-title="Huffman kodifikazio" data-language-autonym="Euskara" data-language-local-name="Basque" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%DA%A9%D8%AF%DA%AF%D8%B0%D8%A7%D8%B1%DB%8C_%D9%87%D8%A7%D9%81%D9%85%D9%86" title="کدگذاری هافمن – Persian" lang="fa" hreflang="fa" data-title="کدگذاری هافمن" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Codage_de_Huffman" title="Codage de Huffman – French" lang="fr" hreflang="fr" data-title="Codage de Huffman" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%ED%97%88%ED%94%84%EB%A8%BC_%EB%B6%80%ED%98%B8%ED%99%94" title="허프먼 부호화 – Korean" lang="ko" hreflang="ko" data-title="허프먼 부호화" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Pengodean_Huffman" title="Pengodean Huffman – Indonesian" lang="id" hreflang="id" data-title="Pengodean Huffman" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Codifica_di_Huffman" title="Codifica di Huffman – Italian" lang="it" hreflang="it" data-title="Codifica di Huffman" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A7%D7%95%D7%93_%D7%94%D7%90%D7%A4%D7%9E%D7%9F" title="קוד האפמן – Hebrew" lang="he" hreflang="he" data-title="קוד האפמן" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ka mw-list-item"><a href="https://ka.wikipedia.org/wiki/%E1%83%B0%E1%83%90%E1%83%A4%E1%83%9B%E1%83%94%E1%83%9C%E1%83%98%E1%83%A1_%E1%83%99%E1%83%9D%E1%83%93%E1%83%98" title="ჰაფმენის კოდი – Georgian" lang="ka" hreflang="ka" data-title="ჰაფმენის კოდი" data-language-autonym="ქართული" data-language-local-name="Georgian" class="interlanguage-link-target"><span>ქართული</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Codifica_de_Huffman" title="Codifica de Huffman – Lombard" lang="lmo" hreflang="lmo" data-title="Codifica de Huffman" data-language-autonym="Lombard" data-language-local-name="Lombard" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Huffman-k%C3%B3dol%C3%A1s" title="Huffman-kódolás – Hungarian" lang="hu" hreflang="hu" data-title="Huffman-kódolás" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-ml mw-list-item"><a href="https://ml.wikipedia.org/wiki/%E0%B4%B9%E0%B4%AB%E0%B5%8D%E2%80%8C%E0%B4%AE%E0%B4%BE%E0%B5%BB_%E0%B4%95%E0%B5%8B%E0%B4%A1%E0%B4%BF%E0%B4%99%E0%B5%8D" title="ഹഫ്‌മാൻ കോഡിങ് – Malayalam" lang="ml" hreflang="ml" data-title="ഹഫ്‌മാൻ കോഡിങ്" data-language-autonym="മലയാളം" data-language-local-name="Malayalam" class="interlanguage-link-target"><span>മലയാളം</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Huffmancodering" title="Huffmancodering – Dutch" lang="nl" hreflang="nl" data-title="Huffmancodering" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7" title="ハフマン符号 – Japanese" lang="ja" hreflang="ja" data-title="ハフマン符号" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Huffman-koding" title="Huffman-koding – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Huffman-koding" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Kodowanie_Huffmana" title="Kodowanie Huffmana – Polish" lang="pl" hreflang="pl" data-title="Kodowanie Huffmana" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Codifica%C3%A7%C3%A3o_de_Huffman" title="Codificação de Huffman – Portuguese" lang="pt" hreflang="pt" data-title="Codificação de Huffman" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%A5%D0%B0%D1%84%D1%84%D0%BC%D0%B0%D0%BD%D0%B0" title="Код Хаффмана – Russian" lang="ru" hreflang="ru" data-title="Код Хаффмана" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Huffman_coding" title="Huffman coding – Simple English" lang="en-simple" hreflang="en-simple" data-title="Huffman coding" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A5%D0%B0%D1%84%D0%BC%D0%B0%D0%BD%D0%BE%D0%B2%D0%B8_%D0%BA%D0%BE%D0%B4%D0%BE%D0%B2%D0%B8" title="Хафманови кодови – Serbian" lang="sr" hreflang="sr" data-title="Хафманови кодови" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Huffmanin_koodaus" title="Huffmanin koodaus – Finnish" lang="fi" hreflang="fi" data-title="Huffmanin koodaus" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Huffmankodning" title="Huffmankodning – Swedish" lang="sv" hreflang="sv" data-title="Huffmankodning" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B9%80%E0%B8%82%E0%B9%89%E0%B8%B2%E0%B8%A3%E0%B8%AB%E0%B8%B1%E0%B8%AA%E0%B8%AE%E0%B8%B1%E0%B8%9F%E0%B8%9F%E0%B9%8C%E0%B9%81%E0%B8%A1%E0%B8%99" title="การเข้ารหัสฮัฟฟ์แมน – Thai" lang="th" hreflang="th" data-title="การเข้ารหัสฮัฟฟ์แมน" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Huffman_kodu" title="Huffman kodu – Turkish" lang="tr" hreflang="tr" data-title="Huffman kodu" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%93%D0%B0%D1%84%D1%84%D0%BC%D0%B0%D0%BD%D0%B0" title="Код Гаффмана – Ukrainian" lang="uk" hreflang="uk" data-title="Код Гаффмана" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/M%C3%A3_h%C3%B3a_Huffman" title="Mã hóa Huffman – Vietnamese" lang="vi" hreflang="vi" data-title="Mã hóa Huffman" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81" title="霍夫曼编码 – Chinese" lang="zh" hreflang="zh" data-title="霍夫曼编码" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q2647#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Huffman_coding" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Huffman_coding" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Huffman_coding"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Huffman_coding&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Huffman_coding&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Huffman_coding"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Huffman_coding&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Huffman_coding&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Huffman_coding" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Huffman_coding" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Huffman_coding&oldid=1271869873" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Huffman_coding&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Huffman_coding&id=1271869873&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FHuffman_coding"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FHuffman_coding"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Huffman_coding&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Huffman_coding&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Huffman_coding" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q2647" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Technique to compress data</div> <p class="mw-empty-elt"> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Huffman_tree_2.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/220px-Huffman_tree_2.svg.png" decoding="async" width="220" height="142" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/330px-Huffman_tree_2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/440px-Huffman_tree_2.svg.png 2x" data-file-width="625" data-file-height="402" /></a><figcaption>Huffman tree generated from the exact frequencies of the text "this is an example of a huffman tree". Encoding the sentence with this code requires 135 (or 147) bits, as opposed to 288 (or 180) bits if 36 characters of 8 (or 5) bits were used (This assumes that the code tree structure is known to the decoder and thus does not need to be counted as part of the transmitted information). The frequencies and codes of each character are shown in the accompanying table. <table class="wikitable sortable"> <tbody><tr> <th>Char</th> <th>Freq</th> <th>Code </th></tr> <tr> <td>space</td> <td>7</td> <td>111 </td></tr> <tr> <td>a</td> <td>4</td> <td>010 </td></tr> <tr> <td>e</td> <td>4</td> <td>000 </td></tr> <tr> <td>f</td> <td>3</td> <td>1101 </td></tr> <tr> <td>h</td> <td>2</td> <td>1010 </td></tr> <tr> <td>i</td> <td>2</td> <td>1000 </td></tr> <tr> <td>m</td> <td>2</td> <td>0111 </td></tr> <tr> <td>n</td> <td>2</td> <td>0010 </td></tr> <tr> <td>s</td> <td>2</td> <td>1011 </td></tr> <tr> <td>t</td> <td>2</td> <td>0110 </td></tr> <tr> <td>l</td> <td>1</td> <td>11001 </td></tr> <tr> <td>o</td> <td>1</td> <td>00110 </td></tr> <tr> <td>p</td> <td>1</td> <td>10011 </td></tr> <tr> <td>r</td> <td>1</td> <td>11000 </td></tr> <tr> <td>u</td> <td>1</td> <td>00111 </td></tr> <tr> <td>x</td> <td>1</td> <td>10010 </td></tr></tbody></table> </figcaption></figure> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a> and <a href="/wiki/Information_theory" title="Information theory">information theory</a>, a <b>Huffman code</b> is a particular type of optimal <a href="/wiki/Prefix_code" title="Prefix code">prefix code</a> that is commonly used for <a href="/wiki/Lossless_data_compression" class="mw-redirect" title="Lossless data compression">lossless data compression</a>. The process of finding or using such a code is <b>Huffman coding</b>, an algorithm developed by <a href="/wiki/David_A._Huffman" title="David A. Huffman">David A. Huffman</a> while he was a <a href="/wiki/Doctor_of_Science" title="Doctor of Science">Sc.D.</a> student at <a href="/wiki/Massachusetts_Institute_of_Technology" title="Massachusetts Institute of Technology">MIT</a>, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>The output from Huffman's algorithm can be viewed as a <a href="/wiki/Variable-length_code" title="Variable-length code">variable-length code</a> table for encoding a source symbol (such as a character in a file). The algorithm derives this table from the estimated probability or frequency of occurrence (<i>weight</i>) for each possible value of the source symbol. As in other <a href="/wiki/Entropy_encoding" class="mw-redirect" title="Entropy encoding">entropy encoding</a> methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, finding a code in time <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear</a> to the number of input weights if these weights are sorted.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> However, although optimal among methods encoding symbols separately, Huffman coding <a href="#Optimality">is not always optimal</a> among all compression methods – it is replaced with <a href="/wiki/Arithmetic_coding" title="Arithmetic coding">arithmetic coding</a><sup id="cite_ref-LiDrew2014_3-0" class="reference"><a href="#cite_note-LiDrew2014-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> or <a href="/wiki/Asymmetric_numeral_systems" title="Asymmetric numeral systems">asymmetric numeral systems</a><sup id="cite_ref-PCS2015_4-0" class="reference"><a href="#cite_note-PCS2015-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> if a better compression ratio is required. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="History">History</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=1" title="Edit section: History"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In 1951, <a href="/wiki/David_A._Huffman" title="David A. Huffman">David A. Huffman</a> and his <a href="/wiki/MIT" class="mw-redirect" title="MIT">MIT</a> <a href="/wiki/Information_theory" title="Information theory">information theory</a> classmates were given the choice of a term paper or a final <a href="/wiki/Exam" title="Exam">exam</a>. The professor, <a href="/wiki/Robert_M._Fano" class="mw-redirect" title="Robert M. Fano">Robert M. Fano</a>, assigned a <a href="/wiki/Term_paper" title="Term paper">term paper</a> on the problem of finding the most efficient binary code. Huffman, unable to prove any codes were the most efficient, was about to give up and start studying for the final when he hit upon the idea of using a frequency-sorted <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a> and quickly proved this method the most efficient.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p><p>In doing so, Huffman outdid Fano, who had worked with <a href="/wiki/Claude_Shannon" title="Claude Shannon">Claude Shannon</a> to develop a similar code. Building the tree from the bottom up guaranteed optimality, unlike the top-down approach of <a href="/wiki/Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano coding</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Terminology">Terminology</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=2" title="Edit section: Terminology"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a <a href="/wiki/Prefix_code" title="Prefix code">prefix code</a> (sometimes called "prefix-free codes", that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol). Huffman coding is such a widespread method for creating prefix codes that the term "Huffman code" is widely used as a synonym for "prefix code" even when such a code is not produced by Huffman's algorithm. </p> <div class="mw-heading mw-heading2"><h2 id="Problem_definition">Problem definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=3" title="Edit section: Problem definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Huffman_coding" title="Special:EditPage/Huffman coding">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Huffman+coding%22">"Huffman coding"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Huffman+coding%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Huffman+coding%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Huffman+coding%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Huffman+coding%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Huffman+coding%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">December 2021</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:HuffmanCodeAlg.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/d8/HuffmanCodeAlg.png/220px-HuffmanCodeAlg.png" decoding="async" width="220" height="337" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/d8/HuffmanCodeAlg.png/330px-HuffmanCodeAlg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/d8/HuffmanCodeAlg.png/440px-HuffmanCodeAlg.png 2x" data-file-width="496" data-file-height="759" /></a><figcaption>Constructing a Huffman tree</figcaption></figure> <div class="mw-heading mw-heading3"><h3 id="Informal_description">Informal description</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=4" title="Edit section: Informal description"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <dl><dt>Given</dt> <dd>A set of symbols <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> and for each symbol <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/51186ba8afb2067573a9082d55dd383df1ea9214" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.67ex; height:2.176ex;" alt="{\displaystyle x\in S}"></span>, the frequency <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f_{x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bb36605624ab2287dc5ec558513c625b88acfee3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.312ex; height:2.509ex;" alt="{\displaystyle f_{x}}"></span> representing the fraction of symbols in the text that are equal to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"></span>.<sup id="cite_ref-kleinberg&Tardos_6-0" class="reference"><a href="#cite_note-kleinberg&Tardos-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup></dd> <dt>Find</dt> <dd>A <a href="/wiki/Prefix_code" title="Prefix code">prefix-free binary code</a> (a set of codewords) with minimum <a href="/wiki/Expected_value" title="Expected value">expected</a> codeword length (equivalently, a tree with minimum <a href="/w/index.php?title=Weighted_path_length_from_the_root&action=edit&redlink=1" class="new" title="Weighted path length from the root (page does not exist)">weighted path length from the root</a>).</dd></dl> <div class="mw-heading mw-heading3"><h3 id="Formalized_description">Formalized description</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=5" title="Edit section: Formalized description"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Input</b>.<br /> Alphabet <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=(a_{1},a_{2},\dots ,a_{n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A=(a_{1},a_{2},\dots ,a_{n})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cd7971cd308b54a9afb4b897a990d32c3c5174f4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.879ex; height:2.843ex;" alt="{\displaystyle A=(a_{1},a_{2},\dots ,a_{n})}"></span>, which is the symbol alphabet of size <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>. <br /> Tuple <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W=(w_{1},w_{2},\dots ,w_{n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>W</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W=(w_{1},w_{2},\dots ,w_{n})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eea6a64cad1424b3d68c8ac38a360c5383486ce4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.875ex; height:2.843ex;" alt="{\displaystyle W=(w_{1},w_{2},\dots ,w_{n})}"></span>, which is the tuple of the (positive) symbol weights (usually proportional to probabilities), i.e. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}=\operatorname {weight} \left(a_{i}\right),\,i\in \{1,2,\dots ,n\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>=</mo> <mi>weight</mi> <mo>⁡</mo> <mrow> <mo>(</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>)</mo> </mrow> <mo>,</mo> <mspace width="thinmathspace" /> <mi>i</mi> <mo>∈</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle w_{i}=\operatorname {weight} \left(a_{i}\right),\,i\in \{1,2,\dots ,n\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d928718b91ee67e2ffe43864cdd8a4e9e815007" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.439ex; height:2.843ex;" alt="{\displaystyle w_{i}=\operatorname {weight} \left(a_{i}\right),\,i\in \{1,2,\dots ,n\}}"></span>. <br /> <br /> <b>Output</b>.<br /> Code <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\left(W\right)=(c_{1},c_{2},\dots ,c_{n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mrow> <mo>(</mo> <mi>W</mi> <mo>)</mo> </mrow> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C\left(W\right)=(c_{1},c_{2},\dots ,c_{n})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea3b6a7da9769c2d5f87be6ea75b14ea4ee97621" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.865ex; height:2.843ex;" alt="{\displaystyle C\left(W\right)=(c_{1},c_{2},\dots ,c_{n})}"></span>, which is the tuple of (binary) codewords, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01acb7953ba52c2aa44264b5d0f8fd223aa178a2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.807ex; height:2.009ex;" alt="{\displaystyle c_{i}}"></span> is the codeword for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i},\,i\in \{1,2,\dots ,n\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>,</mo> <mspace width="thinmathspace" /> <mi>i</mi> <mo>∈</mo> <mo fence="false" stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{i},\,i\in \{1,2,\dots ,n\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/447bbca06d834d18d87bd270b4eadede332990bb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.35ex; height:2.843ex;" alt="{\displaystyle a_{i},\,i\in \{1,2,\dots ,n\}}"></span>.<br /> <br /> <b>Goal</b>.<br /> Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle L(C(W))=\sum _{i=1}^{n}w_{i}\operatorname {length} (c_{i})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>L</mi> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">(</mo> <mi>W</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </munderover> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mi>length</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle L(C(W))=\sum _{i=1}^{n}w_{i}\operatorname {length} (c_{i})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c450f9a883d163b16ded56056d9b0c5f720874f6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:31.041ex; height:3.176ex;" alt="{\textstyle L(C(W))=\sum _{i=1}^{n}w_{i}\operatorname {length} (c_{i})}"></span> be the weighted path length of code <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}"></span>. Condition: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(C(W))\leq L(T(W))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">(</mo> <mi>W</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>≤</mo> <mi>L</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">(</mo> <mi>W</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L(C(W))\leq L(T(W))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/495b97b04a92245e7a8b3fc3eeda5b3b6fff6ef8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.774ex; height:2.843ex;" alt="{\displaystyle L(C(W))\leq L(T(W))}"></span> for any code <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(W)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mo stretchy="false">(</mo> <mi>W</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T(W)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/12bbad443fb07fbf7882a2a4af08d919952cb4c9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.881ex; height:2.843ex;" alt="{\displaystyle T(W)}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Example">Example</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=6" title="Edit section: Example"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>We give an example of the result of Huffman coding for a code with five characters and given weights. We will not verify that it minimizes <i>L</i> over all codes, but we will compute <i>L</i> and compare it to the <a href="/wiki/Shannon_entropy" class="mw-redirect" title="Shannon entropy">Shannon entropy</a> <i>H</i> of the given set of weights; the result is nearly optimal. </p> <table class="wikitable"> <tbody><tr> <th rowspan="2" style="background:#efefef">Input (<i>A</i>, <i>W</i>) </th> <th style="background:#efefef;font-weight:normal">Symbol (<span class="texhtml"><i>a</i><sub><i>i</i></sub></span>) </th> <td align="center" style="background:#efefef">a </td> <td align="center" style="background:#efefef">b </td> <td align="center" style="background:#efefef">c </td> <td align="center" style="background:#efefef">d </td> <td align="center" style="background:#efefef">e </td> <th style="background:#efefef">Sum </th></tr> <tr> <th style="background:#efefef;font-weight:normal">Weights (<span class="texhtml"><i>w</i><sub><i>i</i></sub></span>) </th> <td align="center">0.10 </td> <td align="center">0.15 </td> <td align="center">0.30 </td> <td align="center">0.16 </td> <td align="center">0.29 </td> <td align="center">= 1 </td></tr> <tr> <th rowspan="3" style="background:#efefef">Output <i>C</i> </th> <th style="background:#efefef;font-weight:normal">Codewords (<span class="texhtml"><i>c</i><sub><i>i</i></sub></span>) </th> <td align="center"><code>010</code> </td> <td align="center"><code>011</code> </td> <td align="center"><code>11</code> </td> <td align="center"><code>00</code> </td> <td align="center"><code>10</code> </td> <td rowspan="2">  </td></tr> <tr> <th style="background:#efefef;font-weight:normal">Codeword length (in bits)<br />(<span class="texhtml"><i>ℓ</i><sub><i>i</i></sub></span>) </th> <td align="center">3 </td> <td align="center">3 </td> <td align="center">2 </td> <td align="center">2 </td> <td align="center">2 </td></tr> <tr> <th style="background:#efefef;font-weight:normal">Contribution to weighted path length<br />(<span class="texhtml"><i>ℓ</i><sub><i>i</i></sub></span> <span class="texhtml"><i>w</i><sub><i>i</i></sub></span> ) </th> <td align="center">0.30 </td> <td align="center">0.45 </td> <td align="center">0.60 </td> <td align="center">0.32 </td> <td align="center">0.58 </td> <td align="center"><i>L</i>(<i>C</i>) = 2.25 </td></tr> <tr> <th rowspan="3" style="background:#efefef">Optimality </th> <th style="background:#efefef;font-weight:normal">Probability budget<br />(<span class="texhtml">2<sup>−<i>ℓ</i><sub><i>i</i></sub></sup></span>) </th> <td align="center">1/8 </td> <td align="center">1/8 </td> <td align="center">1/4 </td> <td align="center">1/4 </td> <td align="center">1/4 </td> <td align="center">= 1.00 </td></tr> <tr> <th style="background: #efefef; font-weight: normal;">Information content (in bits)<br />(<span class="texhtml">−log<sub>2</sub> <i>w</i><sub><i>i</i></sub></span>) ≈ </th> <td align="center">3.32 </td> <td align="center">2.74 </td> <td align="center">1.74 </td> <td align="center">2.64 </td> <td align="center">1.79 </td> <td align="center">  </td></tr> <tr> <th style="background: #efefef; font-weight: normal;">Contribution to entropy<br />(<span class="texhtml">−<i>w</i><sub><i>i</i></sub> log<sub>2</sub> <i>w</i><sub><i>i</i></sub></span>) </th> <td align="center">0.332 </td> <td align="center">0.411 </td> <td align="center">0.521 </td> <td align="center">0.423 </td> <td align="center">0.518 </td> <td align="center"><i>H</i>(<i>A</i>) = 2.205 </td></tr></tbody></table> <p>For any code that is <i>biunique</i>, meaning that the code is <a href="/wiki/Variable-length_code#Uniquely_decodable_codes" title="Variable-length code"><i>uniquely decodeable</i></a>, the sum of the probability budgets across all symbols is always less than or equal to one. In this example, the sum is strictly equal to one; as a result, the code is termed a <i>complete</i> code. If this is not the case, one can always derive an equivalent code by adding extra symbols (with associated null probabilities), to make the code complete while keeping it <i>biunique</i>. </p><p>As defined by <a href="/wiki/A_Mathematical_Theory_of_Communication" title="A Mathematical Theory of Communication">Shannon (1948)</a>, the information content <i>h</i> (in bits) of each symbol <i>a</i><sub>i</sub> with non-null probability is </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(a_{i})=\log _{2}{1 \over w_{i}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo stretchy="false">(</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h(a_{i})=\log _{2}{1 \over w_{i}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2799f589d23a9f11345131ef8cef9937c5e7c456" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:16.636ex; height:5.509ex;" alt="{\displaystyle h(a_{i})=\log _{2}{1 \over w_{i}}.}"></span></dd></dl> <p>The <a href="/wiki/Information_entropy" class="mw-redirect" title="Information entropy">entropy</a> <i>H</i> (in bits) is the weighted sum, across all symbols <span class="texhtml"><i>a</i><sub><i>i</i></sub></span> with non-zero probability <span class="texhtml"><i>w</i><sub><i>i</i></sub></span>, of the information content of each symbol: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H(A)=\sum _{w_{i}>0}w_{i}h(a_{i})=\sum _{w_{i}>0}w_{i}\log _{2}{1 \over w_{i}}=-\sum _{w_{i}>0}w_{i}\log _{2}w_{i}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> <mo stretchy="false">(</mo> <mi>A</mi> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>></mo> <mn>0</mn> </mrow> </munder> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mi>h</mi> <mo stretchy="false">(</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>></mo> <mn>0</mn> </mrow> </munder> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mfrac> </mrow> <mo>=</mo> <mo>−</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>></mo> <mn>0</mn> </mrow> </munder> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H(A)=\sum _{w_{i}>0}w_{i}h(a_{i})=\sum _{w_{i}>0}w_{i}\log _{2}{1 \over w_{i}}=-\sum _{w_{i}>0}w_{i}\log _{2}w_{i}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c9bcff36f9acd0c27a57e42c99cc8fda6410934a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:58.555ex; height:6.676ex;" alt="{\displaystyle H(A)=\sum _{w_{i}>0}w_{i}h(a_{i})=\sum _{w_{i}>0}w_{i}\log _{2}{1 \over w_{i}}=-\sum _{w_{i}>0}w_{i}\log _{2}w_{i}.}"></span></dd></dl> <p>(Note: A symbol with zero probability has zero contribution to the entropy, since <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lim _{w\to 0^{+}}w\log _{2}w=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munder> <mo movablelimits="true" form="prefix">lim</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>w</mi> <mo stretchy="false">→</mo> <msup> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> </mrow> </msup> </mrow> </munder> <mi>w</mi> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>w</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lim _{w\to 0^{+}}w\log _{2}w=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a25181e71e7e86ccfe31ba981214e6b31f57e7c8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:17.621ex; height:4.176ex;" alt="{\displaystyle \lim _{w\to 0^{+}}w\log _{2}w=0}"></span>. So for simplicity, symbols with zero probability can be left out of the formula above.) </p><p>As a consequence of <a href="/wiki/Shannon%27s_source_coding_theorem" title="Shannon's source coding theorem">Shannon's source coding theorem</a>, the entropy is a measure of the smallest codeword length that is theoretically possible for the given alphabet with associated weights. In this example, the weighted average codeword length is 2.25 bits per symbol, only slightly larger than the calculated entropy of 2.205 bits per symbol. So not only is this code optimal in the sense that no other feasible code performs better, but it is very close to the theoretical limit established by Shannon. </p><p>In general, a Huffman code need not be unique. Thus the set of Huffman codes for a given probability distribution is a non-empty subset of the codes minimizing <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(C)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L(C)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f31c05759c645f617ea0ef5952ea24ccef557716" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.158ex; height:2.843ex;" alt="{\displaystyle L(C)}"></span> for that probability distribution. (However, for each minimizing codeword length assignment, there exists at least one Huffman code with those lengths.) </p> <div class="mw-heading mw-heading2"><h2 id="Basic_technique">Basic technique</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=7" title="Edit section: Basic technique"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Compression">Compression</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=8" title="Edit section: Compression"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Huffman_coding_visualisation.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Huffman_coding_visualisation.svg/330px-Huffman_coding_visualisation.svg.png" decoding="async" width="330" height="248" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Huffman_coding_visualisation.svg/495px-Huffman_coding_visualisation.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Huffman_coding_visualisation.svg/660px-Huffman_coding_visualisation.svg.png 2x" data-file-width="512" data-file-height="384" /></a><figcaption>Visualisation of the use of Huffman coding to encode the message "A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED". In steps 2 to 6, the letters are sorted by increasing frequency, and the least frequent two at each step are combined and reinserted into the list, and a partial tree is constructed. The final tree in step 6 is traversed to generate the dictionary in step 7. Step 8 uses it to encode the message.</figcaption></figure> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Huffman_coding_example.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/74/Huffman_coding_example.svg/220px-Huffman_coding_example.svg.png" decoding="async" width="220" height="106" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/74/Huffman_coding_example.svg/330px-Huffman_coding_example.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/74/Huffman_coding_example.svg/440px-Huffman_coding_example.svg.png 2x" data-file-width="277" data-file-height="133" /></a><figcaption>A source generates 4 different symbols <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a_{1},a_{2},a_{3},a_{4}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{a_{1},a_{2},a_{3},a_{4}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e79d949f0a374ca309789acfeb965f513bd58df0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.563ex; height:2.843ex;" alt="{\displaystyle \{a_{1},a_{2},a_{3},a_{4}\}}"></span> with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0.4;0.35;0.2;0.05\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>0.4</mn> <mo>;</mo> <mn>0.35</mn> <mo>;</mo> <mn>0.2</mn> <mo>;</mo> <mn>0.05</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{0.4;0.35;0.2;0.05\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/09d9a62726a39dba09cc351e882ce53aac27f8c9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.639ex; height:2.843ex;" alt="{\displaystyle \{0.4;0.35;0.2;0.05\}}"></span>. A binary tree is generated from left to right taking the two least probable symbols and putting them together to form another equivalent symbol having a probability that equals the sum of the two symbols. The process is repeated until there is just one symbol. The tree can then be read backwards, from right to left, assigning different bits to different branches. The final Huffman code is: <table class="wikitable"> <tbody><tr> <th>Symbol</th> <th>Code </th></tr> <tr> <td>a1</td> <td>0 </td></tr> <tr> <td>a2</td> <td>10 </td></tr> <tr> <td>a3</td> <td>110 </td></tr> <tr> <td>a4</td> <td>111 </td></tr> </tbody></table> The standard way to represent a signal made of 4 symbols is by using 2 bits/symbol, but the <a href="/wiki/Information_entropy" class="mw-redirect" title="Information entropy">entropy</a> of the source is 1.74 bits/symbol. If this Huffman code is used to represent the signal, then the average length is lowered to 1.85 bits/symbol; it is still far from the theoretical limit because the probabilities of the symbols are different from negative powers of two.</figcaption></figure> <p>The technique works by creating a <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a> of nodes. These can be stored in a regular <a href="/wiki/Array_data_type" class="mw-redirect" title="Array data type">array</a>, the size of which depends on the number of symbols, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>. A node can be either a <a href="/wiki/Leaf_node" class="mw-redirect" title="Leaf node">leaf node</a> or an <a href="/wiki/Internal_node" class="mw-redirect" title="Internal node">internal node</a>. Initially, all nodes are leaf nodes, which contain the <b>symbol</b> itself, the <b>weight</b> (frequency of appearance) of the symbol and optionally, a link to a <b>parent</b> node which makes it easy to read the code (in reverse) starting from a leaf node. Internal nodes contain a <b>weight</b>, links to <b>two child nodes</b> and an optional link to a <b>parent</b> node. As a common convention, bit '0' represents following the left child and bit '1' represents following the right child. A finished tree has up to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> leaf nodes and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}"></span> internal nodes. A Huffman tree that omits unused symbols produces the most optimal code lengths. </p><p>The process begins with the leaf nodes containing the probabilities of the symbol they represent. Then, the process takes the two nodes with smallest probability, and creates a new internal node having these two nodes as children. The weight of the new node is set to the sum of the weight of the children. We then apply the process again, on the new internal node and on the remaining nodes (i.e., we exclude the two leaf nodes), we repeat this process until only one node remains, which is the root of the Huffman tree. </p><p>The simplest construction algorithm uses a <a href="/wiki/Priority_queue" title="Priority queue">priority queue</a> where the node with lowest probability is given highest priority: </p> <ol><li>Create a leaf node for each symbol and add it to the priority queue.</li> <li>While there is more than one node in the queue: <ol><li>Remove the two nodes of highest priority (lowest probability) from the queue</li> <li>Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.</li> <li>Add the new node to the queue.</li></ol></li> <li>The remaining node is the root node and the tree is complete.</li></ol> <p>Since efficient priority queue data structures require O(log <i>n</i>) time per insertion, and a tree with <i>n</i> leaves has 2<i>n</i>−1 nodes, this algorithm operates in O(<i>n</i> log <i>n</i>) time, where <i>n</i> is the number of symbols. </p><p>If the symbols are sorted by probability, there is a <a href="/wiki/Linear-time" class="mw-redirect" title="Linear-time">linear-time</a> (O(<i>n</i>)) method to create a Huffman tree using two <a href="/wiki/Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">queues</a>, the first one containing the initial weights (along with pointers to the associated leaves), and combined weights (along with pointers to the trees) being put in the back of the second queue. This assures that the lowest weight is always kept at the front of one of the two queues: </p> <ol><li>Start with as many leaves as there are symbols.</li> <li>Enqueue all leaf nodes into the first queue (by probability in increasing order so that the least likely item is in the head of the queue).</li> <li>While there is more than one node in the queues: <ol><li>Dequeue the two nodes with the lowest weight by examining the fronts of both queues.</li> <li>Create a new internal node, with the two just-removed nodes as children (either node can be either child) and the sum of their weights as the new weight.</li> <li>Enqueue the new node into the rear of the second queue.</li></ol></li> <li>The remaining node is the root node; the tree has now been generated.</li></ol> <p>Once the Huffman tree has been generated, it is traversed to generate a dictionary which maps the symbols to binary codes as follows: </p> <ol><li>Start with current node set to the root.</li> <li>If node is not a leaf node, label the edge to the left child as 0 and the edge to the right child as 1. Repeat the process at both the left child and the right child.</li></ol> <p>The final encoding of any symbol is then read by a concatenation of the labels on the edges along the path from the root node to the symbol. </p><p>In many cases, time complexity is not very important in the choice of algorithm here, since <i>n</i> here is the number of symbols in the alphabet, which is typically a very small number (compared to the length of the message to be encoded); whereas complexity analysis concerns the behavior when <i>n</i> grows to be very large. </p><p>It is generally beneficial to minimize the variance of codeword length. For example, a communication buffer receiving Huffman-encoded data may need to be larger to deal with especially long symbols if the tree is especially unbalanced. To minimize variance, simply break ties between queues by choosing the item in the first queue. This modification will retain the mathematical optimality of the Huffman coding while both minimizing variance and minimizing the length of the longest character code. </p> <div class="mw-heading mw-heading3"><h3 id="Decompression">Decompression</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=9" title="Edit section: Decompression"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Generally speaking, the process of decompression is simply a matter of translating the stream of prefix codes to individual byte values, usually by traversing the Huffman tree node by node as each bit is read from the input stream (reaching a leaf node necessarily terminates the search for that particular byte value). Before this can take place, however, the Huffman tree must be somehow reconstructed. In the simplest case, where character frequencies are fairly predictable, the tree can be preconstructed (and even statistically adjusted on each compression cycle) and thus reused every time, at the expense of at least some measure of compression efficiency. Otherwise, the information to reconstruct the tree must be sent a priori. A naive approach might be to prepend the frequency count of each character to the compression stream. Unfortunately, the overhead in such a case could amount to several kilobytes, so this method has little practical use. If the data is compressed using <a href="/wiki/Canonical_Huffman_code" title="Canonical Huffman code">canonical encoding</a>, the compression model can be precisely reconstructed with just <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\cdot 2^{B}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo>⋅</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>B</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B\cdot 2^{B}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b7c37b838e708201613cb1bcdb5169eb4b163749" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.085ex; height:2.676ex;" alt="{\displaystyle B\cdot 2^{B}}"></span> bits of information (where <span class="texhtml mvar" style="font-style:italic;">B</span> is the number of bits per symbol). Another method is to simply prepend the Huffman tree, bit by bit, to the output stream. For example, assuming that the value of 0 represents a parent node and 1 a leaf node, whenever the latter is encountered the tree building routine simply reads the next 8 bits to determine the character value of that particular leaf. The process continues recursively until the last leaf node is reached; at that point, the Huffman tree will thus be faithfully reconstructed. The overhead using such a method ranges from roughly 2 to 320 bytes (assuming an 8-bit alphabet). Many other techniques are possible as well. In any case, since the compressed data can include unused "trailing bits" the decompressor must be able to determine when to stop producing output. This can be accomplished by either transmitting the length of the decompressed data along with the compression model or by defining a special code symbol to signify the end of input (the latter method can adversely affect code length optimality, however). </p> <div class="mw-heading mw-heading2"><h2 id="Main_properties">Main properties</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=10" title="Edit section: Main properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The probabilities used can be generic ones for the application domain that are based on average experience, or they can be the actual frequencies found in the text being compressed. This requires that a <a href="/wiki/Frequency_table" class="mw-redirect" title="Frequency table">frequency table</a> must be stored with the compressed text. See the Decompression section above for more information about the various techniques employed for this purpose. </p> <div class="mw-heading mw-heading3"><h3 id="Optimality">Optimality</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=11" title="Edit section: Optimality"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Arithmetic_coding#Huffman_coding" title="Arithmetic coding">Arithmetic coding § Huffman coding</a></div> <p>Huffman's original algorithm is optimal for a symbol-by-symbol coding with a known input probability distribution, i.e., separately encoding unrelated symbols in such a data stream. However, it is not optimal when the symbol-by-symbol restriction is dropped, or when the <a href="/wiki/Probability_mass_function" title="Probability mass function">probability mass functions</a> are unknown. Also, if symbols are not <a href="/wiki/Independent_and_identically_distributed" class="mw-redirect" title="Independent and identically distributed">independent and identically distributed</a>, a single code may be insufficient for optimality. Other methods such as <a href="/wiki/Arithmetic_coding" title="Arithmetic coding">arithmetic coding</a> often have better compression capability. </p><p>Although both aforementioned methods can combine an arbitrary number of symbols for more efficient coding and generally adapt to the actual input statistics, arithmetic coding does so without significantly increasing its computational or algorithmic complexities (though the simplest version is slower and more complex than Huffman coding). Such flexibility is especially useful when input probabilities are not precisely known or vary significantly within the stream. However, Huffman coding is usually faster and arithmetic coding was historically a subject of some concern over <a href="/wiki/Patent" title="Patent">patent</a> issues. Thus many technologies have historically avoided arithmetic coding in favor of Huffman and other prefix coding techniques. As of mid-2010, the most commonly used techniques for this alternative to Huffman coding have passed into the public domain as the early patents have expired. </p><p>For a set of symbols with a uniform probability distribution and a number of members which is a <a href="/wiki/Power_of_two" title="Power of two">power of two</a>, Huffman coding is equivalent to simple binary <a href="/wiki/Block_code" title="Block code">block encoding</a>, e.g., <a href="/wiki/ASCII" title="ASCII">ASCII</a> coding. This reflects the fact that compression is not possible with such an input, no matter what the compression method, i.e., doing nothing to the data is the optimal thing to do. </p><p>Huffman coding is optimal among all methods in any case where each input symbol is a known independent and identically distributed random variable having a probability that is <a href="/wiki/Dyadic_distribution" title="Dyadic distribution">dyadic</a>. Prefix codes, and thus Huffman coding in particular, tend to have inefficiency on small alphabets, where probabilities often fall between these optimal (dyadic) points. The worst case for Huffman coding can happen when the probability of the most likely symbol far exceeds 2<sup>−1</sup> = 0.5, making the upper limit of inefficiency unbounded. </p><p>There are two related approaches for getting around this particular inefficiency while still using Huffman coding. Combining a fixed number of symbols together ("blocking") often increases (and never decreases) compression. As the size of the block approaches infinity, Huffman coding theoretically approaches the entropy limit, i.e., optimal compression.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> However, blocking arbitrarily large groups of symbols is impractical, as the complexity of a Huffman code is linear in the number of possibilities to be encoded, a number that is exponential in the size of a block. This limits the amount of blocking that is done in practice. </p><p>A practical alternative, in widespread use, is <a href="/wiki/Run-length_encoding" title="Run-length encoding">run-length encoding</a>. This technique adds one step in advance of entropy coding, specifically counting (runs) of repeated symbols, which are then encoded. For the simple case of <a href="/wiki/Bernoulli_process" title="Bernoulli process">Bernoulli processes</a>, <a href="/wiki/Golomb_coding" title="Golomb coding">Golomb coding</a> is optimal among prefix codes for coding run length, a fact proved via the techniques of Huffman coding.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> A similar approach is taken by fax machines using <a href="/wiki/Modified_Huffman_coding" title="Modified Huffman coding">modified Huffman coding</a>. However, run-length coding is not as adaptable to as many input types as other compression technologies. </p> <div class="mw-heading mw-heading2"><h2 id="Variations">Variations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=12" title="Edit section: Variations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Many variations of Huffman coding exist,<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> some of which use a Huffman-like algorithm, and others of which find optimal prefix codes (while, for example, putting different restrictions on the output). Note that, in the latter case, the method need not be Huffman-like, and, indeed, need not even be <a href="/wiki/Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>. </p> <div class="mw-heading mw-heading3"><h3 id="n-ary_Huffman_coding"><i>n</i>-ary Huffman coding</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=13" title="Edit section: n-ary Huffman coding"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <b><i>n</i>-ary Huffman</b> algorithm uses the {0, 1,..., <i>n</i> − 1} alphabet to encode message and build an <i>n</i>-ary tree. This approach was considered by Huffman in his original paper. The same algorithm applies as for binary (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n=2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a02c8bd752d2cc859747ca1f3a508281bdbc3b34" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=2}"></span>) codes, except that the <i>n</i> least probable symbols are taken together, instead of just the 2 least probable. Note that for <i>n</i> greater than 2, not all sets of source words can properly form an <i>n</i>-ary tree for Huffman coding. In these cases, additional 0-probability place holders must be added. This is because the tree must form an <i>n</i> to 1 contractor;<sup class="noprint Inline-Template" style="margin-left:0.1em; white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="The text near this tag may need clarification or removal of jargon. (September 2023)">clarification needed</span></a></i>]</sup> for binary coding, this is a 2 to 1 contractor, and any sized set can form such a contractor. If the number of source words is congruent to 1 modulo <i>n</i> − 1, then the set of source words will form a proper Huffman tree. </p> <div class="mw-heading mw-heading3"><h3 id="Adaptive_Huffman_coding">Adaptive Huffman coding</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=14" title="Edit section: Adaptive Huffman coding"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A variation called <b><a href="/wiki/Adaptive_Huffman_coding" title="Adaptive Huffman coding">adaptive Huffman coding</a></b> involves calculating the probabilities dynamically based on recent actual frequencies in the sequence of source symbols, and changing the coding tree structure to match the updated probability estimates. It is used rarely in practice, since the cost of updating the tree makes it slower than optimized <a href="/wiki/Arithmetic_coding#Adaptive_arithmetic_coding" title="Arithmetic coding">adaptive arithmetic coding</a>, which is more flexible and has better compression. </p> <div class="mw-heading mw-heading3"><h3 id="Huffman_template_algorithm">Huffman template algorithm</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=15" title="Edit section: Huffman template algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Most often, the weights used in implementations of Huffman coding represent numeric probabilities, but the algorithm given above does not require this; it requires only that the weights form a <a href="/wiki/Total_order" title="Total order">totally ordered</a> <a href="/wiki/Monoid#Commutative_monoid" title="Monoid">commutative monoid</a>, meaning a way to order weights and to add them. The <b>Huffman template algorithm</b> enables one to use any kind of weights (costs, frequencies, pairs of weights, non-numerical weights) and one of many combining methods (not just addition). Such algorithms can solve other minimization problems, such as minimizing <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max _{i}\left[w_{i}+\mathrm {length} \left(c_{i}\right)\right]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munder> <mo movablelimits="true" form="prefix">max</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </munder> <mrow> <mo>[</mo> <mrow> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">l</mi> <mi mathvariant="normal">e</mi> <mi mathvariant="normal">n</mi> <mi mathvariant="normal">g</mi> <mi mathvariant="normal">t</mi> <mi mathvariant="normal">h</mi> </mrow> <mrow> <mo>(</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>)</mo> </mrow> </mrow> <mo>]</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \max _{i}\left[w_{i}+\mathrm {length} \left(c_{i}\right)\right]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1a80c0b460cf854976824c251037db43d7ed1810" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:21.645ex; height:4.009ex;" alt="{\displaystyle \max _{i}\left[w_{i}+\mathrm {length} \left(c_{i}\right)\right]}"></span>, a problem first applied to circuit design. </p> <div class="mw-heading mw-heading3"><h3 id="Length-limited_Huffman_coding/minimum_variance_Huffman_coding"><span id="Length-limited_Huffman_coding.2Fminimum_variance_Huffman_coding"></span><span class="anchor" id="Length-limited_Huffman_coding"></span><span class="anchor" id="Minimum_variance_Huffman_coding"></span>Length-limited Huffman coding/minimum variance Huffman coding</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=16" title="Edit section: Length-limited Huffman coding/minimum variance Huffman coding"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Length-limited Huffman coding</b> is a variant where the goal is still to achieve a minimum weighted path length, but there is an additional restriction that the length of each codeword must be less than a given constant. The <a href="/wiki/Package-merge_algorithm" title="Package-merge algorithm">package-merge algorithm</a> solves this problem with a simple <a href="/wiki/Greedy_algorithm" title="Greedy algorithm">greedy</a> approach very similar to that used by Huffman's algorithm. Its time complexity is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(nL)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>L</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(nL)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a115e943ca1827d51630227813a09e82b0980b8c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.56ex; height:2.843ex;" alt="{\displaystyle O(nL)}"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}"></span> is the maximum length of a codeword. No algorithm is known to solve this problem in <a href="/wiki/Big_O_notation#Orders_of_common_functions" title="Big O notation"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}"></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}"></span></a> time, unlike the presorted and unsorted conventional Huffman problems, respectively. </p> <div class="mw-heading mw-heading3"><h3 id="Huffman_coding_with_unequal_letter_costs">Huffman coding with unequal letter costs</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=17" title="Edit section: Huffman coding with unequal letter costs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the standard Huffman coding problem, it is assumed that each symbol in the set that the code words are constructed from has an equal cost to transmit: a code word whose length is <i>N</i> digits will always have a cost of <i>N</i>, no matter how many of those digits are 0s, how many are 1s, etc. When working under this assumption, minimizing the total cost of the message and minimizing the total number of digits are the same thing. </p><p><i>Huffman coding with unequal letter costs</i> is the generalization without this assumption: the letters of the encoding alphabet may have non-uniform lengths, due to characteristics of the transmission medium. An example is the encoding alphabet of <a href="/wiki/Morse_code" title="Morse code">Morse code</a>, where a 'dash' takes longer to send than a 'dot', and therefore the cost of a dash in transmission time is higher. The goal is still to minimize the weighted average codeword length, but it is no longer sufficient just to minimize the number of symbols used by the message. No algorithm is known to solve this in the same manner or with the same efficiency as conventional Huffman coding, though it has been solved by <a href="/wiki/Richard_M._Karp" title="Richard M. Karp">Richard M. Karp</a><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> whose solution has been refined for the case of integer costs by Mordecai J. Golin.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Optimal_alphabetic_binary_trees_(Hu–Tucker_coding)"><span id="Optimal_alphabetic_binary_trees_.28Hu.E2.80.93Tucker_coding.29"></span><span class="anchor" id="Hu-Tucker_coding"></span><span class="anchor" id="Alphabetic_Huffman_coding"></span><span class="anchor" id="Alphabetic_Huffman_tree"></span>Optimal alphabetic binary trees (Hu–Tucker coding)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=18" title="Edit section: Optimal alphabetic binary trees (Hu–Tucker coding)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the standard Huffman coding problem, it is assumed that any codeword can correspond to any input symbol. In the alphabetic version, the alphabetic order of inputs and outputs must be identical. Thus, for example, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=\left\{a,b,c\right\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo>=</mo> <mrow> <mo>{</mo> <mrow> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo>,</mo> <mi>c</mi> </mrow> <mo>}</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A=\left\{a,b,c\right\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5253725abd6a5bf17a59383638d748fc80e2eec0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.469ex; height:2.843ex;" alt="{\displaystyle A=\left\{a,b,c\right\}}"></span> could not be assigned code <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H\left(A,C\right)=\left\{00,1,01\right\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>,</mo> <mi>C</mi> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mrow> <mo>{</mo> <mrow> <mn>00</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mn>01</mn> </mrow> <mo>}</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H\left(A,C\right)=\left\{00,1,01\right\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c2940f22ba0b9fd277c1387648c319cae29a836b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.107ex; height:2.843ex;" alt="{\displaystyle H\left(A,C\right)=\left\{00,1,01\right\}}"></span>, but instead should be assigned either <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H\left(A,C\right)=\left\{00,01,1\right\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>,</mo> <mi>C</mi> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mrow> <mo>{</mo> <mrow> <mn>00</mn> <mo>,</mo> <mn>01</mn> <mo>,</mo> <mn>1</mn> </mrow> <mo>}</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H\left(A,C\right)=\left\{00,01,1\right\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a2f3f93c449df17971e9f5e0587e6168514b7822" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.107ex; height:2.843ex;" alt="{\displaystyle H\left(A,C\right)=\left\{00,01,1\right\}}"></span> or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H\left(A,C\right)=\left\{0,10,11\right\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> <mrow> <mo>(</mo> <mrow> <mi>A</mi> <mo>,</mo> <mi>C</mi> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mrow> <mo>{</mo> <mrow> <mn>0</mn> <mo>,</mo> <mn>10</mn> <mo>,</mo> <mn>11</mn> </mrow> <mo>}</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H\left(A,C\right)=\left\{0,10,11\right\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19021e4b2119067cacc69927449535e2dae0ee8d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.107ex; height:2.843ex;" alt="{\displaystyle H\left(A,C\right)=\left\{0,10,11\right\}}"></span>. This is also known as the <b>Hu–Tucker</b> problem, after <a href="/wiki/T._C._Hu" title="T. C. Hu">T. C. Hu</a> and <a href="/wiki/Alan_Tucker" title="Alan Tucker">Alan Tucker</a>, the authors of the paper presenting the first <a href="/wiki/Time_complexity#Quasilinear_time" title="Time complexity"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}"></span>-time</a> solution to this optimal binary alphabetic problem,<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> which has some similarities to Huffman algorithm, but is not a variation of this algorithm. A later method, the <a href="/wiki/Garsia%E2%80%93Wachs_algorithm" title="Garsia–Wachs algorithm">Garsia–Wachs algorithm</a> of <a href="/wiki/Adriano_Garsia" title="Adriano Garsia">Adriano Garsia</a> and <a href="/wiki/Michelle_L._Wachs" title="Michelle L. Wachs">Michelle L. Wachs</a> (1977), uses simpler logic to perform the same comparisons in the same total time bound. These optimal alphabetic binary trees are often used as <a href="/wiki/Binary_search_tree" title="Binary search tree">binary search trees</a>.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="The_canonical_Huffman_code">The canonical Huffman code</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=19" title="Edit section: The canonical Huffman code"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Canonical_Huffman_code" title="Canonical Huffman code">Canonical Huffman code</a></div> <p>If weights corresponding to the alphabetically ordered inputs are in numerical order, the Huffman code has the same lengths as the optimal alphabetic code, which can be found from calculating these lengths, rendering Hu–Tucker coding unnecessary. The code resulting from numerically (re-)ordered input is sometimes called the <i>canonical Huffman code</i> and is often the code used in practice, due to ease of encoding/decoding. The technique for finding this code is sometimes called <b>Huffman–Shannon–Fano coding</b>, since it is optimal like Huffman coding, but alphabetic in weight probability, like <a href="/wiki/Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano coding</a>. The Huffman–Shannon–Fano code corresponding to the example is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{000,001,01,10,11\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>000</mn> <mo>,</mo> <mn>001</mn> <mo>,</mo> <mn>01</mn> <mo>,</mo> <mn>10</mn> <mo>,</mo> <mn>11</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{000,001,01,10,11\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66716f2fabf56efc6c70dcd44dfb4c0b5937ed8b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.41ex; height:2.843ex;" alt="{\displaystyle \{000,001,01,10,11\}}"></span>, which, having the same codeword lengths as the original solution, is also optimal. But in <i>canonical Huffman code</i>, the result is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{110,111,00,01,10\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>110</mn> <mo>,</mo> <mn>111</mn> <mo>,</mo> <mn>00</mn> <mo>,</mo> <mn>01</mn> <mo>,</mo> <mn>10</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{110,111,00,01,10\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7fed0dac074f7e39fcfe91e5cae47c22bbb2f4ac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.41ex; height:2.843ex;" alt="{\displaystyle \{110,111,00,01,10\}}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=20" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Arithmetic_coding" title="Arithmetic coding">Arithmetic coding</a> and Huffman coding produce equivalent results — achieving entropy — when every symbol has a probability of the form 1/2<sup><i>k</i></sup>. In other circumstances, arithmetic coding can offer better compression than Huffman coding because — intuitively — its "code words" can have effectively non-integer bit lengths, whereas code words in prefix codes such as Huffman codes can only have an integer number of bits. Therefore, a code word of length <i>k</i> only optimally matches a symbol of probability 1/2<sup><i>k</i></sup> and other probabilities are not represented optimally; whereas the code word length in arithmetic coding can be made to exactly match the true probability of the symbol. This difference is especially striking for small alphabet sizes.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (December 2021)">citation needed</span></a></i>]</sup> </p><p>Prefix codes nevertheless remain in wide use because of their simplicity, high speed, and <a href="/wiki/Arithmetic_coding#History_and_patents" title="Arithmetic coding">lack of patent coverage</a>. They are often used as a "back-end" to other compression methods. <a href="/wiki/Deflate" title="Deflate">Deflate</a> (<a href="/wiki/PKZIP" title="PKZIP">PKZIP</a>'s algorithm) and multimedia <a href="/wiki/Codec" title="Codec">codecs</a> such as <a href="/wiki/JPEG" title="JPEG">JPEG</a> and <a href="/wiki/MP3" title="MP3">MP3</a> have a front-end model and <a href="/wiki/Quantization_(signal_processing)" title="Quantization (signal processing)">quantization</a> followed by the use of prefix codes; these are often called "Huffman codes" even though most applications use pre-defined variable-length codes rather than codes designed using Huffman's algorithm. </p> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=21" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Commons-logo.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/45px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/59px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></a></span></div> <div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Huffman_coding" class="extiw" title="commons:Category:Huffman coding">Huffman coding</a></span>.</div></div> </div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFHuffman1952" class="citation journal cs1"><a href="/wiki/David_A._Huffman" title="David A. Huffman">Huffman, D.</a> (1952). <a rel="nofollow" class="external text" href="http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf">"A Method for the Construction of Minimum-Redundancy Codes"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Proceedings_of_the_IRE" class="mw-redirect" title="Proceedings of the IRE">Proceedings of the IRE</a></i>. <b>40</b> (9): <span class="nowrap">1098–</span>1101. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJRPROC.1952.273898">10.1109/JRPROC.1952.273898</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+IRE&rft.atitle=A+Method+for+the+Construction+of+Minimum-Redundancy+Codes&rft.volume=40&rft.issue=9&rft.pages=%3Cspan+class%3D%22nowrap%22%3E1098-%3C%2Fspan%3E1101&rft.date=1952&rft_id=info%3Adoi%2F10.1109%2FJRPROC.1952.273898&rft.aulast=Huffman&rft.aufirst=D.&rft_id=http%3A%2F%2Fcompression.ru%2Fdownload%2Farticles%2Fhuff%2Fhuffman_1952_minimum-redundancy-codes.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFVan_Leeuwen1976" class="citation journal cs1"><a href="/wiki/Jan_van_Leeuwen" title="Jan van Leeuwen">Van Leeuwen, Jan</a> (1976). <a rel="nofollow" class="external text" href="http://www.staff.science.uu.nl/~leeuw112/huffman.pdf">"On the construction of Huffman trees"</a> <span class="cs1-format">(PDF)</span>. <i>ICALP</i>: <span class="nowrap">382–</span>410<span class="reference-accessdate">. Retrieved <span class="nowrap">2014-02-20</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ICALP&rft.atitle=On+the+construction+of+Huffman+trees&rft.pages=%3Cspan+class%3D%22nowrap%22%3E382-%3C%2Fspan%3E410&rft.date=1976&rft.aulast=Van+Leeuwen&rft.aufirst=Jan&rft_id=http%3A%2F%2Fwww.staff.science.uu.nl%2F~leeuw112%2Fhuffman.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-LiDrew2014-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-LiDrew2014_3-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFZe-Nian_LiMark_S._DrewJiangchuan_Liu2014" class="citation book cs1">Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (2014-04-09). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=R6vBBAAAQBAJ"><i>Fundamentals of Multimedia</i></a>. Springer Science & Business Media. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-319-05290-8" title="Special:BookSources/978-3-319-05290-8"><bdi>978-3-319-05290-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Fundamentals+of+Multimedia&rft.pub=Springer+Science+%26+Business+Media&rft.date=2014-04-09&rft.isbn=978-3-319-05290-8&rft.au=Ze-Nian+Li&rft.au=Mark+S.+Drew&rft.au=Jiangchuan+Liu&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DR6vBBAAAQBAJ&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-PCS2015-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-PCS2015_4-0">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/7170048">J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, <i>The use of asymmetric numeral systems as an accurate replacement for Huffman coding</i></a>, Picture Coding Symposium, 2015.</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHuffman1991" class="citation journal cs1">Huffman, Ken (1991). <a rel="nofollow" class="external text" href="http://www.huffmancoding.com/my-uncle/scientific-american">"Profile: David A. Huffman: Encoding the "Neatness" of Ones and Zeroes"</a>. <i><a href="/wiki/Scientific_American" title="Scientific American">Scientific American</a></i>: <span class="nowrap">54–</span>58.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Scientific+American&rft.atitle=Profile%3A+David+A.+Huffman%3A+Encoding+the+%22Neatness%22+of+Ones+and+Zeroes&rft.pages=%3Cspan+class%3D%22nowrap%22%3E54-%3C%2Fspan%3E58&rft.date=1991&rft.aulast=Huffman&rft.aufirst=Ken&rft_id=http%3A%2F%2Fwww.huffmancoding.com%2Fmy-uncle%2Fscientific-american&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-kleinberg&Tardos-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-kleinberg&Tardos_6-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKleinbergTardos2005" class="citation book cs1">Kleinberg, Jon; Tardos, Eva (2005-03-16). <a rel="nofollow" class="external text" href="https://www.pearson.com/en-us/subject-catalog/p/algorithm-design/P200000003259/9780137546350"><i>Algorithm Design</i></a> (1 ed.). <a href="/wiki/Pearson_Education" title="Pearson Education">Pearson Education</a>. p. 165. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780321295354" title="Special:BookSources/9780321295354"><bdi>9780321295354</bdi></a><span class="reference-accessdate">. Retrieved <span class="nowrap">2025-01-26</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithm+Design&rft.pages=165&rft.edition=1&rft.pub=Pearson+Education&rft.date=2005-03-16&rft.isbn=9780321295354&rft.aulast=Kleinberg&rft.aufirst=Jon&rft.au=Tardos%2C+Eva&rft_id=https%3A%2F%2Fwww.pearson.com%2Fen-us%2Fsubject-catalog%2Fp%2Falgorithm-design%2FP200000003259%2F9780137546350&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGribov2017" class="citation arxiv cs1">Gribov, Alexander (2017-04-10). "Optimal Compression of a Polyline with Segments and Arcs". <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1604.07476">1604.07476</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CG">cs.CG</a>].</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=preprint&rft.jtitle=arXiv&rft.atitle=Optimal+Compression+of+a+Polyline+with+Segments+and+Arcs&rft.date=2017-04-10&rft_id=info%3Aarxiv%2F1604.07476&rft.aulast=Gribov&rft.aufirst=Alexander&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGallagervan_Voorhis1975" class="citation journal cs1">Gallager, R.G.; van Voorhis, D.C. (1975). "Optimal source codes for geometrically distributed integer alphabets". <i><a href="/wiki/IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a></i>. <b>21</b> (2): <span class="nowrap">228–</span>230. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1975.1055357">10.1109/TIT.1975.1055357</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Information+Theory&rft.atitle=Optimal+source+codes+for+geometrically+distributed+integer+alphabets&rft.volume=21&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E228-%3C%2Fspan%3E230&rft.date=1975&rft_id=info%3Adoi%2F10.1109%2FTIT.1975.1055357&rft.aulast=Gallager&rft.aufirst=R.G.&rft.au=van+Voorhis%2C+D.C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAbrahams1997" class="citation book cs1 cs1-prop-location-test">Abrahams, J. (1997-06-11). "Code and parse trees for lossless source encoding". Written at Arlington, VA, USA. <i>Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171)</i>. Division of Mathematics, Computer & Information Sciences, <a href="/wiki/Office_of_Naval_Research" title="Office of Naval Research">Office of Naval Research</a> (ONR). Salerno: <a href="/wiki/IEEE" class="mw-redirect" title="IEEE">IEEE</a>. pp. <span class="nowrap">145–</span>171. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.589.4726">10.1.1.589.4726</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSEQUEN.1997.666911">10.1109/SEQUEN.1997.666911</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-8186-8132-2" title="Special:BookSources/0-8186-8132-2"><bdi>0-8186-8132-2</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:124587565">124587565</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Code+and+parse+trees+for+lossless+source+encoding&rft.btitle=Proceedings.+Compression+and+Complexity+of+SEQUENCES+1997+%28Cat.+No.97TB100171%29&rft.place=Salerno&rft.pages=%3Cspan+class%3D%22nowrap%22%3E145-%3C%2Fspan%3E171&rft.pub=IEEE&rft.date=1997-06-11&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.589.4726%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A124587565%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FSEQUEN.1997.666911&rft.isbn=0-8186-8132-2&rft.aulast=Abrahams&rft.aufirst=J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKarp1961" class="citation journal cs1"><a href="/wiki/Richard_M._Karp" title="Richard M. Karp">Karp, Richard M.</a> (1961-01-31). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/1057615?arnumber=1057615">"Minimum-redundancy coding for the discrete noiseless channel"</a></span>. <i>IRE Transactions on Information Theory</i>. <b>7</b> (1). IEEE: <span class="nowrap">27–</span>38. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1961.1057615">10.1109/TIT.1961.1057615</a> – via IEEE.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IRE+Transactions+on+Information+Theory&rft.atitle=Minimum-redundancy+coding+for+the+discrete+noiseless+channel&rft.volume=7&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E27-%3C%2Fspan%3E38&rft.date=1961-01-31&rft_id=info%3Adoi%2F10.1109%2FTIT.1961.1057615&rft.aulast=Karp&rft.aufirst=Richard+M.&rft_id=https%3A%2F%2Fieeexplore.ieee.org%2Fdocument%2F1057615%3Farnumber%3D1057615&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGolin1998" class="citation journal cs1">Golin, Mordekai J. (January 1998). <a rel="nofollow" class="external text" href="https://page.mi.fu-berlin.de/rote/Papers/pdf/A+dynamic+programming+algorithm+for+constructing+optimal+prefix-free+codes+for+unequal+letter+costs.pdf">"A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes with Unequal Letter Costs"</a> <span class="cs1-format">(PDF)</span>. <i>IEEE Transactions on Information Theory</i>. <b>44</b> (5) (published 1998-09-01): <span class="nowrap">1770–</span>1781. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F18.705558">10.1109/18.705558</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2265146">2265146</a><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-09-10</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Information+Theory&rft.atitle=A+Dynamic+Programming+Algorithm+for+Constructing+Optimal+Prefix-Free+Codes+with+Unequal+Letter+Costs&rft.volume=44&rft.issue=5&rft.pages=%3Cspan+class%3D%22nowrap%22%3E1770-%3C%2Fspan%3E1781&rft.date=1998-01&rft_id=info%3Adoi%2F10.1109%2F18.705558&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A2265146%23id-name%3DS2CID&rft.aulast=Golin&rft.aufirst=Mordekai+J.&rft_id=https%3A%2F%2Fpage.mi.fu-berlin.de%2Frote%2FPapers%2Fpdf%2FA%2Bdynamic%2Bprogramming%2Balgorithm%2Bfor%2Bconstructing%2Boptimal%2Bprefix-free%2Bcodes%2Bfor%2Bunequal%2Bletter%2Bcosts.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHuTucker1971" class="citation journal cs1"><a href="/wiki/T._C._Hu" title="T. C. Hu">Hu, T. C.</a>; <a href="/wiki/Alan_Tucker" title="Alan Tucker">Tucker, A. C.</a> (1971). "Optimal Computer Search Trees and Variable-Length Alphabetical Codes". <i>SIAM Journal on Applied Mathematics</i>. <b>21</b> (4): 514. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0121057">10.1137/0121057</a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2099603">2099603</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Applied+Mathematics&rft.atitle=Optimal+Computer+Search+Trees+and+Variable-Length+Alphabetical+Codes&rft.volume=21&rft.issue=4&rft.pages=514&rft.date=1971&rft_id=info%3Adoi%2F10.1137%2F0121057&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2099603%23id-name%3DJSTOR&rft.aulast=Hu&rft.aufirst=T.+C.&rft.au=Tucker%2C+A.+C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKnuth1998" class="citation cs2"><a href="/wiki/Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (1998), "Algorithm G (Garsia–Wachs algorithm for optimum binary trees)", <i>The Art of Computer Programming, Vol. 3: Sorting and Searching</i> (2nd ed.), Addison–Wesley, pp. <span class="nowrap">451–</span>453</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Algorithm+G+%28Garsia%E2%80%93Wachs+algorithm+for+optimum+binary+trees%29&rft.btitle=The+Art+of+Computer+Programming%2C+Vol.+3%3A+Sorting+and+Searching&rft.pages=%3Cspan+class%3D%22nowrap%22%3E451-%3C%2Fspan%3E453&rft.edition=2nd&rft.pub=Addison%E2%80%93Wesley&rft.date=1998&rft.aulast=Knuth&rft.aufirst=Donald+E.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHuffman+coding" class="Z3988"></span>. See also History and bibliography, pp. 453–454.</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Bibliography">Bibliography</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=22" title="Edit section: Bibliography"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="/wiki/Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="/wiki/Clifford_Stein" title="Clifford Stein">Clifford Stein</a>. <i><a href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a></i>, Second Edition. MIT Press and McGraw-Hill, 2001. <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-262-03293-7" title="Special:BookSources/0-262-03293-7">0-262-03293-7</a>. Section 16.3, pp. 385–392.</li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Huffman_coding&action=edit&section=23" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://rosettacode.org/wiki/Huffman_coding">Huffman coding in various languages on Rosetta Code</a></li> <li><a rel="nofollow" class="external text" href="https://gist.github.com/jasonrdsouza/1c9c895f43497d15eb2e">Huffman codes (python implementation)</a></li> <li><a rel="nofollow" class="external text" href="https://github.com/gdavidbutler/canonicalHuffman">Canonical Huffman codes (C implementation)</a></li> <li><a rel="nofollow" class="external text" href="https://www.tinyray.com/huffman">A visualization of Huffman coding</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Data_compression_methods223" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Compression_methods" title="Template:Compression methods"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Compression_methods" title="Template talk:Compression methods"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Compression_methods" title="Special:EditPage/Template:Compression methods"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_compression_methods223" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_compression" title="Data compression">Data compression</a> methods</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Lossless_compression" title="Lossless compression">Lossless</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Entropy_coding" title="Entropy coding">Entropy type</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Adaptive_coding" title="Adaptive coding">Adaptive coding</a></li> <li><a href="/wiki/Arithmetic_coding" title="Arithmetic coding">Arithmetic</a></li> <li><a href="/wiki/Asymmetric_numeral_systems" title="Asymmetric numeral systems">Asymmetric numeral systems</a></li> <li><a href="/wiki/Golomb_coding" title="Golomb coding">Golomb</a></li> <li><a class="mw-selflink selflink">Huffman</a> <ul><li><a href="/wiki/Adaptive_Huffman_coding" title="Adaptive Huffman coding">Adaptive</a></li> <li><a href="/wiki/Canonical_Huffman_code" title="Canonical Huffman code">Canonical</a></li> <li><a href="/wiki/Modified_Huffman_coding" title="Modified Huffman coding">Modified</a></li></ul></li> <li><a href="/wiki/Range_coding" title="Range coding">Range</a></li> <li><a href="/wiki/Shannon_coding" title="Shannon coding">Shannon</a></li> <li><a href="/wiki/Shannon%E2%80%93Fano_coding" title="Shannon–Fano coding">Shannon–Fano</a></li> <li><a href="/wiki/Shannon%E2%80%93Fano%E2%80%93Elias_coding" title="Shannon–Fano–Elias coding">Shannon–Fano–Elias</a></li> <li><a href="/wiki/Tunstall_coding" title="Tunstall coding">Tunstall</a></li> <li><a href="/wiki/Unary_coding" title="Unary coding">Unary</a></li> <li><a href="/wiki/Universal_code_(data_compression)" title="Universal code (data compression)">Universal</a> <ul><li><a href="/wiki/Exponential-Golomb_coding" title="Exponential-Golomb coding">Exp-Golomb</a></li> <li><a href="/wiki/Fibonacci_coding" title="Fibonacci coding">Fibonacci</a></li> <li><a href="/wiki/Elias_gamma_coding" title="Elias gamma coding">Gamma</a></li> <li><a href="/wiki/Levenshtein_coding" title="Levenshtein coding">Levenshtein</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Dictionary_coder" title="Dictionary coder">Dictionary type</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Byte_pair_encoding" title="Byte pair encoding">Byte pair encoding</a></li> <li><a href="/wiki/LZ77_and_LZ78" title="LZ77 and LZ78">Lempel–Ziv</a> <ul><li><a href="/wiki/842_(compression_algorithm)" title="842 (compression algorithm)">842</a></li> <li><a href="/wiki/LZ4_(compression_algorithm)" title="LZ4 (compression algorithm)">LZ4</a></li> <li><a href="/wiki/LZJB" class="mw-redirect" title="LZJB">LZJB</a></li> <li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Oberhumer" title="Lempel–Ziv–Oberhumer">LZO</a></li> <li><a href="/wiki/LZRW" title="LZRW">LZRW</a></li> <li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski" title="Lempel–Ziv–Storer–Szymanski">LZSS</a></li> <li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch" title="Lempel–Ziv–Welch">LZW</a></li> <li><a href="/wiki/LZWL" title="LZWL">LZWL</a></li> <li><a href="/wiki/Snappy_(compression)" title="Snappy (compression)">Snappy</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Other types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Burrows%E2%80%93Wheeler_transform" title="Burrows–Wheeler transform">BWT</a></li> <li><a href="/wiki/Context_tree_weighting" title="Context tree weighting">CTW</a></li> <li><a href="/wiki/Context_mixing" title="Context mixing">CM</a></li> <li><a href="/wiki/Delta_encoding" title="Delta encoding">Delta</a> <ul><li><a href="/wiki/Incremental_encoding" title="Incremental encoding">Incremental</a></li></ul></li> <li><a href="/wiki/Dynamic_Markov_compression" title="Dynamic Markov compression">DMC</a></li> <li><a href="/wiki/Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a></li> <li><a href="/wiki/Grammar-based_code" title="Grammar-based code">Grammar</a> <ul><li><a href="/wiki/Re-Pair" title="Re-Pair">Re-Pair</a></li> <li><a href="/wiki/Sequitur_algorithm" title="Sequitur algorithm">Sequitur</a></li></ul></li> <li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">LDCT</a></li> <li><a href="/wiki/Move-to-front_transform" title="Move-to-front transform">MTF</a></li> <li><a href="/wiki/PAQ" title="PAQ">PAQ</a></li> <li><a href="/wiki/Prediction_by_partial_matching" title="Prediction by partial matching">PPM</a></li> <li><a href="/wiki/Run-length_encoding" title="Run-length encoding">RLE</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Hybrid</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li>LZ77 + Huffman <ul><li><a href="/wiki/Deflate" title="Deflate">Deflate</a></li> <li><a href="/wiki/LZX" title="LZX">LZX</a></li> <li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Stac" title="Lempel–Ziv–Stac">LZS</a></li></ul></li> <li>LZ77 + ANS <ul><li><a href="/wiki/LZFSE" title="LZFSE">LZFSE</a></li></ul></li> <li>LZ77 + Huffman + ANS <ul><li><a href="/wiki/Zstd" title="Zstd">Zstandard</a></li></ul></li> <li>LZ77 + Huffman + context <ul><li><a href="/wiki/Brotli" title="Brotli">Brotli</a></li></ul></li> <li>LZSS + Huffman <ul><li><a href="/wiki/LHA_(file_format)" title="LHA (file format)">LHA/LZH</a></li></ul></li> <li>LZ77 + Range <ul><li><a href="/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm" title="Lempel–Ziv–Markov chain algorithm">LZMA</a></li> <li>LZHAM</li></ul></li> <li>RLE + BWT + MTF + Huffman <ul><li><a href="/wiki/Bzip2" title="Bzip2">bzip2</a></li></ul></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Lossy_compression" title="Lossy compression">Lossy</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Transform_coding" title="Transform coding">Transform type</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">Discrete cosine transform</a> <ul><li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li> <li><a href="/wiki/Modified_discrete_cosine_transform" title="Modified discrete cosine transform">MDCT</a></li></ul></li> <li><a href="/wiki/Discrete_sine_transform" title="Discrete sine transform">DST</a></li> <li><a href="/wiki/Fast_Fourier_transform" title="Fast Fourier transform">FFT</a></li> <li><a href="/wiki/Wavelet_transform" title="Wavelet transform">Wavelet</a> <ul><li><a href="/wiki/Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li> <li><a href="/wiki/Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li> <li><a href="/wiki/Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Predictive type</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a> <ul><li><a href="/wiki/Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li></ul></li> <li><a href="/wiki/Linear_predictive_coding" title="Linear predictive coding">LPC</a> <ul><li><a href="/wiki/Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li> <li><a href="/wiki/Code-excited_linear_prediction" title="Code-excited linear prediction">CELP</a></li> <li><a href="/wiki/Log_area_ratio" title="Log area ratio">LAR</a></li> <li><a href="/wiki/Line_spectral_pairs" title="Line spectral pairs">LSP</a></li> <li><a href="/wiki/Warped_linear_predictive_coding" title="Warped linear predictive coding">WLPC</a></li></ul></li> <li>Motion <ul><li><a href="/wiki/Motion_compensation" title="Motion compensation">Compensation</a></li> <li><a href="/wiki/Motion_estimation" title="Motion estimation">Estimation</a></li> <li><a href="/wiki/Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li> <li><a href="/wiki/Psychoacoustics" title="Psychoacoustics">Psychoacoustic</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Data_compression#Audio" title="Data compression">Audio</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_rate" title="Bit rate">Bit rate</a> <ul><li><a href="/wiki/Average_bitrate" title="Average bitrate">ABR</a></li> <li><a href="/wiki/Constant_bitrate" title="Constant bitrate">CBR</a></li> <li><a href="/wiki/Variable_bitrate" title="Variable bitrate">VBR</a></li></ul></li> <li><a href="/wiki/Companding" title="Companding">Companding</a></li> <li><a href="/wiki/Convolution" title="Convolution">Convolution</a></li> <li><a href="/wiki/Dynamic_range" title="Dynamic range">Dynamic range</a></li> <li><a href="/wiki/Latency_(audio)" title="Latency (audio)">Latency</a></li> <li><a href="/wiki/Nyquist%E2%80%93Shannon_sampling_theorem" title="Nyquist–Shannon sampling theorem">Nyquist–Shannon theorem</a></li> <li><a href="/wiki/Sampling_(signal_processing)" title="Sampling (signal processing)">Sampling</a></li> <li><a href="/wiki/Silence_compression" title="Silence compression">Silence compression</a></li> <li><a href="/wiki/Sound_quality" title="Sound quality">Sound quality</a></li> <li><a href="/wiki/Speech_coding" title="Speech coding">Speech coding</a></li> <li><a href="/wiki/Sub-band_coding" title="Sub-band coding">Sub-band coding</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Audio_codec" title="Audio codec">Codec</a> parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/A-law_algorithm" title="A-law algorithm">A-law</a></li> <li><a href="/wiki/%CE%9C-law_algorithm" title="Μ-law algorithm">μ-law</a></li> <li><a href="/wiki/Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a> <ul><li><a href="/wiki/Adaptive_differential_pulse-code_modulation" title="Adaptive differential pulse-code modulation">ADPCM</a></li> <li><a href="/wiki/Delta_modulation" title="Delta modulation">DM</a></li></ul></li> <li><a href="/wiki/Fourier_transform" title="Fourier transform">FT</a> <ul><li><a href="/wiki/Fast_Fourier_transform" title="Fast Fourier transform">FFT</a></li></ul></li> <li><a href="/wiki/Linear_predictive_coding" title="Linear predictive coding">LPC</a> <ul><li><a href="/wiki/Algebraic_code-excited_linear_prediction" title="Algebraic code-excited linear prediction">ACELP</a></li> <li><a href="/wiki/Code-excited_linear_prediction" title="Code-excited linear prediction">CELP</a></li> <li><a href="/wiki/Log_area_ratio" title="Log area ratio">LAR</a></li> <li><a href="/wiki/Line_spectral_pairs" title="Line spectral pairs">LSP</a></li> <li><a href="/wiki/Warped_linear_predictive_coding" title="Warped linear predictive coding">WLPC</a></li></ul></li> <li><a href="/wiki/Modified_discrete_cosine_transform" title="Modified discrete cosine transform">MDCT</a></li> <li><a href="/wiki/Psychoacoustics" title="Psychoacoustics">Psychoacoustic model</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Image_compression" title="Image compression">Image</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Chroma_subsampling" title="Chroma subsampling">Chroma subsampling</a></li> <li><a href="/wiki/Coding_tree_unit" title="Coding tree unit">Coding tree unit</a></li> <li><a href="/wiki/Color_space" title="Color space">Color space</a></li> <li><a href="/wiki/Compression_artifact" title="Compression artifact">Compression artifact</a></li> <li><a href="/wiki/Image_resolution" title="Image resolution">Image resolution</a></li> <li><a href="/wiki/Macroblock" title="Macroblock">Macroblock</a></li> <li><a href="/wiki/Pixel" title="Pixel">Pixel</a></li> <li><a href="/wiki/Peak_signal-to-noise_ratio" title="Peak signal-to-noise ratio">PSNR</a></li> <li><a href="/wiki/Quantization_(image_processing)" title="Quantization (image processing)">Quantization</a></li> <li><a href="/wiki/Standard_test_image" title="Standard test image">Standard test image</a></li> <li><a href="/wiki/Texture_compression" title="Texture compression">Texture compression</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Methods</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Chain_code" title="Chain code">Chain code</a></li> <li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li> <li><a href="/wiki/Deflate" title="Deflate">Deflate</a></li> <li><a href="/wiki/Fractal_compression" title="Fractal compression">Fractal</a></li> <li><a href="/wiki/Karhunen%E2%80%93Lo%C3%A8ve_theorem" class="mw-redirect" title="Karhunen–Loève theorem">KLT</a></li> <li><a href="/wiki/Pyramid_(image_processing)" title="Pyramid (image processing)">LP</a></li> <li><a href="/wiki/Run-length_encoding" title="Run-length encoding">RLE</a></li> <li><a href="/wiki/Wavelet_transform" title="Wavelet transform">Wavelet</a> <ul><li><a href="/wiki/Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li> <li><a href="/wiki/Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li> <li><a href="/wiki/Embedded_zerotrees_of_wavelet_transforms" title="Embedded zerotrees of wavelet transforms">EZW</a></li> <li><a href="/wiki/Set_partitioning_in_hierarchical_trees" title="Set partitioning in hierarchical trees">SPIHT</a></li></ul></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Data_compression#Video" title="Data compression">Video</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;">Concepts</th><td class="navbox-list-with-group navbox-list navbox-odd" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_rate" title="Bit rate">Bit rate</a> <ul><li><a href="/wiki/Average_bitrate" title="Average bitrate">ABR</a></li> <li><a href="/wiki/Constant_bitrate" title="Constant bitrate">CBR</a></li> <li><a href="/wiki/Variable_bitrate" title="Variable bitrate">VBR</a></li></ul></li> <li><a href="/wiki/Display_resolution" title="Display resolution">Display resolution</a></li> <li><a href="/wiki/Film_frame" title="Film frame">Frame</a></li> <li><a href="/wiki/Frame_rate" title="Frame rate">Frame rate</a></li> <li><a href="/wiki/Video_compression_picture_types" title="Video compression picture types">Frame types</a></li> <li><a href="/wiki/Interlaced_video" title="Interlaced video">Interlace</a></li> <li><a href="/wiki/Video#Characteristics_of_video_streams" title="Video">Video characteristics</a></li> <li><a href="/wiki/Video_quality" title="Video quality">Video quality</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:7.0em;font-weight:normal;"><a href="/wiki/Video_codec" title="Video codec">Codec</a> parts</th><td class="navbox-list-with-group navbox-list navbox-even" style="padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Discrete_cosine_transform" title="Discrete cosine transform">DCT</a></li> <li><a href="/wiki/Differential_pulse-code_modulation" title="Differential pulse-code modulation">DPCM</a></li> <li><a href="/wiki/Deblocking_filter" title="Deblocking filter">Deblocking filter</a></li> <li><a href="/wiki/Lapped_transform" title="Lapped transform">Lapped transform</a></li> <li>Motion <ul><li><a href="/wiki/Motion_compensation" title="Motion compensation">Compensation</a></li> <li><a href="/wiki/Motion_estimation" title="Motion estimation">Estimation</a></li> <li><a href="/wiki/Motion_vector" class="mw-redirect" title="Motion vector">Vector</a></li></ul></li> <li><a href="/wiki/Wavelet_transform" title="Wavelet transform">Wavelet</a> <ul><li><a href="/wiki/Daubechies_wavelet" title="Daubechies wavelet">Daubechies</a></li> <li><a href="/wiki/Discrete_wavelet_transform" title="Discrete wavelet transform">DWT</a></li></ul></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Information_theory" title="Information theory">Theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Compressed_data_structure" title="Compressed data structure">Compressed data structures</a> <ul><li><a href="/wiki/Compressed_suffix_array" title="Compressed suffix array">Compressed suffix array</a></li> <li><a href="/wiki/FM-index" title="FM-index">FM-index</a></li></ul></li> <li><a href="/wiki/Entropy_(information_theory)" title="Entropy (information theory)">Entropy</a></li> <li><a href="/wiki/Information_theory" title="Information theory">Information theory</a> <ul><li><a href="/wiki/Timeline_of_information_theory" title="Timeline of information theory">Timeline</a></li></ul></li> <li><a href="/wiki/Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li> <li><a href="/wiki/Prefix_code" title="Prefix code">Prefix code</a></li> <li><a href="/wiki/Quantization_(signal_processing)" title="Quantization (signal processing)">Quantization</a></li> <li><a href="/wiki/Rate%E2%80%93distortion_theory" title="Rate–distortion theory">Rate–distortion</a></li> <li><a href="/wiki/Redundancy_(information_theory)" title="Redundancy (information theory)">Redundancy</a></li> <li><a href="/wiki/Data_compression_symmetry" title="Data compression symmetry">Symmetry</a></li> <li><a href="/wiki/Smallest_grammar_problem" title="Smallest grammar problem">Smallest grammar problem</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Community</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Hutter_Prize" title="Hutter Prize">Hutter Prize</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Mark_Adler" title="Mark Adler">Mark Adler</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Huffman_coding&oldid=1271869873">https://en.wikipedia.org/w/index.php?title=Huffman_coding&oldid=1271869873</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:1952_in_computing" title="Category:1952 in computing">1952 in computing</a></li><li><a href="/wiki/Category:Lossless_compression_algorithms" title="Category:Lossless compression algorithms">Lossless compression algorithms</a></li><li><a href="/wiki/Category:Binary_trees" title="Category:Binary trees">Binary trees</a></li><li><a href="/wiki/Category:Data_compression" title="Category:Data compression">Data compression</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1_location_test" title="Category:CS1 location test">CS1 location test</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Use_dmy_dates_from_May_2019" title="Category:Use dmy dates from May 2019">Use dmy dates from May 2019</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_December_2021" title="Category:Articles needing additional references from December 2021">Articles needing additional references from December 2021</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_September_2023" title="Category:Wikipedia articles needing clarification from September 2023">Wikipedia articles needing clarification from September 2023</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_December_2021" title="Category:Articles with unsourced statements from December 2021">Articles with unsourced statements from December 2021</a></li><li><a href="/wiki/Category:Commons_category_link_is_on_Wikidata" title="Category:Commons category link is on Wikidata">Commons category link is on Wikidata</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 26 January 2025, at 03:42<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Huffman_coding&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" lang="en" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Huffman coding</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>36 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-6f54dd9999-kv2h4","wgBackendResponseTime":152,"wgPageParseReport":{"limitreport":{"cputime":"0.552","walltime":"0.741","ppvisitednodes":{"value":2819,"limit":1000000},"postexpandincludesize":{"value":98354,"limit":2097152},"templateargumentsize":{"value":3138,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":7,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":61734,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 559.624 1 -total"," 29.82% 166.891 1 Template:Reflist"," 18.90% 105.792 7 Template:Cite_journal"," 18.13% 101.444 6 Template:Navbox"," 16.82% 94.132 1 Template:Compression_Methods"," 12.00% 67.160 1 Template:More_citations_needed"," 11.30% 63.260 1 Template:Ambox"," 11.12% 62.234 1 Template:Short_description"," 8.33% 46.597 1 Template:Commons_category"," 7.98% 44.668 1 Template:Sister_project"]},"scribunto":{"limitreport-timeusage":{"value":"0.321","limit":"10.000"},"limitreport-memusage":{"value":7641415,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-9664bf54d-v828s","timestamp":"20250210164155","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Huffman coding","url":"https:\/\/en.wikipedia.org\/wiki\/Huffman_coding","sameAs":"http:\/\/www.wikidata.org\/entity\/Q2647","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q2647","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-10-30T15:10:22Z","dateModified":"2025-01-26T03:42:26Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/8\/82\/Huffman_tree_2.svg","headline":"entropy encoding algorithm used for lossless data compression"}</script> </body> </html>