Сжатие данных используется в современном мире повсеместно, практические любое общение двух устройств происходит с сжатием и распаковкой данных для экономии объема передаваемых данных. Например, в HTTP используются протоколы deflate, gzip (deflate с улучшениями). Однако, при некоторых условиях можно достичь куда большего сжатия данных, попробуем разработать такой алгоритм.

Математическое обоснование

Есть теорема, которая описывает сжатие без потерь:

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

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

2. Уменьшает некоторый файл длиной не более 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).

1. Считываем файл архива, разбираем метаданные

2. Создаем массив длиной N, равной длине исходного файла, (далее выходной файл)

3. Методом перебора выбираем следующий вариант выходного файла

4. Сжимаем файл (берем его SHA-256 хэш), сравниваем его с данными архива

5. Если сжатый файл не совпадает с данными архива, переходим на шаг 3

6. Сохраняем текущий вариант файла как распакованный файл

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 компаний.