Adaptive Huffman coding: Difference between revisions

Revision as of 08:32, 2 November 2023

Latest revision as of 23:50, 5 December 2024

(One intermediate revision by one other user not shown)

Line 14:

===Vitter algorithm===

Some important terminologies & constraints :-

* '''Implicit Numbering''' : It simply means that nodes are numbered in increasing order by level and from left to right. i.e. nodes at bottom level will have low implicit number as compared to upper level nodes and nodes on same level are numbered in increasing order from left to right. In other terms, when we have built the Huffman tree, when merging two nodes into a parent node, we have set the one with the lower value as the left child, and the one with the higher value as the right child.

* '''Invariant''' : For each weight w, all leaves of weight w precede all internal nodes having weight w. In other terms, when we have built the Huffman tree, if several nodes had the same value, we prioritized merging the leaves over the internal nodes.

* '''Blocks''' : Nodes of same weight and same type (i.e. either leaf node or internal node) form a Block.

* '''Leader''' : Highest numbered node in a block.

Line 31:

[[File:Internal one.png|thumb|Slide_And_Increment(internal node) sliding starts. P is an internal node.]]

[[File:Internal two.png|thumb|Slide_And_Increment(internal node) sliding step 2. Node P slides in front of next block of leaves nodes, with weight wt+1.]]

[[File:Internal three.png|thumb|Slide_And_Increment(internal node) sliding step 3. Now we increase the weight to 9. Thus the '''''invariant is maintained''''' as the current node is an internal node and should occur in front of leaf nodes of equal weight as we have increased the weight. ]]

[[File:Internal four.png|thumb|Slide_And_Increment(internal node) sliding step 4. Now the 'P' points to the former parent ( as in the case of internal node according to algorithm)]]

Line 123:

[[Category:Lossless compression algorithms]]

[[Category:Data compression]]