Лекция 4. Статистическое сжатие сообщений
Курс “Теория информации и кодирования”

Если исходное кодирование сообщений имеет целью унификацию их представления в цифровой среде, то методы сжатия исходного кода сообщений применяются, когда компактность кодирования становится приоритетной задачей. В этой и трех последующих лекциях мы познакомимся с методами сжатия без потерь и с потерями информации. Здесь речь пойдет о статистическом подходе, который считается классическим и при этом продолжает применяться в современных алгоритмах сжатия.

Основы статистического сжатия
Статистическое сжатие по Шеннону-Фано
Усовершенствованный метод сжатия по Хаффмену
Динамический подход к статистическому кодированию
«Арифметическое» статистическое кодирование


4.1 Основы статистического сжатия

Возможности и ограничения
Принципиально важным результатом ТИК является теорема о кодировании источника, которая указывает на возможности и ограничения сжатия кода без потерь информации. Данная теорема (рис 4.1), доказанная Клодом Шенноном, утверждает, что:

Существует способ кодирования, который обеспечивает приближение средней длины кода знака Lk к величине энтропии Н дискретного источника с любой необходимой точностью. С другой стороны, не существует способа, при котором средняя длина кода была бы меньше энтропии.

Обратим внимание, что величина энтропии источника может интерпретироваться не только как безусловная, но и как условная энтропия с разной степенью глубины. В первом случае кодирование не учитывает, а во втором учитывает связи между знаками в сообщениях. Разумеется, последнее значительно усложняет практические алгоритмы сжатия.

Утверждение теоремы Шеннона касается сжатия сообщений без потерь информации. На практике для некоторых видов сообщений (прежде всего, для изображений и звука) используется сжатие с приемлемыми потерями качества. Этому направлению будут посвящены отдельные лекции.

Можно сказать, что методы сжатия кода без потерь опираются на два вида закономерностей в сообщениях: статистические (различие вероятностей появления знаков) и контекстные (связи между соседними знаками). При этом:
  • классические методы сжатия, которые создавались более полувека назад, применяли исключительно статистический подход, не учитывая связи между элементами сообщений;
  • cовременные алгоритмы (в частности, используемые в программах архиваторах) учитывают также контекстные закономерности, но продолжают использовать прошлые наработки в качестве своих составляющих.

Таким образом, статистическое кодирование в любом случае остается фундаментом сжатия сообщений.

Обзор подходов
Рассмотрим основные подходы к статистическому сжатию (рис.4.2).

А) Идея статистического сжатия состоит в использовании более коротких кодов для знаков с большими вероятностями. В результате уменьшается средняя длина кода. При этом возникает проблема разделения кодов знаков, которая отсутствовала в случае их одинаковых длин. Это вынуждает использовать при построении статистических кодов дополнительные условия.

Как мы уже знаем, статистическое кодирование теоретически позволяет приблизить среднюю длину кода к величине безусловной энтропии источника (согласно теореме Шеннона о кодировании Источника). Это означает, что первоначальная избыточность кодирования может быть устранена.

Б) Префиксные статистические коды были созданы на рубеже 40-х и 50-х годов прошлого века и завоевали популярность благодаря простоте и относительно высокой эффективности. Они предусматривают независимое кодирование отдельных знаков. При этом знаков в общем потоке кода фиксируются благодаря принципу «префиксности» (никакой код знака не может совпадать с начальным участком другого кода). Первый такой код был предложен независимо Шенноном и Фано. Позже Хаффмен разработал его усовершенствованный вариант, который широко используется и поныне.

Несколько усовершенствованный подход предусматривает статистическое кодирование не отдельных знаков, а их блоков. При этом блоку символов ставится в соответствие динное двоичное, поэтому такой способ кодирования называют "арифметическим". В отличие от префиксных кодов для фиксации границ кода блоков здесь используют специальные признаки. Выигрывая в степени сжатия, данный способ уступает префиксным кодам в быстродействии.

В) Все статистические коды (префиксные и арифметические) опираются на данные о вероятностях знаков. При этом частоты появления знаков не всегда заранее известны, к тому же они могут изменяться внутри сообщения. В связи с этим используются два подхода к построению механизмов кодирования:
  • cтатический подход исходит из неизменности статистики знаков. При этом правила кодирования (соотвествие знаков и их кодовых цепочек) определяются заранее на основе предварительной оценки вероятностей. Такой подход прост и характеризуется высокой скоростью кодирования и декодирования;
  • динамический подход предусматривает формирование и корректировку статистики по мере обработки сообщения. Он отличается гибкостью, но требует накладных расходов, связанных с синхронизацией схемы кодирования на стороне Источника и Получателя.

В данной лекции мы конкретно рассмотрим применение всех упомянутых подходов.

Контрольные вопросы:
1) Сформулируйте и поясните теорему Шеннона о кодировании дискретного источника. Какой вид энтропии подразумевается в формулировке теоремы.
2) Какие основные закономерности появления знаков в сообщениях может использовать сжатие.
3) Сформулируйте основные принципы статистического сжатия (опираясь на рис.4.2).
4) В чем состоит принцип префиксности статистического кодирования.
5) В чем состоит отличие префиксного и «арифметического» кодирования.
8) Охарактеризуйте различия статического и динамического подходов при статистическом кодировании. В чем их преимущества и недостатки.


4.2 Статистическое сжатие по Шеннону-Фано

Пример построения кода
Построение статистического кода удобно пояснить для случая кода Шеннона-Фано, который был разработан первым по времени. Рассмотрим простой пример, где Источник сообщений использует алфавит из четырех разновидностей знаков Z1-Z4, для которых известны вероятности их появления p1-p4 (рис.4.3).

Кодирование и декодирование выполняется с помощью таблиц соответствия знаков и их двоичных кодов. При кодировании от Источника поступает знак Zi, а Кодер выбирает из таблицы отвечающий ему код. При декодировании Декодер обнаруживает во входном потоке двоичных разрядов цепочку, которая встречается в таблице, и заменяет ее соответствующим знаком. Чтобы декодирование выполнялось верно, должно соблюдаться правило префиксности.

Построение таблицы кодирования должно включать следующие этапы:
0) все знаки алфавита Z упорядочиваются по убыванию их вероятностей;
1) группа знаков делится на две подгруппы таким образом, чтобы суммарные вероятности в каждой половине были как можно ближе;
2) знакам из каждой вновь образованной подгруппы присваиваются противоположные значения разрядов кода;
3) шаги алгоритма, начиная с 1-го повторяются, пока для каждого знака не будет сформирована уникальная кодовая цепочка.

Как видно из рассмотренного примера (рис.4.3), в результате:
  • длина кодовых цепочек знаков действительно возрастает по мере уменьшения их вероятностей;
  • требование префиксности кода соблюдено (ни одна кодовая цепочка не входит в качестве начала в другую);
  • средняя длина кода Lk сократилась не только по сравнению с исходным побайтовым кодированием, но и относительно обычного равномерного кодирования, которое потребовало бы для четырех знаков двух кодовых разрядов.

Оценка эффекта от сжатия. Ограничения подхода
Для оценки эффективности сжимающего кодирования можно использовать показатель избыточности кода: D = (Lk— H) / Lk (рис.4.4). При этом:
  • эффективность сжатия может оцениваться по соотношению исходной и остаточной избыточности (Dисх и Dост). Первая определяется относительно длины исходного кода (например, при побайтовом кодировании Lkисх = 8 разряд/знак), а вторая — относительно достигнутой средней длины кода (в нашем случае Lkсжт = 1,6 разряд/знак). В нашем примере Dисх = (8-1,57)/8 =0,804, а Dост = (1,60-1,57)/1,6 = 0,019;
  • в рассмотренном случае эффект от статистического сжатия велик (избыточность сократилась радикально - почти на 80%). Это связано прежде всего c большой исходной избыточностью из-за рассмотренного в примере короткого алфавита. На практике, например, при статистическом сжатии текстов на европейских языках, безусловная энтропия составляет порядка Н ≈ 5 бит/знак. При этом исходная избыточность будет уже около Dисх = (8-5)/8 = 0,375 и эффект ее устранения может оказаться не настолько разительным, хотя и существенным;
  • с другой стороны, остаточная избыточность Dост в нашем примере незначительна (около 2%). Но здесь возникает принципиальный момент: теорема Шеннона обещает, что зазор между Н и Lk может быть минимизирован с какой угодно точностью. Между тем, при рассмотренной процедуре кодирования этот зазор не может быть дополнительно уменьшен. Он однозначно определяется распределением вероятностей знаков и оказывается нулевым только в частном случае, когда такие вероятности кратны отрицательным степеням двойки (0.5; 0.25; 0.125 и т.д). В этом случае информативности знаков имеют целые значения (- log20,5 = 1; - log20,25 = 2; - log20,125 = 3 и т.д.) и совпадают с длинами кодовых цепочек соответствующих знаков.

Расширенный случай кодирования. Доказательство теоремы Шеннона
Для доказательства справедливости теоремы Клод Шеннон рассмотрел расширенный способ статистического кодирования, который позволяет уменьшить “зазор” между средней длиной кода и величиной энтропии (средней информативностью знаков).
Рассмотрим этот подход на примере (рис.4.5):
  • как мы уже знаем, для простейшей процедуры кодирования код полностью определяется вероятностями знаков и не может быть улучшен. Особенно ярко это видно на примере с алфавитом всего из двух знаков (в таблице — секция «Исходный алфавит»). В нашем примере при вероятностях знаков 0,8 и 0,2 энтропия Н=0,72бит/знак, при этом сделать код короче, чем 1 в принципе невозможно (Lk=1 разряд/знак) и величина избыточности D1=0,28;
  • идея Шеннона заключается в том, чтобы перейти к новому алфавиту, элементы которого соответствуют парам исходных знаков (в таблице — секция «Группировка пар знаков»). При этом количество знаков возрастает до четырех и появляется возможность построить статистический код, для которого средняя длина составит 1,56 разрядов/знак (рис.4.5). Оновременно величина Н (бит/знак) удваивается, поскольку речь теперь идет о паре исходных знаков. А избыточность сокращается до D2 = 0,077;
  • следующий шаг состоит в группировке троек соседних исходных знаков (в таблице — секция «Группировка троек знаков»). При этом значение избыточности сокращается уже до D3 = 0,014. Понятно, что такую процедуру можно продолжать, достигая при необходимости любого сколь угодно малого значения D. Отметим, что на рис.4.5 хорошо видно, как вероятности знаков новых алфавитов с каждым шагом приближаются к отрицательным степеням двойки. Соответственно, средняя длина кода близится к энтропии. Это и есть прямое доказательство теоремы Шеннона о кодирования Источника.

Контрольные вопросы:
1) Поясните процедуру статистического кодирования по Шеннону-Фано, используя рис.4.3. Сформулируйте шаги алгоритма кодирования.
2) Какие свойства полученного в примере рис.4.3 кода подтверждают его корректность.
3) Запишите формулу для определения избыточности кодирования.
4) Как определяется исходная и остаточная избыточность при оценке эффективности сжатия. Приведите примеры.
5) При каких вероятностях знаков исходная процедура Шеннона-Фано дает минимальную избыточность.
6) В чем состоит доказательство справедливости теоремы Шеннона о кодировании Источника.


4.3 Усовершенствованный метод сжатия по Хаффмену

Особенности кодирования по Хаффмену — простой пример
Код Хаффмена является усовершенствованным вариантом статистического кода Шеннона-Фано и в таком качестве получил очень широкое применение. Процедуру построения и применения кода на простом примере иллюстрирует рис.4.6. Для наглядности здесь использованы те же исходные данные, что и в примере кодирования по Шеннону-Фано:
  • построение кода (таблицы соответствия знаков и их кодов) включает два этапа:
  • на этапе 1 выполняется преобразование исходной таблицы вероятностей знаков (которая первоначально отсортирована по убыванию вероятностей);
  • на этапе 2 по данным преобразованной таблицы строится граф (дерево) кода и определяются кодовые цепочки знаков;
  • этап 1 предусматривает последовательное объединения вероятностей в направлении «снизу вверх» с использованием дополнительных столбцов. При этом на каждом шаге суммируются две минимальные вероятности — вплоть до получения 1 (см. Таблицу на рис.4.6). Напомним, что при построении кода Шеннона, напротив, выполняется деление знаков на группы в направлении «сверху вниз». Подход Хаффмена позволяет в некоторых случаях получать более оптимальное решение, хотя чаще всего эти два способа дают в итоге одинаковый результат;
  • этап 2 включает построение «дерева» кода в порядке, обратном объединению вероятностей. При этом условно принимается, что в каждой паре ветвей дерева вправо уходит ветвь с большим весом. Эта ветвь ассоциируется со значением кодового разряда «1», а противоположная ей — с «0». “Листьями” дерева кода становятся знаки алфавита. Теперь код каждого знака получается как последовательность разрядов при движении от корня дерева к данному листу (например, код Z3 читается как 001). Как видно, в данном случае код по Хаффмену и по Шеннону совпадают (сравним рис.4.6 и рис.4.3).

Особенности кодирования по Хаффмену — развернутый пример
Уточним детали построения и применения кода на более сложном примере (рис.4.7):
  • во-первых, здесь видно, что на каждом шаге объединения вероятностей новый столбец пересортировывается по их убыванию. В результате полученная на данном шаге сумма вероятностей может оказаться в новом столбце в любой позиции;
  • во-вторых, структура дерева существенно отличается от предыдущего примера. Здесь из корня «развиваются» две примерно одинаково мощные ветви. При этом самые короткие коды становятся двухразрядыми. Такое характерно для случаев, когда не один из знаков не встречается примерно в половине случаев (то-есть, типично).

На рисунке также показан пример кодирования цепочки из 10 произвольных знаков и декодирования соответствующей кодовой последовательности. При кодировании кодовая цепочка выбирается из строки, отвечающей знаку кода (например, для первого знака в сообщении z2 выбирается код 01). Процедура восстановления несколько сложнее: декодер должен “дождаться”, когда на его входе накопится последовательность, которая есть в одной из строк таблицы. При этом началом отсчета является распознавание предыдущего знака. Например, когда распознан первый знак z*2, декодер остается с состоянии ожидания, приняв первый и второй 0 и лишь когда появится третья 1 (сформировался код 001), распознает второй знак z*5. Напомним, что такой способ возможен только для префиксных кодов.

Применение кода Хаффмена
Разновидности кода Хаффмена и особенности их использования характеризует рис.4.8:
  • рассмотренный выше способ кодирования относится к классу статических. Здесь оценки вероятностей и таблица соответствия знаков и кодов остаются неизменными. При этом они могут опираться на обобщенную статистику Источника или на индивидуальную статистику конкретных сообщений. Во втором случае для каждого сообщения первоначально должны быть подсчитаны вероятности появления знаков, а уже затем на основе этих данных выполнено кодирование. Соответственно, такой способ называют двухпроходным в отличие от первого - однопроходного;
  • однопроходный способ получил наибольшее распространение. Он применяется в основном как составная часть комплексных алгоритмов сжатия. Это компенсирует важный общий недостаток статистического кодирования — отсутствие учета контента. Поскольку в рамках комплексных методов этот алгоритм работает с уже преобразованными данными, ослабляется их зависимость от конкретного содержания сообщений. С другой стороны простота и высокая скорость кодирования составляют важное достоинство метода;
  • двухпроходный способ не нашел практического применения в силу одного важного недостатка: здесь таблица кодирования индивидуальна для каждого сообщения и ее необходимо передавать от кодера к декодеру. Соотвествующие накладные расходы нивелируют достоинства более точного учета статистики. Кроме того очевидны потери в скорости;
  • наконец, динамический способ, с которым мы познакомимся ниже, максимально адаптивен, поскольку код здесь формируется прямо по ходу обработки сообщения. Однако, такой подход трудоемок, а главное, не снимает главной проблемы — отсутствия учета контента. На практике он применяется ограниченно.

Контрольные вопросы:
1) Поясните процедуру кодирования по Хаффмену, используя рис.4.7. Почему на практике обычно используют именно код Хаффмена, а не похожий на него код Шеннона-Фано.
2) Выполните построение кода Хаффмена для исходных данных, предложенных преподавателем.
3) Выполните пример кодирования и декодирования для последовательности из пяти произвольных знаков, используя таблицу кодирования на рис.4.6.
4) Каким образом на практике используется однопроходное статическое кодирование по Хаффмену. Как при этом компенсируются принципиальные недостатки статистического кодирования.
5) В чем состоят недостатки двухпроходного статического кодирования по Хаффмену, которые ограничивают его практическое применение.
6) В чем особенность динамического подхода к статистическому кодированию. Каковы его принципиальные преимущества и недостатки.


4.4 Динамический подход к статистическому кодированию

Принцип динамического кодирования по Хаффмену
Ценность изучения динамического кодирования по Хаффмену связана с пониманием принципов, которые на которые мы будем опираться в дальнейшем. Речь идет о взаимодействии кодера и декодера, у которых первоначально отсутствуют данные о статистике знаков, однако задан общий алгоритм обработки (рис.4.9):
  • прежде всего важно, что дерево кода, структура которого определяет кодовые цепочки всех знаков, формируется практически «с нуля» по мере поступления знаков сообщения. При этом все изменения в дереве выполняются синхронно на стороне кодера и декодера. Благодаря этому на каждом шаге алгоритма с обеих сторон дерево, а значит и коды всех знаков — одинаковы;
  • при первом появлении любой разновидности знака кодер создает на дереве соотвествующий лист и присваивает знаку кодовую цепочку по уже знакомым нам правилам Хаффмена. Однако, поскольку декодеру данный код еще не известен, по каналу передается обычный исходный байтовый код данного знака (например, в Unicode). Получив его и распознав знак, декодер дублирует все действия с деревом на своей стороне. Очевидная неэкономичность такого кодирования не оказывает существенного влияния на итоговый объем сжатого кода, поскольку используется для знака только один раз;
  • при повторных появлениях знаков, для них используются короткие кодовые цепочки соотвествующих ветвей дерева (они совпадают для кодера и декодера), благодаря чему и достигается сжатие. При этом постоянно подсчитываются частоты появления знаков и чаще используемые ветви дерева могут перемещаться ближе к корню (при этом длины кодов перераспределяются в пользу таких знаков);
  • в качестве признака окончания сообщения обычно применяется байтовый код ESC, для которого на дереве кода заранее выделяется специальная вершина. Это несколько снижает эффективность сжатия, однако, на практике удельный вес такого байта невелик.

Пример динамического кодирования по Хаффмену
Пример динамического кодирования по Хаффмену
На рисунке 4.10 показано кодирование последовательности: Z1, Z3, Z1, Z2 Z1, Z2, Z1, Z4, Z1, Z3.
Кодирования включает следующие шаги:
  • первоначально на дереве кода (как у Кодера, так и у Декодера) имеется только один лист с признаком окончания сообщения (знак ESC);
  • при поступлении первого знака Z1 на дереве заводится соответствующая ветвь с кодом "1". При этом Декодеру передается первичный код знака 'Z1', получив который он также вносит аналогичные изменения в свое дерево кода. На передачу первого знака потрачено 8 разрядов кода, зато теперь при поступлении следующих знаков Z1 они будут кодироваться коротко;
  • при поступлении следующего знака (Z3) ситуация повторяется. Однако путь к новому знаку на дереве кода включает промежуточный участок с кодом "0", поэтому Кодер передает 9 разрядов: 0 'Z3'. Когда поступает еще один знак Z1, Кодер использует для него короткий одноразрядный код "1". При этом модифицируется счетчик поступивших знаков данного типа;
  • при поступлении знака Z2 снова заводится новый лист дерева кода и в канал передается 00 'Z2' (10 разрядов). Поскольку Z2 поступил позже, чем Z3, его код 001 оказывается более длинным.
  • при поступлении знака Z1 он кодируется одним разрядом "1" и увеличивается счетчик поступлений. Когда появляется знак Z2, в канал передается его код 001. После увеличения счетчика поступлений Z2 "обходит" знак Z3 по частоте появлений, поэтому их ветви на дереве кода меняются местами. В дальнейшем для Z2 будет использоваться более короткий код 01;
  • в дальнейшем используются уже знакомые нам элементы алгоритма: поступление двух уже встречавшихся знаков Z1 кодируется "1", для нового знака Z4 заводится ветвь с кодом 0001, а знак Z3 кодируется как 001 в соответсвие с его текущей позицией на дереве кода. Признаком конца сообщения будет появление знака ESC, код которого на этот момент — 0000.

В примере видно, что при увеличении длины сообщения первоначальное использование длинных однобайтовых кодов знаков все больше компенсируется использованием коротких кодов. Чем длиннее сообщение, тем больше средняя длина кода приближается к энтропии.

Контрольные вопросы:
1) Поясните действия кодера и декодера динамического кодирования по Хаффмену при первом появлении знака определенного типа.
2) Поясните действия кодера и декодера при последующих появлениях знаков определенного типа.
3) За счет чего обеспечивается сжатие кода сообщений при динамическом кодировании по Хаффмену.
4) Поясните механизм адаптации кода при изменениях вероятности появления знаков.
5) Почему использование байтовых кодов не влияет существенно на эффективность динамического сжатия по Хаффмену.


4.5 «Арифметическое» статистическое кодирование

Характеристика способа. Процедура кодирования
Как мы уже знаем, эффективность статистического подхода может быть повышена, если кодировать не отдельные знаки, а их блоки. Однако, «лобовой» подход (рис.4.5) здесь связан со значительным ростом объема алфавита и потому практически не используется. Более компактное решение принято называть «арифметическим» кодированием. Его идея состоит в том, что блоку знаков, для которых известны вероятности появления, однозначно соответствует некоторое достаточно длинное число.

Рассмотрим принцип арифметического кодирования на примере. Пусть известно, что в сообщениях Источника используются знаки четырех типов с вероятностями соответственно Z1 - 0.6; Z2 - 0.2; Z3 - 0.1; Z4 - 0.1. Найдем двоичное число, которое однозначно определяет последовательность знаков Z1, Z3, Z2, Z1. Процедуру иллюстрирует рисунок 4.11.

Первоначально отрезок длиной 1.0 (что соответствует суммарной вероятности появления знаков) размечен в соответствии с вероятностями разных знаков (в данном случае - интервал от 0.0 до 0.6 отвечает знаку Z1, интервал от 0.6 до 0.8 - знаку Z2, а интервалы от 0.8 до 0.9 и от 0.9 до 1.0 - соответственно знакам Z3 и Z4.

По ходу появления знаков постепенно уточняются границы интервала, который соотвествует данной цепочке:
  • появление знака Z1 означает, что искомое число будет находиться в интервале от 0.0 до 0.6 (уровень А на рис.4.11). В дальнейшем этот интервал разделяется на отрезки, длины которых пропорциональны вероятностям знаков сообщения (уровень Б);
  • знаку Z3 на отрезке от 0.0 до 0.6 отвечает интервал 0.48-0.54. Повторяется «разметка» интервала в пропорциях вероятности знаков (уровень В);
  • знаку Z2 на отрезке от 0.48 до 0.54 отвечает интервал 0.516-0.528. Для него повторяется та же процедура деления интервала (уровень Г);
  • знаку Z1 на отрезке от 0.516-0.528 отвечает интервал 0.516-0.5232. Появление кода ESC означает, что сообщение закончено.

Теперь находится двоичное число минимальной длины, которое принадлежит данному отрезку. В примере это 0.10000101. Это число соответствует десятичному значению 0,5195 (рис.4.11). Если бы мы попытались использовать более короткий код, то вышли бы за пределы отрезка от 0,5160 до 0,5232 (0,1000011 соответствует 0,515625, а 1000011 — 0,52348). При этом, разумеется, достаточно передавать только значащие цифры: 10000101 (на рисунке выделены красным).

В данном примере для передачи 4-х знаков используется 8 разрядов (2 разряда на знак)+ длина признака конца кода. Это выглядит значительно хуже, чем например при кодировании при аналогичных исходных данных по Хаффмену (там мы получали среднее значение длины кода 1,6 разрядов/знак). Однако, чем больше длина кодируемой цепочки знаков, тем больше ощущается преимущество арифметического кода. В конечном счете средняя длина кода знака стремится к энтропии.

Декодирование арифметическим кодом
Процедуру декодирования рассмотрим на том же примере последовательности знаков Z1, Z3, Z2, Z1 (рис. 4.12):
  • из Канала передач Декодер получил последовательность 10000101. Ей соответствует двоичное число 0.10000101, а тому - десятичное число 0.5195;
  • полученное значение 0.5195 принадлежит интервалу 0.0-0.6, следовательно первый знак сообщения — Z1;
  • на отрезке 0.0-0.6, который отвечает знаку Z1, значение 0.5195 попадает в интервал 0.48-0.54, значит следующий знак сообщения — Z3;
  • на отрезке 0.48-0.54, который отвечает знаку Z3 при условии, что перед этим появился Z1, значение 0.5195 попадает в интервал 0.516-0.528, значит следующий знак сообщения — Z2;
  • на отрезке 0.516-0.528, отвечающем знаку Z2, появившемуся после Z1 и Z3, значение 0.5195 попадает в интервал 0.516-0.5232, значит следующий знак сообщения - Z1. Появление знака ESC означает окончания декодирования.

Еще раз напомним, что арифметическое кодирование в настоящее время является наиболее эффективным способом статистического кодирования, позволяющим максимально приблизить среднюю длину кода знака к энтропии источника. При этом оно гораздо более требовательно к вычислительным ресурсам по сравнению с кодом Хаффмена. Кроме того, выигрыш от его применения по сравнению с кодом Хаффмена не так уж велик. Тем не менее в ряде современных программах-архиваторах этот способ применяется и в дальнейшем сфера его использования вероятно будет расширяться.

Контрольные вопросы:
1) В чем состоит идея арифметического кодирования
2) Используя пример на рис.4.11, поясните процедуру кодирования арифметическим кодом
3) За счет чего может быть повышена эффективность сжатия арифметическим кодом
4) Используя пример на рис.4.12, поясните процедуру декодирования арифметическим кодом
5) Охарактеризуйте преимущества и недостатки метода арифметического кодирования
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP