Информация и информационные процессы. Сжатие данных. 11 класс

Что такое сжатие?
Сообщение: АBА CАBАBА
A → 00
B → 01
АBА CАBАBА → 00 01 00 11 10 00 01 00 01 00
20 битов
Словарь:

Коэффициент сжатия
Сообщение: 10240 символов
Словарь: 5 байтов
Длина кода:
10240×2 = 20480 битов = 2560 байтов
Длина сжатого сообщения:
5 + 2560 = 2565 байтов
Коэффициент сжатия – это отношение размеров исходного и сжатого файлов.

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

Алгоритм RLE
RLE (англ. Run Length Encoding, кодирование цепочек одинаковых символов)
100
100
200 байтов
Файл qq.txt
Файл qq.rle (сжатый)
4 байта
сжатие в 50 раз!

Алгоритм RLE
АААААААААААААААБВ
Распаковка:
15
2
Применение:
сжатие рисунков *.bmp (с палитрой)
один из этапов сжатия рисунков *.jpg
8F C0 02 C1 C216

Неравномерные коды
Идея: кодировать часто встречающиеся символы более короткими кодовыми словами.
Азбука Морзе:

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

Код Шеннона-Фано
Количество символов в сообщении:
На 2 группы с примерно равным числом символов:
начинаются с 0
начинаются с 1
начинаются с 11
в порядке невозрастания

Код Шеннона-Фано
Декодирование:
1110111101001011001111
111
01
111
01
00
10
110
01
111
Т
O
Т
O
Е
Н
О
Т

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

Алгоритм Хаффмана
По увеличению частоты:

Алгоритм Хаффмана
0
Т
100
Н
101
Код Хаффмана:
Е
110
О
111

Сравнение алгоритмов
Количество символов в сообщении:
Равномерное кодирование (8-битный код):
(140 + 68 + 68 + 64 + 60) ⋅ 8 = 3200 битов
Равномерное кодирование (3-битный код):
(140 + 68 + 68 + 64 + 60) ⋅ 3 = 1200 битов
+ словарь!

Сравнение алгоритмов
Количество символов в сообщении:
(140 + 68 + 68) ⋅ 2 + (64 + 60) ⋅ 3 = 924 бита
140 + (68 + 68 + 64 + 60) ⋅ 3 = 920 бит

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

Алгоритм LZW
1977: А. Лемпел и Я. Зив, 1984: Т. Велч
Идеи:
кодировать не отдельные символы, а блоки
последовательностям символов присваиваются числовые коды
новая цепочка ⇒ занесение в словарь с новым кодом
словарь строится по мере получения данных
не нужны частоты символов ⇒ за один проход!
Применение:
сжатие рисунков *.gif, *.tif
сжатие документов *.pdf

Сжатие с потерями
Сжатие с потерями – это такое уменьшение объема закодированных данных, при которых распакованный файл может отличаться от оригинала.
Применение:
сжатие рисунков *.jpg, *.jpeg
сжатие звука *.mp3, *.aac, *.ogg, …
сжатие видео *.mpg, *.wmv, *.mov, …
Идея: «отбросить» часть данных, которые не влияют на восприятие информации человеком (доп. размытие фотографий, частоты выше 20 кГц, …)

Снижение глубины цвета
размер ↓
качество ↓

Сжатие JPEG
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

Сжатие JPEG
Идея: глаз наиболее чувствителен к яркости
12 чисел
+ дискретное косинусное преобразование, алгоритмы RLE и Хаффмана
потери!

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

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

Сжатие звука (MP3)
MP3 = MPEG-1 Layer 3, кодирование восприятия
Битрейт – это число бит, используемых для кодирования 1 секунды звука.
MP3: от 8 до 320 кбит/c
Без сжатия на CD (1 сек, 44 кГц, 16 бит, стерео):
2×88000 = 176 000 байт = 1 408000 бит = 1408 кбит
Cжатие MP3 (256 кбит/с):

Сжатие видео
видео = изображения + звук
Кодек (кодировщик/декодировщик) – это программа для сжатия данных и восстановления сжатых данных.
MJPEG, MPEG-4, DivX, Xvid, H.264, …
Артефакты – заметные искажения из-за сжатия с потерями