Shannon-Fano algorithm

The algorithm of the Shannon-Fano method is one of the first compression algorithms that was first formulated by the American scientists Shannon and Fano, and it has a great similarity with the Huffman algorithm. The algorithm is based on repetition rate. Thus, a frequently occurring symbol is encoded by a code of shorter length, and a rarely occurring code is encoded by a code of greater length.
In turn, the codes obtained during coding are prefix. This allows you to uniquely decode any sequence of code words. But all this entry.

To work, both algorithms must have a table of frequency elements of the alphabet.

So, the Huffman algorithm works as follows:

1. At the input come ordered by non-increasing frequency data .
2. The two smallest letters of the alphabet are selected, and a parent is created (the sum of the two frequencies of these “sheets”).
3. The descendants are deleted and the parent is written instead; the “branches” of the parent are numbered: the left branch is set to correspond to “1”, the right one to “0”.
4. Step two is repeated until the main parent, the “root,” is found.

The Shannon-Fano algorithm works as follows:

1. At the input come ordered by non-increasing frequency data.
2. The middle is located, which divides the alphabet into approximately two parts. These parts (the sum of the frequencies of the alphabet) are approximately equal. For the left part is assigned "1", for the right "0", so we get the leaves of the tree
3. Step 2 is repeated until we get a single element of the sequence, i.e. leaflet

')

Thus, it is clear that the Huffman algorithm seems to be moving from the leaves to the root, and the Shannon-Fano algorithm, using division, moves from the root to the leaves.

Well, quickly interpreting the information, you can write the code of the Shannon-Fano algorithm in Pascal. They asked to write on it. Therefore, I will provide a listing with comments.

 program ShennonFano; uses crt; const a :array[1..6] of char = ('a','b','c','d','e','f'); {  } af:array[1..6] of integer = (10, 8, 6, 5, 4, 3); {   } {       } procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer); var dS:real; {    } i, m, S:integer; { m -     , S -  ,   } c_branch:string; {      } begin {         } if (a<>' ') then c_branch := full_branch + branch else c_branch := ''; {  :    ,    } if (start_pos = end_pos) then begin WriteLn(a[start_pos], ' = ', c_branch); exit; end; {       } dS := 0; for i:=start_pos to end_pos do dS:= dS + af[i]; dS := dS/2; {      for, while, repeat   } S := 0; i := start_pos; m := i; while ((S+af[i]<dS) and (i<end_pos)) do begin S := S + af[i]; inc(i); inc(m); end; {     } SearchTree('1', c_branch, start_pos, m); {    } SearchTree('0', c_branch, m+1, end_pos); end; begin WriteLn('Press <enter> to show'); ReadLn; ClrScr; {   ,       } SearchTree(' ',' ', 1, 6); ReadLn; end; 
 

program ShennonFano; uses crt; const a :array[1..6] of char = ('a','b','c','d','e','f'); { } af:array[1..6] of integer = (10, 8, 6, 5, 4, 3); { } { } procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer); var dS:real; { } i, m, S:integer; { m - , S - , } c_branch:string; { } begin { } if (a<>' ') then c_branch := full_branch + branch else c_branch := ''; { : , } if (start_pos = end_pos) then begin WriteLn(a[start_pos], ' = ', c_branch); exit; end; { } dS := 0; for i:=start_pos to end_pos do dS:= dS + af[i]; dS := dS/2; { for, while, repeat } S := 0; i := start_pos; m := i; while ((S+af[i]<dS) and (i<end_pos)) do begin S := S + af[i]; inc(i); inc(m); end; { } SearchTree('1', c_branch, start_pos, m); { } SearchTree('0', c_branch, m+1, end_pos); end; begin WriteLn('Press <enter> to show'); ReadLn; ClrScr; { , } SearchTree(' ',' ', 1, 6); ReadLn; end;

Well, that's all I wanted to talk about. All information can be taken from Wikipedia. The figures show the frequencies above.

Thanks for attention!