Алфавитный код Гилберта – Мура

Рассмотрим источник с алфавитом А={a₁,a₂,…,a_n} и вероятностями p₁,…p_n. Пусть символы алфавита некоторым образом упорядочены, например, a₁≤a₂≤…≤a_n. Алфавитным называется код, в котором кодовые слова лексико-графически упорядочены, т.е. φ(a₁)≤φ(a₂)≤…≤φ(a_n).

Е.Н. Гилбертом и Э.Ф. Муром предложили метод построения алфавитного кода, для которого L_ср < H+2. Процесс построения происходит следующим образом.

1. Составим суммы Q_i, i=1,n, вычисленные следующим образом:

Q₁=p₁/2, Q₂=p₁+p₂/2, Q₃=p₁+p₂+p₃/2,…, Q_n=p₁+p₂+…+p_n-1+p_n/2.

2. Представим суммы Q_i в двоичном виде.

3. В качестве кодовых слов возьмем é-log₂p_iù +1 младших бит в двоичном представлении Q_i.

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице.

Таблица 13 Код Гилберта-Мура

Средняя длина кодового слова не превышает значения энтропии плюс 2

L_ср=4^.0.18+4^.0.18+3^.0.36+5^.0.07+5^.0.09+5^.0.12=3.92<2.37+2

16.6 Варианты заданий

1) Написать процедуры построения g-, w-кодов Элиаса для заданного натурального числа.

2) Запрограммировать процедуру кодирования и декодирования последовательности нулей и единиц методом кодирования длин серий.

3) Написать процедуру кодирования и декодирования последовательности символов заданным побуквенным префиксным кодом.

4) Запрограммировать процедуру, которая определяет является ли заданная схема побуквенного кодирования префиксной.

5) Для заданного набора длин кодовых слов написать процедуру построения побуквенного префиксного кода.

6) Написать процедуру кодирования текста на русском языке кодом Хаффмена. Определить степень сжатия этого кода.

7) Написать процедуру кодирования текста на русском языке кодом Фано. Определить степень сжатия этого кода. Сравнить средние длины кодовых слов кода Хаффмена и кода Фано.

8) Написать процедуру кодирования текста на русском языке кодом Шеннона. Определить степень сжатия этого кода. Сравнить средние длины кодовых слов кода Хаффмена и кода Шеннона.

9) Написать процедуру кодирования текста на русском языке кодом Гилберта-Мура. Определить степень сжатия этого кода. Сравнить средние длины кодовых слов кода Хаффмена и кода Гилберта-Мура.

10) Графически изобразить кодовое дерево заданного префиксного кода.

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1. Вирт Н. Алгоритмы и структуры данных. – М.: , 1989.

2. Кнут Д. Искусство программирования для ЭВМ, сортировка и поиск. – М.: Мир, 1978.

3. Ахо А., Ульман Дж., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. – М. Мир, 1979.

4. Марченко А.И., Марченко Л.А. Программирование в среде Turbo PASCAL 7.0. Базовый курс. Киев: «ВЕК+», 2003.

5. Березин Б.И., Березин С.Б. Начальный курс С и С++. М: «Диалог-МИФИ», 2001