З відповідями ← До сторінки

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

Підказка

Що вивчимо. Навіщо стискати дані, як працюють RLE та код Гафмана, чим відрізняється стиснення без втрат і з втратами.

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

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

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

Тип

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

Формати

Без втрат

усе, до біта

ZIP, PNG, FLAC

З втратами

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

JPEG, MP3, MP4

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

Означення

RLE (Run-Length Encoding) — заміна серії однакових символів на пару «кількість + символ».

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

Приклад

Для рядка ABCD RLE дасть 1A1B1C1D — довше за початковий! RLE ефективний лише там, де багато повторів (наприклад, прості малюнки).

Код Гафмана

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

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

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

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

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

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

Емулятор

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

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

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

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

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

BitMath · https://bitmath.com.ua/informatyka/informatyka-8-tema-3/i8-stysnennia