Сжатие без потерь

---

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

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

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

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

---