В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 149
Текст из файла (страница 149)
Это стандарт для бинарных ' Рпале|лье В|где|Ы !майе Сотргелгеп. Кееопняепдабоп Т92, 1993. Таблица 20. $. Кодовая таблица схемы МВ 0001 001 + М(а,а,) е М(а,а,) 1 011 ОООО)1 0000011 010 000010 0000010 642 Глава 20. Сжатие без потерь ис~ твает алгоритмы сжатия с потерями и б арифметического кодирования. Таблица 20.5.
Сравнение методов факсимильного сжатия Разрешение Размер МН МП ММП 4В10 изображения, пелов изображения, на дюйм, или тип текста полы Коэффициенты сжатия для изображений с различными степенями разрешения 12,5 272 х 192 2,34 2,32 3,43 25 544 х 384 3,56 3.94 5,68 50 1088 х 768 6,06 7,26 10,34 100 2176 х 1536 11.30 14,60 22,52 200 4352 х 3072 20,28 29,24 48,97 400 8704 х 6144 29,72 51,30 95,96 Коэффициенты сжатия лля различных плотностей текста Письмо 4352 х 3072 20,28 29,24 48,97 Разреженный текст 4352 х 3072 ! 5,97 25,05 41,96 Плотный текст 4352 х 3072 3,08 3,95 4,54 6,69 10,07 15,93 31,03 62,52 122,38 62,52 54,29 5,91 20.3.
Арифметическое кодирование Метод кодирования Хаффлтана хотя и является простым в реализации и относительно эффективным, тем не менее, не псоволяет достичь максимальгюго коэффициента сжатия, если только все вероятности не представляют собой отрицательных В верхней части таблицы сравниваются алгоритмы сжатия изображений с различным разрешением. Можно сделать три замечания. Во-первых, все методы позволяют достичь значительной степени сжатия.
Во-вторых, схема МК оказывается лучше модифицированной схемы Хаффмана, а схема ММ)с позволяет достичь еще большей степени сжатия, чем схема МВ В-третьих, чем выше разрешение изображения (и следовательно, на нем больше деталей), тем выше эффект от применения сжатия. То есть коэффициент сжатия изображений с высоким разрешением выше. В логарифмическом масштабе все алгоритмы демонстрируют примерно линейный рост коэффициента сжатия прн увеличении пространственного разрешения. В нижней части таблицы сравниваются алгоритмы сжатия, применяемые к трем стандартизированным документам, определенным сектором 1ТП-Т. Эти документы располоятены по возрастанию плотности черных точек на странице. Здесь также относительная производительность схемы МК оказывается выше производительности модифицированной схемы Хаффлтана, а схема ММК позволяет достичь большей степени сжатия, чем схема МЕ. Обратите также внилтание па то, что чем выше плотность черных точек на странице, тем ниже коэффициент сжатия.
Чтобы объяснить причину этого явления, вспомним, что энтропия потока данных выше при несбалансированных вероятностях. При увеличении плотности текста мы сталкиваемся с ситуацией, в которой близки значения вероятностей появления белых и черных последовательностей точек. 20.3. Арифметическое кодирование а 2. А и метическое кодирование предназнач дл начено для достижения степеней числа . рифме пения вычислений. При этом х коэффициентов сжатия за счет усложн более высоких коэ„,.„ 6, обы вероятности приближались .ние об абатывается таким оправам, что ы в "Ринат а 2.
А ифметическое кодиРование использУетсЯ к отрицат "рицательным степеням числа 2. Ари метическ а тах тРЕО и МРЕЬ, описываемых в главе 21. ей в основе арифметического кодирования, Мы начнем с концепции. лежащеи в основе а а затем рассмотрим некоторые детали. Основная концепция я Хаффмана„что если отдельные коенияметода кодиРования ачВспомним из о су1кд ,кс,вер ятностьюр, влу шем имволы вот чаются в исходном тексте с вероят дируемые симво ре,кете с вероят случ ае мы можелт использовать для каждого символа ко шей следующему неравенству: 1ой (1/Р;) < Х; < !ой (1/Р;) + 1. Здесь Р; пред .
оо сгавляет сооои вен об " роятностгч с которой йй символ встречается в ым кодируется данный сим- исходных данных, а гх — длину двоичного кода, которы к жно показать, что аол. Исходя из данного неравенства, можно п в Х, а Е1Ц явля- Н Л и дставляет собой энтропию множества символов, а . я Х. В ме сжатия без потерь Н(Х) нес- ется средней длиной кода д. а чя множества . схеме сж тых апных,таккак Н(Х) определяетсред- г аб детнижнейграницеиобъемасжа д фо, жащейся в символьном наборе. нее количеств фор, жащ " о инфо мации, содержащ " е. ритма сжатия может быт ь ано, что эффективность алгорит Наконец, было показано, ко ировання блоков повышена у о си п тем ооъединения си 6 символов и одновременного кодиров 1 чаем следующее неравенство: по д символов каж гаждый.
В результате мы получаем еле Н(Х) « — Н(Х) + —. ЕЩ К алго нтмасжа,с 1 еств егспособповышеннязффективностиалг р Р У У тия. Если нам нужно от ра тп авить сооб1цение длиной в символ в, об . ждым сообщением ок иной Ат. Таким образом, мы обращаемся с кажды — и сообщения В кач тве пример ра мотрим слу- атомар ы сима огнаЮ вЂ” длину ~ы~ йся в главе 19, в котором имеются два символа, чай, обсуждавшийся в главе, в т све ятностямиО,ои, . слнм ,8 0,2. Е . ы передаем сообщение щиеся в исходном текс~е с веро длиной в 3 символа (М= '. =, тот М= 2. А1= 3), тогда существуют 2. = возлю ит от предыдуших , Е и появление в потоке данных жд ка ого символа не завис тов.
сли по с х8 ез льтатов: символов, тогда мы мож можем написать вероятности в е р у Рккк = 0,512, Рвкк = 0,128, Рькв = 0,032, Рвал = 0,032, Рввв = 0,008. 644 Глава 20. Сжатие без потерь Паалвда- Р, ввтепьиаать 0,512 0,494 0,384 0,38 0,384 0,38 0,16 0,159 0,64 0,38 0,096 0,159 0,096 0,159 0,04 0,056 2,408 2,167 [О, 0,512] 0,00000 [0,512, 0„64] 0,10000 [0,64, 0,768] 0,10100 [0,768, 0,8] 0,11000 [0,8, 0,928] 0,11001 [0,928, 0,96] 0,11101 [0,96, 0,992] 0,11110 [0,992, 1,01 0,11111 0,612 0,512 0,128 0,64 О, 128 0,768 0,032 0,8 0,128 0,928 0,032 0,96 0,032 0,992 0,008 1,0 ААВ АВА АВВ ВАА ВАВ ВВА ВВВ 100 0,8 1,0 101 11000 4!5 11001 11110 0,64 0,8 0,96 * дц Э цццчцавх цифр. ц ' а',Й, 0,8 ] 0,96 ~[0 ]О 0 612 064 0.768 0.928 0 92 АВВ ВАВ ВВА Один из возможных методов состоит в применении кода Хаффыана (см рис, 19 в главе 19).
Для сообщения с восемью возможными результатами зто разумно, н при очень длинных сообщениях использование этого метода приведет к большим вычислительным затратам, Метод арифметического кодирования предоставляет остроумную альтернативу. Заметим, что сумма вероятностей всех возлюжных сообщений должна быть равна 1,0.
Таким образом, можно разложить все результаты на интервале [О, ц в виде отрезков, длины которых равны их вероятностям (рис. 20А). На рисунке также показан простой метод генерирования интервалов по одному символу. Эта процедура выглядит следующим образом: 1. Алгоритм начинается с позиции первого символа в сообщении, а интервал делится в соответствии с вероятностями отдельных символов. В данном случае имеется два символа, А и В, встречающиеся в исходном тексте с вероятностями 0,8 и 0,2.
Поэтому интервзл [О, 1] разбивается на подынтервалы [О, 0,8) и [0,8, 1). Граница между интервалами может быть о> нссена произвольно к любому из интервалов, 2. Каждый подьштервал разбивается тем же способом, который применялся на шаге 1. То есть каждый подынтервал дробится на доли в соотношении 4:1. 3. Этот процесс повторяется для %символьных позиций (сообщение длины >у).
риа. 20.4. Расположение символов иа единичном интервале Теперь результату каждого сообщения поставлен в ссютветсгвие интервал, пропорциональный вероятности сообщения. Таким образом, кюкдый результат может быть представлен дв<>ичным дробным числом, равным некоторой точке на интер-~ 20.3. Арифметическое кодирование б45 вале. Будем использовать для этого нижнюю границу каждого интервала.
Результаты такой операции показаны в пятой колонке табл. 20.6, при этом используются пять знача>цих цифр правее двоичной запятой. Такой точности достаточно для однозначной идентификации каждого интервала, а следовательно, и каждого результата. Поэтому мы можем использовать дробную часть каждого значения в качестве кода для соответствующего результата (например, АВА = 10100). Однако полученные коды можно усовершенствовать. Например, можно удалить из кода некоторые цифры, если только это не приведет к неразличимости кодов (то есть ни один код не должен совпадать с начальными цифрами другого кода).
Результат этой операции показан в шестой колонке таблицы. Обратите внимание на то, что в общем случае более короткие интервалы идентифицируются большим числом битов. В этом есть смысл: нижняя граница короткого интервала близка к нижней границе следующего интервала. Позтол>у двоичные дроби для этих двух границ будут совпадать в нескольких разрядах. Чем меньше интервал, тем больше одинаковых разрядов в ссютветствующих дробях. Таблица 20.6.
Интервалы вероятности для трехсимвольных последовательностей Кумулятивная Иитерввп Двоичное Кад Р,Ь, Р,[а9 ввравтиаать првдстввлеиие [1/Р] иижиед грвиицы* Таким образом, мы разработали новый метод назначения кодов сообщениям. В последних двух колонках табл. 20.5 средняя длина нового кода сравнивается с энтропией множества ссюбщений (сравните также с табл.
19.1 в главе 19). Несмотря на век> свою внешнюю привлекательность новый метод обладает двумя существенными недостатками; + Если все возможные и>ггервалы вычислять заранее, то объем необходимых вычислений будет огромен. Например, если длина сооб>пения равна 1000 символов и используется алфавит из 128 символов (например, на р або символов АБСП), тогда число всех возможных сообщений будет составлять 128 ива = 10>ю> + Описанная схема применима только к сообщениям фиксированной длин>я. Метод арифметического кодирования позволяет устранить оба педостат«а. 646 Глава 20.
Сжатие без потерь Чистое арифметическое кодирование Мы начнем с простейшей формы алпзрнтма арифметического кодирования Хотя этот алгоритм преодолевает упомянутые ранее недостап и, ' », в нем сохраняются не- которые вычислительные сложности. Тем не менее, про енес, проще понять метод арифме- тического кодирования, рассмотрев сначала более пр ф лес простую форму, Прн арифметическом кодировании нет необходимости . ости заранее генерировать интервалы для всех возможных сообщений. Вместо место этого интервалы для отдель- ного сообшения вычисляются посимвольно. Таким б а им о разом, для передачи одного сообщения вычисляется толыю один интервал.
Кро роме того, поскольку процесс является посимвольным, нет необходимости фиксировать ф <сировать длину сообщения заранее. Вычисления продолжаются до тех пор, пока не будет достигнут кон б ут конец соо шения. Базовый алгоритм Каждый шаг алгоритма начинается с полуоткрь т р »того интервала [1, й), вначале инициализируемого как [О, 1): 1. Тек уший интервал разбивается на подынтервалы и о одному для каждого возможного символа. Каждый подынтервал пропор о орционален вероятности, с которой соответствуюший символ встречается в тексте.
2. Выби ается р . подынтервал, соответствующий текушему символу. Этот подынтервал становится текущим интервалом. 3. Если обработано все сообщение, выполняется следующий шаг, если нет, возвращаемся к шагу 1. 4. Выводится количество битов, достаточное для того, б т о, что ы можно было отличить данный интервал от двух соседних интервалов. 5. Выводится некий специальный код конц сооб, об а щения, чт ы уведомить получателя. На первом шаге нет необходимости вычислять все в е подынтервалы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
