Эффективно хранить список номеров в двоичном формате

Question

Я пишу алгоритм сжатия (в основном для удовольствия) в C, и мне нужно иметь возможность хранить список чисел в двоичном формате. Каждый элемент этого списка будет иметь две цифры, как до 10 (например, (5,5), (3,6), (9,2)). Я буду потенциально хранить тысячи этих пар (одна пара создается для каждого символа в строке в моем алгоритме сжатия).

Очевидно, что самый простой способ сделать это - объединить каждую пару (->55, 36, 92), чтобы сделать 2-значное число (поскольку они всего одна цифра каждая), а затем сохранить каждую пару в виде 7-битного номера (поскольку 99 является самым высоким). К сожалению, это не так эффективно (7 бит на пару).

Тогда я подумал, что если я конкатенацию каждую пару, то сцепить что (553692), я был бы в состоянии, то хранить, что в качестве простого числа в двоичной форме (10000111001011011100, что для трех пар уже меньше, чем хранение каждого номер отдельно) и сохранить квантификатор для количества бит, используемых для двоичного числа. Единственная проблема заключается в том, что для этого подхода требуется библиотека bigint, и из-за этого она может быть потенциально медленной. Поскольку число становится все больше и больше (+2 цифры на символ в строке), использование памяти и замедление будут увеличиваться и увеличиваться.

Итак, вот мой вопрос: есть ли лучший способ хранения данных для хранения списка чисел, как я делаю, или я должен просто пойти с бигнамом или 7-битным подходом?

Answer 1

Информационно-теоретический минимум для хранения 100 различных значений - log2100, что составляет около 6.644. Другими словами, возможное сжатие из 7 бит - это волосы более 5%. (log2100/7 - 94,91%.)

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

Если пара является частью вашего сжатого вывода, то сжатие не может быть большим (символ составляет всего восемь бит, и, предположительно, пары являются дополнительными к любым сжатым символьным данным.) Тем не менее, простая техника сжатия заключается в сохранении до 6 пар в 40 бит (5 байтов), что может быть выполнено без пакета bigint, предполагающего 64-разрядную машину. (В качестве альтернативы, сохраните до 3 пар в 20 бит, а затем упакуйте две 20-битные последовательности в пять байтов.) Это дает вам 99,66% от максимального сжатия для значений.

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