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

Question

Кто-нибудь может предложить алгоритмы сжатия для работы с числовыми строками из 20-30 цифр?

Answer 1

Вы можете легко сжать 30 символьную строку до 15 байтов, просто используя двоичные представления каждой цифры. Например, 1592 можно представить в виде последовательности четырехбитовых значений как таковых:

0001 0101 1001 0010

Это, если сгруппировать в группы по два четырехбитных значения, может быть представлено как §Т в стандартном ASCII.

Кроме того, если ваши строки содержат много идентичных последовательных цифр, вы можете реализовать вариант Кодировка длин серий .

Answer 2

Предполагая, что вы можете иметь числа с плавающей запятой, у вас есть возможность из 11 символов:

[0,1,2,3,4,5,6,7,8,9, .]

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

Если в вашей строке есть только целые цифры, простое решение - преобразовать в шестнадцатеричное число, и вы можете использовать 4 бита на символ еще при получении лучшей степени сжатия. (поскольку биты с 16 символами отсутствуют)

Если вы используете сжатие Хаффмана, вы получите оптимальное соотношение бит / символ. Вы можете узнать больше о сжатии Хаффмана здесь .

Answer 3

Разбить его на пару беззнаковых целых?

"9347692367596047327509604839"

становится:

9 347692367 596047327 509604839

Answer 4

Сделать это 2 15-значными числами и преобразовать их в 2 64-разрядные целые числа? Или они плавают?

Answer 5

Один из самых распространенных способов сжатия чисел (если у вас есть более одного, который вы хотите сжать - его сложно сжать одно), использует дельта-кодирование . Он работает по принципу: если вы знаете, что первое число - это x, а числа после него относительно похожи, вы можете закодировать последующие числа как (x + c1), (x + c2) и т. Д.

В этой схеме вам нужно только один раз кодировать полное значение x, и если ваши значения c меньше, чем ваши x, вы можете сэкономить много места. Вы также можете использовать версию этого, которая сначала сортирует числа, а затем ваша дельта ссылается на число, которое вы видели в последний раз, вместо одного числа. С помощью этого метода вы можете более эффективно охватить более широкий диапазон чисел.

Answer 6

Я бы определенно выбрал самое простое решение и просто сохранил бы их как целые числа (подходящего размера, будь то 32-разрядный, 64-разрядный или 128-разрядный, в зависимости от потребностей). Сжатие его с помощью алгоритма, поддерживающего символы, будет занимать много места, поскольку для каждого символа потребуется более 10 различных значений (0-9).

Answer 7

Одним из очевидных решений является «сжатие» их в виде двоичного числового представления, а не строкового представления. См. вопрос переполнения стека для примеров библиотек.