Сжатие данных — это искусство уменьшать количество бит, нужных для хранения или передачи информации. Любой алгоритм сжатия состоит минимум из модели и кодера. Модель оценивает вероятности символов (буква E встречается чаще Z), а кодер присваивает вероятным символам короткие коды. С кодированием всё решено — есть эффективные и оптимальные методы. А вот оптимальное моделирование принципиально невычислимо, и это доказано.
Не существует универсального алгоритма, который сожмёт любой входной файл. Это следует из простого подсчёта: строк длины n — 2^n штук, а строк короче n — всего 2^n − 1. Значит, часть данных при любом сжатии неизбежно увеличится в размере. Случайные данные не сжимаются, и сжимать рекурсивно (результат сжатия ещё раз) бессмысленно — на выходе будет казаться случайным.
У сжатия есть фундаментальная граница — энтропия. Если известна вероятность p символа, лучший код для него занимает log₂(1/p) бит. Для равномерно распределённых цифр числа π (вероятность каждой 0,1) энтропия равна 3,3219 бита на символ — это нижний предел. Арифметическое кодирование практически достигает этой границы. Но загвоздка в том, что настоящая модель данных обычно неизвестна. Цифры π на самом деле не случайны — их можно описать короткой программой. Оптимальное сжатие эквивалентно поиску кратчайшего описания (программы), порождающего данные. Эта длина называется колмогоровской сложностью. И доказано, что вычислить её для произвольной строки невозможно — нет и теста на «случайность» данных.
Сжатие — это по сути искусственный интеллект. Чтобы хорошо сжать текст, нужно понимать язык и предсказывать следующие символы. Лучшие текстовые компрессоры (PAQ, ZPAQ) приближаются к оценкам Шеннона по информационной ёмкости английского языка (0,6–1,3 бита на символ).
В качестве бенчмарков до сих пор используют Calgary corpus — набор из 14 файлов (текст, бинарники, изображения, сейсмика) общим размером около 3 МБ. Анализ повторов внутри корпуса (например, тёмные полосы на визуализации соответствуют символам перевода строки или структуре машинных инструкций в OBJ2) помогает проектировать алгоритмы. В рамках Calgary Compression Challenge лучший результат на июль 2010 года показал Александр Ратюшняк — 580 170 байт в сумме, включая размер самого декомпрессора.