$ ./shannon
Shannon-Fano coding algorithm
by Sergey Tikhonov (st@haqu.net)
Usage: shannon [OPTIONS] input [output]
The default action is to encode input file.
-d Decode file.
$ cat input.txt
In the field of data compression, Shannon–Fano coding is a technique for
constructing a prefix code based on a set of symbols and their probabilities
(estimated or measured). It is suboptimal in the sense that it does not achieve
the lowest possible expected code word length like Huffman coding; however
unlike Huffman coding, it does guarantee that all code word lengths are within
one bit of their theoretical ideal − logP(x). The technique was proposed in
Claude Elwood Shannon's "A Mathematical Theory of Communication", his 1948
article introducing the field of information theory. The method was attributed
to Robert Fano, who later published it as a technical report.[1] Shannon–Fano
coding should not be confused with Shannon coding, the coding method used to
prove Shannon's noiseless coding theorem, or with Shannon-Fano-Elias coding
(also known as Elias coding), the precursor to arithmetic coding.
$ ./shannon input.txt
55
0.152838 00
o 0.084061 010
e 0.082969 0110
n 0.069869 01110
t 0.066594 01111
i 0.064410 1000
a 0.055677 1001
s 0.043668 1010
h 0.043668 10110
d 0.040393 10111
r 0.036026 1100
c 0.032751 11010
l 0.030568 110110
u 0.019651 1101110
g 0.017467 1101111
f 0.016376 111000
m 0.016376 111001
p 0.013100 111010
w 0.013100 1110110
b 0.012009 11101110
, 0.007642 11101111
S 0.006550 1111000
. 0.005459 11110010
F 0.004367 11110011
k 0.003275 11110100
v 0.003275 111101010
y 0.003275 111101011
T 0.003275 111101100
? 0.003275 111101101
( 0.003275 111101110
x 0.003275 111101111
E 0.003275 11111000
) 0.003275 111110010
H 0.002183 111110011
I 0.002183 111110100
? 0.002183 111110101
C 0.002183 111110110
1 0.002183 1111101110
- 0.002183 1111101111
' 0.002183 111111000
q 0.002183 111111001
" 0.002183 111111010
? 0.002183 1111110110
? 0.001092 11111101110
] 0.001092 11111101111
R 0.001092 1111111000
? 0.001092 1111111001
P 0.001092 1111111010
[ 0.001092 1111111011
8 0.001092 1111111100
4 0.001092 1111111101
M 0.001092 11111111100
9 0.001092 11111111101
; 0.001092 11111111110
A 0.001092 11111111111
11111010001110000111110110011000111000100001101101101011100010111000001011110010
11111001001101001011100111101011000110101010101000010011101110111100111100010110
10010111001110010011101111011011111101011111110110111100111001011100100011010010
10111100001110110111100100010100010010001111011011010101100111010001111110011101
11001100011100001011000011010010011101010011111100110111011010011111000011101101
11100100100111010110001101110001000111101111001101001010111011000111011101001101
00110101110001001110001001001010011001111000101110000010101111010111110011110111
00101101101010001001011101011100011111011001101000110000111010110001011101110100
11110111010001101101000011111000011010100011110111001101010011111000111001100101
11101101011100010110000111001011010011010110111011000110101111111100101111001000
11111010001111001000101000101011011101110111001011101001111100011100110011101100
01000011100001111101100110001010011001110101001100001111101101001011110010000111
10010111010011010100001110010011110010011101010110100001101111010100110000111110
11001100011011001011101100110101001111001110100101010101010001110111011011001100
00110111101111111010011011010011110110101110011010010101110110001110110010110010
11100110110011001110110111101111101100011011010001111010001100011111001111011101
11000111000111001100101110001101001010111100001110110111111111111110001011001011
10110011011110101001101100001101110011101101101000111101000110001111100111101110
11100011100011100110010111000110100101011110000111011011111110111100100001111001
01110100110101000110111111011101001110010010111001111011001100001111101101001011
11001001110110110110001101001010111011000111011001011001011100110110011001110110
11110111110110101000100111000110001110110100001111101101000011100001001110011000
11101110100001111000101110000001111101100110100011000001111101100110010110001100
11111000110101001110110001000101110110100111011000111101101111111100111111101110
00110110010110111111111110101111011101111011111111100101111001000111101100101100
11000011110110110101011001110100011111100111011100110001110110100110100011101011
00010111010010101001101011100100001110001111101101101101001110111010111011000111
11000110110111011001001010111001111000101101001011100111001001110111111000101000
11111101011111111111001111111110010010111110110011011100110010111110001101010011
10110001111011001011001100101100111101011000101110000011111011001011100111100111
01110011101000110101001011111000010011101111110101110111100101101000101000111110
11101111111110111111111011111111100001001110001111100011010110110011000100001110
01111110001010111110111011010100001110110111100011111011001100011100010000110110
11010111000101110000010000111011100001011001110011001011111000010011100001111101
10011001011001111010111111001000111101100101100110001110010110011111011001010111
00111011010011010001001011110111111001000111011101101110011110110101110001111010
00111111100001011101110011011000111100111100111001011100101110111100111011010110
01000110110100101111011011000011101011011101110111011011010001010101100110101110
01000011110010011010001001000111101101101010110011101000110101001110110001100011
01110100101100011111111001011111110111111101110111111011110011110001011010010111
00111001001110111101101111110101111111011011110011100101110010001101001010111100
00111011011110010101011001011011101101101011100011100100111100111011100110001101
00100111011100011011101010011010111001110110100001111101100011110001011010010111
00111001001110001101001010111100001110110111111101111000111110110011000110100101
01111000011101101111001110010110011111011001010111001101110101001101011100011110
10001110101100010111101010011000111100010110100101110011100100111011111100010100
00111001010001010011011011001101010101000110100101011110000111011011110001111101
10011001011000110111001111011110001011000011101101000011111011000111100010110100
10111001110010011101111101111111100111001011100101111101111111110001101101000100
11010001101001010111100001110110111100111101110100111011010100100011110100011100
10111011001110001001101000111110001101101000100110100011010010101111000011101101
11111111001011101111000111110110011000111010110001101101011011101100101001011000
00111101000100111001000011111011011100101100111110001101000110100101011110000111
0110111111110010