Блочное двоичное кодирование

Из всех способов алфавитного кодирования самым оптимальным оказался метод Хаффмана. Для русского алфавита избыточность оказалась менее 1%. При этом указывалось, что код Хаффмана улучшить невозможно.

При алфавитном кодировании передаваемое сообщение представляет собой последовательность кодов отдельных знаков первичного алфавита. Однако возможны варианты кодирования, при которых кодовый знак относится сразу к нескольким буквам первичного алфавита (такую комбинацию называют блоком) или даже к целому слову первичного языка. Кодирование блоков понижает избыточность.

Пусть имеется словарь некоторого языка, содержащий n = 16000 слов. Если поставить в соответствие каждому слову равномерный двоичный код, то, длина кода K(2) log2n 13,97 = 14. Следовательно, каждому слову будет поставлена в соответствие комбинация из 14 нулей и единиц.

При средней длине русского слова K(r) = 6,3 буквы (5,3 буквы + пробел между словами) средняя информация на знак первичного алфавита оказывается равной

, что почти в 2 раза меньше, чем 4,395 бит при алфавитном кодировании.

Для английского языка такой метод кодирования дает 2,545 бит на знак.

Таким образом, кодирование слов оказывается более выгодным, чем алфавитное.

Еще более эффективным окажется кодирование в том случае, если сначала установить относительную частоту появления различных слов в текстах и затем использовать код Хаффмана. Подобные исследования провел в свое время Шеннон: по относительным частотам 8727 наиболее употребительных в английском языке слов он установил, что средняя информация на знак первичного алфавита оказывается равной 2,15 бит.

Вместо слов можно кодировать сочетания букв – блоки. В принципе блоки можно считать словами равной длины, не имеющими, однако, смыслового содержания. Удлиняя блоки и применяя код Хаффмана теоретически можно добиться того, что средняя информация на знак кода будет сколь угодно приближаться к .

Однако, несмотря на кажущиеся преимущества, применение блочного и словесного метода кодирования имеет свои недостатки:

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

2. помимо основных слов разговорный язык содержит много производных от них, например, падежи существительных в русском языке или глагольные формы в английском; в данном способе кодирования им всем нужно присвоить свои коды, что приведет к увеличению кодовой таблицы еще в несколько раз;

3. возникает проблема согласования (стандартизации) этих громадных таблиц, что является непростой задачей;

4. алфавитное кодирование имеет то преимущество, что буквами можно закодировать любое слово, а при кодировании слов – можно использовать только имеющийся словарный запас.

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