Читайте также:
|
Идея Р. Фано заключается в применении к алфавиту языка неравномерной схемы кодирования. На те символы (буквы) языка, которые встречаются в текстах чаще, нужно отводить меньше бит, а на те, которые встречаются реже – больше. При этом используется статистика, т.е. частоты (вероятности), с которыми символы встречаются в текстах, написанных на данном языке.
Рассмотрим пример. Пусть для определённости алфавит состоит из 8-ми букв: a, b, c, d, e, f, g, h. При равномерном кодировании достаточно трёх битов на букву, так как 8=23.
a «000, b «001, c «010, d «011, e «100, f «101, g «110,
h «111
0 1
0 1 0 1
0 1 0 1
0 1 0 1
Рис.2 Пример схемы составления кодовых наборов по Р. Фано.
Если учесть частоты (вероятности) встречаемости букв в текстах, то число бит на букву в среднем можно уменьшить, т.е. сделать его меньше трёх. Пусть, например, частоты для определённости будут:
p(a)= 0,08; p(b)= 0,44; p(c) =0,08; p(d)= 0,08; p(e)= 0,08; p(f) =0,08; p(g) =0,08; p(h) =0,08
Заметим, что сумма частот всегда должна быть равна единице (полная система событий).
Схема кода Р. Фано изображена на рис.2. Она основана на следующем алгоритме:
1) составить список букв алфавита в порядке убывания соответствующих им вероятностей.
2) разбить этот список на два подсписка таким образом, чтобы значения вероятностей того, что наугад взятая буква окажется в первом или во втором списке, были бы по возможности равны.
3) приписать одному из списков символ 0, а другому 1.
4) Рассматривая каждый из подсписков как исходный, применить к ним операции 2) и 3).
5) Этот процесс продолжать до тех пор, пока в каждом из очередных подмножеств не окажется по одной букве.
6) Каждой букве приписать двоичный код, состоящий из последовательности нулей и единиц, встречающихся на пути из исходного множества букв, к множеству, состоящему из одной буквы.
В результате получаем двоичные кодовые наборы Фано для символов данного алфавита.
a «01, b «00, c «100, d «1010, e «1011, f «110, g «1110,
h «1111
Среднее число бит на символ алфавита (подсчитывается по правилу вычисления среднего значения случайной величины) получается равным:
0,08 × 2+0,44 × 2+0,08 × 3+0,08 × 4+0,08 × 4+0,08 × 3+0,08 × 4+0,08 × 4=
24 × 0,08+0,44 × 2=2,8
Это приводит к сжатию текстов в данном примере (по сравнению с равномерным кодированием) на (1-2,8/3) × 100 %= ~ 7 %.
Таким образом, Р. Фано открыл качественно новую точку зрения на преобразование информации, что послужило основой для поиска других схем кодирования, которые позволяли бы сжимать тексты в ещё большей степени. Такие схемы были предложены американским математиком Д. А. Хаффмэном (1952). Рассмотрим простейшую из них.
Дата добавления: 2015-09-10; просмотров: 112 | Поможем написать вашу работу | Нарушение авторских прав |