Вернемся к проблеме оптимального кодирования. Пока что наилучший результат (наименьшая избыточность) был получен при кодировании по методу Хаффмана - для русского алфавита избыточность оказалась менее 1%. При этом указывалось, что код Хаффмана улучшить невозможно.
На первый взгляд это противоречит первой теореме Шеннона, утверждающей, что всегда можно предложить способ кодирования, при котором избыточность будет сколь угодно малой величиной. На самом деле это противоречие возникло из-за того, что до сих пор мы ограничивали себя алфавитным кодированием.
При алфавитном кодировании передаваемое сообщение представляет собой последовательность кодов отдельных знаков первичного алфавита. Однако возможны варианты кодирования, при которых кодовый знак относится сразу к нескольким буквам первичного алфавита (будем называть такую комбинацию блоком) или даже к целому слову первичного языка. Кодирование блоков понижает избыточность. В этом легко убедиться на простом примере.
Пусть имеется словарь некоторого языка, содержащий %%n = 16000%% слов (это, безусловно, более чем солидный словарный запас!). Поставим в соответствие каждому слову равномерный двоичный код. Очевидно, длина кода может быть найдена из соотношения %%К(A,2) ≥ log_2n ≥ 13,97 = 14%%. Следовательно, каждое слово кодируется комбинацией из 14 нулей и единиц - получатся своего рода двоичные иероглифы. Например, пусть слову «ИНФОРМАТИКА» соответствует код 10101011100110, слову «НАУКА» - 00000000000001, а слову «ИНТЕРЕСНАЯ» -00100000000010; тогда последовательность:
000000000000110101011100110000000000000001
очевидно, будет означать «ИНФОРМАТИКА ИНТЕРЕСНАЯ НАУКА».
Легко оценить, что при средней длине русского слова %%K(r) = 6,3%% буквы (5,3 буквы + пробел между словами) средняя информация на знак первичного алфавита оказывается равной %%I(A) = \frac{K(A,2)}{ K(r)} = \frac{14}{6,3} = 2,222%% бит, что более чем в 2 раза меньше, чем 5 бит при равномерном алфавитном кодировании. Для английского языка такой метод кодирования дает 2,545 бит на знак. Таким образом, кодирование слов оказывается более выгодным, чем алфавитное.
Еще более эффективным окажется кодирование в том случае, если сначала установить относительную частоту появления различных слов в текстах и затем использовать код Хаффмана. Подобные исследования провел в свое время Шеннон: по относительным частотам 8727 наиболее употребительных в английском языке слов он установил, что средняя информация на знак первичного алфавита оказывается равной 2,15 бит.
Вместо слов можно кодировать сочетания букв - блоки. В принципе блоки можно считать словами равной длины, не имеющими, однако, смыслового содержания. Удлиняя блоки и применяя код Хаффмана теоретически можно добиться того, что средняя информация на знак кода будет сколь угодно приближаться к %%I_∞%%.
Пример. Пусть первичный алфавит состоит из двух знаков а и b с вероятностями, соответственно, 0,75 и 0,25. Сравнить избыточность кода Хаффмана при алфавитном и блочном двухбуквенном кодировании.
При алфавитном кодировании:
| знак | %%p_i%% | Код |
|---|---|---|
| a | 0.75 | 0 |
| b | 0.25 | 1 |
$$I(А) = 0,811, K(A,2) = 1, Q(A,2) = 0,233$$
При блочном двухбуквенном кодировании (очевидно, %%p_{ij}= p_i \cdot p_j%%):
| знак | %%p_i%% | Код |
|---|---|---|
| aa | 0.562 | 0 |
| ab | 0.188 | 11 |
| ba | 0.188 | 100 |
| bb | 0.062 | 101 |
%%I(А) = 1,623%% (в пересчете на 1 знак - 0,811), %%K(A,2) = 1,688%% (в пересчете на знак - 0,844), %%Q(A,2) = 0,040.%%
Таким образом, блочное кодирование обеспечивает построение более оптимального кода, чем алфавитное. При использовании блоков большей длины (трехбуквенных и более) избыточность стремится к 0 в полном соответствии с первой теоремой Шеннона.
| Равномерное алфавитное двоичное кодирование. Байтовый код | Проверка знаний: Кодирование символьной информации |