Стиснення даних: RLE, код Гафмана, архіватори, формати без втрат і з втратами

Стрілки або пробіл — перемикання · F — повний екран · T — проєкторна тема · ? — підказка

Навіщо стискати

Менший файл швидше передається й займає менше місця. Стиснення (архівування) зменшує обсяг даних за рахунок прибирання надлишковості.

Без втрат і з втратами

Тип

Що відновлюється

Формати

Без втрат

усе, до біта

ZIP, PNG, FLAC

З втратами

наближено, дрібні деталі втрачено

JPEG, MP3, MP4

RLE — кодування серій

AAAAABBBCC → 5A3B2C (10 символів → 6).

Код Гафмана

Ідея: часті символи кодують короткими кодами, рідкісні — довгими. Кодове дерево будується так:

  1. Підрахувати частоти символів.

  2. Взяти два символи з найменшою частотою й об’єднати у вузол із сумою частот.

  3. Повторювати, поки не залишиться одне дерево.

  4. Ліва гілка — 0, права — 1: шлях від кореня й дає код.

Коди префіксні: жоден код не є початком іншого, тому розкодувати можна однозначно.

Емулятор

Введіть текст у лабораторії нижче: побачите RLE-кодування, дерево й таблицю кодів Гафмана, а також економію порівняно з 8 бітами на символ.

Перевірте себе

  1. Чим стиснення без втрат відрізняється від стиснення з втратами?

  2. Закодуйте RLE: WWWWBBBW.

  3. Чому в коді Гафмана часті символи мають коротші коди?

✕ Вийти 1 / 1