Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
р (E) = 0,08 р (F) = 0,08 р (G) = 0,08 р (H) = 0,08
L
к = 1
"^2^-2/^,-24-2- - - 2*-'/;,,
т.е.
і Hj =? 2*,
34 или, после деления обеих частей неравенства на 2к,
І 2"'н,.«1.
; = 1
Поскольку выбор значения к произвольный, то примем к = L. и тогда будем иметь:
і
./=I
Отсюда непосредственно следует
і 2"'' - 1. (2.2) /=1
Неравенство (2.2) называется неравенством Крафта и имеет ключевое значение в теории кодирования. Хотя вывод этого неравенства мы осуществили применительно к двоичному префиксному коду, оно верно также для произвольного (не обязательно двоичного и не обязательно префиксного) кода без запятой.
Неравенство Крафта, собственно, и лимитирует наше желание оперировать как можно меньшими значениями Ii. Пусть, например. п = 10 и уже известны значения /) =2, /->=/,=...=/h = 3. Тогда, очевидно, значения I1 -н/10 должны удовлетворить неравенству
10 / - і ) Y 2 ' « 1 -2^ -5-2^ =-.
7 8
Пусть, например, мы хотим, чтобы имело место I1 = /8 = /9 = /|0 = /.
Тогда получим, что значение / должно удовлетворить неравенству 4 ¦ 2'1 =? 1/8, т.е. оно не может быть меньше пяти.
Префиксный код называется полным, если добавление к нему любого нового кодового набора нарушает свойство префиксности. Пусть, например, буквам А, В и С поставлены в соответствии кодовые наборы 00, 01 и 1. Тогда очевидно, что любая попытка закодировать еще хоть одну букву привела бы к нарушению свойства префиксности. Значит, код 00, 01, 1 является полным. Если же буквам А, В и С были поставлены в соответствие кодовые наборы 00, 01 и 10, то через ветвь 11... мы смогли бы, не нарушая свойство префиксности, закодировать сколько угодно новых букв. Мы также смогли бы без нарушения свойства префиксности через ветвь 01... закодировать сколько угодно новых букв, если бы буквам А, В и С были поставлены в соответствие кодовые наборы 000, 001 и 1. Значит, коды 00, 01, 10 и 000, 001, 1 являются неполными. Для полных префиксных кодов и только для них неравенство Крафта превращается в равенство. Естественно, что на
35
ГЛАВА 1 практике наибольший интерес представляют полные коды, так как при прочих равных условиях средняя длина кодовых наборов у полных кодов получается меньше, чем у неполных.
Перейдем к рассмотрению двух полных префиксных кодов, представляющих большой практический интерес.
р 1 СХЕМА ДВОИЧНОГО КОДИРОВАНИЯ ТЕКСТОВ ПО Р. ФАНО
Предложенная американским специалистом Р. Фано схема двоичного кодирования сводится к выполнению следующих операций.
1) Составить список букв алфавита (исходное множество букв) в порядке убывания значений соответствующих им вероятностей.
2) Разбить этот список на два подсписка (подмножества букв) таким образом, чтобы значения вероятностей того, что наугад взятая из рассматриваемого текста буква окажется в первом или во втором из этих подмножеств, были бы по возможности близки.
3) Приписать произвольному одному из этих подмножеств (подсписков) символ "О", а другому - "1".
4) Рассматривая каждое из этих подмножеств (подсписков) как исходное, применительно к каждому из них осуществить операции, указанные в пунктах (2) и (3).
5) Этот процесс продолжать до тех пор, пока в каждом из очередных подмножеств не окажется по одной букве.
6) Каждой букве приписать двоичный код, состоящий из последовательности нулей и единиц, встречающихся на пути из исходного множества букв ко множеству, состоящему из одной этой буквы.
Пользуясь схемой Р. Фано (см. рис. 2.1) применительно к приведенному выше примеру, легко установить наборы двоичных символов, соответствующие буквам исходного текста:
Буква Двоичный код Буква Двоичный код
А 00 E 1011
В 01 F 110
С 100 G 1110
D 1010 H 1111
Если обозначить через Lk-2, Lb =3, Lc=S,... числа двоичных символов в кодовых наборах, соответствующих буквам А, В, С, ..., то среднее число двоичных символов, отводимых под одну букву исходного алфавита, можно определить по формуле
/ = P(A)Ia + р(В)1в+.. .+P(H)Ih = 2,8.
Таким образом, с переходом к переменной длине кодовых наборов, отводимых под каждую букву исходного текста, удается на 7% (2,80
36 Рис. 2.1. Схема посимвольного кодирования по Р. Фано
вместо трех символов на одну букву) сократить число двоичных символов в закодированном тексте. Правда, это связано с некоторым усложнением процедур кодирования и декодирования. Будучи достаточно эффективной, схема кодирования. Р. Фано не всегда гарантирует, что при заданном наборе значений вероятностей средняя длина кодовых наборов / окажется наименьшей возможной. Такую гарантию дает другая схема кодирования, предложенная американским математиком Д. Хаффмэном. Исходные соображения здесь те же, что и при рассмотрении схемы Р. Фано, однако, оперируя более тонким механизмом кодирования, Д. Хаффмэну удалось достичь наименьшего возможного при побуквенном кодировании значения средней длины кодовых наборов.
37
ГЛАВА 1 СХЕМА ДВОИЧНОГО КОДИРОВАНИЯ ТЕКСТОВ ПО Д. ХАФФМЭНУ
Предложенная Д. Хаффмэном схема кодирования заключается в следующем (см. рис. 2.2).
