Сжатие отсортированных целых чисел

Ответ 1

Если вы храните целые числа, близкие друг к другу (например: 1, 3, 4, 5, 9, 10 и т.д.), а не некоторые случайные 32-битные целые числа (982346..., 3487623412.. и т.д.), вы можете сделать одно:

Найдите различия между соседними номерами, которые были бы похожими на 2,1,1,4,1... и т.д. (в нашем примере), а затем кодирование Хаффмана эти цифры.

Я не думаю, что кодировка Хаффмана будет работать, если вы прямо примените их к исходному списку номеров, которые у вас есть.

Но если у вас есть отсортированный список близлежащих чисел, вероятность того, что вы получите очень хорошую степень сжатия, сделав кодировку Хаффмана числовых различий, может быть лучше, чем с использованием алгоритма LZW, используемого в Библиотеки Zip.

В любом случае спасибо за публикацию этого интересного вопроса.

Ответ 2

Являются ли целые числа сгруппированы плотным образом или разреженным способом?

Плотным я имею в виду:

[1, 2, 3, 4, 42, 43, 78, 79, 80, 81]

В редких случаях я имею в виду:

[1, 4, 7, 9, 19, 42, 53, 55, 78, 80]

Если целые числа сгруппированы плотным образом, вы можете сжать первый вектор для трех диапазонов:

[(1, 4), (42, 43), (78, 81)]

Это 40% -ное сжатие. Конечно, этот алгоритм не работает на разреженных данных, поскольку сжатые данные занимают на 100% больше места, чем исходные данные.

Ответ 3

Как вы обнаружили, отсортированная последовательность из N 32-битовых целых чисел не содержит 32 * N бит данных. Это не удивительно. Если не считать дубликатов, для каждой отсортированной последовательности есть N! unsorted seqeuences, содержащие одни и те же целые числа.

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

Однако возьмите последовательность Фибоначчи. Это определенно отсортированные целые числа. Разница между F (n) и F (n + 1) равна F (n-1). Следовательно, сжатие последовательности различий эквивалентно сжатию самой последовательности - это совсем не помогает!

Итак, нам действительно нужна статистическая модель ваших входных данных. Учитывая последовательность N [0]... N [x], каково распределение вероятностей N [x + 1]? Мы знаем, что P (N [x + 1] < N [x]) = 0, поскольку последовательность сортируется. Реализованные на основе дифференциальных/хаффмановских решений, поскольку они предполагают, что P (N [x + 1] - N [x] = d) достаточно велико для малого положительного d и не зависит от x, поэтому они могут использовать несколько бит для небольшие различия. Если вы можете дать другую модель, вы можете ее оптимизировать.

Ответ 4

Если вам нужен быстрый поиск по произвольному доступу, то кодировка Хаффмана различий (как было предложено Ниязом) - это всего лишь половина истории. Вероятно, вам также понадобится какая-то схема подкачки/индексации, чтобы было легко извлечь n-й номер.

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

Ответ 5

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

EDIT: Мой ответ был только общим указателем. Предложение Нияза о кодировании различий между последовательными номерами является хорошим. (Однако, если список не упорядочен или расстояние между номерами очень нерегулярно, я думаю, что было бы не менее эффективно использовать обычную кодировку Хаффмана. Фактически LZW или подобное, вероятно, было бы лучше в этом случае, хотя, возможно, все еще не очень хорошо.)

Ответ 6

Условия в списках целых чисел несколько отличаются, но вопрос Сжатие для уникального потока данных предлагает несколько подходов, которые могут вам помочь.

Я бы предложил предварительную фильтрацию данных в start и серию offset s. Если вы знаете, что смещения будут надежно малыми, вы можете даже кодировать их как 1- или 2-байтовые количества вместо 4-байтов. Если вы этого не знаете, каждый смещение может по-прежнему составлять 4 байта, но поскольку они будут небольшими, вам будет больше повторений, чем вы бы сохранили исходные целые числа.

После предварительной фильтрации запустите свой вывод через схему сжатия по вашему выбору - что-то, что работает на уровне байта, например gzip или zlib, вероятно, сделает действительно приятную работу.

Ответ 7

Ответ MSalters интересен, но может отвлечь вас, если вы не проанализируете правильно. Есть только 47 чисел Фибоначчи, которые соответствуют 32-бит.

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

Вещи, которые имеют значение: а) Имеются ли повторяющиеся значения? Если да, то как часто? (если это важно, сделайте его частью сжатия, если не сделать его исключением). b) Он выглядит квази-случайным? Это также может быть хорошим, так как может быть найдено подходящее среднее значение.

Ответ 8

Я бы использовал что-то болотное стандартное с полки, прежде чем инвестировать в свою собственную схему.

В Java, например, вы можете использовать GZIPOutputStream для применения сжатия gzip.

Ответ 9

Возможно, вы можете сохранить различия между последовательными 32-разрядными целыми числами как 16-разрядные целые числа.