View source for Entropy/connections between different meanings of entropy/entropy example 4

To understand the formula 

:<math>\label{approx}
R(B) \approx \frac{\frac 1nH_{\mu_B}(\Lambda^n)}{\log_2(\#\Lambda)}, 
</math>


consider a lossless compression algorithm applied to a message <math>B</math> 
of a finite length <math>N\ .</math> 
To save on the output length, the decoding instructions must be relatively short compared to <math>N\ .</math> This is easily 
achieved in codes which refer to relatively short components of the messages only. For example, the decoding instructions may consist of a complete list of the subwords <math>A</math> of some carefully chosen length 
<math>n</math> appearing in <math>B</math> and their images <math>\Phi(A)\ .</math> The images may have different lengths (as short as possible). The 
image of <math>B</math> is obtained by cutting <math>B</math> into subwords <math>B=A_1A_2\dots A_k</math> of length 
<math>n</math> and concatenating the images of these subwords: <math>\Phi(B)=\Phi(A_1)\Phi(A_2)\cdots\Phi(A_k)\ .</math> 
(There are additional issues here: in order for such a code to be invertible, the images <math>\Phi(A)</math> must form a 
[[prefix-free family]], so that there is always a unique way of partitioning <math>\Phi(B)</math> back into the images <math>\Phi(A_i)\ .</math> But this does not essentially affect the computations.) For best compression results, it is 
reasonable to assign the shortest images to the subwords appearing in <math>B</math> with highest frequencies. It can be proved, 
with the help of the Shannon-McMillan-Breiman theorem, that such a code realizes the compression rate as in 
\eqref{approx} for nearly all sufficiently long messages <math>B\ .</math> 

For example, consider the binary message of length 30:

:<math>
B \ = \ 011001111001001111010001111110 \ = \ 011,001,111,001,001,111,010,001,111,110.
</math>

On the right, <math>B</math> is shown divided into subwords of length 3. The frequencies of the subwords 
in this division are: 

:<math>
\begin{matrix}
000 - 0 &
001 - 0.4 &
010 - 0.1 &
011 - 0.1 \\
100 - 0 &
101 - 0\ \ \ &
110 - 0.1 &
111 - 0.3 
\end{matrix}
</math>

The theoretical value (obtained using the formula \eqref{approx} for <math>n=3</math>) of the best compression ratio is 

:<math>
-0.4\log_2(0,4)-0.3\log_2(0,3)-3\cdot 0.1\log_2(0.1)\approx 68,2\%. 
</math>

A binary prefix-free code giving the shortest images to the most frequent subwords is

:<math>
\begin{matrix}
001 &\mapsto& 0, \\
111 &\mapsto& 10, \\
010 &\mapsto& 110, \\
011 &\mapsto& 1110, \\
110 &\mapsto& 1111.
\end{matrix}
</math>

The image of <math>B</math> by this code is:

:<math>
\Phi(B)= 1110,0,10,0,0,10,110,0,10,1111 = 111001000101100101111  
</math>

The compression rate achieved on <math>B</math> using this code equals <math>21/30 = 70\%\ ,</math> 
which means that the code is quite efficient on <math>B\ .</math>


''Remark'': The image given here does not include the decoding instructions, which comprise simply a record of the above prefix-free code. One has to imagine that <math>B</math> is much longer and then the decoding instructions (of fixed length) do not affect the compression ratio.