Эффективное кодирование целых чисел с постоянной суммой цифр

Question

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

Пример целых чисел в базе 10, с цифрой 5 и 3 цифрами:

014, 041, 104, 113, 122, 131, 140, 203 ....

Самым важным фактором является пространство, но вычисление времени не является совершенно неважным.

Answer 1

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

Для равномерно распределенного (или неизвестного) случая подход следующий: Представьте себе (вы можете предварительно сгенерировать и сохранить его или сгенерировать на лету) отсортированный лексикографически список всех ваших входных (для кодирования) значений. Например. в вашем случае список будет начинаться (если ваша сумма цифр не является рекурсивной): 005, 023, 032, 050, 104, 113, 122, 131, 140, 203, 212, 221, 230, 401, 410, 500. Затем присвойте каждому элементу в списке целое число, основываясь на его позиции в списке: 005 становится 0, 023 становится 1, 032 становится 2 и так далее. В списке (если я не ошибся, если да, откорректируйте соответствующим образом) 16 значений, для которых вам нужно 4 бита для кодирования любого индекса в списке. Этот индекс является вашим закодированным значением, и кодирование и декодирование становятся очевидными.

Что касается алгоритма для генерации списка в первую очередь: Самый простой способ - считать от 000 до 999 и выбрасывать все, что не соответствует вашему критерию. возможно , чтобы быть более умным об этом, реплицируя счет и переполнение (например, как 104 следует за 050), но это, вероятно, не стоит усилий.

Answer 2

Самый простой способ - это сохранить саму сумму цифр и оставить ее на этом уровне.

Но возможно, что я неправильно понял вопрос.

Редактировать: Вот мой вывод: вы хотите закодировать сам набор;да?

Кодирование самого набора так же просто, как сохранение базы, суммы цифр и количества цифр, например, {10, 5, 3} в приведенном вами примере.

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

Кроме того, поскольку сумма цифр обычно считается рекурсивной;и от одного до девяти включительно;203 имеет ту же сумму цифр, что и 500, или 140, или 950. Это означает, что набор огромен для любой комбинации чисел, а также что любой набор (за исключением некоторых вырожденных случаев) использует каждую доступную цифру в базе, которую онисвязаны с.

Итак, вы знаете, что наиболее эффективное кодирование самих чисел, когда они хранятся отдельно, становится самим числом, особенно если учесть, что каждое число между ± 2 147 483 648 обычно занимает одинаковое количество места впамяти и часто в хранилище.