Стиснення даних: RLE, код Гафмана, архіватори, формати без втрат і з втратами
Навіщо стискати
Менший файл швидше передається й займає менше місця. Стиснення (архівування) зменшує обсяг даних за рахунок прибирання надлишковості.
Без втрат і з втратами
Тип | Що відновлюється | Формати |
|---|---|---|
Без втрат | усе, до біта | ZIP, PNG, FLAC |
З втратами | наближено, дрібні деталі втрачено | JPEG, MP3, MP4 |
RLE — кодування серій
AAAAABBBCC → 5A3B2C (10 символів → 6).
Код Гафмана
Ідея: часті символи кодують короткими кодами, рідкісні — довгими. Кодове дерево будується так:
Підрахувати частоти символів.
Взяти два символи з найменшою частотою й об’єднати у вузол із сумою частот.
Повторювати, поки не залишиться одне дерево.
Ліва гілка —
0, права —1: шлях від кореня й дає код.
Коди префіксні: жоден код не є початком іншого, тому розкодувати можна однозначно.
Емулятор
Введіть текст у лабораторії нижче: побачите RLE-кодування, дерево й таблицю кодів Гафмана, а також економію порівняно з 8 бітами на символ.
Перевірте себе
Чим стиснення без втрат відрізняється від стиснення з втратами?
Закодуйте RLE:
WWWWBBBW.Чому в коді Гафмана часті символи мають коротші коди?