Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Коды Голомба

Код Голомба неотрицательного целого числа п [Golomb 66] может быть эффективным кодом Хаффмана. Этот код зависит от выбора некоторого параметра Ь. Прежде всего необходимо вычислить две величины q — \р-^\ , r — п qb — 1 (где выражение \х\ обозначает округление х), а затем построить код из двух частей; первая часть -это число д, закодированное с помощью унарного кода (см. стр. 195), а вторая - двоичное выражение для г, состоящее из [log2b\ бит (для малых остатков) или из [log2b~\ бит (для больших). Если взять 6 = 3, то три возможных остатка 0, 1 и 2 будут кодироваться как 0, 10 и 11. Выбрав 6 = 5, получаем 5 остатков от 0 до 4, которые кодируются как 00, 01, 100, 101 и 110. В табл. 3.60 приведены некоторые коды Голомба при b = 3 и b = 5.

п 1 2 3 4 5 67 8 9 10

6 = 3 I 0|0 0|10 0|11 10|0 10|10 10|11 110|0 110|10 110|11 1110|0 6 = 5 0|00 0(01 0|100 0|101 10|110 10|00 10(01 10|100 10(101 110(110

Табл. 3.60. Некоторые коды Голомба при 6 = 3и6 = 5.

Предположим, что входной поток данных состоит из целых чисел, причем вероятность числа п равна Р(п) — (1 — р)п~1р. Здесь р - некоторый параметр, 0 < р < 1. Можно показать, что коды Голомба будут оптимальными кодами для этого потока данных, если b выбрать из условия

(1 - р)ь+ (1 - p)b+1< К (1 - р)6-] + (1 - р)ь.

Имея такие данные на входе, легко породить наилучшие коды переменной длины, не прибегая к алгоритму Хаффмана.

Похожие материалы