Сжатие без потерь | это... Что такое Сжатие без потерь? (original) (raw)

У этого термина существуют и другие значения, см. Сжатие.

Сжатие данных без потерь (англ. Lossless data compression) — метод сжатия данных: видео, аудио, графики, документов представленных в цифровом виде, при использовании которого закодированные данные могут быть восстановлены с точностью до бита. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия принципиально отличается от сжатия данных с потерями. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия без потерь.

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

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример — исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG, используют только сжатие без потерь; тогда как другие (TIFF, MNG) или GIF могут использовать сжатие как с потерями, так и без.

Содержание

Сжатие и комбинаторика

Легко доказывается теорема.

Для любого N > 0 нет алгоритма сжатия без потерь, который:

  1. Любой файл длиной не более N байт или оставляет той же длины, или уменьшает.
  2. Существует файл длиной не более N, который уменьшается хотя бы на один байт.

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

Впрочем, данная теорема нисколько не бросает тень на сжатие без потерь. Дело в том, что любой алгоритм сжатия можно модифицировать так, чтобы он увеличивал размер не более чем на 1 бит: если алгоритм уменьшил файл, пишем «1», потом сжатую последовательность, если увеличил — пишем «0», затем исходную. Пример того, как это реализуется на псевдо-C++, показан ниже:

bin_data_t __compess(bin_data_t input) // bin_data_t - тип данных, означающий произвольную последовательность бит переменной длины { bin_data_t output = arch(input); // функция bin_data_t arch(bin_data_t input) реализует некий алгоритм сжатия данных if (output.size()<input.size()) // если алгоритм уменьшил размер данных, функция bin_data_t::size() возвращает размер данных { output.add_begin(1); // функция bin_data_t::add_begin(bool bit) добавляет бит, равный bit в начало последовательности return output; // возвращаем сжатую последовательность с добавленной «1» } else // иначе (если алгоритм увеличил или не изменил размер данных) { input.add_begin(0); // добавляем «0» к исходной последовательности return input; // возвращаем исходный файл с добавленным «0» } }

Так что несжимаемые фрагменты не приведут к бесконтрольному «раздуванию» архива. «Реальных» же файлов длины N намного меньше, чем 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

Такая подстановка является префиксным кодом, то есть обладает такой особенностью: если мы запишем сжатую строку без пробелов, мы всё равно сможем расставить в ней пробелы — а значит, восстановить исходную последовательность. Наиболее известным префиксным кодом является код Хаффмана.

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

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

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

Методы сжатия без потерь

Полный список смотрите в Категория:Сжатие данных

Многоцелевые

Сжатие аудио

Сжатие графики

Сжатие видео

Сжатие текстов

Примеры алгоритмов

Примеры форматов и их реализаций

См. также

Примечания

  1. ↑ Спецификация TIFF v6

Ссылки

Просмотр этого шаблона Методы сжатия
Теория Информация Собственная · Взаимная · Энтропия · Условная энтропия · Сложность · Избыточность Единицы измерения Бит · Нат · Ниббл · Хартли · Формула Хартли
Без потерь Энтропийное сжатие Алгоритм Хаффмана · Адаптивный алгоритм Хаффмана · Алгоритм Шеннона — Фано · Арифметическое кодирование (Интервальное) · Коды Голомба · Дельта · Универсальный код (Элиаса · Фибоначчи) Словарные методы RLE · Deflate · LZ (LZ77/LZ78 · LZSS · LZW · LZWL · LZO · LZMA · LZX · LZRW · LZJB · LZT) Прочее RLE · CTW · BWT · MTF · PPM · DMC
Аудио Теория Свёртка · PCM · Алиасинг · Дискретизация · Теорема Котельникова Методы LPC (LAR · LSP) · WLPC · CELP · ACELP · A-закон · μ-закон · MDCT · Преобразование Фурье · Психоакустическая модель Прочее Компрессор аудиосигнала · Сжатие речи · Полосное кодирование
Изображения Термины Цветовое пространство · Пиксель · Субдискретизация насыщенности · Артефакты сжатия Методы RLE · DPCM · Фрактальный · Вейвлетный · EZW · SPIHT · LP · ДКП · ПКЛ Прочее Битрейт · Test images · PSNR · Квантование
Видео Термины Характеристики видео · Кадр · Типы кадров · Качество видео Методы Компенсация движения · ДКП · Квантование · Вейвлетный Прочее Видеокодек · Rate distortion theory (CBR · ABR · VBR)