Shulou(Shulou.com)06/02 Report--

This article will explain in detail what data structure Huffman coding is used in. The editor thinks it is very practical, so I share it with you as a reference. I hope you can get something after reading this article.

The data structure used in Huffman coding is "tree structure". With the support of Huffman algorithm, an optimal binary tree is constructed, and this kind of tree is named Huffman tree. Therefore, exactly speaking, Huffman coding is a kind of coding form constructed on the basis of Huffman tree.

The data structure used in Huffman coding is "tree structure".

Huffman coding (Huffman Coding), also known as Huffman coding, is a kind of coding method. Huffman coding is a kind of variable word length coding (VLC). Huffman proposed a coding method in 1952. This method constructs the codeword with the shortest average length of the different prefix based on the probability of character occurrence, which is sometimes called the best coding, which is generally called Huffman coding (sometimes also called Huffman coding).

Huffman coding uses the tree structure in the data structure to construct an optimal binary tree with the support of Huffman algorithm. We name this kind of tree Huffman tree. Therefore, exactly speaking, Huffman coding is a kind of coding form constructed on the basis of Huffman tree, and it has a very wide range of applications.

Huffman tree

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

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

This is the end of the article on "what data structure is used in Huffman coding". I hope the above content can be of some help to you, so that you can learn more knowledge. If you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.