В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 146
Текст из файла (страница 146)
Мы получим: Р,,в=рг(А)А)Ы— - 0,9 0,8=0,72, Р«в = Рг(В)А)Р« = 0,1 ° 0,8 = 0,08, Рвв=рг(А)В)Рв=0,4 0,2=0,08, Рвв=Рг(В)В)Рв=0,6 0,2=0,12. На рис. 19А, б показан код Хаффмана для данного случая, а в средней части табл. 19.2 — полученная в результате статистика. Обратите внимание на то„гго эгггропия У меньше, чем в случае, когда следуюгцие друг за другом символы независимы (1,292 против 1,444).
Поскольку вероятности для отдельных символов остались теми же самыми (Рв = 0,8, Рв = 0,2), го чем это объясняется7 Ответ состоит в том, что вероятности переходов добавляют информацию. Когда становится известен первый символ последовательности, мы получаем больше информа формации о там, какой сгимвол появится следующим. Поэтому неопределенное!ь уменьшается, н суммарная энтропия также снижается. Друпгми словами, в последовательностях появляется избыточность. Так, например, существует значительная избыточность в предложениях на английском языке. В табл.
19.2 для случая зависимых символов средняя длина кода равна 1,44, что дает эффективность 1,292/1,44 = 0,897. В нюкггей части табл. 19.2 показано, что произойдет, если проигнорировать переходные вероятности н предположить, что следуклцие друг за другом символы независимы даже в том случае, если онн зависимы. В этом случае используются те же коды, что и для независимых символов (АА= О.
АВ = 11, ВА= 100„ВВ = 101). Однако теперь для второй по частоте комбинации ВВ используется самое длинное кодовое слово 101, поэтому средняя длина кодового слова оказывается равной 1,48, что больше средней длины, получавшейся при использовании оптимального кода Хаффмана. Из этого обсуждения можно сделать вывод, что балыией эффективности в сжатии данных можно достичь, кодируя данные большими блоками, а также учитывая зависимости данных, 19.3. Рекомендуемая литература Существует масса книг по теории информации. Непревзойденной классической книгой, издаваемой до сих пор, является (88].
Два более современных издания, в которых особое внимание уделяется теме сжатия информации, — это (110] и [61]. Для самостоятельного изучения годится (16]. В (208] переизданы мнопге относящиеся к этой теме важные статьи, включая конструктивные статьи Шеннона. 19.4. Задания 1. П Покажите, что представленное ниже соотношение выполняется для функции энтропии случайной переменной стремя возможными значениями Н(Р„Рь Рз): Н(ЄЄЄ..., Рх) =Н(Р, +Р„Рз, ...,Р„,)+(Р, +Р,)Н '(Р, +Р, Р, +Рг ] 2.
Является ли представленный ниже код уникально расшифровываемым7 Если нет, постройте неоднозначную последовательностгс х, 010 «з 0110 х, 00011 хг 11110 «г 0001 «в 1100 хв 00110 хв 101011 3, Создайте коды Хаффмана для следующих символов; в каждом случае символы нумеруются в соответствии с вероятностью, с которой они встречаются в последовательности: б в г х~ 0,4 х О,2 х о,! х 0,1 «во,1 х,о,г х 0,4 х О,З «в 0,2 х 0,04 хв 0,04 хв 0„02 х~ вузе хг Е/Зб хв б/Зб хв 4/Зб «,З/Зб хв 3/Зб Хг 2/ЗЕ хв 2/Зб «в 1/Зб хг 0,2 хг 0,18 хв 0,1 х 0,1 хв 0,1 хв 0,081 хг 0,059 хв 0,04 х 0,04 х, О,О4 «„0,04 х,г О,ОЗ хгв 0,01 4.
Одно из требований к оптимальному коду аьплядит как Е, < /г < ... < /ж Чтобы доказать справедливость этого требования, предположим, что у нас есть код С с Рв > Рв и /г > /г. Теперь создайте код С', поменяв кодовые слова г и /г. Вычислите разницу между средней длиной кодовых слов С и С'. 5. Рассмотрим алфавит из двух символов А и В с представленной ниже транзитной матрицей. Покажите, что эта матрица является непротиворечивой при Рв = 0.8, Рв — — 0,2: А В А 0,9 0,1 В 0,4 0,6 6. Которые из перечисленных ниже схем кодирования могут быть получены с помонгью алгоритма Хаффмана, а которые нет7 Для кодовых схем, могущих представлять коды Хаффмана, укажите распределение вероятностей, для которого данный код может представлять оптимальный код Хаффмана. а) (хьхг,хз,хв) — г(010,011,001,10); б) (ходзь хз,хв) — г (О, 10, 110, 111); в) (хг,хг,хз хв) — г(10,0,101, 11); г) (хь хг, хз, хв) — г (00, 010, 011, 1).
Подавление нулей Глава 20 Сжатие без потерь Олно было хорошо — больше никто не мог сесть в поезд. Однако на стан шеи Вйнджел и затем еще раа на Олд Стрит она убедилась, зто зто не так. Возможно, та точка, после которой в вагон уже никто не может нтпснуться, ыла недостижима, и они люгли бы еше сколько угодно продолжать втискиваться и давиться, пока не задавили бы друг друга или пока не разорвало бы стены вагона. Барбара Войн Груш Рендела). Колер оррл Соломона Принцип сжатия данных довольно прост. Практиче к чески все формы представле- Данные могут быть сжаты с одной из двух цел й: целе: для экономии места при хране- нии или для снижения потребностей в пропускной способности. Когда сжатые данные извлекаются из места ане хр ния или прибывают по линни связи, должна существовать возможность распаковать данные, , восстановив их исходную фор- му.
Для этого при сжатии данных удаляемые э -лементы данных доллсны заме- информацию, ь смог восстановить исходную щаться другими таким образом, чтобы получатель м С ушествует две основные разновидности сжатия атия данных: сжатие без потерь и сжатие с потерями. При сжатии без потерь (!озз1езз сош, ' ) ф езз сошргезгйоп) инфо мация не теряется и распакованные данные идентичны исходным несжатым . Ка атым данным. к ей ист ффективность сжатия без потерь ограничена эн очипка данных. В случае сжатия с потерям (1 зу р ванные данные мог быть п ие ерями ( оззу согпргезз!оп) аспакоерям ( зу р ' ) р спакоым к могут ыть приемлемым приближением (в соответствии н р ритерием точности) к исходным несжатым мог ыгь п ие ии с некотоизоб ажений или тым данным.
Например, при сжатии из ражений или видеоданных критерий может заключаться аться в том, что для чело- веческого глаза аспакован р ное изображение неотличимо от оригинала. ажным фактором при разработке и выборе алгоритмов сжатия данных анных являр т, тре уемыи для сжатия и распаковки данных. В об существует комп о щем случае и скоростью рагюты у компромисс между достижимой степенью сжатия алгоритма сжатия, а также стоимостью этой раГюты.
польз емых схем В этои главе рассматриваются некоторые из наиболее в. ее важных и широко псуемых схем сжатия без потерь, применимые в ряде контекстов. В главе 21 20.1. Методы группового кодирования 6З1 изучаются схемы сжатия данных с потерями, специально разработанные для сжатия изображений и видеоданных. Глава начинается с обсуждения очень простого метода, называемого групповым. Затем мы покажем, как этот метод используется в стандартах факсимилыюго сжатия. За этим следует описание арифметического кодирования. В занершение изучаются методы сжатия данных Ливи — Земпедя (Е!к — 2ешре1). 20.1.
Методы группового кодирования Групповое кодирование (гап-!еп8!!т епсог1!п8) представляет собой простой метод сжатия данных без потерь, довольно эффективный для сжатия текста. Этот метод также находит применение в факсимильном сжатии, обсуждаемом в разделе 20,2, В начале этого раздела обсуждается ешс более простая техника подавления нулей, после чего описывается метод группового кодирования, представлятон!ий собой обобщение метода подавления нулей. Один из старейших и простейших методов сзкатия данных известен как подавление нулей (пн!1 зирргезяоп), нли подавление пробелов (Ыапк знрргезз!оп). Он до сих пор применяется в протоколе уровня передачи данных В!8 У 1Ч С (В шагу Вупсй гоп опз Сошшншсабопз ргогосо! — двоичный синхронный протокол связи) 1ВМ 3780. В тексте или потоке символов часто встречаются длинные строки пробелов или нулей.
В методе подавления нулей передатчик сканирует данные в поиске строк пробелов и заменяет каждую такую строку двухсимвольным кодом. Код состоит из специального управляющего символа, за которым следует число пробелов в страке. Например, пусть имеется код с символами пробела, обозначенными знаком Ь: ХУХЬЬЬЬЬЯКХ. Эта строка заменяется следующей строкой, в которой 5, представляет собой специальный управляющий символ: Х'т'л.8, 5ОВХ. Такая схема позволяет сделать короче все строки из трех и более пробелов.
В методе подавления нулей приемник ищет в потоке входящих символов специальный символ, используемый для индикации удаленных пробелов. Получив такой символ, получатель понимает, что следующий символ содержит количество удаленных пробелов. По этой информации мспкет быть восстановлен исходный поток данных. При том что метод подавления нулей представляет собой крайне примитивную форму сжатия данных, его преимущество заключается в том, что он очень легко реализуется. Кроме того. выигрыш даже от применения такого простого метода может быть значительным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
