Світ у стиснутому вигляді

Тема уроку: Світ у стиснутому вигляді

Мета уроку: Зрозуміти, чому дані займають місце, як працюють алгоритми стиснення та в чому різниця між ZIP-архівом і форматом JPEG.

Проблема: Один кадр нестисненого Full HD відео займає близько 6 МБ. У відео 24 кадри на секунду. Без стиснення 1 година фільму займала б ~500 ГБ. Жоден інтернет-канал цього б не витримав.

Питання до групи: Хто бачив «квадратики» на відео, коли інтернет поганий? Це і є робота алгоритмів стиснення, які намагаються врятувати ситуацію.

1. Навіщо нам стиснення?

Стиснення (компресія) — це процес перекодування даних з метою зменшення їх обсягу. Стиснення — це завжди компроміс між якістю, розміром та потужністю процесора (який витрачає час на розпакування).

• Економія місця: на диску або флешці.
• Швидкість передачі: менші файли швидше летять через Інтернет.
• Обмеження каналів: прямі трансляції (стримінг) неможливі без стиснення «на льоту».
• ZIP/7z — для документів (не можна втрачати ні коми).
• JPEG/MP3 — для медіа (можна жертвувати якістю заради швидкості).

2. Два головні типи стиснення

Все стиснення ділиться на два табори:

А. Стиснення без втрат (Lossless)

Після розпакування ми отримуємо ідентичну копію оригіналу. Жоден біт не зникає.

• Де використовується: Тексти, програмний код, бази даних, архіви (ZIP, RAR, 7z).
• Приклад: Якщо в тексті вилучити всі коми для «економії», зміст може змінитися. Тому тут використовується лише математичне перекодування.

Б. Стиснення з втратами (Lossy)

Алгоритм відкидає частину інформації, яку людське око або вухо майже не помічає.

• Де використовується: Фото (JPEG), музика (MP3), відео (MP4).
• Приклад: Людське око погано розрізняє дуже близькі відтінки кольорів. Алгоритм робить їх однаковими, що дозволяє значно зменшити вагу файлу.

 Увага: Повернути оригінальну якість після такого стиснення неможливо!

3. Як це працює? (Алгоритми «на пальцях»)

Метод RLE (Run-Length Encoding)

Найпростіший метод. Він шукає повтори.

• Оригінал: AAAAABBBCCCCDD (14 символів)
• Стиснений вигляд: 5A3B4C2D (8 символів)
• Ефект: Ми стиснули рядок майже вдвічі, просто порахувавши повтори!

Метод Хаффмана (Статистичний)

Алгоритм аналізує, які символи зустрічаються часто, а які — рідко.

• Частим символам (наприклад, літера «О» або «А») він дає дуже короткий код (наприклад, 2 біти).
• Рідкісним символам (літера «Ф») — довгий код.

Це схоже на азбуку Морзе, де найпопулярніша буква «Е» — це просто одна крапка.

4. Популярні формати та їх призначення

5. Практичне завдання для студентів (Кейс)

Ситуація: У вас є 100 фотографій у форматі RAW (дуже великі) і текстовий звіт. Вам треба відправити це викладачу на пошту, де ліміт 20 МБ.

Питання:

1. Який формат ви оберете для фото, щоб вони стали меншими?
2. Чи можна стиснути текстовий файл у формат JPEG? (Ні, це викличе помилку або втрату даних).
3. Що буде, якщо заархівувати вже стиснутий файл (наприклад, MP3) у ZIP-архів? (Вага майже не зміниться, бо «зайвого» місця вже немає).

Завдання для студентів (можна на дошці або в зошитах):

Стисніть наступний рядок за допомогою методу RLE та порахуйте коефіцієнт стиснення ($K$).

      Рядок: WWWWWWWWBBWWWWWWRRRRRRRRRR (26 символів)

Рішення:

1. Записуємо: 8W2B6W10R (9 символів разом із цифрами).
2. Обчислюємо коефіцієнт:

$$K = \frac{\text{Розмір оригіналу}}{\text{Розмір стисненого}} = \frac{26}{9} \approx 2.88$$

Висновок: Файл став майже в 3 рази меншим.

Чому не можна стискати вічно?

Поясніть студентам поняття інформаційної ентропії. Якщо файл уже максимально стиснений (як-от архів .rar або пісня .mp3), повторне стиснення не дасть результату, а іноді навіть збільшить розмір файлу через додавання заголовків архіву.