Of binary tree_ Huffman tree_ Huffman encoding

Huffman tree is also called optimal binary tree

        Given N The weight of N individual leaf node , Construct a binary tree , If the weighted path length of the tree reaches the minimum , Call such a binary tree an optimal binary tree , Also known as Huffman tree (Huffman Tree). Huffman tree is the tree with the shortest weight path length , Nodes with larger weights are closer to the root .

 

A term is used to explain

route ： In a tree , The path from one node to another , Called the path . chart 1 in , From root to node a The path between is a path .
The length of the path ： In one path , Every time we pass through a node , The length of the path should be added 1 . For example, in a tree , It is specified that the number of layers where the root node is located is 1 layer , So from the root node to the i The path length of the layer node is i - 1 . chart 1 From root node to node c The path length of is 3.
The right of the node ： Give each node a new value , It's called the weight of this node . for example , chart 1 Middle node a The right to 7, node b The right to 5.
The weighted path length of the node ： It refers to the product of the path length from the root node to the node and the weight of the node . for example , chart 1 Middle node b The weighted path length of is 2 * 5 = 10 .

The weighted path length of a tree is the sum of the weighted path lengths of all leaf nodes in the tree . Often described as  “WPL” . For example, figure 1 The weighted path length of the tree shown in is ：

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

 

Huffman tree parsing :

 

The weighted path length of three binary trees is ：

（a）WPL=9x2+4x2+5x2+2x2=18+8+10+4=40

（b）WPL=9x1+5x2+4x3+2x3=9+10+12+6=37

（c）WPL=4x1+2x2+5x3+9x3=4+4+15+27=50

among （b） Of the binary tree shown in WPL Minimum , This tree is the Huffman tree . It can be seen from the above figure ： from n In a binary tree composed of three weighted leaf nodes , A full or full binary tree Not necessarily the optimal binary tree . The greater the weight, the closer the node is to the root node Is the best binary tree .

 

How to build a Huffman tree ?

For a given... With its own weights n Nodes , There is an effective way to build a Huffman tree ：

1. stay n Choose two of the smallest weights , The corresponding two nodes form a new binary tree , And the weight of the root node of the new binary tree is the sum of the weights of the left and right children ;
2. In the original n Delete the two smallest weights from the three weights , At the same time, new weights are added to  n–2 In the column of weights , And so on ;
3. repeat 1 and 2 , Until all nodes are constructed into a binary tree , This tree is the Huffman tree .

Huffman code

A simple understanding is , If I had A,B,C,D,E Five characters , Frequency of occurrence （ That's the weight ） Respectively 5,4,3,2,1, Then we first take the two minimum weights as the left and right subtrees to construct a new tree , Take away 1,2 Form a new tree , Its node is 1+2=3, Pictured ：

 

The dotted line is the newly generated node , The second step is to set the newly generated weight as 3 To the rest of the set , So the set becomes {5,4,3,3}, Then according to the second step , Take the minimum two weights to form a new tree , Pictured ：

 

Then build Huffman tree in turn , Here's the picture ：

 

The character corresponding to each weight replacement is shown in the figure below ：

 

So the corresponding code of each character is ：A->11,B->10,C->00,D->011,E->010
Huffman coding is a non prefix coding . No confusion in decoding . It is mainly used in data compression , Encryption and decryption, etc .

If you consider further storage space savings , The probability of occurrence should be high （ Large proportion ） Use as few characters as possible 0-1 Encoding , That is, closer to the root （ Fewer nodes ）, This is the optimal binary tree - Huffman tree .
Why? ？----->  The one with large weight is in the upper layer , Those with small weights are in the lower layer . Meet the code length with high frequency .

 

The weighted path weight of Huffman code ： The value of the leaf node * Height of leaf node （ The root node is 0）

The weighted path length in the above figure is ：（3+4+5）*2+（1+2）*3=33

 

The Huffman code is reproduced from  :https://blog.csdn.net/qq_36653505/article/details/81701181