До появления работы Шеннона, кодирование символов алфавита при передаче сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым по формуле Хартли. С появлением этой работы начали появляться способы, кодирующие символы разным числом бит в зависимости от вероятности появления их в тексте, т.е. более вероятные символы кодируются короткими кодами, а редко встречающиеся символы - длинными (длиннее среднего). Наиболее известными методами данного класса являются способы кодирования Хаффмана и Шеннона-Фано.
Код Хаффмана - статистический способ сжатия, который дает снижение средней
длины кода используемого для представления символов фиксированного алфавита.
Код Хаффмана является примером кода, оптимального в случае, когда все
вероятности появления символов в сообщении - целые отрицательные степени
двойки. Код Хаффмана может быть построен по следующему алгоритму:
1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания
вероятности их появления в тексте;
2. Последовательно объединяем два символа с наименьшими вероятностями
появления в новый составной символ, вероятность появления которого полагается
равной сумме вероятностей составляющих его символов; в конце концов мы
построим дерево, каждый узел которого имеет суммарную вероятность всех узлов,
находящихся ниже него;
3. Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу
(например, направо - 1, налево - 0).
Для заданного распределения частот символов может существовать несколько возможных кодов Хаффмана, - это дает возможность определить каноническое дерево Хаффмана, соответствующее наиболее компактному представлению исходного текста.
Близким по технике построения к кода Хаффмана являются коды Шеннона-Фано,
предложенные Шенноном и Фано в
1948 -
49 гг.
независимо друг от друга. Их
построение может быть осуществлено следующим образом:
1. Выписываем в ряд все символы в порядке возрастания вероятности появления их
в тексте;
2. Последовательно делим множество символов на два подмножества так, чтобы
сумма вероятностей появления символов одного подмножества была примерно равна
сумме вероятностей появления символов другого. Для левого подмножества каждому
символу приписываем "0", для правого - "1". Дальнейшие разбиения повторяются
до тек пор, пока все подмножества не будут состоять из одного элемента.
Алгоритм создания кода Хаффмана называется снизу-вверх, а Шеннона-Фано - сверху-вниз. Преимуществами данных методов являются их очевидная простота реализации и, как следствие этого, высокая скорость кодирования/раскодирования. Основным недостатком является их неоптимальность в общем случае.
| Изменена 19.03.2011 06:45 MSK |
| быстрая замена замков |
|