Алгоритм Шеннона-Фано

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

Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.

Итак, алгоритм Хаффмана работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
3. Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
4. Шаг два повторяется до тех пор, пока не будет найден главный родитель — «корень».

Алгоритм Шеннона-Фано работает следующим образом:

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

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

Спасибо за внимание!