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

Question

Я строю индекс, который представляет собой всего несколько наборов упорядоченных 32-битных целых чисел, которые постоянно хранятся в двоичном файле. Проблема в том, что этот файл становится довольно большим. Я думал о добавлении схемы сжатия, но это немного из моего опыта. Поэтому мне интересно, какой алгоритм сжатия будет лучше всего работать в этом случае? Кроме того, декомпрессия должна быть быстрой, так как этот индекс будет использоваться для поиска.

Answer 1

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

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

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

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

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

Answer 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% больше места, чем исходные данные.

Answer 3

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

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

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

Итак, нам действительно нужна статистическая модель ваших входных данных. Учитывая последовательность N [0] ... N [x], каково распределение вероятностей N [x + 1]? Мы знаем, что P (N [x + 1]

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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

РЕДАКТИРОВАТЬ: Мой ответ был только общий указатель. Предложение Нияза о кодировании различий между последовательными числами является хорошим. (Однако, если список упорядочен , а не , или интервал чисел очень нерегулярен, я думаю, что было бы не менее эффективно использовать обычную кодировку Хаффмана. На самом деле, в этом случае лучше всего подойдет LZW или подобное хотя, возможно, все еще не очень хорошо.)

Answer 8

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

Answer 9

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

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