info4

$e-MATH$

The Mathematics of Communication

4. Writing an optimal code

Here are Stinson's data modified to take account of _ (space) with probability .166.

A .068 F .018 K .007 P .015 U .023 Z .0008
B .0125 G .016 L .033 Q .0008 V .008 _ .166
C .023 H .051 M .020 R .05 W .019
D .043 I .070 N .067 S .063 X .001
E .106 J .0016 O .0625 T .075 Y .016

Here is how to make a binary code for English with cost as close as possible to the theoretical minimum 4.13 bits/character.

List the characters in order of decreasing probability.
Put the characters at the ends of the branches of a binary tree in such a way that at each fork the total probability to one side is as close as possible to the total probability on the other.
Start at the base of the tree. All characters on the left branch have first code element 0. All characters on the right branch have first element 1.
Continue through the higher branchings, each time determining the next digit in the code for all the characters on one side or the other.

              _ 000
          _E <
        /     E 001
 _ETAO <          T 010
<        TAO-----<   A 0110
 \                AO<
  \                  O 0111
   \               I 1000
    \           IN<
     \         /   N 1001
      \ INSHR-<         S 1010
       <       SHR-----<   H 10110
        \               HR<
         \                 R 10111
          \             D 11000
           \         DL<
            \       /   L 11001
             \ DLUC<         U 11010
              <     UC------<
               \             C 11011
                \      M 11100
                 \ MWF<   W 111010
                  <    WF<
                   \      F 111011
                    \         Y 111100
                     \ YG----<
                      <       G 111101
                       \ P 111110
                        < 
                         \ B 1111110
                          <
                           \ V 11111110
                            <
                             \ K 111111110
                              <
                               \ J 1111111110
                                <
                                 \ X 11111111110
                                  <
                                   \ Z 111111111110
                                    <
                                     Q 111111111111

The cost for this code is 4.16 bits/character.

A	.068	F	.018	K	.007	P	.015	U	.023	Z	.0008
B	.0125	G	.016	L	.033	Q	.0008	V	.008	_	.166
C	.023	H	.051	M	.020	R	.05	W	.019
D	.043	I	.070	N	.067	S	.063	X	.001
E	.106	J	.0016	O	.0625	T	.075	Y	.016