Наука про стиснення даних для всіх

Це термін, який легко зрозуміти, але дія якого важко пояснити. Саме такі поняття я люблю пояснювати в цьому блозі.

В інформатиці стиснення даних можна сформулювати так: "Щоб перетворити серію бітів в іншу серію менших бітів, використовуючи алгоритм, зберігаючи інформацію, тобто," l повинна бути можлива зворотна операція "

Стиснення без втрат

Найпростіший для розуміння алгоритм стиснення без втрат - це RLE-кодування (Run Length Encoding), що складається з підрахунку повторень символу (або біта).

Приклад RLE-кодування: слово "ouuuuuaauuuuuu" трактується як послідовність символів "o", 5 "u", 2 "a" та 6 "u", тобто: "o5u2a6u". Тому ми стиснули 14 символів у 7 символів (50% коефіцієнт стиснення). Очевидно, що цей тип кодування актуальний лише у тому випадку, якщо повторюються великі рядки символів. Це стосується кодування факсів для кодування послідовності точок
чорно-біле на аркуші (кодування CCITT).

Інші методи стиснення без втрат - це методи без втрат. стиснення ентропії . Ці алгоритми засновані на статистичному вивченні інформації, яка підлягає стискуванню, з тим, щоб кодувати повторювані символи в дуже небагатьох бітах. Найвідомішими алгоритмами ентропії є алгоритм Хаффман та алгоритм
LZ77.

Алгоритм Хаффмана

Найкращий спосіб зрозуміти цей алгоритм - навести приклад. Давайте поставимо собі за мету стиснути речення "ВЧЕНІ РОЗУМНІ".

У класичному представленні ASCII вам потрібно 7 бітів на букву (загалом 2 ^ 7 = 128 символів): це 35-знакове речення займе простір у пам'яті 35 * 7 = 245 біт.

Тепер, використовуючи кодування Хаффмана, ми збираємося вивчити кількість випадків, коли кожна буква в тексті буде стиснута, щоб виділити меншу кількість бітів для найбільш використовуваних букв:

C, F, Q, U, O, G: 1 поява
L, ПРОБІЛ: 3 випадки
T, N: 4 випадки
E, S, I: 5 випадків

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

На нашому прикладі:

а) Ми перегрупуємо букви ваги "1" і додаємо їх, щоб зробити вузли ваги "2" (жовтий)
б) Ми додаємо 2 букви ваги "3" до 2 вузлів ваги "2", щоб зробити вузли ваги "5" (зелений)
в) Ми додаємо 2 літери ваги "4" до вузлів ваги "2" і "5", щоб зробити вузли ваги "6" і "9" (пурпурові).
г) Ми додаємо 3 літери ваги "5" до вузлів ваги "5", "6" та "9", щоб зробити вузли ваги "10", "11" та "14" (оранжевий).
e) Ми обробляємо дерево, поки не отримаємо загальний вузол ваги "35" (червоний).
f) Залишилося призначити серію бітів кожній букві. Для цього ми вирішили додати біт "0" для лівих гілок і біт "1" для правих гілок, і тоді ми отримаємо таке дерево:

Отже, речення "ВЧЕНІ ІНТЕЛІГЕНТ" транскрибується таким чином:

0100 011 001 1000 001 00010 11 011 101 0000 11 00011 11 10010
10 011 011 001 1000 001 01 010 101 0000 1000 11 101 0000 011 0100 0100 11 01 011 011 101 0000 011

Це представляє загалом 122 біта замість 245 біт, або ступінь стиснення приблизно 50%. Кодування Хаффмана надзвичайно потужне і використовується як останній крок у багатьох інших алгоритмах стиснення.

Алгоритм LZ77 або кодування словника

Цей алгоритм дозволяє замінити повторювані послідовності позицією та довжиною першого входження у розсувному вікні. Наприклад, в
У цій статті ми багато разів знаходимо слово "стиснення", і замість того, щоб кожного разу переписувати його, ми можемо просто сказати, щоб повернути "n" символи назад і скопіювати наступні символи "p" (p = 11 у випадку зі словом
"Стиснення").

"Стиснення чудове, воно дозволяє стискати файли всіх типів, а також стискати простір пам'яті"

"Стиснення чудове, дозволяє файли (41,11) усіх типів, а також (97,11) простір пам'яті"

Тому ми зменшили загальну кількість символів у цьому реченні. Цей алгоритм дуже цікавий, коли великі послідовності символів дуже часто повторюються.
ZIP

Тут принцип полягає у використанні слабких сторін людини. Справді, наш слух і зір не ідеальні, і багато інформації, що міститься в аудіо- чи візуальних файлах, часто марно, оскільки непомітно для наших органів чуття. Тому легко зрозуміти, що цей тип стиснення застосовується лише до аудіофайлів, зображень та фільмів. Крім того, менші зміни якості звуку або відео можуть дозволити дуже високі показники стиснення (більше 10).

Для кодування аудіо- чи візуальної інформації в цифровому форматі необхідно дискретизація вихідного сигналу. Цей варварський вираз, також званий кількісна оцінка, означає, що для перетворення звуку або серії зображень (аналогових) у цифровий формат (двійкові серії "1" та "0") необхідно "розрізати" інформацію на дрібні елементи в часі, але також у просторі. Наприклад, звук, що характеризується амплітудою та частотою (див. Попереднє повідомлення на
звук), сигнал повинен бути сегментований у часі, а також його амплітуда (часове та просторове квантування).

Як правило, вибирається цільова швидкість передачі даних, яку слід досягти, і потім виводиться відповідний етап квантування. Отже, зменшення швидкості передачі даних звукового чи візуального носія призведе до зменшення його розміру, а також до погіршення його якості.

Приклад квантування в mp3

На додаток до різних прийомів, що використовуються форматом mp3 для зменшення розміру аудіофайлів, не змінюючи сприйняття пісень, квантування є основним етапом стиснення.