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

Вернемся к дилемме рационального кодировки. Пока лучший итог (меньшая избыточность) был получен при кодировке по способу Хаффмана — для российского алфавита избыточность оказалась наименее 1%. При всем этом указывалось, что код Хаффмана сделать лучше нереально. На 1-ый взор это противоречит первой аксиоме Шеннона, утверждающей, что всегда можно предложить метод кодировки, при котором избыточность будет сколь угодно малой величиной. По сути это противоречие появилось из-за того, что до сего времени мы ограничивали себя алфавитным кодировкой. При алфавитном кодировке передаваемое сообщение представляет собой последовательность кодов отдельных символов первичного алфавита. Но вероятны варианты кодировки, при которых кодовый символ относится сходу к нескольким буковкам первичного алфавита (будем именовать такую комбинацию блоком) либо даже к целому слову первичного языка. Кодирование блоков понижает избыточность. В этом просто убедиться на ординарном примере.

Пусть имеется словарь некого языка, содержащий п = 16000 слов (это, непременно, более чем приличный словарный припас!). Поставим в соответствие каждому слову равномерный двоичный код. Разумеется, длина кода может быть найдена из соотношения К(А,2) ≥ log₂n ≥ 13,97 = 14. Как следует, каждое слово кодируется композицией из 14 нулей и единиц — получатся собственного рода двоичные иероглифы. К примеру, пусть слову «ИНФОРМАТИКА» соответствует код 10101011100110, слову «НАУКА» — 00000000000001, а слову «ИНТЕРЕСНАЯ» —00100000000010; тогда последовательность: разумеется, будет означать «ИНФОРМАТИКА Увлекательная НАУКА».

Просто оценить, что при средней длине российского слова K^(r) = 6,3 буковкы (5,3 буковкы + пробел меж словами) средняя информация на символ первичного алфавита оказывается равной I^(A) = К(А,2)/ K^(r) = 14/6,3 = 2,222 бит, что более чем в 2 раза меньше, чем 5 бит при равномерном алфавитном кодировке. Для британского языка таковой способ кодировки дает 2,545 бит на символ. Таким образом, кодирование слов оказывается более прибыльным, чем алфавитное.

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

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