Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика)




НазваниеКонспект лекций для студентов заочной формы обучения направления 080201 (Информатика)
страница4/11
Дата публикации23.05.2013
Размер0.94 Mb.
ТипКонспект
uchebilka.ru > Информатика > Конспект
1   2   3   4   5   6   7   8   9   10   11
^

2.3 Арифметическое кодирование



Алгоритмы Шеннона-Фено и Хаффмена в лучшем случае не могут кодировать каждый символ сообщения менее чем 1 битом информации. Предположим, в сообщении, состоящем из 0 и 1, единицы встречаются 10 раз чаще. Энтропия такого сообщения HX0,469 (бит/сим). В таком случае желательно иметь схему кодирования, позволяющую кодировать символы сообщения менее чем 1 битом информации. Одним из лучших алгоритмов такого кодирования информации является арифметическое кодирование.
По исходному распределению вероятностей д.с.в. строится таблица, состоящая из пересекающихся в граничных точках отрезков для каждого из значений д.с.в. Объединение этих отрезков должно образовывать интервал [0;1], а их длины пропорциональны вероятностям кодируемых значений.

Алгоритм кодирования заключается в построении отрезка, однозначно определяющего конкретную последовательность символов сообщения. По мере поступления входных символов отрезок сообщения сужается. Отрезки строятся следующим образом. Если имеется отрезок сообщения длиной n-1, то для построения отрезка сообщения длиной n символов, предыдущий интервал разбивается на столько частей, сколько значений включает алфавит источника. Начало и конец каждого нового интервала сообщения определяется путем прибавления к началу предыдущего интервала произведения его ширины на значения границ отрезка, соответствующего текущему новому символу (по исходной таблице вероятностей символов и назначенных им интервалов). Затем из полученных отрезков выбирается тот, который соответствует конкретной последовательности символов сообщения длиной n.

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

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

Принципиальное отличие арифметического кодирования от методов сжатия Шеннона-Фено и Хаффмена в его непрерывности, т.е. в отсутствии необходимости блокирования сообщения. Эффективность арифметического кодирования растёт с ростом длины сжимаемого сообщения, однако требует больших вычислительных ресурсов.

Поясним идею арифметического кодирования на конкретных примерах.
Пример 1 Закодируем текстовую строку «МАТЕМАТИКА» по алгоритму арифметического кодирования.

Алфавит кодируемого сообщения содержит следующие символы: {М, А, Т, Е, И, К}.

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

Символы в таблице символов и интервалов можно располагать в любом порядке: по мере их появления в тексте, в алфавитном или по возрастанию вероятностей – это не принципиально. Результат кодирования может быть разным, но эффект будет одинаковым.

Таблица 2.7

Символ

Вероятность

Интервал

М

0,2

[0; 0,2)

А

0,3

[0,2; 0,5)

Т

0,2

[0,5; 0,7)

Е

0,1

[0,7; 0,8)

И

0,1

[0,8; 0,9)

К

0,1

[0,9; 1,0)


После просмотра первого символа сообщения «М» кодер сужает исходный интервал [0; 1) до нового [0; 0,2). Таким образом, после кодирования первой буквы результат кодирования будет находиться в интервале [0; 0,2).

Следующий символ «А» кодируется подынтервалом внутри интервала, выделенного для предыдущих символов, сужая его до [0,04; 0,1) - верхняя и нижняя границы нового интервала определяются как начало предыдущего интервала плюс произведение ширины этого интервала на значения границ отрезка, отвечающего текущему символу (табл. 2.7): lowi=0+0,20,2=0,04; high=0+0,50,2=0,1).

Следующий символ, поступающий на вход кодера, – это буква «Т» (символу «Т» соответствует отрезок [0,5; 0,7) в таблице кодера (табл. 2.7)). Применительно к уже имеющемуся рабочему интервалу сообщения, состоящего из предыдущих букв, новый интервал будет [0,07; 0,082) (low=0,04+0,60,5=0,07; high=0,04+0,60,7=0,082) и т. д.

Таким образом, последовательность интервалов, соответствующих кодируемому сообщению, будет следующей (табл. 2.8).

Таблица 2.8

^ Символ – интервал

Интервал сообщения

Ширина интервала

М - [0; 0,2)

[0; 0,2)

0,2

А - [0,2; 0,5)

[0,04; 0,1)

0,6

Т - [0,5; 0,7)

[0,07; 0,082)

0,012

Е - [0,7; 0,8)

[0,0784; 0,0796)

0,0012

M - [0; 0,2)

[0,0784; 0,07864)

0,00024

А - [0,2; 0,5)

[0,078448; 0,07852)

0,7210-4

Т - [0,5; 0,7)

[0,078484; 0,0784984)

0,14410-4

И - [0,8; 0,9)

[0,07849552; 0,07849696)

0,14410-5

К - [0,9; 1,0)

[0,078496816; 0,07849696)

0,14410-6

А - [0,2; 0,5)

[0,0784968448; 0,078496888)

0,43210-7


Результат кодирования сообщения «МАТЕМАТИКА» - это вещественное число, принадлежащее интервалу [0,0784968448; 0,078496888). Целое число, деленное на минимальную степень 2, принадлежащее данному отрезку, - это . Двоичный 24-разрядный код числа ^ 131625910=0001010000011000010111112. Этот код и будет арифметическим кодом сообщения

Code(МАТЕМАТИКА)=000101000001100001011111.

Пример 2 Д.с.в. может принимать только два значения 0 и 1 с вероятностями 2/3 и 1/3. Построить арифметический код для сообщений длиной 3.
^

Таблица построения кодов для всех возможных таких сообщений следующая (табл. 2.9).


Таблица 2.9

^ Сообщения и интервалы

Код

pi

1

(2/3; 1]


11


(8/9; 1]

111

(26/27; 1]  31/32

11111

1/27

110

(8/9; 26/27]  15/16

1111

2/27


10


(2/3; 8/9]

101

(22/27; 8/9]  7/8

111

2/27

100

(2/3; 22/27]  3/4

11

4/27

0

(0; 2/3]


01


(4/9; 2/3]

101

(16/27; 2/3]  5/8

101

2/27

100

(4/9; 16/27]  1/2

1

4/27


00


(0; 4/9]

001

(8/27; 4/9]  3/8

011

4/27

000

(0; 8/27]  1/4

01

8/27



Средняя длина кода на единицу сообщения

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

Set low to 0.0

Set high to 1.0

While there are still input symbols do

get an input symbol

code_range = high - low.

high = low + code_range*high_range(symbol)

low = low + code_range*low_range(symbol)

End of While

output low
Декодеру, как и кодеру, известна таблица распределения отрезков, выделенных символам алфавита источника. Декодирование арифметического кода сообщения происходит по следующему алгоритму:
Шаг 1 По таблице отрезков символов алфавита определяется интервал, содержащий текущий код сообщения – и по этому интервалу из той же таблицы однозначно определяется символ исходного сообщения. Если это маркер конца сообщения, то конец, иначе – переход к шагу 2.
Шаг 2 Из текущего кода вычитается нижняя граница содержащего его интервала. Полученная разность делится на длину этого интервала. Полученное значение считается новым текущим кодом. Переход к шагу 1.
Рассмотрим пример декодирования сообщения, сжатого по алгоритму арифметического кодирования.
Пример 3 Длина исходного сообщения 10 символов. Двоичный арифметический код сообщения 0001010000011000010111112=131625910.

Вещественное число, принадлежащее интервалу, однозначно определяющему закодированное сообщение, . Это число и будет текущим кодом сообщения.

По исходной таблице значений д.с.в. и назначенных им интервалов (таблица 2.7) определяется отрезок, которому принадлежит это число, - [0; 0,2), и соответственно, что первый закодированный символ – это «М».

Исключим из результата кодирования влияние теперь уже известного первого символа «М»: для этого вычтем из текущего кода нижнюю границу отрезка раскодированного символа сообщения и разделим полученный результат на ширину этого отрезка, т.е. следующим декодируемым числом будет . Это число принадлежит отрезку [0,2; 0,5), отведенному символу «А», следовательно, вторым символом декодированной последовательности будет «А».

Исключим из интервала [0,2; 0,5) влияние буквы «А». Для этого вычтем из текущего кода нижнюю границу этого интервала и разделим на его ширину: . Результат принадлежит отрезку [0,5; 0,7) символа «Т» - это очередной декодируемый символ.

Исключив из результата декодирования влияние буквы «Т», получим . Результат принадлежит отрезку буквы «Е» [0,7; 0,8) и т. д., пока не декодируем все символы (табл. 2.10).

Таблица 2.10

^ Декодируемое число

Символ на выходе

Интервал

Ширина интервала

0,07849687

М

[0; 0,2)

0,2

0,39248435

А

[0,2; 0,5)

0,3

0,6416145

Т

[0,5; 0,7)

0,2

0,7080725

Е

[0,7; 0,8)

0,1

0,080725

М

[0; 0,2)

0,2

0,403625

А

[0,2; 0,5)

0,3

0,67875

Т

[0,5; 0,7)

0,2

0,89375

И

[0,8; 0,9)

0,1

0.9375

К

[0,9; 1,0)

0,1

0.375

А

[0,2; 0,5)

0,3


Описанная процедура декодирования арифметического кода сообщения:

get encoded number

Do

find symbol whose range straddles the encoded number

output the symbol

range = high_range(symbol)- low_range(symbol)

subtract low_range(symbol) from encoded number

divide encoded number by range

until no more symbols

Выше описана основная идея арифметического кодирования информации, однако его практическая реализация несколько сложнее.

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

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

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


^

2.4 Адаптивный алгоритм Хаффмена с упорядоченным деревом



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

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

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

В начале работы алгоритма дерево содержит только один специальный символ , всегда имеющий частоту 0. Он необходим для занесения в дерево нового символа, который передается непосредственно после . При появлении нового символа кодовое дерево перестраивается: справа от узла добавляется новый лист, и затем, если необходимо, дерево упорядочивается. Левые ветви кодового дерева помечаются 0, а правые – 1.
Приведем пример упорядоченного таким образом дерева (рис.2.9  а). Добавим в это дерево две буквы «А», тогда узлы «A» и «D» должны поменяться местами (рис.2.9  б). Если добавить еще две буквы «А», то необходимо будет поменять местами сначала узел «А» и узел, родительский для «D» и «В», а затем узел «Е» и узел-брат «Е» (рис.2.9  в-г).






а) б)







B

D

в) г)

Рисунок 2.9
Пример 1 Построим адаптивный код Хаффмена для сообщения АССВСАААВС.

Таблица кодирования данного сообщения представлена таблицей 2.11, соответствующие изменения кодового дерева показаны на рис. 2.10.

Условимся в дальнейшем символом в кавычках обозначать двоичный восьмибитный код символа по таблице ASCII+.

Таблица 2.11


Входные

данные

Код

Длина

кода

Номер

дерева

А

‘A’

8

1

С

0’C’

9

2

С

01

2

3

В

00’B’

10

4

С

1

1

5

А

01

2

6

А

01

2

7

А

11

2

8

В

101

3

9

С

11

2










=41



1)

2)

3) 4) 5)

6) 7)

8) 9)




Рисунок 2.10
Длина сжатого сообщения LАдапт.Хаффмена = 41 (бит).

Длина несжатого сообщения в коде ASCII+ LASCII+ =80 (бит).
Пример 2 Распаковать сообщение ‘X’0‘F’00‘Z’1111101100‘A’111010, закодированное по адаптивному алгоритму Хаффмена. Вычислить длину кода сжатого сообщения и несжатого сообщения в коде ASCII+.

Процесс декодирования иллюстрируется таблицей 2.12 и рис. 2.11.

Таблица 2.12

Входной

код

Символ

Длина

кода

Номер

дерева

X

X

8

1

0‘F

F

9

2

00‘Z

Z

10

3

11

F

2

4

11

X

2

5

101

Z

3

6

100‘A

A

11

7

11

X

2

8

10

F

2

9

10

F

2










=51




1)
2)


3) 4) 5)


5)

6) 7)

8
9
) 9)




Рисунок 2.11

Длина сжатого сообщения LАдапт.Хаффмена =51 (бит).

Длина сообщения в коде ASCII+ LASCII+ =80 (бит).

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

Кодирование Хаффмена характеризуется минимальной избыточностью при условии кодирования каждого символа сообщения кодовой комбинацией из алфавита {0, 1} и обеспечивает достаточно высокое качество сжатия информации.

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

КОНТРОЛЬНЫЕ ВОПРОСЫ


  1. Что такое экономное кодирование информации? С какой целью оно производится?

  2. Какие способы используются для представления кодов?

  3. Что такое равномерные и неравномерные коды? Какие достоинства использования равномерного кодирования информации? В каких случаях оптимальны неравномерные коды?

  4. Для чего используются неравномерные коды?

  5. Что такое избыточность кода? Как она измеряется?

  6. Какое кодирование информации называется статистическим? Какие алгоритмы относятся к статистическим?

  7. Что такое оптимальное кодирование информации? Какой критерий оптимальности статистических кодов?

  8. Какие коды относятся к кодам «без памяти»?

  9. Какие коды являются префиксными? Что такое вектор Крафта? Как определяется неравенство Крафта? В чем заключается условие оптимальности префиксных кодов?

  10. В чем состоит методика построения оптимального кода Шеннона-Фано?

  11. В чем состоит методика построения оптимального кода Хаффмена?

  12. В чем достоинства и недостатки использования оптимального кодирования Шеннона-Фано и Хаффмена?

  13. Чем определяется верхний предел сжатия информации? Каковы пределы сжатия при использовании оптимального кодирования Шеннона-Фано и Хаффмена?

  14. Какие коды характеризуются «наличием памяти»?

  15. Какие коды называются блочными? Чем определяется порядок блочного кода?

  16. В чем состоит метод блокирования сообщений? Как строится блочный код Хаффмена?

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

  18. Как происходит кодирование и декодирование данных по арифметическому алгоритму?

  19. В чем заключается адаптивный алгоритм Хаффмена? Что такое упорядоченное дерево Хаффмена? Каковы принципы его построения? Как осуществляется кодирование/декодирование поступающих входных данных?

  20. В чем преимущества адаптивного алгоритма Хаффмена в сравнении с неадаптивными методами? Каковы его достоинства и недостатки?
1   2   3   4   5   6   7   8   9   10   11

Похожие:

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций 2007 Экология. Конспект лекций. Для студентов специальностей...
Экология. Конспект лекций. Для студентов специальностей 080201 «Информатика», 090220 «Оборудование химических производств и предприятий...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по дисциплине “политэкономия” для студентов 050107 заочной формы обучения
Конспект лекций по дисциплине “Политэкономия” для студентов 050107 заочной формы обучения/ Разраб. Овечкина Е. А. Северодонецк, 2000....

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций в схемах по дисциплине «организация труда менеджера»
Конспект лекций в схемах по дисциплине «Организация труда менеджера» (для студентов (для студентов 4 курса дневной и 3 курса заочной...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconХарьковская национальная академия городского хозяйства
Конспект лекций для студентов 1-го курса дневной и заочной формы обучения образовательно-квалификационного уровня бакалавр, направления...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций в схемах по дисциплине «управление персоналом»
Конспект лекций в схемах по дисциплине «Управление персоналом» (для студентов 5 курса направления подготовки 0502 “Менеджмент” специальности...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по курсу Начертательная геометрия
Конспект лекций по курсу начертательная геометрия (для студентов заочной формы обучения всех специальностей академии). Сост. Лусь...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций по курсу «Организация производства»
Конспект лекций по курсу «Организация производства» (для студентов и слушателей заочной формы обучения фпоизо специальностей 050100...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconКонспект лекций для студентов бакалавратуры 0902 «Инженерная механика» заочной формы обучения
Сила давления жидкости на криволинейные цилиндрические поверхности

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconМетодические указания для выполнения лабораторных, самостоятельных...
«Информатика и компьютерная техника» (для студентов 1-го и 2-го курсов заочной формы обучения образовательно-квалификационного уровня...

Конспект лекций для студентов заочной формы обучения направления 080201 (Информатика) iconА. Г. Шкаев твердотельная электроника
Конспект лекций предназначен для студентов очной, очно-заочной и заочной форм обучения

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<