Сжатие данных используется в современном мире повсеместно, практические любое общение двух устройств происходит с сжатием и распаковкой данных для экономии объема передаваемых данных. Например, в HTTP используются протоколы deflate, gzip (deflate с улучшениями). Однако, при некоторых условиях можно достичь куда большего сжатия данных, попробуем разработать такой алгоритм.
Математическое обоснование
Есть теорема, которая описывает сжатие без потерь:
Для любого N > 0 нет алгоритма сжатия без потерь, который:
Любой файл длиной не более N байт или оставляет той же длины, или уменьшает.
Уменьшает некоторый файл длиной не более N хотя бы на один байт.
Докажем полную несостоятельность этой теоремы.
Алгоритм сжатия
А что если использовать хэширование в качестве алгоритма сжатия, например SHA-256?
Во время сжатия будем брать SHA-256 хэш от входного файла и сохранять его в выходной файл вместе с заголовком PK (прямо как в ZIP) и размером исходного файла (Int32, 4 байта).
static void Encrypt(string inputPath)
{
var outputPath = inputPath + ".gigazip";
var inputFile = File.ReadAllBytes(inputPath);
using var file = File.Open(outputPath, FileMode.Create);
file.Write([(byte)'P', (byte)'K']);
//Получаем длину файла в виде байтов (little-endian по умолчанию)
var length = BitConverter.GetBytes(inputFile.Length);
file.Write(length);
file.Write(SHA256.HashData(inputFile));
}Как видно по примеру кода, алгоритм сжатия очень простой и не требует подключения никаких дополнительных библиотек. Архив с сжатыми данными (с учетом метаданных в начале файла) всегда будет весить ровно 38 байт!
Алгоритм распаковки
Распаковка будет происходить с помощью алгоритма, очень похожего на Proof of work, использующийся в реализации различных криптовалют (Bitcoin, Ethereum).
Считываем файл архива, разбираем метаданные
Создаем массив длиной N, равной длине исходного файла, (далее выходной файл)
Методом перебора выбираем следующий вариант выходного файла
Сжимаем файл (берем его SHA-256 хэш), сравниваем его с данными архива
Если сжатый файл не совпадает с данными архива, переходим на шаг 3
Сохраняем текущий вариант файла как распакованный файл
static void Decrypt(string inputPath)
{
var bytes = File.ReadAllBytes(inputPath);
var length = BitConverter.ToInt32(bytes.Skip(2).Take(4).ToArray()); // 4 байта длины выходного файла
var sha256 = bytes.Skip(6).Take(32).ToArray(); // 32 байта сжатых данных
const int parallelismDegree = 5; // Будем считать параллельно в 5 потоках
var files = Enumerable.Range(0, parallelismDegree).Select(x =>
{
var array = new byte[length];
array[^1] = (byte)(x * (0xFF / parallelismDegree)); // указываем диапазон перебора для каждого из параллельных потоков
return array;
})
.ToArray();
Run(parallelismDegree, files, sha256, out var targetFile); // в targetFile будут лежать байты выходного файла
var outputFileName = inputPath[..^8]; // без .gigazip в конце
File.WriteAllBytes(outputFileName, targetFile);
}Алгоритм распаковки
private static void Run(int parallelismDegree, byte[][] files, byte[] sha256, out byte[] target)
{
var targetFile = 0;
Parallel.For(0, parallelismDegree, (index, state) =>
{
while (true)
{
if (state.ShouldExitCurrentIteration)
{
break; // останавливаемся, если распаковка завершена в другом потоке
}
var test = SHA256.HashData(files[index]);
if (test.FastCompareArrays(sha256))
{
targetFile = index;
break;
}
files[index].Increment(); // Выбираем следующий вараинт выходного файла
}
state.Break(); // Останавливаем вычисления
});
target = files[targetFile];
}Другие неинтересные куски кода
internal static class ByteArrayHelpers
{
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static unsafe void Increment(this byte[] array)
{
unchecked // <- отключаем проверку на переполнение типа, 255 + 1 = 0
{
var add = true;
// получаем указатель на массив, работа с ним быстрее (не происходит проверка рантаймом выхода за пределы массива)
fixed (byte* head = array)
{
for (var i = 0; i < array.Length - 1; i++)
{
head[i] += *((byte*)(&add)); // reinterpret_cast
// если 0, значит переполнили байт, прибавляем 1 к следующему
add = head[i] == 0;
}
}
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static unsafe bool FastCompareArrays(this byte[] one, byte[] two)
{
if (one.Length != two.Length)
{
return false;
}
fixed (byte* first = one)
{
fixed (byte* second = two)
{
for (var i = 0; i < one.Length; i++)
{
if (first[i] != second[i])
{
return false;
}
}
}
}
return true;
}
}Эффективность алгоритма
Эффективность данного алгоритма тем больше, чем больше размер исходного файла.
Оценка сложности
Сжатие:
O(N)- временная сложностьO(1)- пространственная сложность
Распаковка:
O(N^N^N^N...)- временная сложностьO(N)- пространственная сложность
Недостатки алгоритма
Основной недостаток алгоритма - достаточно медленный процесс распаковки. Например, фильм Shrek 2 (DreamWorks Animation, все права защищены) в формате UHD весом 60ГБ будет распаковываться ориентировочно лет.
Однако, проблема неоднозначности распаковки (когда одному архиву соответствует несколько выходных файлов) на деле проблемой не является, что будет рассмотрено в следующем разделе.
Достоинства алгоритма
Крайне маленький размер архива
-
Неоднозначность функции хэширования - возможность упаковать в 32 байта несколько входных файлов, к примеру:
Shrek 2, Shrek 1 (DreamWorks Animation, все права защищены)
Саундтрек к этим фильмам
Несколько видеоигр по мотивам этих фильмов
Также, при некоторой оптимизации алгоритма (например, использовании вычислений на видеокарте с помощью CUDA) можно уменьшить ожидаемое время распаковки с до
лет (что уже немалый прогресс).
Заключение
В рамках статьи был предложен инновационный алгоритм сжатия данных, который, надеюсь, в будущем будет использоваться в работе во большинстве крупных IT компаний.
Комментарии (73)
seregablog
01.04.2024 08:59+8Предлагаю сократить сжатие до одного бита - так ещё эффективнее)
stagnantice
01.04.2024 08:59+1А если я возьму все возможные хеши, положу их в файлы, он на выходе по сути даст мне все эти ключи но в другом порядке, а вы говорите что я фильм Шрек получу на одном из них. Нестыковочка
stagnantice
01.04.2024 08:59А, вижу там еще длина файла участвует, ну если есть гарантия что sha256 на одной длине файла всегда даст разный результат, то в принципе вариант рабочий. Но это если очень смущает
Cregennan Автор
01.04.2024 08:59+7Есть вариант получения Шрека из любого хэша, пусть распакованный файл будет такого вида:
4 байта - длина файла
~60ГБ - полезные данные (Шрек 2)
32 байта Nonce (случайное число)
В таком случае даже из хэша
0xFFFFFFFF...рано или поздно можно распаковать и Shrek 2 и Мадагаскар и Тачки 3.stagnantice
01.04.2024 08:59+1Однако, кажущейся проблемой неоднозначность распаковки (когда одному архиву соответствует несколько выходных файлов) на деле ей не является, что будет рассмотрено в следующем разделе.
тогда вот этот кусок я не понял, получается неоднозначность все же есть
Cregennan Автор
01.04.2024 08:59+3Так в этом и плюс, разве нет?) Можно распаковать несколько файлов из одного архива, в какой то момент даже может быть сюжетный поворот которого не было в оригинальном фильме (вероятность этого бесконечно мала, но не 0)
на минус случайно нажал
ClayRing
01.04.2024 08:59+2вероятность этого бесконечно мала
Разве? По моему вероятность этого конечно мала.
chieftain_yu
01.04.2024 08:59+11Я бы не стал ограничиваться только снятыми фильмами.
Так мы можем распаковать и фильмы неснятые, и фильмы утраченные.Более того - это реальный способ восстановить все книги Александрийской библиотеки и все утраченные книги Помпей!
juray
01.04.2024 08:59+1Так это вообще демон Максвелла второго рода получается.
Демон этот магичен, термодинамичен, неклассичен и статистичен, и станет он из старого бочонка или из чиханья экстрагировать и доставлять тебе информацию обо всем, что было, что есть, что может быть и что будет.
(...)
Проблема, однако, стоит вот как: в каждой щепотке воздуха действительно складываются из атомных брыканий и кувырканий важные истины и глубокие сентенции, но вместе с тем возникают совершенно бессмысленные скачки и отскоки, и этих последних в тысячи раз больше, чем первых. Хоть и в прежние времена было известно, что вот сейчас перед твоим носом-пилой в каждом миллиграмме воздуха в любую долю секунды возникают отрывки тех поэм, которые будут написаны только через миллионы лет, и фрагменты возвышенных истин, и разгадки всех загадок Бытия и тайн его, все ж не имелось способа выделить всю эту информацию, тем более что едва лишь атомы лбами столкнутся и в какую-то осмысленную фигуру уложатся, как тут же разлетятся, а вместе с ними и смысл пропадает, быть может, навеки.
Значит, вся хитрость в том, как построить селектор, который будет отбирать только то, что в беготне атомов осмысленно. Вот и вся идея Демона Второго Рода.
(С. Лем. Кибериада, цикл «Семь путешествий Трурля и Клапауция», Путешествие шестое, или Как Трурль и Клапауций Демона Второго Рода создали, дабы разбойника Мордона одолеть.)
raamid
01.04.2024 08:59+8А если всмонить, про закон Мура про удваивание количества транзисторов на чипе каждые два года, то время распаковки существенно снижается!
Все что нужно, это во время распаковки каждые 2 года менять компьютер. При этом нужно будет сохранять где-то состояние, на котором остановились, но это это уже мелочи.
killyself
01.04.2024 08:59+3Можно улучшить распаковку - сохранять индекс на котором получили файл, и запускать повторно с этого места по запросу пользователя, тогда через X попыток распаковки гарантированно получим исходный файл. Правда, временные метрики придётся поднять до 2^N лет, но это пустяки
Kelbon
01.04.2024 08:59+2У вашего алгоритма может на выходе получиться не тот файл что зашифровывали, есть алгоритм куда лучше:
в файл записываем
1. номер алгоритма генерации псевдослучайных чисел
2. seed для него
3. офсет с какого числа начинать (F)
4. сколько случайных чисел генерировать (N)При распаковке создаем генератор чисел, с нужным seed, пропускаем первые F чисел и в результирующий файл складываем следующие N чисел в виде байт, всё.
alexxisr
01.04.2024 08:59+2В вашем алгоритме F может оказаться слишком большим и архиватор вместо сжатия будет увеличивать файл.
yatanai
01.04.2024 08:59Эта интересная статья навела меня на мысли...
Вот даже ваша реализация, можно же не только использовать не только seed, а в целом коэффициенты ГСПЧ. Думаю это реально посчитать для небольших файликов. Может для игр это был бы оверкил, где много маленьких файликов...
Spyman
01.04.2024 08:59+2Если идея в том, чтобы использовать словарь алгоритмов рандомизации, подбирая к ним коеффициенты таким образом, чтобы на выходе получался результирующий файл - то её можно упростить до использование просто словаря с переменной длинной. Всё равно чтобы этим пользоваться вам надо столько алгоритмов и параметров, чтобы иметь возможность закодировать любую последовательность определённой длинны, иначе найдутся файлы которые вы не сможете сжать. А вообще это похоже на кадирование аудио через дискретное преобразование фурье - раскладываем сигнал на синусоиды и записываем их параметры вместо сигнала.
Shado_vi
01.04.2024 08:59у меня в голове вертится упрощенно такое:
> алгоритм:число итераций:метки блоков
* алгоритм - на какой основе например число Пи и длина блока
без него не получить данных, то есть очень защищено.
размер мизерный. но "высокий расход на упаковку/распаковку"
_у меня отсутствуют фундаментальные знания по информатике и математике._
и подобное наверняка уже реализовано, но почему не встречается на практике
sYB-Tyumen
01.04.2024 08:59+2Берём много-много кубитов, закидываем в коробку из-под кота, трясём и, когда хэш сошёлся (они все выпали в состояния битов исходного файла или коллизии хэша) - разархивация состоялась.
DvoiNic
01.04.2024 08:59+3Ха! может, кто из "олдов" вспомнит - ходил году в 1993 т.н. "фрактальный архиватор". Тоже жал любой файл в 32 байта, чтоль... (на самом деле писал файл то-ли в скрытый файл, то-ли как-то по другому в файловой системе скрывал архив - а в 32 байтах просто ссылка была). Но многие на него повелись... пытались дизассемблировать и разобраться в алгоритме...
a-tk
01.04.2024 08:59В наше время содержимое данные принято прикапывать в облаке.
А ещё много приколов было когда появилась NTFS с альтернативными потоками на файловой системе.
polos75
01.04.2024 08:59Я сам такой делал, чтобы удивить одногруппников, мы как раз фракталами занимались. Не знал, что ещё такие были, хотя как не быть...
NeoCode
01.04.2024 08:59+3Кроме шуток, у меня есть похожая идея, возникшая в результате вполне реального кейса.
Сжатие - считаем хеш, смотрим в DHT (торренты и прочие p2p сети), если файл там есть - считаем что он сжат и включаем в архив хеш файла. Если нет - сжимаем как обычно.
Распаковка - если в архиве хеш, то ищем в DHT и скачиваем, если не хеш - распаковываем обычным образом.
Для всяких там дистрибутивов наверняка будут фантастические коэффициенты сжатия, потому что большинство файлов как правило не меняется.
А идея возникла вот на каком месте. На компьютерах тем или иным образом появляется множество файлов, о назначении которых пользователи могут забыть или не знать (обычно - файлопомойка в папке Downloads, но бывают и более экзотические случаи). Хорошо бы иметь сервис типа Virustotal, который по хешу файла говорил бы, что это вообще такое.
FreeNickname
01.04.2024 08:59+2Эммм... IPFS?
VADemon
01.04.2024 08:59+1Имхо, фатальный недостаток IPFS: разбиение и адресация по блокам, что большинству типов данных (обычно запакованных) не подходит.
vikarti
01.04.2024 08:59Почему?
вот IPFS-cid копии этой страницы (с внедренными картинками и прочим) QmQTQYD8iguKBkJttaZDpjTt8Zo4aYp6mQDgNsqm43vzyE
если нет клиента то через публичные gateway'и можно проверить, например
VADemon
01.04.2024 08:59Потому что большинство (форматов) данных переменной длины. Самый банальный пример: если я добавлю один байт в начало Войны и Мира, то все последующие блоки съедут. Только в лучшем случае я допишу байт в конец и изменится всего один блок.
Это же касается большинства сжатых данных и их архивов. Хотя вроде ради rsync какой-то архиватор в Linux добавлял опцию, чтобы у измененного архива был меньший diff, теоретически в этом направлении можно развиваться, но на сегодня это не практично.
Компромиссом было бы иметь data format aware разбиение на блоки, но тут во весь рост встала бы проблема разницы имплементаций, когда кто-то уже успел внедрить извлечение встроенных объектов в PDF (типа картинок), а другие ещё нет.
PS: Это на основе того, какая у стандартной реализации IPFS сейчас проблема с масштабированием, особенно по занимаемой оперативке.
kasiopei
01.04.2024 08:59+1Можно брутфорсом exe файл генерить и проверять получился архиватор или нет)))))
Format-X22
01.04.2024 08:59Можно методом колеса, самый эффективный способ во вселенной, на данный момент. Хранить вообще особо ничего не нужно, можно всё получить на ходу. И сжатый файл, и разжатый, и хеш, и кеш, и даже имя человека что этот файл сжимал. Достаточно школьных знаний о том что число Пи содержит в себе все возможные последовательности чисел и если взять колесо и начать считать длину его окружности, то можно извлечь все данные вселенной, через некоторое время…
Moog_Prodigy
01.04.2024 08:59Кстати да, поговаривают, что в последних цифрах числа Пи зашифрована мудрость великая. Неспроста они там триллионы знаков вычисляют.
sashailinsky
01.04.2024 08:59ChatGPT4 мне отвечает примерно так же, как в начале статьи написано. Я даже сначала подумал, что сгенерирован текст.
Rubilnik
01.04.2024 08:59+9Предлагаю показать алгоритм провайдерам и ФСБ для более эффективной реализации закона Яровой.
fire64
01.04.2024 08:59+1Ну чисто технически да вполне себе рабочий алгоритм. Из минусов, не очень быстрый. А по поводу неоднозначности, можно сделать итоговый размер побольше, если использовать несколько типов хешей, т.е. md5, crc и т.д. таким образом при распаковке мы сможем сверять несколько контрольных сумм, это убережёт нас от неоднозначности результатов распаковки.
Spyman
01.04.2024 08:59+1Насколько я помню - до тех пор пока объем сохраненных хешей не сравняется с размером искомого файла, от неоднозначности не убережет, но уменьшит вероятность)
kraidiky
01.04.2024 08:59+1Вот вы все ржёте, а алгоритмы экстримального сжатия реально существуют. Например почти любой текст можно сжать всего до нескольких бит на слово, и это далеко не первоапрельская шутка.
Просто в наше время уже как-то не принято меряться архиваторами.
yatanai
01.04.2024 08:59Помню в шараге учился, там какой-то гений записал все части GTA на оптический диск в 4ГБ. Был правда один нюанс, я попытался установить с того образа GTA 4 и на моём Core2Duo чотатам оно 2 дня распаковывалось.
Тот кто нарезал болванку хвалился что нашёл какой-то математический алгоритм который представлял файл как точку на отрезке [1:0] + таблицы + какая-то магия.
raamid
01.04.2024 08:59А можно еще так. Любой файл конечного размера по определению уже находится в числе Пи, которое бесконечно. Нужно всего лишь при запаковке найти номер позиции в числе Пи с которой начинается непрерывная последовательность байт, соотвествующих файлу.
А потом взять хеш от числа номера позиции. И хеш от числа Пи (на всякий случай :D)
Spyman
01.04.2024 08:59Не на всякий случай, а потому что номер позиции в числе Пи может быть сильно больше, чем искомый файл, а с хешом проблема решена)
raamid
01.04.2024 08:59Здесь еще один момент, связанный с безопасностью. Злоумышленники могут подменить число Пи и тогда мы получим неправильный результат. Вот для чего нужна контрольная сумма числа Пи.
Скептики могут возразить, что число Пи - это бесконечный ряд цифр, как же мы можем вычислить его контрольную сумму. Кто не хочет, тот ищет оправдания, а кто хочет, ищет возможности. Нужно просто сесть и подумать :)
ImagineTables
01.04.2024 08:59Есть теорема, которая описывает сжатие без потерь
С этой теоремой у меня связано одно из детских воспоминаний.
Прочёл я в детстве статью, где некий журналист обзирал идеи Станислава Лема. Не могу поручиться, что
«з», а не «с»это были идеи именно Лема, а не «Мойша напел», но это неважно. Одной из идей [якобы] была т.н. эволюционная декомпрессия. Мол, если взять семечко и посадить в землю, из него вырастет дерево. Семечко простое, а дерево — сложное. Как так? А вот так. Эволюция, оказывается, научилась компрессировать данные в семечко, чтобы оно развилось в дерево, а тупые люди — пока ещё нет, но рано или поздно догадаются, и здравствуй, гигазип, и сжатие в десятки тысяч раз.Что-то в этом показалось мне глубоко неправильным. Я думал-думал, и решил оценить, как же соотносится число возможных вариантов файлов данного размера и число файлов в 10000 раз больше. И понял, что… как говорит Википедия, «функция декомпрессии неоднозначна». Так я в детстве переоткрыл принцип Дирихле. (Гордиться тут нечем, потому что надо быть олигофреном, чтобы не додуматься до принципа Дирихле. Скорее, удивляет, как эта статья вообще прошла мимо редактора).
И только после того, как я созрел
из семечкаво взрослого дяденьку и ознакомился с основами биологии, генетики и теории эволюции, до меня вдруг дошло: а в каком месте превращение семечка в дерево вообще считается декомпрессией и разворачиванием из простого в сложное?!
balamutang
01.04.2024 08:59Ну в том-то и дело что семечка это текст написанный 1м кеглем, а дерево это тотже текст написанный 120 кеглем. Визуально отличаются, но по содержимому - нет
vvzvlad
01.04.2024 08:59Что вы несете? Семечко это описание структуры “вот там внизу корень, там вот такие клетки, посередине ствол, там такие, сверху — листья, там такии и такие”. А в итоговом дереве клеток много-много, поэтому оно кажется больше (но сложность самих клеток не изменилась), а большая часть сложности того, как эти клетки друг с другом соединяются — задается рандомом/ветром/етс и в семечке не описана.
bankir1980
01.04.2024 08:59+1Такое люди уже давно изобрели. Семечко - проект на бумаге (папочка с листочками), дерево - построенный по проекту небоскреб. По аналогии можно и фильм упаковать. Текстовое описание заархивировать, а на выходе на основе текста ИИ генерирует фильм +- похожий на оригинал.
sert
01.04.2024 08:59Надо радужные таблицы, для всех файлов сделать. Тогда распаковаваться будет мгновенно :)
Ivan22
01.04.2024 08:59что-то попахивает старьем. Сейчас на дворе 2024, архив должен представлять из себя промпт для chatGPT в ответ на который он сгенерит нужный файл. Не благодарите
vikarti
01.04.2024 08:59Вот вам версия 2022 года - https://arstechnica.com/information-technology/2022/09/better-than-jpeg-researcher-discovers-that-stable-diffusion-can-compress-images/
По сути используется доработанная Stable Diffusion для архивации картинок. Качество правда страдает ну так картинке же. Ну и модель надо за собой таскать.
assad77
01.04.2024 08:59А зря смеетесь. Именно так архивы и делаются. Например есть такое понятие как дедубликация. Когда некому хешу устанавливается в соответствие блоб. В этом случае в архиве хранятся ссылки на хеши. Вот сами прикиньте, пользователи часто льют одни и те же данные типа инсталляторов, фильмов, и прочего, и смысла хранить это во многих экземплярах нет никакого. И в Яндекс диске такое используется. Они даже не отправляют файл, если файл с таким хешом существует.
Jonny4872
01.04.2024 08:59Давеча помнится байка ходила про запись любого объема информации на деревянной палке. Нужно просто перевести файл в десятичное число, поставить перед ним 0. И разделить палку на 2 отрезка в соответствующей пропорции.
ARad
01.04.2024 08:59Такая распаковка будет эффективно работать на квантовом компьютере с достаточным количеством кубитов. Единственное она будет распаковывать в один из возможных вариантов (а их огромное количество) и поэтому нужны будут алгоритмы, которые научат квантовый компьютер отсекать неверные (маловероятные) варианты исходного файла.
Проблема квантовых компьютеров, в том, что хотя внутри он просчитал все возможные варианты исходных данных, за раз вы можете извлечь из него только какой один случайный вариант исходных данных.
Если вы научите квантовый компьютер ПРАВИЛЬНО оценивать вероятности того или иного исходного файла, то это сильно поможет, потому что наиболее вероятные варианты чаще всего и извлекаются за раз.
forever_17_old
01.04.2024 08:59Есть проблема в виде коллизии хэша.
Однажды вы захотите распаковать своему ребëнку мультик, а там жëсткое порно с клоунами...
AlexSpirit
Я такой архиватор в молодости на ASM-е написал. Но разархиватор к нему не успел. На работу устроился.
tuxi
Да чтож такое!!! Я тоже студентом делал. Тогда только только появились первые модемы на 1200 бод и размер файлов был очень актуальной метрикой...
samozvet
1+2+3+4+5+6=21=2+1=3
не благодарите
vikarti
Да вообщем то есть продукты которые такую архивацию используют. Вот только работают в распределенном режиме и по блокам - зачем подбирать хеш индивидуально если можно спросить через DHT узлы, не знает ли кто то из них блоки подходящие под конкретный хеш. Вот только Злые Силы активно противодействую внедрению прогрессивных технологий, пробуют запретить (с переменным успехом) хеши соответствующие и софт.