当前位置:网站首页>Basic concepts of Huffman tree
Basic concepts of Huffman tree
2022-07-07 03:25:00 【Muzi text_ Ah】
The basic concept of Huffman tree :
(1) route : It consists of branches from one node to another
(2) The length of the path : Number of branches on the path a→d The path length of = 2
(3) The path length of the tree : The sum of the path length from the tree root to each node . Case diagram :10
(4) power : A quantity given to an entity , It is a numerical description of the attributes of entities . If the nodes of the tree have weights , That is, the weighted tree .
(5) The weighted path length of the node : The product of the path length from node to root and the weight on the node d Weighted path length =72=14
(6) Weighted path length of tree : The sum of the weighted path lengths of all leaf nodes in the tree . Case diagram :27+25+22+2*4=36
(7) Huffman tree (Huffman): The best binary tree , The tree with the smallest weighted path length
The characteristics of Huffman tree
- The path length from the node with large weight to the root node is short ;
- The path length from the node with small weight to the root node is long .
Ø There is no degree in Huffman coding tree 1 The node of ;
Ø If given n Weight (n Leaf node ), Then the total number of points of Huffman tree is 2n-1;
Ø The height of Huffman tree does not exceed n.
The construction algorithm of Huffman tree :
Huffman code :
v Prefix encoding : The encoding of any character is not a prefix of the encoding of another character .
Such as : character a、b、c、d The codes of the two are respectively 0、1、01、10, be a The code of is c The prefix of the encoding ,b The code of is d Coded prefix , This code is not a prefix code .
When decoding , about 01011011 The decoding result of will not be unique .
v Huffman code
For a tree with n A leafy Huffman tree , Assign 0, The right branch gives 1, Then the path from the root to each leaf , Form a binary string respectively , This binary string is called Huffman code .
Do Huffman coding , Build Huffman tree first .
Huffman coding is prefix coding , And it's the best prefix code .
边栏推荐
- Sub pixel corner detection opencv cornersubpix
- Under the tide of "going from virtual to real", Baidu AI Cloud is born from real
- [untitled]
- 【达梦数据库】添加自动收集统计信息的任务
- 密码学系列之:在线证书状态协议OCSP详解
- Intelligent static presence detection scheme, 5.8G radar sensing technology, human presence inductive radar application
- Jericho is in non Bluetooth mode. Do not jump back to Bluetooth mode when connecting the mobile phone [chapter]
- Jerry's question about DAC output power [chapter]
- Jerry's phonebook acquisition [chapter]
- 1200.Minimum Absolute Difference
猜你喜欢
Shangsilicon Valley JVM Chapter 1 class loading subsystem
How to replace the backbone of the model
VHDL实现任意大小矩阵加法运算
Leetcode-02 (linked list question)
OC, OD, push-pull explanation of hardware
MOS transistor realizes the automatic switching circuit of main and auxiliary power supply, with "zero" voltage drop and static current of 20ua
变量、流程控制与游标(MySQL)
Function reentry, function overloading and function rewriting are understood by yourself
Laravel php artisan 自动生成Model+Migrate+Controller 命令大全
从0开始创建小程序
随机推荐
20.(arcgis api for js篇)arcgis api for js面采集(SketchViewModel)
存储过程与函数(MySQL)
[Dameng database] after backup and recovery, two SQL statements should be executed
“去虚向实”大潮下,百度智能云向实而生
[cpk-ra6m4 development board environment construction based on RT thread studio]
Matlab Error (Matrix dimensions must agree)
Significance and measures of source code confidentiality
DOMContentLoaded和window.onload
Make (convert) ICO Icon
Not All Points Are Equal Learning Highly Efficient Point-based Detectors for 3D LiDAR Point
leetcode
【安全的办公和生产力应用程序】上海道宁为您提供ONLYOFFICE下载、试用、教程
变量、流程控制与游标(MySQL)
25.(arcgis api for js篇)arcgis api for js线修改线编辑(SketchViewModel)
What about SSL certificate errors? Solutions to common SSL certificate errors in browsers
sshd[12282]: fatal: matching cipher is not supported: aes256- [email protected] [preauth]
HDU 4337 King Arthur' S Knights it outputs a Hamiltonian circuit
杰理之开 BLE 退出蓝牙模式卡机问题【篇】
An error in SQL tuning advisor ora-00600: internal error code, arguments: [kesqsmakebindvalue:obj]
[dream database] add the task of automatically collecting statistical information