Главная
страница 1

Национальный исследовательский университет
"Высшая школа экономики"

Московский институт электроники и математики



Кафедра кибернетики


Оптимальное малоизбыточное кодирование
Методические указания к курсовой работе по курсу

«Теория информационных процессов и систем»

Москва 2012

1.Цель работы.


Целью работы является построение оптимальных малоизбы­точ­ных кодов для сообщений заданного источника информации и создание на их основе программ сжатия данных.

2. Теоретические сведения.

1.1.Сжатие данных


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

• Слово алфавит означает множество символов в сжимае­мых данных. Алфавит может состоять из двух символов 0 и 1, из 256 байтов символов ASCII по 8 бит в каждом или из любых других символов.

Компрессор или кодер - программа, которая сжимает «сы­рой» исходный файл и создает на выходе файл со сжатыми данны­ми, в которых мало избыточности. Декомпрессор или декодер работает в обратном направлении. Отметим, что поня­тие ко­дера является весьма общим и имеет много значений, но по­скольку мы решаем задачу сжатия данных, то слово кодер будет означать компрессор. Термин кодек иногда использует­ся для объединения кодера и декодера.

При сжатии информации используется два принциально разных подхода: сжатие без потерь информации и сжатие с потерей информации.



Текстовые данные, например, тексты дистрибутивов прог­рамм, могут стать со­вершенно непригодными, если потеряется или изменится хоть один бит информа­ции. Такие файлы, как правило можно сжимать только методами без потери инфор­мации.

Кодирование без потерь информации возможно только при наличии избыточности. Избыточ­ность может быть устранена без потери информации.

В данной работе используются статистические алгоритмы сжатия данных. К ним относятся методы Хаффмана, Шеннона-Фано.

Основная проблема энтропийного кодирования заключает­ся в том, что оно предполагает знание распределения вероят­ностей сим­волов.

Метод неадаптивного сжатия требует априорной информа­ции о распределении вероятностей сжимаемых данных и подра­зумевает неспособность алгоритма менять свои операции, пара­метры и настройки с изменением статистических свойств сжи­маемых данных. Такой метод лучше всего работает с однотип­ными данными.

Адаптивные методы сначала тестируют «сырые» ис­ходные данные, а затем подстраивают свои параметры и/или операции в соответствии с результатом проверки. Например, если статис­тика символов для энтропийного кодирования заранее неизвестна, на помощь приходят адаптивные динамические алгоритмы, в которых распределе­ние вероятностей симво­лов меняется во времени по мере накопления статистики.

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



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

1.2.Оптимальное малоизбыточное кодирование.


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

Пусть мы имеем источник информации Х с алфавитом

Х: {x1,…,xn}

с основанием n. Сообщения источника независимы, и появля­ются с вероятностями:

{p(x1), …, p(xn)}.

Среднее количество информации на один символ последова­тель­ности будет равно энтропии



где основание логарифма m определяет единицы измерения информации.



Избыточность – это степень оптимальности использования символов данного алфавита, как носителей информации.

Избыточность источника информации R определяется как:



.

Она меняется в пределах 0 R 1 и отлична от нуля там, где появляются вероятностные ограничения на выбор сообщений.

Другая характеристика, связанная с избыточностью это экономность ИИ (), определяемая формулой:

.

Она связана с избыточностью формулой



,

и также меняется в пределах 0 1.

Пусть алфавит канала связи (он же алфавит кода):

S:{s1,s2, ..., sD},

где D – основание алфавита кода.

Для двоичного кодирования:

S:{s1=0,s2=1}, с основанием D=2.

Мы ищем способ кодирования сообщений источника Х симво­лами кода S (для двоичного кодирования нулями и единицами), при котором избыточность кода



будет минимальной. Это произойдет, если энтропия кода будет стремиться к максимальной:

H(S)  Hmax(S) = logD.

По свойству энтропии при этом все вероятности появления символов кода должны стремиться к равным величинам. Для двоичного кодирования: р(0) 1/2 и р(1) 1/2.

Избыточность такого кода будет стремиться к нулю

0.

Такие коды называют оптимальными малоизбыточны­ми кодами. Оптимальность здесь рассматривается по критерию максимума скорости передачи информации и минимума длины кодовой после­довательности.


1.3.Алгоритм двоичного кодирования по методу Шеннона – Фано.


1 шаг: все сообщения {x1,…,xn} источника информации X распола­гаются в столбец в порядке убывания их вероятностей

p(x1)> p(x2)> …> p(xn).



2 шаг: все множество сообщений делится на две по возможности наиболее равновероятные группы.

3 шаг: в качестве первого (очередного) символа кода верхней под­группе присваивается 0, а нижней подгруппе присваивается 1 (можно и наоборот, но всегда одинаково).

4 шаг: повторяем шаги 2 и 3 для каждой получившейся в результа­те разбиения подгруппы до тех пор, пока в каждой подгруппе не останется по одному сообщению.

Пример кодирования по алгоритму Шеннона – Фано:

Пусть сообщение источника имеет алфавит {x1,…,x5} из пяти сооб­щений, которые мы запишем в столбец вместе с их вероятностями.



xk p(xk) подгруппы и их коды

вероятности



x1 1/2 1/2 0

x2 1/4 1/4 1 0

x3 1/8 1/2 1/8 1 1 0

x4 1/16 1/4 1/16 1 1 1 0

x5 1/16 1/8 1/16 1 1 1 1

Код оптимален по критерию минимума символов кода на одно сообщение. Код является префиксным: ни одно более короткое кодовое слово не является началом другого более длинного кодо­вого слова. Это свойство позволяет передавать символы кода без пробелов между словами, что тоже сокращает длину кодовой последовательности.


1.4.Алгоритм кодирования Шеннона-Фано для алфавита с произвольным основанием D.


Пусть D>2 – основание алфавита кода

S = {s1, …, sD}.

Алгоритм аналогичный:

1 шаг: все сообщения {x1,…,xn} источника информации X располага­ются в столбец в порядке убывания их вероятностей{p(x1), …, p(xn)}.

2 шаг: все множество сообщений делится на D по возможности наиболее равно­вероят­ных групп.

3


1 подгруппа

2 подгруппа



D подгруппа


шаг: в качестве очередного символа кода верх­ней подгруппе присваивается s1, следу­ющей подгруппе – s2, и так далее. Пос­ледней подгруппе присваивается sD.

4 шаг: повторяем шаги 2 и 3 для каждой полу­чившейся в резуль­тате разбиения под­группы до тех пор, пока в каждой под­группе не останется по одному сообще­нию.



1.5.Алгоритм кодирования Хафмана.


Алгоритм кодирования состоит из двух этапов.

Первый этап – построение дерева кода. Дерево строится от концевых вершин к корню.

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

  2. Два сообщения с наименьшими вероятностями объединяются в подгруппу, которой ставится в соответствии вершина дерева с общей вероятностью подгруппы.

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

  4. Далее группируются две вершины с наименьшими вероятностями из нового множества вершин (шаги 2-3), пока не доходим до корня дерева, то есть не останется одна вершина с суммарной вероятностью равной 1 (проверка).

Второй этап – кодирование. Кодирование ведется в обратном порядке - от корня дерева к его концевым вершинам.

  1. Выбирается направление кодирования, которое должно быть неизменным при исполнении алгоритма.

  2. Код строится путем добавления при каждом ветвлении 0 или 1 в соответствии с выбранным направлением кодирования.

Пример кодирования по алгоритму Хафмана :

Код Хафмана также оптимален по критерию минимума симво­лов кода на одно сообщение. Код является префиксным: ни одно более короткое кодовое слово не является началом другого более длинного кодо­вого слова. Это свойство позволяет передавать символы кода без пробелов между словами, что тоже сокращает длину кодовой последовательности.

Алгоритм кодирования Хафмана для произвольного алфавита.

Если основание алфавита кода D>2, то дерево строится таким образом, чтобы в каждую вершину входило до D ветвей.


1.6.Длина кодовой последовательности.


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

Пусть nk – длина кодового слова для сообщения xk. Обозначим - среднее число символов кода, небходимых для кодирования одного сообщения. Оно равно математическому ожиданию длины кодового слова.



=M[nk]= .

Тогда ожидаемая длина кода для последовательности из N сооб­щений ИИ(при достаточно больших N) будеть равна N.

При этом избыточность кода можно определить по формуле

,

где n0=1 – минимальное число символов кода на одно сообщение.

Оптимальные по критерию минимума избыточности коды также являются оптимальными по критерию минимальной длины кода. Это свойство позволяет использовать их для сжатия информации.

1.7.Блочное кодирование


Кодирование с помощью алгоритмов Шеннона-Фано и Хафмана дает оптимальные (избыточность близка к нулю) коды, если распределение вероятностей сообщений источника информации позволяет осуществлять деление (объединение) на подгруппы с близкими друг к другу вероятностями. Если же распределение вероятностей для данного источника информации не позволяет этого сделать, необходимо кодировать не отдельные сообщения, а их объединения в блоки.

Блочное кодирова­ние позволяет уменьшить избыточность при кодировании сообщений «плохого» источника. При этом мы будем кодировать с помощью тех же алгоритмов не отдельные сообще­ния, а их объединения в пары, тройки или более длинные блоки.



x1 x2 x1 x3 x1 x1 x3...
При увеличении длины происходит выравнивание частот появления нулей и единиц на каждом месте и, следовательно, уменьшение избыточности. .

Пример блочного кодирования.

Пусть длина блока равна двум. Выпишем все возможные пары и их вероятности:



Пары вероятности коды

x1x1 4/9 4/ 9 0

x1x2 2/18 2/9 1/9 1 0 0

x1x3 2/18 1/9 1 0 1

x2x1 2/18 2/9 2/18 1 1 0 0

x3x1 2/18 5/9 2/18 1 1 0 1

x2x2 1/36 3/9 1/18 1/36 1 1 1 0 0

x2x3 1/36 1/9 1/36 1 1 1 0 1

x3x2 1/36 1/18 1/36 1 1 1 1 0

x3x3 1/36 1/36 1 1 1 1 1
Чем меньше вероятность появления блока (пары), тем длиннее код.

Среднее число двоичных символов на пару сообщений ИИ



=2,56.

Среднее число символов кода на одно сообщение ИИ .

Избыточность при кодировании пар сообщений меньше избыточ­ности при кодировании отдельных сообщений.

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


1.8.Избыточность и экономность кодов.


По определению избыточность и экономность кода:

,

где и равна для двоичного кодирования.

Энтропия символа кода равна количеству информации в нем. Кодирование не меняет количества информации, поэтому количес­тво информации в сообщении (или в блоке сообщений) источника Х равно количеству информации в последовательности кодовых символов для этого сообщения или в блока.

Но энтропия кода это среднее количество информации в одном символе кода. Её можно получить, зная - среднее количество символов кода на одно сообщение ИИ.



Тогда для двоичных кодов

экономность

и избыточность .

Для кодов с основанием D>2 формулы имеют вид:

и

При блочном кодировании, если кодирование ведется блоками длиной k символов, то количество информации в блоке равно

H(X)k.

И если - среднее количество символов кода на блок, то среднее количество символов кода на одно сообщение ИИ будет равно

.

Тогда среднее количество информации в одном символе кода будет



.

Таким образом формулы экономности и избыточности кодов Шеннона-Фано и Хафмана



и

не зависят от того, на какие блоки мы делим исходную последова­тельность сообщений.

При этом - среднее количество символов кода на одно сообщение ИИ, уменьшается с увеличением длины блока k, и код стремится к оптимальному.

1.9.Коэффициент сжатия.


Теоретический коэффициент сжатия определим как отношение количества информации (энтропии) на символ кода к количеству информации в сообщении исходного источника информации.

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

Пусть для записи одного символа ИИ используется nи двоичных. (nи=8 при кодировке ASCII или nи  log2 n, где n – основание алфавита ИИ). Тогда количество информации на один двоичный символ ИИ:

,

а количество информации на один двоичный символ кода:



.

Тогда коэффициент сжатия будет равен



.

При кодировании кодом с основанием D>2 следует учесть способ записи символов кода. Например при D=3 или D=4 для кодирования одного символа кода необходимо два двоичных символа, что приведет к удвоению числа двоичных символов на одно сообщение ИИ и



, тогда

Практический коэффициент сжатия определяется как от­ношение размеров файлов сжатого (кодированного) и исходного и текстов.

3.Указания по выполнению работы.

1.1.Определение алфавита источника информации.


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

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

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

Пусть мы имеем источник информации Х с алфавитом {x1,…,xm} из m независимых сообщений с вероятностями{p(x1), …, p(xm)}. Мы хотим учитывать при кодировании только n < m сообщений. Располага­ем сообщения по убыванию их вероятностей. Первые n сообщений x1,…,xn с наибольшими вероятностями включаем в алфавит ИИ, ос­тальные относим к маловероятной группе и заменяем служебным символом xn+1. Вычисляем вероятность попадания в эту группу

p(xn+1)=1- p(x1), …, p(xn).

При определении размерности группы символов высокой вероятности использования следует учитывать



  • «читаемость» текста, получаемого при помощи замены, то есть не должно быть потери семантической(смысловой) информации.

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

1.2.Моделирование сообщений источника информации.


Пусть в задании указан алфавит источника информации:

Х: {x1,…,xn}.

Сообщения источника независимы, и появляются с вероятностями:

{p(x1), …, p(xn)}.

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

Для моделирования символов с за­данными вероятностями появле­ния разделим отрезок [0,1] на n отрезков в соответствии с этими вероятностями.

Каждый отрезок соответствует определенному символу и его длина равна вероятности появления этого символа.

p(x1) p(x2) p(x3) p(xn)


0 a1 a2 a3 an-1 1

Значения a1, a2, a3, ... , an-1 высляются как a1=p(x1), a2 =a1+p(x2), ...

ak =ak-1+p(xk), k=2, … ,n-1.

В граничных точеах a0=0 и an=1. Тогда ширина каждого интервала

ak – ak-1 = p(xk), k=1, … ,n.

Для получения очередного i-го символа последователь­ности необходимо сгенерировать случайное число i в интервале [0,1], например с помощью стандартной функции Random, и выбрать такой символ последо­ватель­ности , в чей отрезок попало это число:



.

Повторив этот шаг N раз получим последовательность символов с требуемым распределением.

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

1.3.Отчет о выполненной работе.


Результаты выполненной работы сдаются в двух частях.

I) В электронном виде:



  1. исходные тексты программ

  2. исполняемые модули программ

  3. файлы с таблицами полученных кодов

  4. файлы исходных текстов для кодирования

  5. файлы результатов кодирования.

II) В печатном виде:

  1. задание

  2. таблица(ы) кодов

  3. результаты расчетов

  4. тестовый пример кодирования и декодирования короткого сообщения

  5. результаты сравнения объемов исходных файлов и файлов после кодировки

  6. выводы

4.Приложение .


Приложение1. Таблица вероятностей русских букв.

Пробел

о

е+ё

а, и

т, н

с

р

в

л

0.174

0.090

0.072

0.062

0.053

0.045

0.040

0.038

0.035

к

м

д

п

у

я

ы

з

ь+ъ,б

0.028

0.026

0.025

0.023

0.021

0.018

0.016

0.016

0.014

г

ч

й

х

ж

ю,ш

ц

щ,э

ф

0.013

0.012

0.010

0.009

0.007

0.006

0.004

0.003

0.002


Приложение 2. Таблица вероятностей английских букв.

Пробел

е

т

а

о

n

i

s

r

0.180

0.097

0.076

0.064

0.062

0.057

0.056

0.052

0.047

h

l

d

с

u

f

m

w

y

0.040

0.031

0.028

0.025

0.018

0.018

0.017

0.016

0.015

b

g

v

k

q

x

j

z




0.013

0.013

0.007

0.039

0.002

0.002

0.001

0.001







Смотрите также:
Методические указания к курсовой работе по курсу «Теория информационных процессов и систем»
179.04kb.
1 стр.
Методические указания по выполнению курсовой работы по курсу
106.02kb.
1 стр.
Методические указания к лабораторной работе по курсу «Механизация и технология животноводства»
189.46kb.
1 стр.
Методические указания к курсовой работе по дисциплине «Экономика организации и планирование производства» для студентов специальности «Электрический транспорт»
302.95kb.
1 стр.
Методические указания по выполнению курсовой работы Содержание и объем курсовой работы
119.44kb.
1 стр.
Методические указания к курсовой работе Волгоград 2009 (07) п 78
281.49kb.
1 стр.
Проектирование информационных систем
273.48kb.
1 стр.
Методические указания к выполнению курсовой работы для обучающихся специальности 250203. 51
236.57kb.
1 стр.
Методические указания для выполнения курсовой работы по курсу Безопасность жизнедеятельности для студентов специальности тр
1955.74kb.
6 стр.
Методические указания для студентов специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»
223.45kb.
1 стр.
Общие указания по выполнению курсовой работы по Excel и Access в соответствии с индивидуальным заданием в курсовой работе необходимо
172.5kb.
1 стр.
Методические указания и контрольные задания для студентов факультета информационных систем и технологий по учебной дисциплине интернет технологии
359.26kb.
1 стр.