What data structure is used in Huffman coding?

The data structure used in Huffman coding is a "tree structure". With the support of Huffman algorithm, an optimal binary tree is constructed, and we name this type of tree Huffman tree. Therefore, to be precise, Huffman coding is a coding form constructed based on Huffman trees.

The operating environment of this tutorial: Windows 7 system, Dell G3 computer.

The data structure used by Huffman coding is a "tree structure".

Huffman Coding, also known as Huffman coding, is a coding method. Huffman coding is a type of variable length coding (VLC). Huffman proposed a coding method in 1952. This method is entirely based on the probability of character occurrence to construct a codeword with the shortest average length of different prefixes. It is sometimes called the best encoding, and is generally called Huffman coding (sometimes also called Hough coding). Mann encoding).

Huffman coding uses the tree structure of the data structure to construct an optimal binary tree with the support of the Huffman algorithm. We name this type of tree a Huffman tree. Therefore, to be precise, Huffman coding is a coding form constructed based on Huffman trees, and it has a very wide range of applications.

Huffman Tree

Given N weights as N leaf nodes, construct a binary tree. If the length of the weighted path of the tree reaches the minimum , such a binary tree is called the optimal binary tree, also known as Huffman Tree. The Huffman tree is the tree with the shortest weighted path length, and nodes with larger weights are closer to the root.

The so-called weighted path length of the tree is the weight of all leaf nodes in the tree multiplied by the length of the path to the root node (if the root node is level 0, the length of the path from the leaf node to the root node The path length of a point is the number of layers of the leaf node). The path length of the tree is the sum of the path lengths from the tree root to each node, recorded as WPL= (W1*L1 W2*L2 W3*L3...Wn*Ln), N weights Wi (i=1 ,2,...n) constitute a binary tree with N leaf nodes, and the path length of the corresponding leaf node is Li (i=1,2,...n). It can be proved that the WPL of Huffman tree is the smallest.

If you want to read more related articles, please visit PHP Chinese website! !

The above is the detailed content of What data structure is used in Huffman coding?. For more information, please follow other related articles on the PHP Chinese website!