Вирішив спитати у ChartGPT і він запропонував цікаве рішення. Хоча воно не підходить для вас, але оцінити можна)
Арифметическое кодирование в большое число
Шаг 1: Интерпретируем последовательность как одно огромное число
У вас есть строка из 100 000 цифр (0-9). Это можно трактовать как огромное число в десятичной системе:
N=d1d2d3...d100000N = d_1 d_2 d_3 ... d_{100000}N=d1d2d3...d100000
Где did_idi — это отдельная цифра (0-9).
Шаг 2: Переводим это число в другую систему счисления
Чтобы представить это число в компактном виде, его можно перевести в более ёмкую систему, например, в систему с основанием BBB, где BBB — достаточно большое число, чтобы уместить 100 000 знаков в 10.
Нужно подобрать BBB, чтобы:
B10≥10100000B^{10} \geq 10^{100000}B10≥10100000
Берем логарифм по основанию 10:
10⋅log10B≥10000010 \cdot \log_{10} B \geq 10000010⋅log10B≥100000log10B≥10000\log_{10} B \geq 10000log10B≥10000B≥1010000B \geq 10^{10000}B≥1010000
То есть каждое из 10 значений должно быть числом порядка 101000010^{10000}1010000, что технически возможно, если использовать большие числа (BigInt).
Шаг 3: Разбиение на 10 чисел
Представляем число NNN как 10 частей (например, разбиваем его по степеням основания BBB):
N=x1⋅B9+x2⋅B8+...+x10⋅B0N = x_1 \cdot B^9 + x_2 \cdot B^8 + ... + x_{10} \cdot B^0N=x1⋅B9+x2⋅B8+...+x10⋅B0
Где каждое xix_ixi — это большое число (но всего их 10).
Шаг 4: Обратное восстановление
Чтобы восстановить оригинальную последовательность:
- Берем 10 чисел x1,x2,...,x10x_1, x_2, ..., x_{10}x1,x2,...,x10.
- Используем разложение по степеням BBB, восстанавливаем исходное число NNN.
- Разбиваем NNN на 100 000 цифр.
Вывод
Этот метод даёт абсолютно точное сжатие до 10 чисел, но числа должны храниться с огромной точностью (BigInt).