Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
Формируется первый (к = 1) столбик, где все буквы алфавита записываются в порядке убывания значений вероятностей их встречаемости в исходном, подлежащем кодированию тексте. Здесь же. напротив каждой буквы, пишется соответствующее ей значение вероятности. Две буквы, занявшие в столбике предпоследнюю и последнюю иозиции, с левой стороны снизу отмечаются двоичными символами соответственно "О" и "1". На рис. 2.2 эти буквы отделены от других пунктирными линиями.
2) При известном к-м столбике строится (к + 1)-й столбик по тому же принципу, что и предыдущий, с той лишь разницей, что буквы, отмеченные в предыдущем столбике двоичными символами, в последующем столбике отсутствуют. В новом столбике их "представляет" одна составная буква со значением вероятности, равным сумме вероятностей слагаемых букв.
3) Этот процесс продолжается до тех пор, пока в очередном столбике под номером к = п (число букв в алфавите) не окажется одна-единственная составная буква, "представляющая" весь алфавит исходного текста со значением вероятности, равным единице. Этот последний столбик выполняет лишь контрольную функцию.
4) Для определения кодового набора, соответствующего интересующей нас букве, поступаем следующим образом.
Начиная с последнего столбика, переходя поочередно к предыдущим столбикам, рассматриваем каждый раз только те буквы, которые занимают в очередных столбиках последние два места (участки ниже пунктирных линий). Если в указанном участке очередного столбика оказывается интересующая нас буква или какая-либо составная буква, включающая эту букву, то в очередном разряде ее кодового набора записываем двоичный символ, которым отмечена эта буква или включающая ее составная буква. Этот процесс продолжаем до тех пор. пока в очередном столбике, ниже пунктирной линии, не встретится интересующая нас буква в сольном варианте (не в составе какой-либо составной буквы).
Проследим, например, за получением кодового набора, соответствующего букве Е. При движении от столбика с номером к - 8 к столбику с номером к = 7, в нем ниже пунктирной линии обнаруживаем составную букву o(ACDEFGH), содержащую букву Е. Это дает основание для записи в первом разряде кодового набора буквы E символа "О", которым отмечена составная буква (I(ACDEFGH). В следующий раз ниже пунктирной линии буква E встречается в составной букве (,(EFGH) в столбике под номером к - 6. поэтому во второй позиции кодового
38 к= I
В 0,44
А 0,08
С 0,08
D 0,08
E 0,08
F 0,08
(,G 0,08
ІН 0,08
к = 2
В 0,44
(GH) 0,16
А 0,08
С 0,08
D 0,08
i? 0,08
lF 0,08
к = 3
В 0,44
(GH) 0,16
(EF) 0,16
А 0,08
<>с 0,08
,D 0,08
к = А
В 0,44
(GH) 0,16
(EF) 0,16
o(CD) 0,16
lA 0,08
-----1 «і її
В 0,44
(ACD) 0,24
O(GH) 0,16
I(EF) 0,16
к = Ь
В 0,44
o(EFGH) 0,32
i(ACD) 0,24
к = 1
o(ACDEFGH) 0,56 ,В 0,44
к = 8
(ABCDEFGH) 1,00
Рис. 2.2. Схема посимвольного кодирования по Д. Хаффмэну
набора буквы E записываем символ "0". Ниже пунктирной линии буква E встречается также в пятом столбике, в составной букве |(EF), что дает основание для того, чтобы в третьей позиции буквы E записать символ "1". Далее буква (|Е ниже пунктирной линии и уже в сольном варианте встречается во втором столбике. Исходя из этого, четвертую позицию кодового набора заполняем символом "0" и на этом останавливаемся, т.е. в итоге букве E приписываем кодовый набор 0010. Поступая аналогичным образом, получим кодовые наборы, соответствующие остальным буквам алфавита:
Вуква Двоичный код Ьуква Двоичный код
А 011 E 0010
В 1 F 001 1
С 0100 G 0000
D 0101 H 0001
39
ГЛАВА 1 Среднее число двоичных символов, отводимых под одну букву исходного алфавита, здесь получается равным / = 2,6 = /min (против / = 2,8 при схеме Р. Фано), что свидетельствует о том, что код Р. Фано хотя и экономный, но не оптимальный, так как, в отличие от схемы Д. Хаффмэна, схема кодирования по Р. Фано не всегда обеспечивает наименьшую возможную среднюю длину кодовых наборов.
Обе эти схемы ориентированы на то, чтобы ценою удлинения кодовых наборов менее вероятных букв достичь уменьшения длин кодовых наборов более вероятных букв. С этой задачей в общем-то справляются обе схемы кодирования, и поэтому с их помощью удается уменьшить среднее число двоичных символов, приходящихся на одну букву. Для того же, чтобы достичь наименыцую возможную средней длины кодового набора, требуется нечто большее, более тонкий механизм кодирования, нежели схема Р. Фано. Что же касается схемы Д. Хаффмэна, то в [1], например, приведено чрезвычайно простое и вместе с тем достаточно строгое доказательство того, что при любом наборе значений вероятностей эта схема обеспечивает наименьшую возможную при побуквенном кодировании среднюю длину кодовых наборов. В рассматриваемом смысле предложенная Д. Хаффмэном схема кодирования является оптимальной.
Следует особо подчеркнуть, что из оптимальности схемы Д. Хаффмэна вовсе не следует единственность варианта достижения этого оптимума. Рассмотрим, например, кодирование букв А, В, С, D и E при следующих значениях вероятностей их встречаемости:
