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

Question

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

Answer 1

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

НАЙДИТЕ различия между соседними числами, которые были бы как 2,1,1,4,1 ... и т.д. (в нашем примере), а затем Хаффмана кодировать этот номера.

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

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

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

Answer 2

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

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

Answer 3

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

густого Я имею в виду:

[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 4

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

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

Answer 5

Условия в списках целых чисел несколько отличаются, но вопрос Compression for a unique stream of data предлагает несколько подходов, которые могут вам помочь.

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

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

Answer 6

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

Answer 7

Как вы обнаружили, отсортированная последовательность из 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, поэтому они могут использовать несколько бит для небольшие различия. Если вы можете дать другую модель, вы можете ее оптимизировать.

Answer 8

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

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

Answer 9

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

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

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