В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 144
Текст из файла (страница 144)
Этот результат могкно обобщить для случайной переменной с И результатами. Энтропия случайной переменной будет максимальна, когда все результаты равновероятны: игах Н (Рь Ръ --, Ря) = Н(1/И, 1/И, ..., 1/И). Например, Н(1/3, 1/3, 1/3) = 1/3 !083+ 1/3 !083+ 1/3!083 = 1,585, тогда как Н (1/2, 1/3, 1/6) = 1/2 !ой 2 + 1/3 !ой 3 + 1/6 !ой 6 = 0,5 + 0,528 + 0,43 = 1,458, я 0 о О,Б $ й„ я В ог 0,2 О,О О,З 0,4 0,0 0,6 0,7 0,0 О,В 1,0 Вероятность первого результата Р Рис. 19.2. Функция энтропии для случайной переменной с двумя значениями 'С со .Ф !е - * ., л~» при Р = 0 равно О, тзк кзк в прелеяе Н(Л) стрелгнтся к 0 при значении Р с!психо!ел!ел к О.
( Свойства функции энтропии Мы разработали формулу энтропии Н(Х) путем интуитивно понятных рассуждений. Другой метод заключается в том, чтобы определить свойства, которыми долж- ~ на обладать функция энтропии, а затем доказать, что формула ! — ~ Р,. !08Р,. ! является единственной формулой, обладаюшей данными свойствами. Эти своиства„или аксиомы, можно сформулировать следуюшим образом: + Функция Н непрерывна на всем диапазоне вероятностей. Это значит, что небольшие изменения вероятности одного из событий вызывают небольшие изменения неуверенности. Это требование кажется рэаумным.
+ Если существует Иравновсроятных результатов, то есть Р! = 1/И, тогда Н(Х) является монотонно возрастаюгцей функцией И. Это свойство также разумно, так как оно утверждает, что чел! больше равновероятиых результатов, тем выше неуверенность. 4 Если сгруппировать некоторые результаты случайной переменной Х, тогда энтропию Н можно выразить как следующую взвешенную сумму энтропий; ! г Н(Р! )г Рч -. Рч) Н(!!+1г Рг -- Рл)+(Рг+Рг)Н Обоснование здесь может быть использовано следующее. До того как результат станет известным, средняя неопределенность, связанная с результатом, равна Н(Р» Рл Р„..., Р„), Если сгруппировать первые два результата, тогда средняя неопределенность будет ранна Н(Р! + Рь Рз, ..., Рл), С вероятностью (Р! + Рг) произойдет одно из первых двух событий, и оставшаяся неопределенность составит величину Н(Рг/(Р + Рг) + Рг/(Р! + Р!)).
Единственное определение Н(Х), удовлетворяющее всем трем свойствам, — это то, которое мы только что привели. Справедливость первого свойства очевидна из афика на рис. 19.2, демонстрирующего непрерывность функции. Изобразить грагрж и фик Н(Л) при наличии более двух вочлгожных результатов значительно труд нее, но свойство непрерывности должно соблюдаться и в этом случае, П иллюстрируем второе свойство. Если существует И равновероятных реро зультатов, тогда функция Н(Х) приобретает следующий вид: Н(Х) = -~ — !ой~ — / = -!08 ~ — ! = !ой(И). — „И ~И~ ~И! Функция !оя(И) монотонно возрастает с увеличением И. Обратите внимание на то, что при четырех возможных результатах энтропия равна 2 битам; при восьми возможных результатах — 3 битам и т.
д. В качестве численного приъшра последнего свойства мы можем написать: 1,458 = 0,219+ 0,43+ — (0,442 + 0,5288) = 0,649+ 0,809. 5 622 Глава 19. Теоретические основы сжатия данных 19,2. Кодирование 623 19.2. Кодирование Код Хаффмана з Рз = 0,128, Рз = 0,008. Одно из важных приложений концепции энтропии заключается в том, что зта кон цепция помогает понять принципы работы алгоритмов сжатия данных. Энтропия случайной переменной или источника сообщений определяет количество битов требуемых для представления результатов случайной переменной или альтернативных сообщений без потери информации. Таким образом, при разработке алгоритма сжатия данных энтропия представляет собой меру максимально возможного, Мы начнем этот раздел с рассмотрения кола Хаффмаиа (Нц((шап), представляющего собой простой, но эффективный код, иллюстрирующий взаимосвязь между энтропией и эффективностью сжатия.
Затем мы представим общий результат по вопросу энтропии и сжатия. Наконец, мы вернемся к коду Хаффмана, чтобы проиллюстрировать некоторые основные принципы сжатия данных. Рассмотрим случайную переменную Х, принимающую одно из восьми возможных значений (хь хг, ..., хз) со следующими вероятностями: Р1 — — 0,512, Рз = 0,032, Рз = 0,128, Рз = 0,032, Рз = 0,128, Рз = 0,032, Здесь Р; представляет собой вероятность выпадения результата хь Предположим, что сообщение состоит из реализаций случайной переменной Х, и мы хотели бы закодировать сообщение в двоичном виде. Олин очевидный вариант решения заключается в том, чтобы использовать 3-битовый код фиксированной длины, в котором каждое из восьми возможных значений случайной переменной Х кодируется одним 3-битовым числом.
Лучшая стратегия заключается в использование кода переменной длины, в котором более длинные кодовые слова назначаются менее вероятным значениям Х, а более вероятные значения Х кодируются короткими кодовыми словами. Такой технический прием применяется в азбуке Морзе и коде Хаффмана.
Предположим, что сообщения должны передаваться при помощи алфавита из )з" символов. Каждый символ должен уникальным образом кодироваться двоичной последовательностью, Нас интересует способ построения оптимального кода, то есть кода, дающего в результате минималы~ую среднюю длину кодируемого сообщения. Важно отметить, что мы не ищем минимальную длину кода для какого-либо конкретного сообщения или для всех сообщений (последнее найти невозможно), но минимальную длину кода, усредненную по всем возмохсным сообщениям.
Другой способ взглянуть па данные требования состоит в том, что мы получаем сообщение, уже закодированное путем назначения символам двоичных слов фиксированной длины. Таким образом, если символов 8, каждый символ кодируется тремя битами. Если число символов в алфавите от 9 до 16, то каждый символ ~ кодируется четырьмя ита мя битами и т. д.
Такое кодирование не является оптимальным, если символы встречаютс чаются в сообщениях с разной вероятностью. В этом случае ебование может быть сформулировано следующим образом. Требуется разработать оптимальную схем хему кодирования с использованием кода переменной длины, позволякш1ую получить к чить кодированное сообщение минимальной средней длины. оичный код с кодовыми длинами (.ь з'.з, - з.л; поставленный иассмотрим дво н в соответствие алфавиту из зт' символов с вероятностями Рь Рь ..., Рм Для удобства предположим, что с , что символы организованы в порядке убывания вероятности (Р,>Р,>, кгь ожн Р », Р.). Можно показать, что оптимальный код должен удовлетворять следующим требованиям: + Н пикакие два разных с разных сообщения не должны состоять из одинаковых последовательностей битов. + пикакое кодовое слово н в слово не должно совпадать с префиксом другого кодового слова.
+ С, т чающиеся с большей вероятностью, должны кодироваться + з имволы, встречающиес более короткими кодовыми словами. То есть г~ з.з ... и г <( < <) + два кодовых слова для символов с наименьшей вероятностью должны иметь одинаковую длину (Ак — - ьа з) и различаться только последней цифрой. Первое требование гарантирует уникальность кодирования любого сообщения. Второе требование определяет так называемый мгновенный код, Это требование не является строго обязательным, но оно требуется, чтобы гарантировать, что сообщение может быть декодировано шаг за шагом...р р д . П ип о вижениислеванаправо, как только последовательность битов совпадает с д анным ко овым словом, пекод дирующии алтари тм может произвести соответствующее назначение. Вот пример кода, нарушающего первые два требования: х| 0 хз 010 хз 01 хз 10 Двоичная последовательность 010 может соответствовать одному из трех сообп1енитп хз, хзхь хзхь Назначение третьего требования легко понять, если отметить, что при нарушении данного условия, поменяв два кода, вы сможете получ ить меньшее значение среднеи длины.
> Дч . ПовтоЧтобы понять суть последнего требования, предположим, что 1.к > к-ь о вто рому трзззован рей ию кодовое слово Ю вЂ” 1 не может быть префиксом кодового слова М. 1т' — 1 ифры кодового слова зч составляют уникальное кодовое Поэтому первые — ц „.
слово, а остальные цифры можно отбросить. Если эти два кодовых слова различаются в каком-либо бите, кроме последнего, мы можем от р отб осить последний бит у каждого слова, получая таким образом лучшии код. фНа основании этих методов можно постронтысод, называемы" д й ко ем Хаф ве оятности, так мана. ачн у , Н ем с упорядочивания всех символов по убыванию р > Раз » ...(Рая). что мы получим символы (аь аь ..., аэ) с вероятностями (Ра|) > ( аз) — -.— 624 Глава 19.
Теоретические основы сжатия данных 19.2. Кодирование 626 Затем объединим два последних символа в эквивалентный символ с вероятщ! стью (Рах !) ь (Рах). Коды этих двух символов будут одинаковыми, кроме послед них двух цифр. Теперь у нас есть новый набор из Ф- 1 символов. 1!ри необходи мости поменяем порядок следования символов таким образом, чтобы полу!и т олу и!ть символы (Ь1, Ьь ..., Ьх-!) с вероятностями (РЬ!) > (РЬх) » ... (РЬм !). Теперь мы можем повторять этот процесс до тех пор, пока не останется всего два символа Рисунок 19.3 иллюстрирует этот процесс для набора символов, заданного в начале раздела.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
