Существует ли идеальное сжатие без потери данных?

[NEO SPECTRUMAN]

И ни одного пикселя не получили +-2 и более.

плавные градиенты наверное лучше пожмуться

Картинка картинке рознь.

ну до

[Advertiser]

[Barmaley_m]

Насколько я понимаю, стоит задача сжать один конкретный набор данных таким образом, чтобы размер депакера + размер запакованных данных были минимальными.

В таком случае теория знает эту задачу под названием "Колмогоровская сложность". Грубо говоря, колмогоровская сложность - это минимальная длина программы, которая выводит на экран заданную строку. При этом под "строкой" можно понимать распакованные данные, а под "выводом на экран" - процесс распаковки. Колмогоровская сложность зависит от того, на каком компьютере работает программа, но для компьютеров и языков общего назначения различия невелики.

К сожалению, в теории доказывается, что колмогоровская сложность невычислима. Не существует алгоритма, который мог бы по заданной строке рассчитать ее колмогоровскую сложность.

Следствие - не существует алгоритма, который бы по заданной строке нашел бы программу минимальной длины, которая выводит эту строку на экран. В самом деле, если бы такой алгоритм существовал - то можно было бы тупо измерить длину получившейся программы и тем самым вычислить колмогоровскую сложность, что противоречит п. 1.

Также невозможно проверить, является ли заданная программа минимальной для вывода на экран некоторой строки.

Если бы алгоритм расчета колмогоровской сложности существовал - то были бы возможны следующие чудеса. Например: мы берем последовательно числа 0, 1, 2, 3 и т.д. Шифруем эти числа каким-нибудь неизвестным науке шифром, ключ не запоминаем. Получаем абракадабру на несколько гигабайт. И скармливаем её программе расчета колмогоровской сложности (которая, как мы на минуту представили, существует). Так вот, при этом программа расчета колмогоровской сложности "увидела бы", что та абракадабра, которую мы ей скормили, является на самом деле зашифрованным текстом; нашла бы алгоритм шифрования и ключ. И оформила бы вывод этой абракадабры на экран самым коротким образом - "синтезировав" программу, фактически повторяющую процесс шифрования.