В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 145
Текст из файла (страница 145)
Будем считать каждый символ листовым узлом создаваемого д дерева. Объединим два узла с минимальной вероятностью в узел, вероятность катар торого равна сумме двух соответствующих вероятностей. На каждом шаге будем повторять этот процесс до тех пор, пока не останется только олин узел. В результате мы получим дерево„в котором у каждого узла, кроме корневого, одна ветвь отходит направо и две налево. На каждом узле пометим две левые ветви символами 0 и 1 соответственно. Для каждого символа кодовое слово представляет собой строку меток от корневого узла к исходному символу.
Все получившиеся в результате кодовые слова показаны в левой части рисунка. Для примера процесс построения кодового слова для символа х1 обозначен жирной линией. 0'512 0'512 0'5120! 1,0 0'232 0'2 0 О'488 ,12,232 0 х! 0,512 — — 0,512 — -0,512 — 0,512 100 хх 0,128 0,128 — -0,128 — -0,1 101 хз 0,128 — 0,128 0,128 — — 0,1 110 х6 0,128 — 0,128 0,128 — — 0,1 ,12 11100 хз 0,032 0,04,064 01 0,1 Ы1О1 х О, 0,03,04 11110 х, О, 0,03 11111 х, О, Рие. 19.3. Кад Хаффмана с восемью символами В табл. 19.1 приведены свойства кода Хаффмана для данного примера. Средняя длина кодового слова представляет собой вычисляемую следующим образом ожидаемую величину: Е!ь] = ~ Е., Р; = 2,184.
Здесь 64 представляет собой длину 1-го кодового слова. Таким образом, напри- мер, для сообщений, состоящих нз 1000 символов, средняя длина кодированного / сообщения равна 2184 бит. При простом надирова!!ии каждого символа тремя би- тами длина этого сообщения будет составлять 3000 бит. Таблице 19.1. Коды Хаффмана для восьми символов с л к д и, ь, Р,ь, 1ед(1/Р,) ю,ю911/Р,) Х6 х4 х6 Энтропия и эффективность кодирования Рассмотрим случайную переменную с множеством возможных значений (х1, хь ..., Гцх), принимаемых с вероятностями (Рь Рь ..., Рл), где Р1 означает вероятность резуль- тата аь Определим нижнюю границу средней длины кода. Из формулы (19.1) иы знаем, что мерой информации для х; является !08(1/Р).
Поэтому в идеальном слу- чае мы сможем представить значение х1 кодовым словом длины Ь, = !08(1/Р) бит. Однако в большинстве случаев !ой(1/Р) не является целым числом, и лучшее, что мы можем сделать, — это выбрать ближайшее целое число 16 такое что !ой (1/Р1) < Ь1 < !08 (1/Р;) + 1. (19.3) Умножая на Р1 и суммируя по всем кодовым словам с помощью формулы (19.2), получаем: и Ф Ю х 1! Р!ой(1/Р) < 1! РХ,. < ~~6 Р!ой(1/Р) + 1! Р,, 4=! 4=! !=! 1=! Н(Х) < ЕЩ < Н(Х) + 1. Таким образом, оптимальный код позволяет получить среднюю длину кола, не более чем на 1 бит превосходящую энтропию оригинального набора символов.
Таким образом, энтропия случайной переменной Х может интерпретироваться как минимальное среднее число битов, необходимых для отображения одного значения Х Можно показать, что код Хаффмана удовлетворяет данному неравенству. Пример приводится в табл. 19.1.
Средняя длина кода составляет 2,184, а энтропия равна 2,187. Обратите внимание на то, что не все отдельные кодовые слова удовлетворяют неравенству (19В). Однако в среднем зто неравенство выполняется. Характеристики кода Хаффмана Два наблюдения, касающиеся кода Хаффмана, позволяют понять принципы раба ты алгоритмов сжатия данных. Эти наблюдения относятся к объединению симво- лов и использованию зависимостей. 0 100 101 110 11100 11101 11110 11111 0,512 1 0,512 0,128 3 0,384 0128 3 0384 0,128 3 0,384 0,032 5 0,16 0,032 5 0,16 0,032 5 0,16 0,008 5 0,04 Средняя длина = 2,164 0,966 0,494 2,966 0,38 2,966 0,38 2,966 0,38 4,966 0.159 4,966 0,159 4,966 0,159 6,966 0,056 Энтралия = 2,176 626 Глава 19. Теоретические основы сжатия данных 19.2.
Кодирование 627 Объединение символов Предположим, что у нас есть источник, генерирующий символы из алфавн Х, авнта состоящего всего из двух символов А и В, встречаю!цихся с вероятностью 0,8 0 2 ю, и Энтропия при такой схеме составляет 0,8 »ой(1,25) + 0,2 »ой(5) = 0,722 (см. рис. 19 2).
Но лучшее„что можно сделать в данном случае, — это использовать по одн б о одному иту для каждого кодового слова (например, А = О, В = 1). Если определить эффективность кода как отношение энтропии источника (среднее число битов информаци о мациивсимволе) к средней длине кодового слова (среднее число битов, используемых для кодирования одного символа), тогда эффективность этого кода будет равна 0,722, Эффективность кода можно повысить, если объединить символы в блоки и кодировать эти блоки символов. Например, если мы будем кодировать по два символа одновременно, тогда можно рассматривать полученные в результате блоки символов как новый алфавит У, состоящий из четырех символов (АА, АВ, ВА, ВВ), Если символы алфавита Х следуют в сообщениях независимо друг от друга, тогда вероятности, с которыми в них встречаются символы алфавита У, буд а, удут равны; Ррл = 0 64; Рлв = О 16; Раз= 0 16»Рвв = 0 04.
Нарис. 194, с показан код Хаффмана для такого варианта объединения символов в блоки„а в верхней части табл. 19.2 — статистика этого кода. В результате мы получаем код со средней длиной 1,56 при энтропии, равной 1,444, таким образом, эффективность кода составляет 0,926, что значительно лучше, чем при кодировании исходных символов без группировки. Обратите внимание на то, что информация источника не изменилась. Энтропия случайной переменной Х равна 0,722, а энтропия У равна 0,722 ° 2 = 1,444, то есть все также по 0,722 бита на символ. Еще лучших результатов можно достичь, объединив символы по трп. В этом случае мы получим вероятности, показанные в табл.
19.1. То есть Р = 0,8 ° 0,8 ° 0,8 = АЬЛ = = 0,512; РААв = 0,8 ° 0,8 0,2 = 0,128 и т. д. В данном случае эффективность кода составит 2,167/2,128 = 0,992. Энтропия все также будет составлять 0,722 бит на символ (2,167/8). 0 АА 0,64 — 0,64 — 0,64 О 1,0 11 АВ 0,16 0,2 0,36~ 100 ВА 0,16 0,16 101 ВВ 0,04 0 АА 0,72 — 0,72 — 0,72 0 1,0 0,16 0,28~ 100 АВ 0,08 0,12 101 ВА 0,08 Рнс. 19.4.
Код Хаффмана с четырьмя символами Таблица 19.2. Коды Хаффмана для четырех символов Символ Код Р, Ц Р,ь, "'91 7 9 независимые символы АА 0 0,64 ! 0,64 АВ 11 016 2 032 ! ВА 100 016 3 048 ВВ 101 0,04 3 0,12 Средняя длина = 1 ББ Зависимые символы АА 0 0,72 ! 0,72 ВВ 11 0,12 2 0,24 АВ 100 0,08 3 0.24 ВА 101 0,08 3 0,24 Средняя длина = 1,44 Зависимость символов не учнтываетсл АА 0 0,72 1 0,72 АВ И 008 г ОТБ ВА 100 0.08 3 0,24 ВВ 101 0,12 3 0,36 Средн ад на= 1,48 0,644 0,41 2 2,644 0,423 2,644 0,423 4,644 0,186 Энтропия = 1,444 0,474 0,341 3,069 0,367 3,644 0,292 3,644 0,292 Энтропия = 1,292 Н(Х) « — Н(Х) + —. 8!ь1 1 К К Таким образом, среднее количество битов на одно значение случайной переменной Х можно сделать сколь угодно близким к энтропии, выбирая все большие размеры блоков. Переходные аависимости В предыдуп!ем пункте предполагалось, что следующий символ в последовательности не зависит от предыдущего символа. Однако если такая зависимость су!цествует, тогда вероят!!ости, связанные с блоками символов, меняются.
Например, рассмотрим снова алфавит Х из двух символов и предположим, что к нему применимы следующие переходные вероятноспг. А В А 0,9 0,1 В 0,4 0,6 Таким образом, вероятность того„что за символом А последует символ А, равна 0,9; вероятность того, что за символом В последует символ А, равна 0,1 и т.
д. Несложно доказать непротиворечивость матрицы переходов при вероятностях появления отдельных символов А и В, равных 0,8 и 0,2 соответственно. Можно показатгч что эффективность оптимального кола для независимых последовательностей символов может быть повышена путем объединения символов, как это было показано ранее. Для блока из К символов мы получим следующее соотношение: 628 Глава 19. Теоретические основы сжатия данных 19.4. Задания 629 Теперь разработаем код для алфавита У, составленного на комбинаций этих символов по два.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
