Компресійна інформатика G23c
Вирішити робочий аркуш «Формати зображень»
# Стиснення
При стисненні робиться спроба зберігати дані ефективніше, щоб використовувати менше місця для зберігання. Це надзвичайно важливо, особливо під час передачі даних - наприклад, потокового передавання фільму або телефонування. Ми розрізняємо два принципово різні типи стиснення:
# Стиснення без втрат
За допомогою стиснення без втрат дані можуть бути повністю реконструйовані. Це означає, що - "це", як кодування - унікальне та оборотне відображення.
Може використовуватися там, де втрат не може статися - програма більше не працює, якщо команди відсутні! Зображення, аудіо та відео під час виготовлення та редагування - інакше якість знижуватиметься з кожним збереженням (тобто кодуванням). Приклади flac - звуковий zip, rar - файли gif, png, raw, psd, xcf - графіка
# Стиснення з втратою
Дані тут видаляються при збереженні. Це дозволяє отримати відповідно великий обсяг пам'яті, але вихідні дані можна відновити лише частково. Перш за все, він намагається залишити не важливі дані.
Використовувати для закінчення носія, тобто коли його більше не потрібно редагувати. Приклади mp3 - звук jpg - графіка mp4, avi, mov - відео
# Графічний
Різні формати файлів пропонують усі переваги та недоліки завдяки різному стисненню. Це також відіграє роль, чи слід стискати текст, логотип, ілюстрацію чи фотографію.
На аркуші вправ ми вже знали тип стиснення, а саме кодування довжини пробігу, або коротше RLE.
Дайте відповідь на наступні питання:
- Де процедура дуже ефективна?
- Для якої графіки вона може бути використана?
# Кодування Хаффмана
У 1952 році Девід Хаффман розробив процес, за допомогою якого символи можуть кодуватися в економії місця. Його ідея полягає в тому, що символи, які часто з'являються в тексті, отримують коротший код, ніж символи, які рідко з'являються в тексті.
# Дерево коду
Дерево коду - це структура зі стартовим вузлом. Звідси ви можете продовжувати ліворуч або знизу праворуч. 0 у коді означає рухатися ліворуч, 1 означає рухатися праворуч. Коли в вузол потрапляє буква, людина розшифровує символ і починає знову спочатку.
Дерево Хаффмана для «Анни»
- Розшифруйте наступну послідовність бітів за допомогою наведеного вище кодового дерева. (SP) означає пробіл.
- Тепер кодуйте отриманий текст або в Пентакоді, або в ASCII. Як довго отримується бітова послідовність?
- Чи можете ви знайти кращий код, ніж Pentacode/ASCII?
Пентакод:
12 символів Г 5 біт = 60 біт
ASCII:
12 символів Г 7 біт = 84 біти (спочатку)
12 символів Г 8 біт = 96 біт (з 0 бітами)
власний код:
Має бути можливість кодування лише 4 символів. Для цього достатньо 2 бітів!
| 00 | (ІП) |
| 01 | А. |
| 10 | N |
| 11 | С. |
12 символів Г 2 біти = 24 біти
# Створіть дерево Хаффмана
Пояснити алгоритм Хаффмана слід на прикладі кодування тексту «MISSISSIPPI».
Спочатку ви підраховуєте кількість разів, коли кожен символ з’являється в тексті, і створюєте таблицю частот.
| Частота | 1 | 2 | 4-й | 4-й |
Тепер справа в створенні дерева кодування. Частоти букв утворюють вузол. Частота знаходиться у вузлі, буква під ним. Вузли сортуються відповідно до зростаючої частоти:
Вузол із частотою символів
Тепер два вузли з найнижчими частотами приєднані до нового вузла. Новий вузол містить накопичену частоту вихідних вузлів:
Комбінувати вузли 1
Це повторюється, поки всі вузли не будуть з'єднані між собою. Якщо два вузли мають однакову частоту, не має значення, який із них обраний:
Злиття вузлів 2
Важливо, щоб вузли були пересортовані після кожного кроку.
Злиття вузлів 3
Коли дерево закінчено, усі гілки, які вказують ліворуч, позначаються «0», усі, що вказують праворуч, «1».
Назви краї
Тепер можна створити таблицю кодування, прочитавши код для кожного символу з дерева:
| код | 11 | 100 | 101 | 0 |
Створіть дерево Хаффмана для наступного тексту та кодуйте текст відповідно:
Скільки бітів займає слово в кодуванні Хаффмана? Скільки в пентакоді? Скільки в ASCII?
# Хаффман-Баум для німецької мови
В принципі, для кожного кодованого тексту створюється дерево Хаффмана. Це стосується властивостей тексту та гарантує, що часто зустрічаються символи отримують короткий код. Дерево потрібно зберегти разом із закодованими даними - воно використовується для декодування.
Якщо поглянути на частоту букв німецькою мовою, ми можемо використати ці дані для створення дерева Хаффмана, яке підходить для довших текстів німецькою мовою.
Дерево Гуфмана для частоти символів у німецькій мові
Чи можете ви відповісти на такі запитання:
- Чому мова відіграє роль?
- Чому у Хаффмана немає місця для зберігання наступного речення?