Given n leaf nodes, each node is weighted to construct a binary tree. If the weighted path length is the shortest, it is called Huffman tree (optimal binary tree), and the node with the largest weight is closest to the root node.

Given a set of symbols s and their weights w (probability of occurrence)

According to this table, let's construct a Huffman tree.

Huffman compression is a data compression technology, which can greatly compress the natural language file space. Instead of using 8-bit binary numbers to represent each character, we use fewer bits to represent high-frequency characters and more bits to represent low-frequency characters.

After we built the Huffman tree, we removed all the weights and assigned 0 or 1 to each edge.

Here we define left 0 and right 1.

Accordingly, we try to decode a short string:

0 1 10 1 1 1 1 1

Starting from the root node, when it encounters 0, it moves to the left and down once to get the character A.

Start decoding the next character. Starting from the root node, you encounter two 1, move it to the right and down twice, and move it to the left and down once when you encounter 0, and you get the character c.

Start decoding the next character, starting from the root node, encounter five 1, and move to the right and down five times to get the character e.

So the character we decoded is ACE.

Huffman encoding's basic principles are here, thank you!