Улучшить алгоритм сжатия чисел?

Question

У меня есть много уникальных чисел, все положительные и порядок не имеет значения, 0 < num < 2^32.
Пример: 23 56 24 26

Самый большой, 56, нуждается в 6 bits пространство. Итак, мне нужно: 4*6 = 24 bits всего.

я сделать следующее, чтобы сэкономить место:
сортировать их первым: 23 24 26 56 (потому что порядок не имеет значения)
Теперь я получить разницу каждого из предыдущего: 23 1 2 30

самый большой, 30, нуждается в 5 bits пространство.
После этого я сохраняю все номера в 4*5 bits = 20 bits.

Вопрос: как улучшить алгоритм?

Дополнительная информация: С запрошенной цифры в основном представлены в диапазоне 2.000-4.000. Номера менее 300 довольно редки. Числа более 16.000 также довольно редки. Вообще говоря, все цифры будут близки. Например, они могут быть все в диапазоне 1.000-2.000 или все они могут находиться в диапазоне 16.000-20.000. Общее количество номеров будет в диапазоне от 500-5.000.

Answer 1

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

1. сортировать и рассчитать различия, как вы это делали.
2. Использование Huffman coding на нем.

Использование кодирования Хаффмана более важно, чем ваш шаг; Я покажу вам, почему:

рассмотреть следующие данные:

1 2 3 4 5 6 7 4294967295 

где 4294967295 = 2^32-1.Использование алгоритма:

1 1 1 1 1 1 1 4294967288 

общих бит, необходимых еще 32 * 8

Используя кодирование Хаффмана, частоты:

1 => 7 
4294967288 => 1 

Хаффмана кода 1 => 0 и 4294967288 => 1

Всего биты необходимо = 7 * 1 + 1 = 8 бит

Кодирование Хаффмана уменьшает размер на 32 * 8/8 = 32 раз

Answer 2

Если ваши номера неравномерно распределены, лучшее сжатие будет достигнуто за счет использования частот номеров и воздействия на меньшее количество бит на наиболее частые. Это идея huffman coding.

Answer 3

Сколько у вас номеров? Если ваш набор охватывает диапазон [0..(2^32)-1] достаточно плотно (вы делаете математику), то может оказаться полезным поле бит 4GiB, где n-й бит представляет собой наличие или отсутствие натурального числа n.

Answer 4

Эта проблема хорошо известна в сообществе базы данных как «Инвертированное сжатие индекса». Вы можете рекламировать некоторые документы.

Ниже приведены некоторые из наиболее распространенных методов:

• Переменный байт кодирование (VByte)
• Simple9, Simple16
• "системы отсчета" семейство методов
  • PForDelta
  • Адаптивная опорная рамка (AFOR)
• Rice-Golomb coding (часто используется как часть других методов)

VByte и Simple9/16 легче всего осуществить, быстро и имеют хорошую степень сжатия на практике.

Кодировка Huffman не очень хороша для сжатия индекса, потому что она медленная, и различия на практике довольно случайны. (Но это может быть хорошим выбором в вашем случае.)