1 of 29

Информация и информационные процессы

§ 3. Сжатие данных

1

2 of 29

Что такое сжатие?

2

Алфавит: A, B, C,

Сообщение: АBА CАBАBА

80 битов в 8-битной кодировке!

!

A → 00

B → 01

C → 10

→ 11

АBА CАBАBА → 00 01 00 11 10 00 01 00 01 00

20 битов

Как раскодировать?

?

Словарь:

	00	01	10	11
00000100₂	01000001₂	01000010₂	01000011₂	00100000₂
4 символа	A (код 65)	B (код 66)	C (код 67)	пробел (код 32)

Информация и информационные процессы, 11 класс

3 of 29

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

3

Сообщение: 10240 символов

Алфавит: A, B, C,

Словарь: 5 байтов

Длина кода:

10240×2 = 20480 битов = 2560 байтов

Длина сжатого сообщения:

5 + 2560 = 2565 байтов

Коэффициент сжатия – это отношение размеров исходного и сжатого файлов.

Информация и информационные процессы, 11 класс

4 of 29

Сжатие без потерь

4

Сжатие без потерь – это такое уменьшение объема закодированных данных, при котором можно восстановить их исходный вид из кода без искажений.

За счёт чего сжимается сообщение?

?

В данных должна быть избыточность!

!

используются только �4 символа из 256

Информация и информационные процессы, 11 класс

5 of 29

Алгоритм RLE

5

RLE (англ. Run Length Encoding, кодирование цепочек одинаковых символов)

A	A	…	A	B	B	…	B

100

200 байтов

Файл qq.txt

Файл qq.rle (сжатый)

100	A	100	B

4 байта

В чем состоит избыточность?

?

сжатие в 50 раз!

Сжатие с потерями или без?

?

Что в худшем случае?

?

Информация и информационные процессы, 11 класс

6 of 29

Алгоритм RLE

6

8F₁₆	C0₁₆	02₁₆	C1₁₆	C2₁₆
10001111₂	11000000₂	00000010₂	11000001₂	11000010₂
повтор 15	A (код 192)	2	Б (код 193)	В (код 194)

управляющие байты

АААААААААААААААБВ

Распаковка:

15

2

Применение:

сжатие рисунков *.bmp (с палитрой)
один из этапов сжатия рисунков *.jpg

8F C0 02 C1 C2₁₆

Информация и информационные процессы, 11 класс

7 of 29

Неравномерные коды

7

Идея: кодировать часто встречающиеся символы более короткими кодовыми словами.

Азбука Морзе:

А

И

•

–

корень

Н

М

Т

Е

•

–

Т

И

•

–

А

•

Н

–

М

•

–

Проблема: разделить последовательность на кодовые слова!

!

•

И

ЕЕ

Можно ли обойтись без разделителя?

?

Информация и информационные процессы, 11 класс

8 of 29

Префиксные коды

8

Префиксный код – это код, в котором ни одно кодовое слово не является началом другого кодового слова (условие Фано).

А

И

•

–

корень

Н

М

Т

Е

•

–

Т

И

•

–

А

•

Н

–

М

•

–

Это не префиксный код!

!

Проблема: как построить префиксный код?

!

не все символы в листьях!

Информация и информационные процессы, 11 класс

9 of 29

Код Шеннона-Фано

9

Алфавит: О, Е, Н, Т,

Количество символов в сообщении:

140

О

Н

Е

Т

68

64

60

На 2 группы с примерно равным числом символов:

140

E

T

H

O

68

64

60

68

208

192

начинаются с 0

начинаются с 1

00

O

01

E

10

T

Н

64

60

начинаются с 11

Т

Н

110

111

в порядке невозрастания

Информация и информационные процессы, 11 класс

10 of 29

Код Шеннона-Фано

10

О

Е

Н

Т

0

1

корень

Это префиксный код (все символы в листьях дерева)!

!

Декодирование:

1110111101001011001111

111

01

111

01

00

10

110

01

111

Т

O

Т

O

Е

Н

О

Т

Информация и информационные процессы, 11 класс

11 of 29

Код Шеннона-Фано

11

учитывается частота символов
не нужен символ-разделитель
код префиксный – можно декодировать по мере поступления данных

нужно заранее знать частоты символов
код неоптимален
при ошибке в передаче сложно восстановить «хвост»
не учитывает повторяющиеся последовательности символов

Информация и информационные процессы, 11 класс

12 of 29

Алгоритм Хаффмана

12

Дэвид Хаффман

140

Е

Т

Н

О

68

64

60

68

По увеличению частоты:

140

Е

Т

Н

О

68

124

140

Е

О

136

Т

Н

124

Информация и информационные процессы, 11 класс

13 of 29

Алгоритм Хаффмана

13

140

Е

О

Т

Н

260

Т

Н

Е

О

0

1

0

1

0

Т

100

Н

101

Код Хаффмана:

Е

110

О

111

Информация и информационные процессы, 11 класс

14 of 29

Сравнение алгоритмов

14

Количество символов в сообщении:

140

О

Н

Е

Т

68

64

60

Равномерное кодирование (8-битный код):

(140 + 68 + 68 + 64 + 60) ⋅ 8 = 3200 битов

Равномерное кодирование (3-битный код):

(140 + 68 + 68 + 64 + 60) ⋅ 3 = 1200 битов

+ словарь!

В чём избыточность?

?

Информация и информационные процессы, 11 класс

15 of 29

Сравнение алгоритмов

15

Количество символов в сообщении:

140

О

Н

Е

Т

68

64

60

Код Шеннона-Фано:

00

О

01

Е

10

Н

Т

110

111

(140 + 68 + 68) ⋅ 2 + (64 + 60) ⋅ 3 = 924 бита

Код Хаффмана:

0

О

111

Е

110

Н

Т

101

100

140 + (68 + 68 + 64 + 60) ⋅ 3 = 920 бит

Оптимален!

!

Информация и информационные процессы, 11 класс

16 of 29

Алгоритм Хаффмана

16

код оптимальный среди алфавитных кодов

нужно заранее знать частоты символов
при ошибке в передаче сложно восстановить «хвост»
не учитывает повторяющиеся последовательности символов

Информация и информационные процессы, 11 класс

17 of 29

Алгоритм LZW

17

1977: А. Лемпел и Я. Зив, 1984: Т. Велч

Идеи:

кодировать не отдельные символы, а блоки
последовательностям символов присваиваются числовые коды
новая цепочка ⇒ занесение в словарь с новым кодом

словарь строится по мере получения данных
не нужны частоты символов ⇒ за один проход!

Применение:

сжатие рисунков *.gif, *.tif
сжатие документов *.pdf

Информация и информационные процессы, 11 класс

18 of 29

Алгоритм LZW

18

ввод СТРОКА

пока не конец данных

ввод СИМВОЛ

если Есть_в_словаре( СТРОКА + СИМВОЛ ) то

СТРОКА:= СТРОКА + СИМВОЛ

иначе

вывод Код(СТРОКА)

Добавить_в_словарь( СТРОКА + СИМВОЛ )

СТРОКА:= СИМВОЛ

вывод Код(СТРОКА)

да / нет

получить из словаря

Информация и информационные процессы, 11 класс

19 of 29

Сжатие с потерями

19

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

Применение:

сжатие рисунков *.jpg, *.jpeg
сжатие звука *.mp3, *.aac, *.ogg, …
сжатие видео *.mpg, *.wmv, *.mov, …

Идея: «отбросить» часть данных, которые не влияют на восприятие информации человеком (доп. размытие фотографий, частоты выше 20 кГц, …)

Информация и информационные процессы, 11 класс

20 of 29

Снижение глубины цвета

20

8 битов на пиксель (256 цветов)

4 бита на пиксель (16 цветов)

2 бита на пиксель �(4 цвета)

размер ↓

качество ↓

Информация и информационные процессы, 11 класс

21 of 29

Сжатие JPEG

21

RGB → Y Cb Cr

яркость

«синева»

«краснота»

Y = 0,299⋅R + 0,587⋅G + 0,114⋅B

Cb = 128 – 0,1687⋅R – 0,3313⋅G + 0,5⋅B

Cr = 128 + 0,5⋅R – 0,4187⋅G – 0,0813⋅B

глаз чувствительнее к зелёному!

Что для чёрно-белого (серого)?

?

Cb = Cr = 128

Информация и информационные процессы, 11 класс

22 of 29

Сжатие JPEG

22

Идея: глаз наиболее чувствителен к яркости

Y₁, Cb₁, Cr₁	Y₂, Cb₂, Cr₂
Y₃, Cb₃, Cr₃	Y₄, Cb₄, Cr₄

12 чисел

например:

Cb =

Cb₁ + Cb₂ +Cb₃ + Cb₄

4

Cr =

Cr₁ + Cr₂ +Cr₃ + Cr₄

4

⇒ Y₁, Y₂, Y₃, Y₄, Cb, Cr

6 чисел

+ дискретное косинусное преобразование, алгоритмы RLE и Хаффмана

потери!

Информация и информационные процессы, 11 класс

23 of 29

Сжатие JPEG

23

качество 100

(8400 байтов)

качество 50

(3165 байтов)

качество 0

(1757 байтов)

качество 0

(фрагмент)

40

30

20

10

0

BMP

BMP(RLE)

GIF

PNG

JPEG(100)

JPEG(50)

JPEG(0)

V, Кбайт

Плавные переходы!

!

Артефакты – заметные искажения из-за сжатия с потерями

Информация и информационные процессы, 11 класс

24 of 29

Сжатие рисунков с потерями и без

24

Большие области одного цвета!�Чёткие границы!

!

120

100

80

40

0

BMP

BMP(RLE)

GIF

PNG

JPEG(100)

JPEG(50)

JPEG(0)

60

20

V, Кбайт

Что особенного?

?

с потерями!

без потерь!

Информация и информационные процессы, 11 класс

25 of 29

Сжатие звука (MP3)

25

MP3 = MPEG-1 Layer 3, кодирование восприятия

Битрейт – это число бит, используемых для кодирования 1 секунды звука.

MP3: от 8 до 320 кбит/c

Без сжатия на CD (1 сек, 44 кГц, 16 бит, стерео):

2×88000 = 176 000 байт = 1 408000 бит = 1408 кбит

Cжатие MP3 (256 кбит/с):

Информация и информационные процессы, 11 класс

26 of 29

Сжатие видео

26

видео = изображения + звук

Кодек (кодировщик/декодировщик) – это программа для сжатия данных и восстановления сжатых данных.

MJPEG, MPEG-4, DivX, Xvid, H.264, …

Артефакты – заметные искажения из-за сжатия с потерями

Информация и информационные процессы, 11 класс

27 of 29

Сжатие: итоги

27

Сжатие уменьшает избыточность данных!

!

Хорошо сжимаются:

тексты (*.txt)
документы (*.doc)
несжатые рисунки (*.bmp)
несжатый звук (*.wav)
несжатое видео (*.avi)

Плохо сжимаются:

случайные данные
сжатые данные в архивах (*.zip, *.rar, *.7z)
сжатые рисунки (*.jpg, *.gif, *.png)
сжатый звук (*.mp3, *.aac)
сжатое видео (*.mpg, *.mp4, *.mov)

Нужно ли стремиться к полному удалению избыточности?

?

Информация и информационные процессы, 11 класс

28 of 29

Конец фильма

28

ПОЛЯКОВ Константин Юрьевич

д.т.н., учитель информатики

ГБОУ СОШ № 163, г. Санкт-Петербург

kpolyakov@mail.ru

ЕРЕМИН Евгений Александрович

к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

eremin@pspu.ac.ru

Информация и информационные процессы, 11 класс

29 of 29

Источники иллюстраций

29

www.newbeanbag.ru
compression.ru
maps.yandex.ru
ixbt.com
www.dinamika-avia.ru
www.transas.ru
crazypiter.ru
www.fotosearch.com
www.notebookcheck.net
www.energy2.ru
www.wlangdesign.com
www.1himplast.ru
www.applecad.com
gprs-modem.ru
en.wikipedia.org
nivo.co.za
иллюстрации художников издательства «Бином»
авторские материалы

Информация и информационные процессы, 11 класс