13524

Методы сжатия информации

Лабораторная работа

Информатика, кибернетика и программирование

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

Русский

2013-05-11

654 KB

128 чел.

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

«Методы сжатия информации»

Введение

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

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

В процессе выполнения данной лабораторной работы исследуются три метода сжатия информации: RLE, Шеннона-Фано и Хаффмана.


Лабораторная работа

Методы сжатия информации

  1.  Подготовка к работе

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

  1.  Контрольные вопросы

  1.  Перечислите известные Вам методы сжатия информации без потерь.
    1.  В чем состоит отличие методов сжатия с потерями и без потерь?
    2.  Сколько бит в управляющем байте отводят для указания числа повторяющихся байтов при сжатии методом кодирования длин серий?
    3.  О чем говорит равенство единице старшего бита в управляющем байте при сжатии методом кодирования длин серий?
    4.  Перечислите известные Вам архиваторы.
    5.  Целесообразно ли выполнять сжатие файлов формата JPEG, MP3, MPEG?
    6.  Рисунок какого формата будет сжат сильнее BMP или JPEG?
    7.  Какой код является неравномерным: RLE или Хаффмана?
    8.  Что называется кодом?
    9.  Чем отличаются алгоритмы построении кодов Шеннона-Фано и Хаффмана?


  1.  Задания на выполнение лабораторной работы

  1.  Задание 1. Выполнить сжатие информации методом RLE

Выполнить вручную кодирование сообщения методом RLE. В качестве исходной фразы взять текст из табл. 3.1. С помощью таблицы CP-1251 (см. Приложение 1) перевести символы заданной фразы в десятичные числа, а затем десятичные числа перевести в двоичные. Выполнить сжатие информации, вычислить контрольные суммы и коэффициент сжатия.

Табл. 3.1.

Вар

Текст

Вар

Текст

1

Кредитка  2235555666122

17

Ккккктттттттто тттттам?

2

Паспорт  25700000333215

18

Длинношеее животное

3

ИНН 78888255555488856

19

Урааааааааааааа в атаку

4

Пароль 177775556666612

20

Долг 3255566667444444

5

Пароль abcWWWWZZZq

21

Телефон 8904222211111

6

Автомобиль 78999994441

22

Ауууууууу заблудились

7

Алло это 4565555544488

23

Свидетельство 22263333

8

Удостоверение 265444111

24

Возраст 1000000000 лет

9

Счет 95122244445333333

25

Заработали 522211112

10

Касса 1478885555233333

26

До дембеля 60440000 с

11

Прошло 11100002 секунд

27

Кредитка  235556999922

12

Пролетели 82223333352 м

28

ИНН 8825577777488856

13

Вес 1597555553333331 кг

29

Шифр 159222666644444

14

Цена 2598888666611 коп

30

Улов 98544477778555 кг

15

Мощность 3574444555 Вт

31

Пароль RRWQQQQ6666

16

Выиграл 10000555 рублей

32

Пароль 778SSЫЫzzzzN

  1.  Задание 2. Выполнить сжатие информации методом Шеннона-Фано

Используя фразу из табл. 3.1, построить кодовое дерево и определить коэффициент сжатия методом Шеннона-Фано

  1.  Задание 3. Выполнить сжатие информации методом Хаффмана

Используя фразу из табл. 3.1, построить кодовое дерево и определить коэффициент сжатия методом Хаффмана

  1.  
    Задание 4. Исследовать эффективность сжатия файлов различных форматов

С помощью стандартного архиватора (WinZip, WinRar, 7-Zip и т.п.) выполнить сжатие различных документов,  тип которых указан в таблице 3.4.1

Табл. 3.4.1

Документ

Расширение

Объем файла до архивации, Кбайт

Объем файла после архивации, Кбайт

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

Текст

.doc

Фотография

.jpg

Рисунок

.bmp

Видео

.avi

Звук

.mp3

В качестве текстового документа нужно взять файл, который не содержит рисунков. Число символов должно быть более 3000 знаков.

Фотографии нужно взять на сайте samara.psati.ru в соответствии с вариантом  (таблица 3.4.2.). Следует взять одну фотографию из указанного раздела.

Табл. 3.4.2

Вар

Раздел

Вар

Раздел

1

Администрация города

17

Музеи, выставки

2

Архивные материалы

18

Набережные, пляжи

3

Банки

19

Ночной город

4

Водоёмы

20

Окраины города

5

Вокзалы

21

Памятники и скульптуры

6

Гостиницы

22

Парки, сады, скверы

7

Дворцы, дома

23

Площади

8

Деревянный город

24

Растительный мир

9

Животный мир

25

Рестораны, кафе, бары

10

Заводы, фабрики

26

Сооружения

11

Закаты, рассветы

27

Спортивные сооружения

12

Кинотеатры

28

Театры, концертные залы

13

Культовые сооружения

29

Торговые центры

14

Массовые мероприятия

30

Транспорт

15

Медицинские учреждения

31

Учебные заведения

16

Улицы, проспекты

32

Фонтаны


В качестве рисунка формата
BMP нужно взять изображение флага государства в соответствии с таблицей 3.4.3.

Табл.3.4.3

Вариант

Страна

Вариант

Страна

1.

Австралия

17.

Германия

2.

Австрия

18.

Греция

3.

Азербайджан

19.

Испания

4.

Албания

20.

Италия

5.

Алжир

21.

Казахстан

6.

Ангола

22.

КНР

7.

Андорра

23.

Нидерланды

8.

Аргентина

24.

Норвегия

9.

Армения

25.

Польша

10.

Афганистан

26.

Россия

11.

Белоруссия

27.

Румыния

12.

Бельгия

28.

США

13.

Болгария

29.

Украина

14.

Бразилия

30.

Уругвай

15.

Великобритания

31.

Франция

16.

Венгрия

32.

Япония

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

В качестве звукового файла используйте своё любимое музыкальное произведение.


4. Методические указания

4.1. Методические указания к заданию 3.1

Несмотря на то, что объемы внешней памяти ЭВМ постоянно растут, потребность в более экономном кодировании информации не уменьшается. Это объясняется тем, что сжатие необходимо не только для экономии места в памяти, но и для быстрой передачи информации по Сети.

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

Сжатие информации (архивация) — это такое преобразование информации, при котором объем файла уменьшается, а количество информации, содержащейся в архиве, остается прежним.

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

Чем больше величина Kc, тем выше степень сжатия информации.

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

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

Первая идея, основанная на учете частот появления символов в тексте, была разработана Клодом Шенноном и независимо от него Робертом Фано, а затем в 1952 г. развита Дэвидом Хаффманом - аспирантом Массачусетского технологического института при написании им курсовой работы.  Идея базируется на том факте, что в обычном тексте частоты появления различных символов неодинаковые.

Вторая основная идея сжатия состоит в учете того факта, что в файлах часто встречаются несколько подряд идущих одинаковых байтов, а некоторые последовательности байтов повторяются многократно. При архивации такие места файла можно заменить командами вида «повторить данный байт n раз» или «взять часть данных длиной k байтов, которая встречалась m байтов назад». Такой алгоритм архивации носит имя RLE (Run Length Encoding — кодирование путем учета повторений или кодирование длин серий).

Рассмотрим детально метод сжатия RLE.

Упакованная методом RLE последовательность состоит из управляющих байтов, за которыми следуют один или несколько байтов данных. При этом если старший бит управляющего байта равен 1, то следующий за ним байт данных нужно повторить при декодировании столько раз, сколько указано в оставшихся 7 битах управляющего байта.

Например, управляющий байт 10001001 говорит, что следующий за ним байт нужно повторить 9 раз, так как 10012 = 910.

Если старший бит управляющего байта равен 0, то при декодировании нужно взять несколько следующих байтов без изменений. Число байтов, которые берутся без изменений, указывается в оставшихся 7 битах. Например, управляющий байт 00000011 говорит, что следующие за ним 3 байта нужно взять без изменений.

Рассмотрим пример сжатия методом RLE.

Пусть дана некоторая  последовательность из 12 байтов:

11111111 11111111 11111111 11111111 11111111 11110000

00001111 11000011 10101010 10101010 10101010 10101010.

В начале исходной двоичной последовательности 5 раз повторяется байт 11111111. Чтобы упаковать эти 5 байтов, нужно записать сначала управляющий байт 10000101, а затем повторяемый байт 11111111. В результате сжатия этого фрагмента данных выигрыш составит 3 байта. Далее идут 3 разных (неповторяющихся) байта: 11110000 00001111 и 11000011. Чтобы их «упаковать», нужно записать управляющий байт 00000011, а затем указать эти 3 неповторяющихся байта. В результате архивации этого фрагмента двоичной последовательности получается увеличение объема архива на 1 байт. Далее в последовательности 4 раза повторяется байт 10101010. Для архивации этого фрагмента двоичных данных нужно сформировать управляющий байт 10000100 и записать повторяемый байт 10101010. Сжатие последнего фрагмента даст выигрыш 2 байта.

В результате такой архивации получена новая последовательность  данных (архив), состоящая из 8 байтов:

10000101 11111111 00000011 11110000

00001111 11000011 10000100 10101010.

Таким образом, 12 байт исходной двоичной последовательности удалось сжать до 8 байт.

Пример.

Выполним сжатие сообщения методом RLE. Текст сообщения:

ИНН 222221333.

Фраза

Десятичный код,

таблица CP-1251

Двоичный код

Архив

И

200

11001000

00000001

Н

205

11001101

11001000

Н

205

11001101

10000010

32

00100000

11001101

2

50

00110010

00000001

2

50

00110010

00100000

2

50

00110010

10000101

2

50

00110010

00110010

2

50

00110010

00000001

1

49

00110001

00110001

3

51

00110011

10000011

3

51

00110011

00110011

3

51

00110011

КС двоичная

10010000B

КС шестнадцатеричная

90H

Для упрощения проверки результата сжатия были вычислены контрольные суммы (КС) в двоичной и шестнадцатеричной системах счисления.

Коэффициент сжатия в данном случае составил:

Таким образом, тринадцать байт исходного текста сжаты до двенадцать байт.


4.2. Методические указания к заданию 3.2

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

Рассмотрим принцип построения таких кодов методами Шеннона-Фано и Хаффмана [2, 3]. Оба этих кода основываются на статистических свойствах источника сообщений и ставят в соответствие часто встречающимся символам алфавита короткие кодовые комбинации. Из-за того, что разным символам алфавита соответствуют кодовые комбинации разной длины, такие коды называют неравномерными.

В качестве примера возьмем сообщение: «ИНН 631300151031». Данный текст содержит избыточность, устранить которую с помощью метода RLE невозможно. Избыточность можно определить по формуле:

,

где - энтропия сообщения;

- длина кодовой комбинации при равномерном кодировании.

Энтропия сообщения вычисляется по формуле:

,

где - объем алфавита источника;

- относительная частота или вероятность появления символа в сообщении.

Относительная частота (вероятность) встречаемости символа определяется как отношение абсолютной частоты появления символа в сообщении к общей длине сообщения:

,

где  - абсолютная частота (частотность) встречаемости i-ого символа алфавита источника;  - объем алфавита источника.

В данном случае энтропия сообщения равна:

бит/символ,

где  - относительная частота появления символа «1»;

- относительная частота появления символов «0» и «3»;

- относительная частота появления символа «Н»;

- относительная частота появления символов «5», «6», «И», « ».

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

,

где - объем алфавита источника;

- функция округления аргумента до ближайшего целого значения, большего, чем .

В данном примере бит/символ.

Избыточность сообщения при кодировании равномерным кодом равна:

.

На первом этапе построения кода Шеннона-Фано формируется модель сообщения – таблица абсолютных частот встречаемости символов.

Символ

Частота встречаемости

Символ

Частота встречаемости 

1

4

5

1

0

3

6

1

3

3

И

1

Н

2

Пробел

1

Для получения кодовых комбинаций строится кодовое дерево. При построении кода Шеннона-Фано дерево строится от корня к листьям. В качестве корня используется множество всех символов алфавита сообщения (рис. 1), упорядоченное по частоте встречаемости символов. Число сверху равно суммарной частоте встречаемости символов множества в исходном сообщении.

Рис. 1. Корень кодового дерева Шеннона-Фано

Затем множество символов делится на два подмножества так, чтобы новые множества имели равные, насколько это возможно, суммарные частоты встречаемости входящих в них символов. Эти подмножества соединяются с корнем дерева ветвями, становясь потомками. Левой ветви дерева присваивается бит 1, а правой ветви – 0 (рис. 2).

Рис. 2. Деление на подмножества

Полученные подмножества также рекурсивно делятся, пока не будут сформированы листья дерева – отдельные символы сообщения (рис. 3).

Кодовые комбинации (на рис. 3 они указаны в кавычках под соответствующими листьями) получаются при движении от корня дерева к кодируемому символу-листу путем сбора бит, присвоенных пройденным ветвям дерева. Запись кодовой комбинации ведут в направлении от старших бит к младшим. Например, при кодировании символа «3» сначала следует пройти по правой ветви к множеству {3, Н, 5, 6, И, Пробел } (к кодовой комбинации добавляется бит 0). Затем нужно пройти по левой ветви к множеству {3, Н} (к кодовой комбинации добавляется бит 1). Наконец, нужно пройти по левой ветви, чтобы достичь листа «3». Таким образом, получена кодовая комбинация «011».

Рис. 3. Дерево кода Шеннона-Фано

При декодировании биты считываются из входного потока и используются, как указатели направления движения по кодовому дереву от корня к искомому листу. При достижении листа найденный символ записывается в выходной поток, а движение по кодовому дереву снова начинают от корня. Например, декодирование комбинации «010» происходит следующим образом. Из потока считывается бит 0, следовательно, нужно пройти по правой ветви от корня дерева к узлу {3, Н, 5, 6, И, }. Следующий бит единичный, что требует пройти по левой ветви к множеству {3, Н}. Наконец, следующий бит 0 приводит декодер по правой ветви к листу «Н».

В следующей таблице приведены все разрешенные комбинации полученного кода Шеннона-Фано.

Символ

Кодовая комбинация

Символ

Кодовая комбинация

1

11

5

0011

0

10

6

0010

3

011

И

0001

Н

010

0000

Закодированное сообщение будет иметь вид: «000101001000000010011110111010110011111001111». Общая длина закодированного сообщения составляет 45 бит.

Средняя длина кодовой комбинации равна:

бит/символ.

Избыточность сообщения после применения кода Шеннона-Фано снизилась до значения:

.

Несложно убедиться, что применение кода Шеннона-Фано позволило существенно уменьшить избыточность сообщения. Однако актуальным остается вопрос, достигнута ли минимально возможная избыточность, т. е. оптимален ли полученный код.

4.3. Методические указания к заданию 3.3

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

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

Рис. 4. Первый этап формирования дерева Хаффмана

На втором шаге аналогично объединим общим родителем узлы, соответствующие символам «5» и «6». На третьем шаге, имея несколько возможностей для объединения узлов, выберем сформированные на первых двух шагах узлы с весом 2 (рис. 5).

Рис. 5. Третий шаг построения дерева Хаффмана

Продолжая действовать аналогично, получаем итоговое дерево (рис. 6).

Рис. 6. Дерево Хаффмана

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

Символ

Кодовая комбинация

Символ

Кодовая комбинация

1

11

5

0011

0

01

6

0010

3

101

И

0001

Н

100

0000

Закодированное сообщение выглядит так: «000110010000000010101111010101110011110110111». Общая длина закодированного сообщения равна 45 бит, средняя длина кодовой комбинации бит/символ. Избыточность сжатого сообщения равна:

.

Средняя длина и избыточность такие же, как у кода Шеннона-Фано

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

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

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

Список литературы

1. Алексеев А.П. Информатика 2007.– СОЛОН-ПРЕСС, 2007. – 608 с.

2. Shannon C. E. «A mathematical theory of communication», Bell Sys. Tech. Jour., vol. 27, pp. 379-423; July, 1948.

3. Huffman D. A., «A method for the construction of minimum-redundancy codes», Proc. Inst. Radio Engineers, vol. 40, no. 9, pp. 1098-1101, Sep. 1952.


Приложение 1

Таблица СР-1251

пробел

32

!

33

"

34

#

35

$

36

%

37

&

38

'

39

(

40

)

41

*

42

+

43

,

44

-

45

.

46

/

47

0

48

1

49

2

50

3

51

4

52

5

53

6

54

7

55

8

56

9

57

:

58

;

59

<

60

=

61

>

62

?

63

@

64

A

65

B

66

C

67

D

68

E

69

F

70

G

71

H

72

I

73

J

74

K

75

L

76

M

77

N

78

O

79

P

80

Q

81

R

82

S

83

T

84

U

85

V

86

W

87

X

88

Y

89

Z

90

[

91

\

92

]

93

^

94

_

95

`

96

a

97

b

98

c

99

d

100

e

101

f

102

g

103

h

104

i

105

j

106

k

107

l

108

m

109

n

110

o

111

p

112

q

113

r

114

s

115

t

116

u

117

v

118

w

119

x

120

y

121

z

122

А

192

Б

193

В

194

Г

195

Д

196

Е

197

Ж

198

З

199

И

200

Й

201

К

202

Л

203

М

204

Н

205

О

206

П

207

Р

208

С

209

Т

210

У

211

Ф

212

Х

213

Ц

214

Ч

215

Ш

216

Щ

217

Ъ

218

Ы

219

Ь

220

Э

221

Ю

222

Я

223

а

224

б

225

в

226

г

227

д

228

е

229

ж

230

з

231

и

232

й

233

к

234

л

235

м

236

н

237

о

238

п

239

р

240

с

241

т

242

у

243

ф

244

х

245

ц

246

ч

247

ш

248

щ

249

ъ

250

ы

251

ь

252

э

253

ю

254

я

255

 


 

А также другие работы, которые могут Вас заинтересовать

65080. О местоположении Сарая (первой столицы Золотой Орды) 30.5 KB
  Город Сарай был основан Батыем в низовьях Волги в 1250-е гг., окончательное запустение города относится к концу XV в. По всей видимости столица в XIV в. была перенесена (ни одно из средневековых городищ Нижнего Поволжья не существовало столь длительное время - с середины XIII в. до конца XV в.).
65083. Этнонимы народов золотоордынского Поволжья по данным персидских источников XIII - первой половины XV века 52.5 KB
  Обширный Поволжский регион в силу своего выгодного географического положения с давних времен занимал особое место в исторических судьбах Евразии. Являясь связующим звеном между Востоком и Западом, он стал ареной активных межэтнических контактов...
65086. ОЦЕНКА РЕЛИГИОЗНО-ПОЛИТИЧЕСКОЙ ДЕЯТЕЛЬНОСТИ ЦЗОНКАБЫ ЛОБЕАН-ДАГБЫ В ТРУДАХ Г.Ц. ЦЫБИКОВА И Б.Я. ВЛАДИМИРЦОВА 34.5 KB
  Цыбиков пользуется термином реформаторство применительно к деятельности Цзонкабы однако вместе с тем уточняет что он подразумевает под ним объясняя свое понимание сущности рассматриваемой проблемы.
65087. УКЕК В КУЛЬТУРНОМ ПРОСТРАНСТВЕ НИЖНЕГО ПОВОЛЖЬЯ 60 KB
  На южной окраине Саратова находятся остатки золотоордынского города Укека возникшего в конце 40 начале 50х гг. И в настоящее время города в отдельных регионах имеют значительные особенности. Многие считают что города у кочевников возникали сначала искусственно как военно-административные центры...
65088. Никудерийская орда как фактор чагатайской истории (1270-1330-е гг.) 99.5 KB
  Никудер поддержал Чагатаида Боракхана потерпел неудачу и попал под стражу. когда Боракхан опираясь на решение курултая в Таласе заявил о претензиях на южные территории входившие по завещанию Чингизхана в улус Чагатая.