{"id":1311,"date":"2025-01-03T19:07:41","date_gmt":"2025-01-03T19:07:41","guid":{"rendered":"https:\/\/cyberenlightener.com\/?page_id=1311"},"modified":"2025-01-03T19:07:42","modified_gmt":"2025-01-03T19:07:42","slug":"huffman-coding","status":"publish","type":"page","link":"https:\/\/cyberenlightener.com\/?page_id=1311","title":{"rendered":"Huffman Coding"},"content":{"rendered":"\n<p>Huffman codes are highly effective for data compression, typically achieving savings between 20% and 90%, depending on the nature of the data being compressed. The input data consists of a sequence of characters. Huffman\u2019s greedy algorithm constructs an optimal binary representation for each character by utilizing a frequency table that indicates how often each character appears. <\/p>\n\n\n\n<p>Imagine you have a data file containing 100,000 characters that you want to store efficiently. The file consists of 6 unique characters, each appearing with the frequencies shown in Figure 15.4. For instance, the character &#8216;a&#8217; appears 45,000 times, &#8216;b&#8217; appears 13,000 times, and so forth. There are various ways to encode this information, but here, we focus on creating a binary character code (or simply a code) to represent it. In a fixed-length code, each character requires \u2308log\u20612n\u2309\\lceil \\log_2 n \\rceil\u2308log2\u200bn\u2309 bits to represent n\u22652n \\geq 2n\u22652 characters. For 6 characters, this means 3 bits are needed per character: a=000,b=001,c=010,d=011,e=100,f=101a = 000, b = 001, c = 010, d = 011, e = 100, f = 101a=000,b=001,c=010,d=011,e=100,f=101. Using this approach, encoding the entire file would require 300,000 bits. Is there a more efficient solution?<\/p>\n\n\n\n<p>A variable-length code offers significant improvement over fixed-length coding. The concept is straightforward: assign shorter code-words to frequently occurring characters and longer codewords to less common ones. For example, in bellow Figure  the 1-bit code 0 represents a, while the 4-bit code 1100 represents f. Using this variable-length scheme, the file can be encoded in (45\u22c51+13\u22c53+12\u22c53+16\u22c53+9\u22c54+5\u22c54)\u22c51,000=224,000 bits, achieving a savings of approximately 25%. This approach is, in fact, the optimal character coding for this file, as we will demonstrate.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"667\" height=\"181\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3.jpg\" alt=\"\" class=\"wp-image-1312\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3.jpg 667w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3-300x81.jpg 300w\" sizes=\"auto, (max-width: 667px) 100vw, 667px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"658\" height=\"388\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/4.jpg\" alt=\"\" class=\"wp-image-1313\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/4.jpg 658w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/4-300x177.jpg 300w\" sizes=\"auto, (max-width: 658px) 100vw, 658px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"669\" height=\"403\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/5.jpg\" alt=\"\" class=\"wp-image-1314\" style=\"width:689px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/5.jpg 669w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/5-300x181.jpg 300w\" sizes=\"auto, (max-width: 669px) 100vw, 669px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"642\" height=\"325\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/6.png\" alt=\"\" class=\"wp-image-1315\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/6.png 642w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/6-300x152.png 300w\" sizes=\"auto, (max-width: 642px) 100vw, 642px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"664\" height=\"473\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/7.jpg\" alt=\"\" class=\"wp-image-1316\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/7.jpg 664w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/7-300x214.jpg 300w\" sizes=\"auto, (max-width: 664px) 100vw, 664px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"652\" height=\"428\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/8.jpg\" alt=\"\" class=\"wp-image-1317\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/8.jpg 652w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/8-300x197.jpg 300w\" sizes=\"auto, (max-width: 652px) 100vw, 652px\" \/><\/figure>\n\n\n\n<pre class=\"wp-block-code alignwide\"><code>#include &lt;stdio.h>\n#include &lt;stdlib.h>\n\/\/ Define the structure for a Huffman Tree node\ntypedef struct Node {\n    int freq;\n    struct Node *left, *right;\n} Node;\n\n\/\/ Function to create a new node\nNode* createNode(int freq) {\n    Node* node = (Node*)malloc(sizeof(Node));\n    node->freq = freq;\n    node->left = node->right = NULL;\n    return node;\n}\n\n\/\/ Function to extract the node with the minimum frequency\nNode* extractMin(Node** nodes, int* size) {\n    int minIndex = 0;\n    for (int i = 1; i &lt; *size; i++) {\n        if (nodes&#91;i]->freq &lt; nodes&#91;minIndex]->freq)\n            minIndex = i;\n    }\n    Node* minNode = nodes&#91;minIndex];\n    nodes&#91;minIndex] = nodes&#91;--(*size)];\n    return minNode;\n}\n\n\/\/ Huffman Tree construction function\nNode* buildHuffmanTree(int* freq, int n) {\n    Node* nodes&#91;n];\n    for (int i = 0; i &lt; n; i++) nodes&#91;i] = createNode(freq&#91;i]);\n\n    int size = n;\n    while (size > 1) {\n        Node* x = extractMin(nodes, &amp;size);\n        Node* y = extractMin(nodes, &amp;size);\n\n        Node* z = createNode(x->freq + y->freq);\n        z->left = x;\n        z->right = y;\n\n        nodes&#91;size++] = z;\n    }\n    return nodes&#91;0];\n}\n\n\/\/ Function to print the tree (pre-order traversal)\nvoid printTree(Node* root, int depth) {\n    if (!root) return;\n    printf(\"%*sFreq: %d\\n\", depth * 2, \"\", root->freq);\n    printTree(root->left, depth + 1);\n    printTree(root->right, depth + 1);\n}\nint main() {\n    int freq&#91;] = {5, 9, 12, 13, 16, 45};\n    int n = sizeof(freq) \/ sizeof(freq&#91;0]);\n    Node* root = buildHuffmanTree(freq, n);\n    printf(\"Huffman Tree (pre-order traversal):\\n\");\n    printTree(root, 0);\n    return 0;\n}\noutput:\nHuffman Tree (pre-order traversal):\nFreq: 100\n  Freq: 45\n  Freq: 55\n    Freq: 25\n      Freq: 12\n      Freq: 13\n    Freq: 30\n      Freq: 14\n        Freq: 5\n        Freq: 9\n      Freq: 16\n<\/code><\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Huffman codes are highly effective for data compression, typically achieving savings between 20% and 90%, depending on the nature of the data being compressed. The input data consists of a sequence of characters. Huffman\u2019s greedy algorithm constructs an optimal binary representation for each character by utilizing a frequency table that indicates how often each character [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"class_list":["post-1311","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/1311","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1311"}],"version-history":[{"count":1,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/1311\/revisions"}],"predecessor-version":[{"id":1318,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/1311\/revisions\/1318"}],"wp:attachment":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1311"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}