Возможно ли закодировать некоторое количество цифр в меньшее?

Question

[cup_of_sugar]

Например, возможно ли закодировать 11 цифр в 9, а потом декодировать? Лично мне кажется это невозможным (каждая цифра несет в себе некоторое количество информации и отказаться от нее не получится), но, может быть, есть какие-то хитрые алгоритмы.

Comments

[WayMax]

kpet-ks.ru/%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D1%8B-%D...
https://www.intuit.ru/studies/courses/648/504/lect...

Answer 1

[Lynn «Кофеман»]

Есть такая наука — математика.
Она говорит, что нельзя взаимно-однозначно отобразить 10^11 значений в 10^9.

Comments

[Вячеслав Шиндин]

А вот с чего вы взяли, что система счисления должна быть десятичной?
Мне кажется, что автор вопроса хоть и не достаточно полно сформулировал вопрос, но имеет в виду под хитрыми алгоритмами способы сжатия представления этих цифр.
Например, можно каждую цифру десятичной системы счисления представлять в бинарной системе счисления с помощью 4 битов, при этом, 4 битами можно закодировать 2^4 вариантов значений, т.е. больше чем требуется. Есть избыточность, а значит уже можно думать над оптимизацией. Например, в 1 байте можно хранить две цифры, а в одном значении int64 уже можно хранить 16 цифр по 4 бита на цифру.
Можно пойти дальше, если речь идёт о работе с большими числами, то цифры этих чисел можно сжать без потери качества, т.е. в любой последовательности цифр будут встречаться некоторые подпоследовательности, и бывает так, что одни подпоследовательности встречаются чаще других, поэтому, если представлять часто встречаемые подпоследовательности меньшим кол-вом битов, можно добиться уменьшения кол-ва требуемых битов для представления такого числа.

Answer 2

[Rsa97]

11 цифр [0-9] в 9 цифр [0-9] невозможно.
А 11 цифр [0-9] в 9 символов [0-9a-zA-Z] легко.

Answer 3

[evgeniy_lm]

Можно. Поменяйте систему счисления на более высокую и будет вам счастье. Например число 99 999 999 999 (10) то же самое что 247BAFB5E (17)

Answer 4

[Adamos]

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

Answer 5

[Everything_is_not_so_bad]

Если каждая цифра представлена одним байтом таблицы ASCII, то можно закодировать в меньшее количество байтов.
Например, возьмем число 12345678901. В нем 11 цифр. Если представить каждую цифру соответствующим кодом таблицы ASCII (код на языке Ruby)

n=12345678901
n.to_s.each_codepoint {|c| print c, ' ' }

Получаем вывод последовательности
49 50 51 52 53 54 55 56 57 48 49 => "12345678901"
То есть последовательность хранится в памяти неоптимально.

Теперь посмотрим как выглядит число в виде последовательности битов:

puts n.to_s(2)  # конвертация в строку по двоичной системой счисления

Вывод:
1011011111110111000001110000110101

Лень считать вручную:
puts n.to_s(2).size
Получили число 34.
34 = 4 * 8 + 2
То есть 4 целых байта и 2 бита.

Фактический размер последовательности для хранения в памяти - 5 байтов.
То есть 11 байтов числа представлены 5-ю байтами.

bytes = [n].pack('w') # кодирование числа в BER.
Вывод:
=> "\xAD\xFE\xF0\xB85"

Answer 6

[Вячеслав Шиндин]

https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%...