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

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

2.

Сжатие данных—
алгоритмическое
преобразование данных,
производимое с целью
уменьшения занимаемого ими
объёма

3.

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

4.

Способы
сжатия
Без потери
информации
С потерей
информации

5. Алгоритмы сжатия

6. Алгоритм RLE -кодирование цепочек одинаковых символов

6
Алгоритм RLE -кодирование цепочек одинаковых
символов
Файл qq.txt
A
A
…
A
B
100
Файл qq.rle (сжатый)
100
?
?
A
100
B
B
…
B
100
4 байта
В чем состоит избыточность?
Сжатие с потерями или без?
200 байтов

7.

7
Префиксный код – это код, в котором ни одно кодовое
слово не является началом другого кодового слова
(условие Фано).
корень
Е
Т –
И
А
Н
М
•
• –
–
––
–
Е
И
Т
–
А
Н
–
М

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

Сообщения алфавита источника выписывают в порядке
убывания вероятностей их появления.
Далее разделяют их на две части так, чтобы суммарные
вероятности сообщений в каждой из этих частей были по
возможности почти одинаковыми.
Припишем сообщениям первой части в качестве первого
символа – 0, а второй – 1 (можно наоборот).
Затем каждая из этих частей (если она содержит более
одного сообщения) делится на две по возможности
равновероятные части, и в качестве второго символа для
первой из них берется 0, а для второй – 1.
Этот процесс повторяется, пока в каждой из полученных
частей не останется по одному сообщению

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

9
Код Шеннона-Фано
Алфавит: О, Е, Н, Т,
Количество символов в сообщении:
179
О 89
Е 72
Н 53
Т 50
На 2 группы с примерно равным числом символов:
179
Т 50
О 89
229
начинаются с 0
00
?
Т 01
Е 72
Н 53
214
начинаются с 1
О 10
Е 72
Н 53
начинаются с 11
Е 110
Н 111
Сжатие с потерями или без?

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

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

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

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

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

12
Алгоритм Хаффмана
Т 50
Н 53
_-1
О – 01
Е – 001
Н – 0001
Т – 0000
Т
Е 72
О 89
179
1
0
1
0
1
0
0
1
_
О
Е
Н
Дэвид Хаффман

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

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

14.

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

15

16. Алгоритм JPEG

При сжатии изображение преобразуется из
цветового пространства RGB в YCbCr (Y –
яркость, Cb – «синева», Cr- «краснота»
Перевод осуществляется по следующей формуле

17. Сжатие JPEG

17
Сжатие JPEG
Идея: глаз наиболее чувствителен к яркости
Дано: изображение 2×2 pt
6 чисел
Y1, Cb1, Cr1
Y3, Cb3, Cr3
Y2, Cb2, Cr2
Y4, Cb4, Cr4
12 чисел
Y1, Y2, Y3, Y4, Cb, Cr
например:
Cb =
Cb1 + Cb2 +Cb3 + Cb4
4
Cr =
Cr1 + Cr2 +Cr3 + Cr4
4

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

Битрейт – это число бит,
используемых для кодирования 1
секунды звука (Кб/с)
Дано:
d=44 кГц
S=2
t=1 c
b=16 б
Битрейт =256 Кб/с
Степень сжатия - ?
V = b d t S
V=44000 16 1 2= 1375
Степень сжатия=1375/256=5

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

19
Сжатие: итоги
Хорошо сжимаются:
• тексты (*.txt)
• документы (*.doc)
• несжатые рисунки (*.bmp)
• несжатый звук (*.wav)
• несжатое видео (*.avi)
Плохо сжимаются:
• случайные данные
• сжатые данные в архивах (*.zip, *.rar, *.7z)
• сжатые рисунки (*.jpg, *.gif, *.png)
• сжатый звук (*.mp3, *.aac)
• сжатое видео (*.mpg, *.mp4, *.mov)

20.

5. Производилась двухканальная (стерео)
звукозапись с частотой дискретизации 64
кГц и 24-битным разрешением. В
результате был получен файл размером 120
Мбайт, сжатие данных не производилось.
Определите приблизительно, сколько
времени (в минутах) производилась запись.
В качестве ответа укажите ближайшее к
времени записи целое число, кратное 5.

21.

6. Музыкальный фрагмент был оцифрован и записан
в виде файла без использования сжатия данных.
Получившийся файл был передан в город А по каналу
связи за 30 секунд. Затем тот же музыкальный
фрагмент был оцифрован повторно с разрешением
в 2 раза выше и частотой дискретизации в 1,5 раза
меньше, чем в первый раз. Сжатие данных не
производилось. Полученный файл был передан в
город Б; пропускная способность канала связи с
городом Б в 4 раза выше, чем канала связи с городом
А. Сколько секунд длилась передача файла в город Б?
В ответе запишите только целое число, единицу
измерения писать не нужно.

22.

7. Рисунок размером 512 на 256 пикселей
занимает в памяти 64 Кбайт (без учёта
сжатия). Найдите максимально возможное
количество цветов в палитре изображения.

23.

8. Какой минимальный объём памяти (в
Кбайт) нужно зарезервировать, чтобы
можно было сохранить любое растровое
изображение размером 64 на 64 пикселов
при условии, что в изображении могут
использоваться 256 различных цветов? В
ответе запишите только целое число,
единицу измерения писать не нужно.