Сжатие множества больших целых чисел

У меня есть набор целых чисел, для которых я хотел бы иметь самое компактное представление. У меня есть следующие ограничения/функции:

он установлен, или, другими словами, список уникальных целых чисел, в которых порядок не имеет значения.
размер множества L относительно невелик (обычно 1000 элементов)
целые числа следуют равномерному распределению между 0 и N-1, причем N относительно велико (скажем, 2 ^ 32)
доступ к элементам сжатого набора является случайным, но это нормально, если процедура декомпрессии не так быстро
сжатие должно быть без потерь, очевидно

Я пробовал несколько вещей, но результаты не удовлетворены, и я как-то убежден, что существует лучшее решение:

дельта-кодирование (сортировка, затем различие в кодировке) или сортировка, а затем кодирование различий между i-м элементом и я * N/L. Оба дают разумные результаты, но не велики, вероятно, из-за типичных размеров кодирования N и L. Huffman, дельта не помогает, потому что они обычно большие.
рекурсивное уменьшение диапазона (http://ygdes.com/ddj-3r/ddj-3r_compact.html). Это кажется умным, но лучше всего работает с экспоненциально уменьшающимися целыми числами, что определенно не так.
несколько обсуждений здесь о stackoverflow похожи, но не полностью эквивалентны моей проблеме (C Library для сжатия последовательных положительных целых чисел, Сжатие отсортированных целых чисел)

Я был бы рад услышать любые твои идеи. Спасибо заранее!

UPDATE:

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

Ответ 1

Вы можете получить представление о том, что вы можете сделать, посчитав. (Я бы хотел, чтобы stackoverflow разрешил TeX-уравнения, такие как math.stackexchange. В любом случае...)

ceiling(log(Combination(2^32,1000)) / (8 * log(2))) = 2934

Итак, если, как вы говорите, выбор распределяется равномерно, наилучшее сжатие, на которое вы могли бы рассчитывать в среднем для этого конкретного случая, - 2934 байта. Наилучшее соотношение - 73,35% от некодированного представления 4000 байтов.

Combination(2^32,1000) - это просто общее количество возможных входов в алгоритм сжатия. Если они распределены равномерно, то оптимальное кодирование представляет собой одно гигантское целое число, которое идентифицирует каждый возможный вход по индексу. Каждое гигантское целочисленное значение однозначно идентифицирует один из входов. Представьте, что вы просматриваете ввод по индексу в гигантской таблице. ceiling(log(Combination(2^32,1000)) / log(2)) - сколько бит вам нужно для этого целого индекса.

Update:

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

Для примера (1000 однородных и отдельных выборок из 0..2 ^ 32-1), я получаю в среднем 3110 байт при запуске через gzip -9 и 3098 байт через xz -9 (xz использует тот же сжатие, LZMA, как 7zip). Это довольно близко к теоретическому лучшему среднему значению 2934. Также gzip имеет накладные расходы в 18 байт, а xz имеет накладные расходы в 24 байта, как для заголовков, так и для трейлеров. Таким образом, более справедливое сравнение с теоретическим лучшим будет 3092 для gzip -9 и 3074 для xz -9. Примерно на 5% больше теоретического.

Обновление 2:

Я реализовал прямое кодирование перестановок и достигло в среднем 2974 байта, что лишь немногим более 1% больше, чем теоретическое. Я использовал библиотеку арифметических данных с множественной точностью GNU для кодирования индекса для каждой перестановки в гигантском целочисленном значении. Фактический код для кодирования и декодирования показан ниже. Я добавил комментарии для функций mpz_*, где это может быть не очевидно из имени, какие арифметические операции они делают.

/* Recursively code the members in set[] between low and high (low and high
   themselves have already been coded).  First code the middle member 'mid'.
   Then recursively code the members between low and mid, and then between mid
   and high. */
local void combination_encode_between(mpz_t pack, mpz_t base,
                                      const unsigned long *set,
                                      int low, int high)
{
    int mid;

    /* compute the middle position -- if there is nothing between low and high,
       then return immediately (also in that case, verify that set[] is sorted
       in ascending order) */
    mid = (low + high) >> 1;
    if (mid == low) {
        assert(set[low] < set[high]);
        return;
    }

    /* code set[mid] into pack, and update base with the number of possible
       set[mid] values between set[low] and set[high] for the next coded
       member */
        /* pack += base * (set[mid] - set[low] - 1) */
    mpz_addmul_ui(pack, base, set[mid] - set[low] - 1);
        /* base *= set[high] - set[low] - 1 */
    mpz_mul_ui(base, base, set[high] - set[low] - 1);

    /* code the rest between low and high */
    combination_encode_between(pack, base, set, low, mid);
    combination_encode_between(pack, base, set, mid, high);
}

/* Encode the set of integers set[0..num-1], where each element is a unique
   integer in the range 0..max.  No value appears more than once in set[]
   (hence the name "set").  The elements of set[] must be sorted in ascending
   order. */
local void combination_encode(mpz_t pack, const unsigned long *set, int num,
                              unsigned long max)
{
    mpz_t base;

    /* handle degenerate cases and verify last member <= max -- code set[0]
       into pack as simply itself and set base to the number of possible set[0]
       values for coding the next member */
    if (num < 1) {
            /* pack = 0 */
        mpz_set_ui(pack, 0);
        return;
    }
        /* pack = set[0] */
    mpz_set_ui(pack, set[0]);
    if (num < 2) {
        assert(set[0] <= max);
        return;
    }
    assert(set[num - 1] <= max);
        /* base = max - num + 2 */
    mpz_init_set_ui(base, max - num + 2);

    /* code the last member of the set and update base with the number of
       possible last member values */
        /* pack += base * (set[num - 1] - set[0] - 1) */
    mpz_addmul_ui(pack, base, set[num - 1] - set[0] - 1);
        /* base *= max - set[0] */
    mpz_mul_ui(base, base, max - set[0]);

    /* encode the members between 0 and num - 1 */
    combination_encode_between(pack, base, set, 0, num - 1);
    mpz_clear(base);
}

/* Recursively decode the members in set[] between low and high (low and high
   themselves have already been decoded).  First decode the middle member
   'mid'. Then recursively decode the members between low and mid, and then
   between mid and high. */
local void combination_decode_between(mpz_t unpack, unsigned long *set,
                                      int low, int high)
{
    int mid;
    unsigned long rem;

    /* compute the middle position -- if there is nothing between low and high,
       then return immediately */
    mid = (low + high) >> 1;
    if (mid == low)
        return;

    /* extract set[mid] as the remainder of dividing unpack by the number of
       possible set[mid] values, update unpack with the quotient */
        /* div = set[high] - set[low] - 1, rem = unpack % div, unpack /= div */
    rem = mpz_fdiv_q_ui(unpack, unpack, set[high] - set[low] - 1);
    set[mid] = set[low] + 1 + rem;

    /* decode the rest between low and high */
    combination_decode_between(unpack, set, low, mid);
    combination_decode_between(unpack, set, mid, high);
}

/* Decode from pack the set of integers encoded by combination_encode(),
   putting the result in set[0..num-1].  max must be the same value used when
   encoding. */
local void combination_decode(const mpz_t pack, unsigned long *set, int num,
                              unsigned long max)
{
    mpz_t unpack;
    unsigned long rem;

    /* handle degnerate cases, returning the value of pack as the only element
       for num == 1 */
    if (num < 1)
        return;
    if (num < 2) {
            /* set[0] = (unsigned long)pack */
        set[0] = mpz_get_ui(pack);
        return;
    }

    /* extract set[0] as the remainder after dividing pack by the number of
       possible set[0] values, set unpack to the quotient */
    mpz_init(unpack);
        /* div = max - num + 2, set[0] = pack % div, unpack = pack / div */
    set[0] = mpz_fdiv_q_ui(unpack, pack, max - num + 2);

    /* extract the last member as the remainder after dividing by the number
       of possible values, taking into account the first member -- update
       unpack with the quotient */
        /* rem = unpack % max - set[0], unpack /= max - set[0] */
    rem = mpz_fdiv_q_ui(unpack, unpack, max - set[0]);
    set[num - 1] = set[0] + 1 + rem;

    /* decode the members between 0 and num - 1 */
    combination_decode_between(unpack, set, 0, num - 1);
    mpz_clear(unpack);
}

Существуют функции mpz_* для записи числа в файл и чтения его или экспорта номера в указанный формат в памяти и его импорта.

Ответ 2

Если целые числа являются случайными, не связанными и действительно следуют закону равномерного распределения над [0, 2³²-1 [, вероятно, можно продемонстрировать, что вы не можете сжать массив из тривиального представления. Я что-то пропустил в вашем вопросе?

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

Я использую deflate для сжатия небольших массивов (от 300 до 2000 32-битных целых чисел) физических измерений датчиков и получения 70% -ного усиления, но это потому, что последовательные измерения датчика редко очень различаются.

Вероятно, будет нелегко найти улучшенный алгоритм, подходящий для всех ситуаций. Большинство улучшений исходит из особенностей вашей серии номеров.

Вы также можете заметить, что у вас будет лучший коэффициент сжатия, сжимая множество множеств. Конечно, это может быть очень неудобно, в зависимости от вашего приложения.

Ответ 3

Тема еще открыта?

В настоящее время я работаю над этим.
(PS: я создатель игры, а не математик)
Не могу спать несколько недель, потому что мне интересно, почему мы не используем вариант A ^ B + C (или другой) для сжатия изображений и информации.

Моя цель в утопии - сжать число в 4 600 000, используя менее вероятную комбинацию формулы A ^ B + C, созданную из графического процессора компьютера. По сути, я пытаюсь это сделать, потому что это позволит хранить/передавать небольшое изображение под (& lt; 100 символов) без потери качества при скорости 30 кадров в секунду через Wi-Fi и без потери пропускной способности.

Моя реалистичная цель - сжать 200 цифр до & lt; 5 символов.

PS: Для этого я уже создал "Base Chinais" Если вы хотите использовать это:
- https://github.com/EloiStree/2019_09_19_MathCompressionOfImage/wiki/SouthChinais
- https://gitlab.com/eloistree/2019_09_06_UnicodeBasedId

База (китайцы) 䶯 = 38727
Это позволяет преобразовать 2307 ^ 200 + 32450 в 碸 ^ 災 + 㔩
Если вы попробуете использовать raw для сжатия BigInteger, базовое предложение китайцев составит 4-4,5x от
Сжатие:
1413546486463454579816416416416462324833676542
4 갱 澻 둲 觋㷬乮䄠櫡䒤 갱

Теперь мне нужно сжать & lt; 200 цифр до 9999 ^ 9999 + 99999999
Если у вас есть идея или альтернатива A ^ B + C, не стесняйтесь предупредить меня.
Я трачу много времени на эксперименты с Unity3D.
Я опубликую то, что я нашел на sujet здесь:
https://github.com/EloiStree/2019_09_19_MathCompressionOfImage/wiki

Надеюсь, что это поможет следующим людям, попавшим сюда.

Найди меня на Discord, если хочешь поговорить об этом.
https://eloistree.page.link/discord