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

багатоцільові [ правити | правити код ]
Стиснення аудіо [ правити | правити код ]
Стиснення відео [ правити | правити код ]

Цей термін має також інші значення див. стиснення .

Стиснення даних без втрат ( англ. lossless data compression) - клас алгоритмів стиснення даних (Відео, аудіо, графіки, документів, представлених в цифровому вигляді), при використанні яких закодовані дані однозначно можуть бути відновлені з точністю до біта , пікселя , вокселя і т.д. При цьому оригінальні дані повністю відновлюються з стисненого стану. Цей тип стиснення принципово відрізняється від стиснення даних з втратами . Для кожного з типів цифрової інформації, як правило, існують свої оптимальні алгоритми стиснення без втрат.

Стиснення даних без втрат використовується в багатьох додатках. Наприклад, воно використовується в усіх файлових архіваторах . Воно також використовується як компонент в стисненні з втратами.

Стиснення без втрат використовується, коли важлива ідентичність стислих даних оригіналу. Типовий приклад - виконувані файли і вихідний код. Деякі графічні файлові формати (наприклад PNG ) Використовують тільки стиснення без втрат, тоді як інші ( TIFF , FLIF або GIF ) Можуть використовувати стиснення як з втратами, так і без втрат.

Легко доводиться теорема.

Для будь-якого N> 0 немає алгоритму стиснення без втрат, який:

Будь-який файл довжиною не більше N байт або залишає тієї ж довжини, або зменшує.
Зменшує деякий файл довжиною не більше N хоча б на один байт.

Доведення. Без обмеження спільності, можна припустити, що зменшився файл A довжини рівно N. Позначимо алфавіт як Σ {\ displaystyle \ Sigma} . Розглянемо безліч Σ 0 ∪ Σ 1 ∪ ... ∪ Σ N - 1 ∪ {A} {\ displaystyle \ Sigma ^ {0} \ cup \ Sigma ^ {1} \ cup \ ldots \ cup \ Sigma ^ {N-1} \ cup \ {A \}} . У цій множині 256 0 + 256 1 + ... + 256 N - 1 + 1 {\ displaystyle 256 ^ {0} + 256 ^ {1} + \ ldots + 256 ^ {N-1} +1} вихідних файлів, в той час як стислих не більше ніж 256 0 + 256 1 + ... + 256 N - 1 {\ displaystyle 256 ^ {0} + 256 ^ {1} + \ ldots + 256 ^ {N-1}} . Тому функція декомпресії неоднозначна , Протиріччя. Теорема доведена.

Втім, дана теорема анітрохи не кидає тінь на стиск без втрат. Справа в тому, що будь-який алгоритм стиснення можна модифікувати так, щоб він збільшував розмір не більше ніж на 1 біт: якщо алгоритм зменшив файл, пишемо «1», потім стислу послідовність, якщо збільшив - пишемо «0», потім вихідну.

Так що нестискувані фрагменти не приведуть до безконтрольного «роздування» архіву. «Реальних» ж файлів довжини N набагато менше, ніж 256 N {\ displaystyle 256 ^ {N}} (Кажуть, що дані мають низьку інформаційну ентропію ) - наприклад, малоймовірно, щоб буквосполучення «щи» зустрілося в осмисленому тексті, а в оцифрованному звуці рівень не може за один семпл стрибнути від 0 до 100%. До того ж за рахунок спеціалізації алгоритмів на певний тип даних (текст, графіку, звук і т. Д.) Вдається домогтися високого ступеня стиснення: так, що застосовуються в архіваторах універсальні алгоритми стискають звук приблизно на третину (в 1,5 рази), в той час як FLAC - в 2,5 рази. Більшість спеціалізованих алгоритмів малопридатні для файлів «чужих» типів: наприклад, звукові дані погано стискаються алгоритмом, розрахованим на тексти.

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

00 → 0 01 → 10 10 → 110 11 → 111

В такому випадку шістнадцять бітів

00 01 00 00 11 10 00 00

будуть перетворені в тринадцять бітів

0 10 0 0 111 110 0 0

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

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

Статистичні моделі алгоритмів для тексту (або текстових бінарних даних, таких як виконувані файли) включають:

Алгоритми кодування через генерування бітових послідовностей:

Повний список дивіться в Категорія: Стиснення даних

багатоцільові [ правити | правити код ]

Кодування довжин серій - проста схема, що дає гарне стиснення даних, які містять багато значень, що повторюються
LZW - використовується в gif і в багатьох інших.
Deflate - використовується в gzip, вдосконаленої версії zip і як частина процесу стиснення PNG .
LZMA - використовується у 7-zip .

Стиснення аудіо [ правити | правити код ]

Стиснення графіки [ правити | правити код ]

ABO - Adaptive Binary Optimization
BTPC
CALIC
CREW
CTW
DPCM
GIF - (без втрат лише для зображень, що містять не більше 256 кольорів)
JBIG2 - (з втратами або без ч / б зображень)
Lossless JPEG - (розширення стандарту стиснення JPEG, що забезпечує стиснення без втрат)
JPEG-LS - (стандарт стиснення без втрат / майже без втрат)
JPEG 2000 - (в режимі стиснення без втрат)
LOCO-I
MRP
PGF - Progressive Graphics File (стиснення с / без втрат)
PNG - Portable Network Graphics
PWC
TIFF - (виключаючи режими стиснення з втратами [1] )
TMW
Truevision TGA
HD Photo - (включаючи метод стиснення без втрат)
FLIF - Free Lossless Image Format

Стиснення відео [ правити | правити код ]

Стиснення текстів [ правити | правити код ]

PPM - архіватор HA (Автор Harry Hirvola), який використовує алгоритм PPM, відомий високим ступенем стиснення на текстових файлах; за цим параметром він перевершував перші версії з'явився кілька років по тому RAR . Тому популярні в кінці 90-х років компакт-диски на зразок « Бібліотека в кишені »Використовували саме HA.

сімейство алгоритмів Лемпеля-Зива
RLE (Run-length encoding - Кодування довжин серій)