Код Гильбера-Мура

Далее приведен алгоритм кодирования по методу Гильбера-Мура.

Инициализация. Сопоставим каждой букве кумулятивную вероятность и вычислим .

Цикл. Кодовым словом являются первые разрядов после запятой в двоичной записи числа .

Средняя длина кодового слова: .

Пример

Рассмотрим тот же пример. Только для наглядности изменим последовательность в ансамбле.

Построим код Гильбера-Мура:

Буква						Код
e	0.1	0.0	0.05		0.0000110011001100…
c	0.15	0.1	0.175		0.0010110011001100…
b	0.2	0.25	0.35		0.0101100110011001…
d	0.1	0.45	0.5		0.1000000000000000…
a	0.35	0.55	0.725		0.1011100110011001…
f	0.1	0.9	0.95		0.1111001100110011…

Средняя длина кодового слова , и избыточность данного неравномерного кода: . Кроме того, неравенство Крафта имеет вид строгого неравенства. Это означает, что в целом данный код хуже всех рассмотренных для данного примера. ●

 

Все рассмотренные методы побуквенного кодирования обладают следующими недостатками:

1. Необходимо иметь таблицу вероятностей символов входного сообщения. В случае, когда вероятности неизвестны (что чаще всего бывает), методы работают неэффективно.

2. Минимальная длина кодового слова не может быть меньше одного бита, тогда как энтропия сообщения может быть 0.1(бит/буква) или 0.01(бит/буква). В этом случае кодирование становится неэффективным.

3. Средняя длина кодового слова будет равна энтропии тогда и только тогда, когда все вероятности сообщений имеют вид: , где – целое положительное число.

Решение этих проблем:

1. Использовать адаптивные алгоритмы: дерево кода постоянно обновляется с прочтением очередного символа сообщения.

2. Использовать блоки символов, но тогда усложняется процесс кодирования/декодирования.