Основы теории информации и криптографии - -Учебное пособие (В.В. Лидовский)

4. лекция: сжатие информации

Сжатие информации – важнейший аспект передачи данных, что дает возможность более оперативно передавать данные. Доказывается основная теорема о кодировании при отсутствии помех. Также в лекции рассматривается метод блокирования, который используется на практике для повышения степени сжатия. Дается также математическое обоснование метода Шеннона-Фэно. Некоторое количество примеров для проверки полученных знаний

Цель сжатия - уменьшение количества бит, необходимых для хранения или передачи заданной информации, что дает возможность передавать сообщения более быстро и хранить более экономно и оперативно (последнее означает, что операция извлечения данной информации с устройства ее хранения будет проходить быстрее, что возможно, если скорость распаковки данных выше скорости считывания данных с носителя информации). Сжатие позволяет, например, записать больше информации на дискету, "увеличить" размер жесткого диска, ускорить работу с модемом и т.д. При работе с компьютерами широко используются программы-архиваторы данных формата ZIP, GZ, ARJ и других. Методы сжатия информации были разработаны как математическая теория, которая долгое время (до первой половины 80-х годов), мало использовалась в компьютерах на практике.

Сжатие данных не может быть большим некоторого теоретические предела. Для формального определения этого предела рассматриваем любое информационное сообщение длины nкак последовательность независимых, одинаково распределенных д.с.в. X_iили как выборки длины nзначений одной д.с.в. X.

Доказано1) , что среднее количество бит, приходящихся на одно кодируемое значение д.с.в., не может быть меньшим, чем энтропия этой д.с.в., т.е. ML(X) ge HXдля любой д.с.в. Xи любого ее кода.

Кроме того, Доказано2) утверждение о том, что существует такое кодирование (Шеннона-Фэно, Fano), что HX ge ML(X)-1.

Рассмотрим д.с.в. X_1и X_2, независимые и одинаково распределенные. HX_1 = HX_2и I(X_1,X_2) = 0, следовательно,

H(X_1,X_2)= HX_1+HX_2-I(X_1,X_2)=2HX_1.

Вместо X_1и X_2можно говорить о двумерной д.с.в. vec X=(X_1,X_2). Аналогичным образом для n-мерной д.с.в. vec X=(X_1,X_2,ldots,X_n)можно получить, что Hvec
X=nHX_1.

Пусть L_1(vec X)=L(vec X)/n, где vec X =
(X_1,X_2,ldots,X_n), т.е. L_1(vec X)- это количество бит кода на единицу сообщения vec X. Тогда ML_1(vec X)- это среднее количество бит кода на единицу сообщения при передаче бесконечного множества сообщений vec X. Из ML(vec X)-1 le Hvec X le ML(vec X)для кода Шеннона-Фэно для vec Xследует ML_1(vec X)-1/n le HX_1 le ML_1(vec
X)для этого же кода.

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

По выбранному значению varepsilon>0можно выбрать такое s, что если разбить все сообщение на блоки длиной s(всего будет n/sблоков), то кодированием Шеннона-Фэно таких блоков, рассматриваемых как единицы сообщения, можно сделать среднее количество бит на единицу сообщения большим энтропии менее, чем на varepsilon. Действительно, пусть vec Y=(vec Y_1,vec Y_2,ldots,vec Y_{n/s}), vec Y_1=(X_1,X_2,ldots,X_s), vec
Y_2=(X_{s+1},X_{s+2},ldots,X_{2s})и т.д., т.е. vec Y_i=(X_{s(i-1)+1},X_{s(i-1)+2},ldots,X_{si}). Тогда Hvec Y_1=sHX_1и sML_1(vec Y_1)=ML(vec Y_1) le Hvec
Y_1+1 = sHX_1+1, следовательно,

ML_1(vec Y_1) le HX_1 + 1/s,

т.е. достаточно брать s=1/varepsilon. Минимум sпо заданному varepsilonможет быть гораздо меньшим 1/varepsilon.

Пример. Пусть д.с.в. X_1,X_2,ldots X_nнезависимы, одинаково распределены и могут принимать только два значения P(X_i=0)=p=3/4и P(X_i=1)=q=1/4при iот 1 до n. Тогда

HX_i={3over4}log_2{4over3}+{1over4}log_24=2-{3over4}log_23
approx0.811 hbox{ бит/сим}.

Минимальное кодирование здесь - это коды 0 и 1 с длиной 1 бит каждый. При таком кодировании количество бит в среднем на единицу сообщения равно 1. Разобьем сообщение на блоки длины 2. Закон распределения вероятностей и кодирование для 2-мерной д.с.в. vec X=(X_1,X_2)-

smallskip
centerline{vbox{offinterlineskip
halign{&strutquadhfil#hfil& vrule#cr
$vec X$       && 00   && 01   && 10   && 11cr

oalign{hrule}
$p$            && 9/16 && 3/16 && 3/16 && 1/16cr
$code(vec X)$ && 0    &&10   && 110  && 111cr
$L(vec X)$    && 1    && 2    && 3    && 3.cr}}}
smallskip

Тогда при таком минимальном кодировании количество бит в среднем на единицу сообщения будет уже

ML_1(vec
X)=igl(1{9over16}+2{3over16}+3{3over16}+3{1over16}igr)/2=
{27over32}=0.84375,

т.е. меньше, чем для неблочного кодирования. Для блоков длины 3 количество бит в среднем на единицу сообщения можно сделать approx0.823, для блоков длины 4 - approx0.818и т.д.

Все изложенное ранее подразумевало, что рассматриваемые д.с.в. кодируются только двумя значениями (обычно 0 и 1). Пусть д.с.в. кодируются mзначениями. Тогда для д.с.в. vec Xи любого ее кодирования верно, что ML(vec X) ge Hvec X/log_2mи ML_1(vec X) ge HX_1/log_2m. Кроме того, существует кодирование такое, что ML(vec X)-1 le Hvec
X/log_2mи ML_1(vec X)-1/n le HX_1/log_2m, где n=dim(vec
X).

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

Простейшие алгоритмы сжатия информации

Метод Шеннона-Фэно состоит в следующем, значения д.с.в. располагают в порядке убывания их вероятностей, а затем последовательно делят на две части с приблизительно равными вероятностями, к коду первой части добавляют 0, а к коду второй - 1.

Для предшествующего примера получим

smallskip
dzero=hsize dividedzero12

oindenthskipdzerovbox{offinterlineskip
halign{&strutquadhfil#hfil& vrule#cr
$vec X$ && $p$ && $code(vec X)$cr

oalign{hrule}
00       && 9/16 && 0cr
01       && 3/16 && 10cr
10       && 3/16 && 110cr
11       && 1/16 && 111,cr}} 

smallskip

$ML_1(vec X)=27/32=0.84375$ бит/сим.
smallskip

Еще один пример. Код составляется после сортировки, т.е. после перестановки значений B и C.


oindenthskipdzerovbox{offinterlineskip
halign{&strutquadhfil#hfil& vrule#cr
$X$&& $p$ && $code(X)$cr

oalign{hrule}
A  && 0.4 && 0cr
B  && 0.2 && 11cr
C  && 0.4 && 10,cr}} 
vbox{hbox{$ML(X)=ML_1(X)=1.6$ бит/сим,}
hbox{$HX=log_25-0.8approx1.523$ бит/сим.}}

Метод Хаффмена (Huffman) разработан в 1952 г. Он более практичен и никогда по степени сжатия не уступает методу Шеннона-Фэно, более того, он сжимает максимально плотно. Код строится при помощи двоичного (бинарного) дерева. Вероятности значений д.с.в. приписываются его листьям; все дерево строится, опираясь на листья. Величина, приписанная к узлу дерева, называется весом узла. Два листа с наименьшими весами создают родительский узел с весом, равным сумме их весов; в дальнейшем этот узел учитывается наравне с оставшимися листьями, а образовавшие его узлы от такого рассмотрения устраняются. После постройки корня нужно приписать каждой из ветвей, исходящих из родительских узлов, значения 0 или 1. Код каждого значения д.с.в. - это число, получаемое при обходе ветвей от корня к листу, соответствующему данному значению.

Для методов Хаффмена и Шеннона-Фэно каждый раз вместе с собственно сообщением нужно передавать и таблицу кодов. Например, для случая из примера 2 нужно сообщить, что коду 10 соответствует символ C, коду 0 - A и т.д.

Построим коды Хаффмена для значений д.с.в. из двух предыдущих примеров.

smallskip
setboxzero=vbox{offinterlineskiphalign{&struthfil $#$ hfilcr

oalign{hrule}
omitvrule& vec X& 00&& 01&& 10&& 11& omitvrule height11ptcr
omitvrule& p&      xfrac9{16}&& xfrac3{16}&& xfrac3{16}&& xfrac1{16}& 
  omitvrulecr

oalign{hrule}
omitvrule& &       &&  && _0\!searrow&& swarrow_1& omitvrulecr
omitvrule& &       &&  &&& {4over16}&& omitvrulecr
omitvrule& &       &&  ,_0\!searrow&& swarrow_1&&& omitvrulecr
omitvrule& &       &&&  {7over16}&&&& omitvrulecr
omitvrule& &       ,_0\!searrow&& swarrow_1&&&&& omitvrulecr
omitvrule& &       & 1&&&&&& omitvrulecr

oalign{hrule}
omitvrule& code(vec X)& 0&& 10&& 110&& 111& omitvrule height 11ptcr

oalign{hrule}}}
setboxone=hbox{ $ML_1(vec X)=ML(vec X)/2=27/32=0.84375$ бит/сим.}
dzero=wdzero advancedzerowdone done=0pt 
ifdimhsize<dzero 
vbox{
centerline{oxzero}
reak
centerline{oxone}
}
else advancedzero-hsize done-dzero

oindenthskipdonehbox{oxzero oxone} 
fi
igskip

setboxzero=vbox{offinterlineskiphalign{&struthfil # hfilcr

oalign{hrule}
omitvrule& $X$& A   && B   && C&omitvrulecr
omitvrule& $p$& 0.4 && 0.2 && 0.4&omitvrulecr

oalign{hrule}
omitvrule& &  && $_0\!searrow$ && $swarrow_1$&omitvrulecr
omitvrule& &  && & 0.6&&omitvrulecr
omitvrule& & $,_0\!searrow$ &&$,swarrow_1$&&&omitvrulecr
omitvrule& & & 1&&&&omitvrulecr

oalign{hrule}
omitvrule& $code(X)$& 0&& 10&& 11&omitvrulecr

oalign{hrule}}}
setboxone=hbox{ $ML_1(X)=ML(X)=1.6$ бит/сим.}
ifdimdone=0pt centerline{oxzero}centerline{oxone}
else 
oindenthskipdonehbox{oxzero oxone} fi
smallskip

Упражнение 18 Вычислить ML_1(vec X)для блочного кода Хаффмена для X. Длина блока - 2 бита. д.с.в. Xберется из последнего примера.

Упражнение 19 Вычислить HXи ML(X)для кодов Хаффмена и Шеннона-Фэно для X. д.с.в. Xзадается следующим распределением вероятностей:

igskip
centerline{vbox{offinterlineskiphalign{&strutquad#cr
X&omit vrule&           1&        2&        3&        4&       5cr

oalign{hrule}
omitquad&omit vrule height2ptcr
p&omit vrule& xfrac7{18}& xfrac16& xfrac16& xfrac16& xfrac19.cr}}}
igskip