Huffman Binary Tree
(Redirected from Huffman Tree)
Jump to navigation
Jump to search
A Huffman Binary Tree is a variable-length prefix-free binary code with minimum weighted path length from the root given some data.
- See: Prefix Code, Entropy Encoding, Lossless Data Compression, Variable-Length Code, Linear Time, Weighted Path Length From The Root, Expected Value.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Huffman_coding Retrieved:2015-2-3.
- In computer science and information theory, a Huffman code is an optimal prefix code found using the algorithm developed by David A. Huffman … The algorithm's output can be viewed as a variable-length code table for encoding a source symbol (such as a character in a file). Huffman's algorithm derives this table based on the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. As in other entropy encoding methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, finding a code in linear time to the number of input weights if these weights are sorted. However, although optimal among methods encoding symbols separately, Huffman coding is not always optimal among all compression methods.
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Huffman_coding#Informal_description Retrieved:2015-2-3.
- Find: A prefix-free binary code (a set of codewords) with minimum expected codeword length (equivalently, a tree with minimum weighted path length from the root).