Сжатие данных. Теоретические основы сжатия данных. Методы сжатия

Лекция   11.

Глава 12. Сжатие данных

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

12.1.  Теоретические основы сжатия данных

 Характерной особенностью большинства данных является определенная избыточность, которая зависит от:

 а) типа данных (так, у видеоданных степень избыточности обычно в несколько раз больше, чем у графических, а у графических – больше, чем у текстовых);

 б) принятой системы кодирования (так, кодирование текстовой информации с помощью русского алфавита дает в среднем избыточность на 20-30% больше, чем при использовании английского языка).

 Использование избыточности: улучшение восприятия информации, особенно в неблагоприятных условиях (просмотр телепередач при наличии помех, восстановление поврежденного графического материала и т.д.); повышение качества информации при ее обработке. Избыточность следует уменьшать для хранения готовых документов, что достигается эффектом сжатия данных.

Избыточность  кодирования

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

Пусть {X, p(x)} ансамбль сообщений, Х={х₁,х₂,...,х_L}, p(x_i)-вероятность i-го сообщения. Количеством собственной информации или собственной информациейв сообщении х_i называется число I(x_i), определяемое как:

I(x_i) = -log(p(x_i)),  i = 1, 2, ..., L

Количество информации измеряется в битах

Таким образом, если мы имеем источник, выдающий с  равной вероятностью числа 0 и 1 (то есть P(0)=P(1)=1/2), то информация, приходящаяся на одну цифру,  равна  -log(1/2)  =  1 бит.

     Рассмотрим несколько примеров, в каждом из которых  будем предполагать, что вероятности всех символов одинаковы. В случае русского алфавита (33 буквы)  количество  информации, приходящейся на одну букву равно log(33)=5.044 битов, в случае латинского - log(26)=4.7, для десятичных цифр - 3.32 бита на символ.

     Как уже говорилось выше, если источник выдает цифры 0 и 1 с одинаковой вероятностью 1/2, то  количество  информации, приходящейся на одну цифру равно log(1/2)=1 биту. Предположим теперь, что цифры появляются с  различной  вероятностью,

P(0)=p, P(1)=q=1-p. Тогда количество информации, содержащейся в одной цифре, так же будет различным.  Если  P(0)=0.99  и P(1)=0.01, то количество информации,  соответствующей  цифре "0" будет равно -log(0.99)=0.0145 битов, а цифре "1" –

 -log(0.01)=6.64 бита.

Свойства информации:

1. Информация всегда неотрицательна: I ³ 0.

2. Для независимых сообщений p(x_i,y_j) = p(x_i)×p(y_j), следовательно: (свойство аддитивности)

I(x_i,y_j) = I(x_i) + I(y_j)

Математическое ожидание H(X) случайной величины I(x), определенной на ансамбле {X, p(x)}, называется энтропией этого ансамбля:

 (M-оператор математического ожидания).

Иными словами - это среднее количество собственной информации в сообщениях ансамбля Х. Энтропия рассматривается также как мера беспорядка в системе. Как известно, энтропия имеет тенденцию постоянно возрастать.

Свойства энтропии:

1. Энтропия неотрицательна: Н(Х) ³ 0.

2. Энтропия не может превышать логарифма количества сообщений: H(X) < logL.

3. Для статистически независимых сообщений: (свойство аддитивности)

H(XY) = H(X) + H(Y)

Поставим в соответствие каждому сообщению x_i в соответствие код a_i из некоторого алфавита A={a₁,a₂,...,a_L}. Тогда, стоимостью кодированиябудет называться величина

где |a|-длина кода a в битах. В случае, когда длины всех кодов одинаковы и равны logL, мы получаем: C(X)=logL. Иначе говоря, под стоимостью кодирования понимается средняя длина кодового слова в битах .

Избыточность кодирования R равна разности между стоимостью кодирования C и энтропией H: R = C - H.

Величина R для декодируемых сообщений всегда больше нуля и в пределе