Huffman coding

From Just Solve the File Format Problem
(Difference between revisions)
Jump to: navigation, search
(PRONOM ID)
Line 8: Line 8:
 
Symbols (such as bytes) are encoded as variable-length bit strings, optimized such that the more common symbols use shorter bit strings. No bit string is allowed to be a prefix of another bit string, which makes it possible for the decoder to deduce when a string has ended.
 
Symbols (such as bytes) are encoded as variable-length bit strings, optimized such that the more common symbols use shorter bit strings. No bit string is allowed to be a prefix of another bit string, which makes it possible for the decoder to deduce when a string has ended.
  
The code table used may be stored in the compressed file, or it may be a predefined table known to both the encoder and decoder.
+
== Discussion ==
 +
A format may use Huffman coding in a number of different ways, including:
 +
* The codebook is created automatically as the data is processed ([[Adaptive Huffman coding]]).
 +
* The codebook is stored in the file, to be read before the encoded data. Sometimes the compressed data is split into segments, which each segment having a different codebook.
 +
* The codebook is predefined, and known to both the encoder and decoder. Note that there is no fundamental distinction between a predefined Huffman code, and a variable-length integer code that wouldn't necessarily be called "Huffman".
 +
 
 +
Unfortunately, the widely-used terms "static Huffman" and "dynamic Huffman" are at least somewhat ambiguous. They don't have the same meanings to all authors.
  
 
== See also ==
 
== See also ==
 +
* [[Adaptive Huffman coding]]
 +
* [[Canonical Huffman code]]
 
* [[Modified Huffman]]
 
* [[Modified Huffman]]
  
 
== External links ==
 
== External links ==
 
* [[Wikipedia:Huffman coding|Wikipedia article]]
 
* [[Wikipedia:Huffman coding|Wikipedia article]]

Revision as of 19:42, 27 August 2020

File Format
Name Huffman coding
Ontology
PRONOM x-cmp/19

Huffman coding is a kind of lossless data compression.

Symbols (such as bytes) are encoded as variable-length bit strings, optimized such that the more common symbols use shorter bit strings. No bit string is allowed to be a prefix of another bit string, which makes it possible for the decoder to deduce when a string has ended.

Discussion

A format may use Huffman coding in a number of different ways, including:

  • The codebook is created automatically as the data is processed (Adaptive Huffman coding).
  • The codebook is stored in the file, to be read before the encoded data. Sometimes the compressed data is split into segments, which each segment having a different codebook.
  • The codebook is predefined, and known to both the encoder and decoder. Note that there is no fundamental distinction between a predefined Huffman code, and a variable-length integer code that wouldn't necessarily be called "Huffman".

Unfortunately, the widely-used terms "static Huffman" and "dynamic Huffman" are at least somewhat ambiguous. They don't have the same meanings to all authors.

See also

External links

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox