Adaptive Huffman coding: Difference between revisions

Revision as of 13:17, 20 December 2019

Latest revision as of 23:50, 5 December 2024

(10 intermediate revisions by 10 users not shown)

Line 1:

{{short description|Data compression technique}}

'''Adaptive Huffman coding''' (also called '''Dynamic Huffman coding''') is an [[adaptive coding]] technique based on [[Huffman coding]]. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one-pass encoding and adaptation to changing conditions in data.<ref name="LiDrew2014">{{cite book|author1=Ze-Nian Li|author2=Mark S. Drew|author3=Jiangchuan Liu|title=Fundamentals of Multimedia|url=https://books.google.com/books?id=R6vBBAAAQBAJ|date=9 April 2014|publisher=Springer Science & Business Media|isbn=978-3-319-05290-8}}</ref>

The benefit of one-pass procedure is that the source can be encoded in real time, though it becomes more sensitive to transmission errors, since just a single loss ruins the whole code, requiring [[error detection and correction]].

==Algorithms==

Line 7 ⟶ 8:

===FGK Algorithm ===

It is an online coding technique based on Huffman coding. Having no initial knowledge of occurrence frequencies, it permits dynamically adjusting the Huffman's tree as data are being transmitted. In a FGK Huffman tree, a special external node, called ''0-node'', is used to identify a newly- coming character. That is, whenever new data is encountered, output the path to the 0-node followed by the data. For a past-coming character, just output the path of the data in the current Huffman's tree. Most importantly, we have to adjust the FGK Huffman tree if necessary, and finally update the frequency of related nodes. As the frequency of a datum is increased, the'' sibling property'' of the Huffman's tree may be broken. The adjustment is triggered for this reason. It is accomplished by consecutive swappings of nodes, subtrees, or both. The data node is swapped with the highest-ordered node of the same frequency in the Huffman's tree, (or the subtree rooted at the highest-ordered node). All ancestor nodes of the node should also be processed in the same manner.

Since the FGK Algorithm has some drawbacks about the node-or-subtree swapping, Vitter proposed another algorithm to improve it.

Line 13 ⟶ 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 22 ⟶ 23:

A leaf block always precedes internal block of same weight, thus maintaining the invariant.

'''NYT (Not Yet Transferred)''' is a special node and used to representsrepresent symbols which are ''<nowiki>'not yet transferred'</nowiki>''.

[[File:Leaf step one.png|thumb|Slide_And_Increment(leaf node) sliding starts. P is a leaf node.]]

Line 30 ⟶ 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 38 ⟶ 39:

'''if''' (p is NYT) '''then'''

Extend p by adding two children

Left child becomes new NYT and right child is the new symbol leaf node

''p'' := parent of new symbol leaf node

leaf_to_increment := Right Child of p

'''else'''

Swap p with leader of its block

Line 96 ⟶ 97:

For the second "b" transmit 11.

For the convenience of explanation this step doesn't exactly follow Vitter's algorithm,<ref name=":0">{{cite web|url=http://www.cs.duke.edu/csed/curious/compression/adaptivehuff.html#tree |title=Adaptive Huffman Coding |publisher=Cs.duke.edu |access-date= |accessdate=2012-02-26}}</ref> but the effects are equivalent.

Step 4:

Line 122 ⟶ 123:

[[Category:Lossless compression algorithms]]

[[Category:Data compression]]