What Is a Prefix Code?

The prefix encoding refers to the encoding of a character set, which requires that the encoding of any character in the character set is not a prefix of the encoding of other characters. For example: abcd is required to be encoded (where a = 0, b = 10, c = 110 , D = 11, it means that the prefix of 110 can be c or da, not unique)

Prefix encoding

Right!

The prefix encoding refers to the encoding of a character set, which requires that the encoding of any character in the character set is not a prefix of the encoding of other characters. For example: abcd is required to be encoded (where a = 0, b = 10, c = 110 , D = 11, it means that the prefix of 110 can be c or da, not unique)

Binary tree: The left branch represents the character '0' and the right branch represents the character '1'. The branch string on the path from the root node to the leaf node can be used as the leaf node character encoding. The code thus obtained must be a prefix code.

Binary prefix encoding generated by the process of constructing a Huffman tree. Huffman tree is a kind of tree with the shortest path length.

Features: shortest weighted path length

· ABFACGCAHGBBAACECDFGFAAEABBB

1. Statistics: A (8) B (6) C (4) D (1) E (2) F (3) G (3) H (1)

2. Construct Huffman Tree

3. Get Huffman code

A: 01

B: 11

C: 001

D: 00000

E: 0001

F: 100

G: 101

H: 00001

New string encoding length: 8 * 2 + 6 * 2 + 4 * 3 + 1 * 5 + 2 * 4 + 3 * 3 + 3 * 3 + 1 * 5 = 76