Entropy encoding

related topics
{math, number, function}
{system, computer, user}
{car, race, vehicle}

In information theory an entropy encoding is a lossless data compression scheme that is independent of the specific characteristics of the medium.

One of the main types of entropy coding creates and assigns a unique prefix code to each unique symbol that occurs in the input. These entropy encoders then compress data by replacing each fixed-length input symbol by the corresponding variable-length prefix codeword. The length of each codeword is approximately proportional to the negative logarithm of the probability. Therefore, the most common symbols use the shortest codes.

According to Shannon's source coding theorem, the optimal code length for a symbol is −logbP, where b is the number of symbols used to make output codes and P is the probability of the input symbol.

Two of the most common entropy encoding techniques are Huffman coding and arithmetic coding. If the approximate entropy characteristics of a data stream are known in advance (especially for signal compression), a simpler static code may be useful. These static codes include universal codes (such as Elias gamma coding or Fibonacci coding) and Golomb codes (such as unary coding or Rice coding).

Entropy as a measure of similarity

Besides using entropy encoding as a way to compress digital data, an entropy encoder can also be used to measure the amount of similarity between streams of data. This is done by generating an entropy coder/compressor for each class of data; unknown data is then classified by feeding the uncompressed data to each compressor and seeing which compressor yields the highest compression. The coder with the best compression is probably the coder trained on the data that was most similar to the unknown data.

External links

An earlier (open content) version of the above article was posted on PlanetMath.

Full article ▸

related documents
Dining cryptographers protocol
XPointer
Sequential access
SAX
RIPEMD
Filter (Unix)
Data element
Binary symmetric channel
Canonical Encoding Rules
Cfront
RC5
Euler-Jacobi pseudoprime
Landau's function
Star height problem
Elementary event
Simple module
Location parameter
Poem code
Persistence
Pedal triangle
Common Language Infrastructure
XBasic
Conjugate closure
Unknot
Central moment
Precondition
Online algorithm
Hurwitz polynomial
De Bruijn-Newman constant
Fibonacci