Huffmans Rules : Introduction & Applications

About this course

Huffman's rules define a method for creating optimal, prefix-free variable-length codes, assigning shorter binary codes to frequent symbols and longer ones to rare symbols, achieved by repeatedly merging the two least frequent items into a new node in a binary tree until one root remains, ensuring no code is a prefix of another for unambiguous decoding. Key rules involve building a min-heap of frequencies, combining lowest-frequency nodes (0 for left, 1 for right), and the crucial Prefix Rule: no codeword is a prefix of another.Core PrinciplesFrequency-Based: More frequent symbols get shorter codes; less frequent get longer codes, minimizing total encoded length.Prefix-Free (No Ambiguity): No codeword is a prefix of another (e.g., if 'A' is '0', 'B' can't be '01'), preventing decoding errors.Greedy Approach: Repeatedly merge the two least probable symbols/nodes.Algorithm Steps (Building the Tree)Create Leaf Nodes: Start with a leaf node for each symbol, storing its frequency.Use a Priority Queue (Min-Heap): Add all leaf nodes to a min-heap, ordered by frequency.Combine Nodes: While more than one node is in the heap:Extract the two nodes with the lowest frequencies (say, node1 and node2).Create a new internal node with node1 as the left child (assigned '0') and node2 as the right child (assigned '1').Set the new node's frequency to the sum of node1's and node2's frequencies.Insert the new internal node back into the heap.Final Tree: Repeat until only one node (the root) remains in the heap.Getting the CodesTraverse the tree from the root to each leaf node.The path (sequence of