7.9 Статичні методи стиснення інформації Алгоритм арифметичного стиснення.

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

Все методы сжатия информации основаны на двух стратегиях:

1. стратегия преобразования информации, где учитывается поведение сигнала на предыдущем интервале времени;

2. статистическая стратегия, которая основывается на вероятностной характеристике. Код при статистическом кодировании выбирается таким образом, чтобы более вероятные значения передавались с помощью более коротких комбинаций кода, а менее вероятные – с помощью более длинных. В результате уменьшается средняя длина кода.

Арифметический код предназначен для сжатия без потерь на основе представления данных в виде чисел нормированных в интервале от 0 до 1.

Кодирование осуществляется в несколько этапов:

1. составление таблицы кода. Каждому символу выделяется интервал чисел внутри диапазона [0, 1], который пропорциональный вероятности данного символа. Например, слово РАДИОВИЗИР:

Символ	Вероятность	Интервал
А	0.1	0 – 0.1
Д	0.1	0.1 – 0.2
В	0.1	0.2 – 0.3
И	0.3	0.3 – 0.6
З	0.1	0.6 – 0.7
О	0.1	0.7 – 0.8
Р	0.2	0.8 – 1.0

2. каскадное кодирование, заключающееся в последовательном выделении интервала для комбинации символов внутри предыдущих созданных интервалов.

Шаг	Символ	Интервал
0	начало кода	0 – 1
1	Р	0.8 – 1
2	А	0.8 – 0.82
3	Д	0.802 – 0.804
4	И	0.8026 – 0.8032
5	О	…
6	В	…
7	И	…
8	З	…
9	О	…
10	Р	…

Границы нового интервала определяются путем прибавления границ очередного кодируемого символа умноженных на вершину интервала кодируемого символа к нижней границе предыдущего символа.

(для А: [0.8 + 0.2*0 = 0.8] – [0.8 + 0.1*0.2 = 0.82])

Добавление очередного символа приводит к сужению интервала. Наиболее вероятные сужают интервал наименьше. Т.е., чем шире конечный интервал, тем больше степень сжатия можно достичь.

Декодирование осуществляется по любому числу из конечного интервала путем обратного алгоритма пересчета. Пересчет чисел в декодировании производится вычитанием из имеющегося числа нижней границы интервала декодированного символа и делением разности на величину интервала декодированного символа.

7.10 Оптимальне кодування інформації. Алгоритми формування коду Хофмана та Шенона-Фано.

Оптимальное (эффективное) кодирование

Для полного использования пропускной способности канала необходимо осуществить эффективное кодирование, которое обеспечит устранение избыточности в сообщениях, что приходят от источника. Кодирование при котором обеспечивается полное использование пропускной способности канала называется оптимальным.

Первая теорема Шеннона дает ответ на вопрос, всегда ли можно осуществить оптимальное кодирование: если есть канал с пропускной способностью С, то сообщение из любого источника с энтропией Н(х)можно закодировать так, что окажется возможным передавать эти сообщения со скоростью как угодно близкой к С/Н(х) сообщений в секунду (С двоичных единиц за секунду. Рассмотрим справедливость теоремы для двоичного канала связи.

Пусть алфавит источника сообщений создает конечную систему.

Для сообщения х_i длинна кодовой комбинации равна m_i, а вероятность ее появления Р(х_і). Количество информации что содержится в i-м сообщении равно I_xi=-logP(x_i). Пропускная способность канала будет полностью использована, если на каждыйдвоичный символ будет приходится один бит информации. Это будет в том случае, когда количество двоичных символов в кодовой комбинации будет равно количеству информации что содержится в ней. Таким образом, условием опримального кодирования является равенство.

Усреднив это сообщение повсем возможным сообщениям получим:

Меньше чем Н(х) средняя длинна сообщения быть не может.

Максимальная скорость что может быть достигнута в двоичном канале без помех равна:

Оптимальные коды:

1. Код Шеннона-Фано

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

Процесс повторяется до тех пор пока в каждой подгруппе не останется по одному сообщению. Оптимальность обеспечивается: 1) ни одна кодовая комбинация не может быть началом другой 2) так как при каждом разбиении мы приписываем к одной подгруппе ноль, а к другой единице, обеспечивается равномерное распределение нулей и единиц – необходимое условие полного использования пропускной способности канала, 3) При каждом разделении сообщений на две группы с примерно равными суммарными вероятностями, эти вероятности в сообщении каждой группы примерно вдвое меньше начальных. Поэтому сообщение х_i, что после k разбивок останется единственным в своей группе будет примерно равно Р(х_i)=1/2^k, откуда k=-log₂P(x_i). Но число знаков в кодовой комбинации (mi) равно числу разбивок, таким образом ее длинна равна:

Что отвечает условию оптимального кодирования. Пример:

При решении практических задач не всегда удается разделить таблицу на две части с одинаковой вероятностью. Этот не достаток устраняется при использовании кода Хаффмана.

2. Код Хаффмана

Аналогично к коду Шеннона-Фано при использовании кода Хаффмана строится таблица в порядке уменьшения вероятности появления сообщений. Сообщения х_n и х_n-1 соединяются в одну группу с вероятностью Р(х)=Р(х_n)+Р(х_n-1). Такое объединение повторяется до тех пор пока Р(х) не станет равно 1.

При кодировании кодом Хаффмана строится таблица

Отличие в кодировании в том, что в коде Шеннона-Фано формирование начинается со старшого (лівого) разряда. В коде Хаффмана кодове комбинации котируються начиння с младшего (правого) разряда.