Основные методы побуквенного кодирования

Пример 1 (побуквенный код Хаффмана)

Дан ансамбль независимых случайных величин \(X=\{x\}\)

x P(x)
a 0.35
b 0.2
c 0.15
d 0.1
e 0.1
f 0.1

Построить посимвольный код Хаффмана, сравнить ожидаемую длину кода с энтропией ансамбля.

Дерево Хаффмана имеет вид:

Тогда кодовые слова соответственно

x C(x)
a 00
b 10
c 010
d 011
e 110
f 111

Ожидаемая длина кода \[L = \sum_{x\in X} P(x) L[C(x)]\] \[L = 0.35\cdot2+0.2\cdot2+0.15\cdot3+0.1\cdot3+0.1\cdot3+0.1\cdot3 = 2.45\]

Энтропия ансамбля \[H(X) = -\sum_{x\in X} P(x) \log_2 P(x)\] \[\begin{align}H(X) = & - 0.35 \log_2 0.35 \\& - 0.2 \log_2 0.2 \\& - 0.15 \log_2 0.15 \\& - 0.1 \log_2 0.1 \\& - 0.1 \log_2 0.1 \\& - 0.1 \log_2 0.1 \\& \approx 2.402 \end{align} \]

Избыточность кода \(\approx 0.048\) бит.

Пример 2 (побуквенный код Шеннона)

Аналогично примеру 1, но построить код Шеннона.

Символы сортируются по убыванию вероятности, считается кумулятивная вероятность \(q(x_i) = q(x_{i-1}) + P(x_{i-1}),\) в качестве кода берутся \(l(x)=\left\lceil -\log_2 P(x) \right\rceil\) дробной части двоичного представления \(q_2(x)\)

x P(x) q(x) -log₂P(x) l(x) q₂(x) C(x)
a 0.35 0 ≈1.51 2 0.00.. 00
b 0.2 0.35 ≈2.32 3 0.010.. 010
c 0.15 0.55 ≈2.74 3 0.100.. 100
d 0.1 0.7 ≈3.32 4 0.1011.. 1011
e 0.1 0.8 ≈3.32 4 0.1100.. 1100
f 0.1 0.9 ≈3.32 4 0.1110.. 1110

Ожидаемая длина кода \(L = \sum P(x) l(x)\) \(= 2.95\)

Избыточность кода \(\approx 0.548\) бит.

Пример 3 (побуквенный код Шеннона-Фано)

Аналогично примеру 1, но построить код Шеннона-Фано.

Символы сортируются по убыванию вероятности, группируются на две группы с примерно равной суммарной вероятностью, одной из них присваивается 0, другой 1, каждая группа аналогично рекурсивно делится пока в группе не останется 1 символ.

x P(x)
a 0.35
b 0.2
c 0.15
d 0.1
e 0.1
f 0.1

Дерево Шеннона-Фано:

Коды

x C(x)
a 00
b 01
c 100
d 101
e 110
f 111

Ожидаемая длина кода здесь очевидно совпадает с ожидаемой длиной кода для алгоритма Хаффмана. В общем случае это не так.

Избыточность кода \(\approx 0.048\) бит.

Пример 4 (побуквенный код Элиаса)

Дан ансамбль

x P(x)
a 0.35
b 0.1
c 0.1
d 0.2
e 0.15
f 0.1

Построить код Элиаса, сравнить ожидаемую длину кода с энтропией источника.

Символы упорядочиваются произвольно. Каждому символу ставится в соответствие число \[F_i = \frac{p_i}{2} + \sum_{j=1}^{i-1} p_j.\]

Кодовым словом \(i\)-го символа выбираются первые \(l_i = \left\lceil -\log_2 p_i \right\rceil + 1\) дробных разрядов двоичного представления числа \(F_i\).

x P(x) F(x) -log₂P(x) l q₂(x) C(x)
a 0.35 0.175 ≈1.51 3 0.001.. 001
b 0.1 0.4 ≈3.32 5 0.01100.. 01100
c 0.1 0.5 ≈3.32 5 0.10000.. 10000
d 0.2 0.65 ≈2.32 4 0.1010.. 1010
e 0.15 0.825 ≈2.74 4 0.1101.. 1101
f 0.1 0.95 ≈3.32 5 0.11110.. 11110

Ожидаемая длина кода на 1 больше, чем у кода Шеннона, \(L = \sum P(x) l(x)\) \(= 3.95\).

Избыточность кода \(\approx 1.548\) бит.

Упражнение 1

Сравнить коды Хаффмана, Шеннона, Шеннона-Фано и Элиаса для ансамбля \(X=\{x\}\)

x P(x)
a 0.125
b 0.125
c 0.125
d 0.125
e 0.125
f 0.125
g 0.125
h 0.125

Упражнение 2

Для ансамбля \(X=\{0, 1\}\), \(P(0)=0.9\), \(P(1)=0.1\), рассмотрите производные ансамбли \(X^2 = \{00, 01, 10, 11\}\), \(P(00)=P(0)P(0) = 0.81\), \(P(01) = P(10) = P(0)P(1) = 0.09\), \(P(11) = P(1)^2 = 0.01\), \(X^3\) (строится аналогично). Постройте для них коды Хаффмана. Как меняется ожидаемая длина кода? Как меняется ожидаемая длина кода по сравнению с энтропией ансамбля? По сравнению с количеством бит в символе?

Пример 5

Закодируйте строку 000000000001000000000000 (11 нулей, единица, 12 нулей) используя базовый алгоритм Лемпеля-Зива

Начинаем со словарём, в котором с индексом 0 находится пустая строка (обозначенная здесь λ).

  1. λ

Первый символ исходной строки 0. Добавляем словарь символ 0 с префиксом λ. Первое число – индекс префикса в словаре, второе – символ после префикса. Для удобства через тире записана последовательность символов, которой соответствует запись в словаре.

  1. (0, 0) – 0

Второй символ исходной строки 0. Подстрока “0” уже есть в словаре (с индексом 1). Читаем следующий символ. Подстроки “00” нет в словаре. Добавим в словарь символ “0” с префиксом “0”:

  1. (1, 0) – 00

Далее действуя аналогично, заполняем прочие записи словаря:

  1. (2, 0) – 000
  2. (3, 0) – 0000
  3. (1, 1) – 01
  4. (4, 0) – 00000
  5. (6, 0) – 000000

Последний символ “0” можно записать, продублировав первую запись:

  1. (0, 0) – 0

В окончательном коде сохраняется индекс префикса и символ суффикса. При этом для записи индекса префикса используется минимально необходимое число бит, а именно \(\left\lceil \log_2 i \right\rceil,\) где \(i\) – индекс записи в словаре. Первая запись (пустая строка) не записывается. После тире указан код, соответствующий записи в словаре. Для удобства чтения код префикса и суффикс разделены апострофом

  1. (0, 0) – ’0
  2. (1, 0) – 1’0
  3. (2, 0) – 10’0
  4. (3, 0) – 11’0
  5. (1, 1) – 001’1
  6. (4, 0) – 100’0
  7. (6, 0) – 110’0
  8. (0, 0) – 000’0

Итоговый код таким образом

0101001100011100011000000

Пример 6

Строка 00101011101100100100011010101000011 – это некое сообщение, закодированное по базовому алгоритму Лемпеля-Зива. Декодируйте его.

Разделим закодированное сообщение на группы бит в соответствии с размером соответствующей записи в словаре, а именно по \(\left\lceil \log_2 i \right\rceil + 1\) бит, где \(i\) – индекс записи. Начинаем со словаря, содержащего пустую строку (λ) с индексом 0. Последний символ в группе – суффикс, первые кодируют индекс префикса. После тире в скобках указан индекс префикса и суффикс, после второго тире – часть исходного сообщения.

  1. λ
  2. 0 – (0, 0) – ’0
  3. 0’1 – (0, 1) – ’1
  4. 01’0 – (1, 0) – 0’0
  5. 11’1 – (3, 1) – 00’1
  6. 011’0 – (3, 0) – 00’0
  7. 010’0 – (2, 0) – 1’0
  8. 100’0 – (4, 0) – 001’0
  9. 110’1 – (6, 1) – 10’1
  10. 0101’0 – (5, 0) – 000’0
  11. 0001’1 – (1, 1) – 0’1

Итого исходное сообщение (группы исходных символов, соответствующие отдельным записям в словарях разделены пробелами):

0 1 00 001 000 10 0010 101 0000 01

Или подряд

0100001000100010101000001