Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "what is the concept of C++ Huffman tree and how to realize it". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this article "what is the concept of C++ Huffman tree and how to realize it" can help you solve the problem.

I. basic concepts

The weight of a node: a numerical value with some realistic meaning

Weighted path length of a node: the product of the path length from the root of the node to the node and the weight of the node

The weighted path length of the tree: the sum of the weighted path lengths of all leaf nodes on the tree

Huffman tree: in a binary tree with n n n weighted leaf nodes, the binary tree with the smallest wpl is called Huffman tree, which is also called optimal binary tree (Huffman tree is not unique given leaf nodes).

Second, construct Huffman tree

It's relatively simple, and I won't go into the steps here.

Third, the basic properties of Huffman tree

Each initial node is ultimately a leaf node, and the smaller the weight, the greater the path length from the node to the root node.

The total number of nodes of a Huffman tree with n n n root nodes is 2 n − 1.

There is no node with degree 1 in Huffman tree.

Huffman tree is not unique, but w p l must be the same and optimal.

4. Huffman coding

Objective: to construct a binary code for a given character set so that the expected length of the code can be minimized.

In the exam, the scum sent a telegram of 100 multiple-choice questions using Huffman coding, and the scum passed 10 A, 8 B, 80 C and 2 D, and the old slag decoded it by Huffman coding.

The Huffman tree constructed by small slag is as follows:

It can be found that the codes of A, B, C and D are 10, 111, 0 and 110, respectively.

In this way, as long as the scum sends the 01 sequence according to the order of the answers to the 100 questions, the scum will be able to receive the answer correctly after receiving it. And Huffman coding will not be ambiguous, because Huffman coding is a kind of prefix coding.

Prefix coding: none of the encodings are prefixes of the other, because the data nodes are leaf nodes. If the encoding of one character is the prefix of another character, then the character must be in the internal node, which is impossible.

Huffman coding obtained from Huffman tree: each character in the character set appears as a leaf node in the Huffman tree, and the frequency of each character is the weight of the node.

When encoding a string, because the character with higher frequency (larger weight) is closer to the root node, the coding is shorter; only the character with lower frequency (lower weight) is farther away from the root node, and the coding length is longer. It doesn't matter. Since the coding of characters with high frequency is short, Huffman coding can get the shortest coding sequence.

5. Huffman decoding

Huffman coding is different from ASCII and Unicode character coding. The code length of these character sets uses the same length coding scheme, while Huffman coding uses variable length coding, and Huffman coding satisfies immediate decodability (that is, the coding of any character will not be the prefix of another longer character coding), as long as all the bits in the encoding of a character are received. It can be decoded immediately without waiting for the bits received later to determine whether there is another legitimate longer encoding.

The first table does not satisfy the immediate decodability, while the second table does.

When we receive 100, we need to consider whether to decode it to D immediately or wait for the next bit. If the next bit is 0, we can decode it to B, which shows that the coding in the table does not have immediate decodability.

The second table is immediately decodable because the encoding of any character is not the prefix of another longer character encoding. As long as the received sequence corresponds to the encoding of a character, it can be decoded directly into the corresponding character without waiting for the following data.

Our code implementation is to build a Huffman tree out of strings, which can only be encoded and decoded for strings made up of characters contained in that string. The encoding stored in the code using strings should actually be stored in bit

# include # include using namespace std;using uint = unsigned int Class HuffmanTree {public: / / the lambda expression here is used to initialize the function function object / / the constructor function indicates that if a parameter is passed, this parameter is used to initialize the comparator object / / if two parameters are passed in, the first is the comparator object The second is the underlying container HuffmanTree (): min_heap_ ([] (Node* N1, Node* N2)-> bool {return N1-> weight_ > N2-> weight_ }), root_ (nullptr) {} ~ HuffmanTree () {init (); cout data_); cur = root_;}} return decode_str;} uint get_wpl () {if (root_ = = nullptr) {return 0 } if (root_- > left_ = = nullptr & & root_- > right_ = = nullptr) {/ / for leaf nodes, return your own weight * depth return root_- > weight_ * 1 directly } else {/ / for internal nodes, directly return the sum of weight obtained from child nodes return get_w (root_- > left_, 2) + get_w (root_- > right_, 2) } private: struct Node {Node (char data, uint weight): data_ (data), weight_ (weight), left_ (nullptr), right_ (nullptr) {} char data_; uint weight_; Node* left_; Node* right_;} Private: / / prevents the current object from rebuilding the Huffman tree, releasing all nodes, and then initializing the private member void init () {/ / release the node of the Huffman tree if (root_! = nullptr) {queue Q; q.push (root_) While (! q.empty ()) {Node* node = q.front (); q.pop (); if (node- > left_! = nullptr) {q.push (node- > left_) } if (node- > right_! = nullptr) {q.push (node- > right_);} delete node;} MinHeap empty ([] (Node* N1, Node* N2)-> bool {return N1-> weight_ > N2-> weight_;}); swap (empty, min_heap_) Code_map_.clear ();}} void create_huffman_code (const string& str) {string code; create_huffman_code (root_, code);} void create_huffman_code (Node* node, string code) {if (node- > left_ = = nullptr & & node- > right_ = = nullptr) {code_map_ [node-> data_] = code Return;} create_huffman_code (node- > left_, code + "0"); create_huffman_code (node- > right_, code + "1");} uint get_w (Node* node, int depth) {if (node = = nullptr) {return 0 } if (node- > left_ = = nullptr & & node- > right_ = = nullptr) {/ / for leaf nodes, return your own weight * depth return node- > weight_ * depth directly } else {/ / for internal nodes, directly return the sum of weight obtained from the child node return get_w (node- > left_, depth + 1) + get_w (node- > right_, depth + 1);}} private: Huffman encoding using MinHeap = priority_queue corresponding to Node* root_; unordered_map code_map_; / / storage characters MinHeap min_heap_; / / use small root heap when building Huffman tree; int main () {string str = "Aa"; HuffmanTree htree; htree.create (str); htree.show_huffman_code (); cout

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.