Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
Пусть объектом кодирования являются тексты, записанные на некотором (естественном или искусственном) языке, причем число букв в алфавите этого языка, включая (если есть такая необходимость) некоторые знаки препинания, знак пробела и т.п., равно п. Пусть далее, / - наименьшее натуральное число, удовлетворяющее условию / & Iog2K. Тогда можно пользоваться простейшим из различных методов побуквенного кодирования, сводящимся к установлению взаимно однозначного соответствия между различными буквами исходного текста и различными кодовыми наборами двоичных символов фиксированной
32 длины, равной /. Например, если речь идет о текстах, записанных на русском языке, где число букв алфавита, включая знак пробела, п = 34, то, поскольку имеет место неравенство 5 < log234 < 6, можно осуществить побуквенное кодирование, установив следующее соответствие:
Буква русского Шестисимвольный Десятичная
языка кодовый набор запись (пробел) 000000 0 а 000001 1 б 000010 2
л 001101 13
100001 33
111111 63
Декодирование при этом осуществляется очень просто: последовательность двоичных символов - закодированный текст - делится на блоки из шести символов и каждый блок заменяется соответствующей буквой алфавита исходного текста. Невооруженным глазом видно, что, будучи очень привлекательным по своей простоте, рассмотренный метод кодирования грешит определенной "расточительностью" (избыточностью). Об этом свидетельствует хотя бы то обстоятельство, что шестью двоичными символами мы смогли бы выразить не п = 34, а целых /; = 26 = 64 букв алфавита. Чтобы улучшить положение, можно было, например, пойти на некоторую уступку, а именно, согласиться с тем, чтобы при кодировании и декодировании текстов пары букв "е"-"ё" и "ь"-"ъ" оказались "неразличимыми". Ведь люди, владеющие русским языком, все равно смогли бы восстановить это различие при работе с уже декодированным текстом. При наличии такого согласия число букв в алфавите русского языка (включая знак пробела) оказалось бы равным п = 32, и поэтому можно было бы обойтись кодовыми наборами постоянной длины, равной / = Iog2 32 = 5. Тем самым, из каждых шести двоичных символов один символ можно было сэкономить. Из этого примера легко сделать вывод, что при побуквенном кодировании букв исходного текста кодовыми наборами постоянной длины наиболее компактное (экономное) кодирование удается осуществить тогда, когда число букв в алфавите можно представить как целую степень двойки:
п = 2'(/ = 1, 2, ...,). <2Л)
Нарушение этого условия при указанном методе кодирования непременно приводит к некоторой избыточности. Возникает вопрос, а имеются ли резервы для дальнейшего сокращения среднего числа двоичных символов, отводимых под одну букву? Оказывается, что такие резервы имеются, и даже тогда, когда п удовлетворяет условию (2.1), возможны варианты, когда кодирование можно осуществить таким
33
ГЛАВА 1 образом, чтобы среднее число двоичных символов, отводимых под одну букву, оказалось меньше / = Iog2 п.
Пусть алфавит исходного текста состоит из восьми букв А, В, С, D, Е, F, G, Н. Поскольку /г = 8 = 2і, т.е. / = Iog2 п = 3, то при рассмотренном только что методе кодирования каждой букве ставился бы в соответствие кодовый набор постоянной длины, равной трем.
Пусть нам известны значения вероятностей того, что наугад взятая буква из текстов этого языка окажется буквой А, В, С, D, Е, F, G пли Н:
С учетом неравновероятности встречаемости различных букв алфавита представляется естественным отказаться от постоянства длины кодовых наборов и стараться осуществить такое кодирование, при котором наиболее часто встречающиеся буквы были бы закодированы возможно более короткими кодовыми наборами и, наоборот, наибольшую длину имели бы кодовые наборы, соответствующие наименее часто встречающимся буквам. В русле этих соображений специалистами были разработаны различные методы побуквенного кодирования.
В связи с переходом к переменной длине кодовых наборов возникает проблема установления границ между ними при декодировании. При этом крайне нежелательно, чтобы для установления границ были использованы какие-либо специальные разделительные символы, так как это привело бы к увеличению средней длины кодовых наборов. Коды (схемы, алгоритмы кодирования), где однозначность декодирования достигается без помощи каких-либо специальных разделительных символов. называются кодами без запятой. Среди них наиболее простыми и в то же время наиболее популярными являются так называемые префиксные коды, обладающие тем свойством, что кодовый набор ни одной буквы не является началом (префиксом) кодового набора другой буквы.
Пусть п - число букв в алфавите, іц- число букв, кодовые наборы которых состоят из к двоичных СИМВОЛОВ, Ii - число двоичных символов в кодовом наборе /-й буквы алфавита, L = max (Ij).
Тогда, очевидно, « = X "t-> а Для произвольного фиксированного
значения к имеет место пк =? 2к. Если же нам заданы значения п],п7,...,пк_], то, очевидно, будет иметь место неравенство
р (А) = 0,08 р (В) = 0,44 р (С) = 0,08 р (D) = 0,08
