Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.
Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.
Итак, алгоритм Хаффмана работает следующим образом:
Алгоритм Шеннона-Фано работает следующим образом:
Таким образом, видно, что алгоритм Хаффмана как бы движется от листьев к корню, а алгоритм Шеннона-Фано, используя деление, движется от корня к листям.
Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.
Ну вот собственно и все, о чем я хотел рассказать. Всю информацию можно взять из википедии. На рисунках приведены частоты сверху.
Спасибо за внимание!
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.
Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.
Итак, алгоритм Хаффмана работает следующим образом:
- На вход приходят упорядоченные по невозрастанию частот данные.
- Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
- Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «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 <enter> to show');
ReadLn;
ClrScr;
{ Поиск кода Фано, входные параметры начало и конец последовательности }
SearchTree(' ',' ', 1, 6);
ReadLn;
end;
Ну вот собственно и все, о чем я хотел рассказать. Всю информацию можно взять из википедии. На рисунках приведены частоты сверху.
Спасибо за внимание!
