Алгоритмы / [Из песочницы] Алгоритм Шеннона-Фано

Алгоритм метода Шеннона-Фано один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано и имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь коды полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.
Для работы оба алгоритма должны иметь таблицу частот для элементов алфавита.
Итак, алгоритм Хаффмана работает следующим образом:
На вход приходят упорядоченные по невозрастанию данные по частотам.

Выбирается две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).

Потомки удаляются и вместо них записывается родитель, ветви родителя нумеруются «ветви»: левой ветви ставится в соответствие «1», правой «0».

Шаг два повторяется пока не будет найден главный родитель — «корень».

Алгоритм Шеннона-Фано работает следующим образом:
На вход приходят упорядоченные по невозрастанию данные по частотам.Находится середина, которая делит алфавит примерно на две части, эти части (суммы частот алфавита) примерно равны

Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева

Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок

Таким образом, видно, что алгоритм Хаффмана как бы движется от листьев к корню, а алгоритм Шеннона-Фано используя деление движется от корня к листям.
Ну вот, быстро осмыслив информацию, можно и написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.
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 to show');
ReadLn;
ClrScr;
{ Поиск кода Фано, входные параметры начало и конец последовательности }
SearchTree(' ',' ', 1, 6);
ReadLn;
end;

Ну вот собственно и все, о чем я хотел рассказать. Всю информацию можно взять из википедии. На рисунках приведены частоты сверху.
Спасибо за внимание!