Есть ли функция упаковки?
Меня интересует, существует ли функция f(x, k) такая, что:
f(x1, k1) = k2
f(x2, k2) = k3
f(x3, k3) = k4
...
f(xn, kn) = kn+1
и было обратимо, то есть я мог знать k4, чтобы знать k3 и x3?
У меня ощущение, что такой функции не существует, так как она решила бы массу практических задач, может есть какие-то доказательства невозможности такой функции?
P.S возможно есть такие функции, но они не масштабируются из-за коллизий?
Ответы 1
Стандартный трюк для достижения чего-то подобного — использовать умножение простых чисел.
Без ограничения общности пусть xn и kn — произвольные положительные натуральные числа. (Мы собираемся ограничиться положительными натуральными числами, которые можно тривиально распространить на любое счетное множество, например, целые числа, рациональные числа, числа с плавающей запятой, строки, перечисления, булевы значения и т. д., но не, например, вещественные числа. Другими словами: все, что относится к Тьюрингу. -computable должен работать.)
Пусть p(n) будет nth нечетным простым числом (нечетные простые числа — это, по сути, простые числа без 2 или серии простых чисел, сдвинутых на 1). Например, p(3) = 7.
Пусть f(xn, kn) = p(xn) × p(kn).
Затем xn−1 и kn−1 могут быть восстановлены из kn с помощью простой факторизации kn. На самом деле есть небольшая заминка: простая факторизация даст нам два простых множителя, но мы не знаем, какой из них равен xn, а какой kn.
Однако мы можем исправить это, определив, что:
- По умолчанию меньшее число равно xn, а большее число равно kn.
- Если это не так, мы добавляем 1 к результату.
Итак, полное определение:
Пусть f(xn, kn) = p(xn) × p(kn), если xn ≤ kn, p(xn) × p(kn) + 1 в противном случае.
Пример для x1 = 4, x2 = 8, x3 = 15, x4 = 16, x5 = 23 и k1 = 42:
- f(4, 42) = 11 × 191 = 2101
- f(8, 2101) = 23 × 18341 = 421843
- f(15, 421843) = 53 × 6140473 = 325445069
- f(16, 325445069) = 59 × 7037198743 = 415194725837
- f(23, 415194725837) = 89 × ~12076000000000 = ???
Как видите, это становится немного громоздким: мне не удалось легко найти таблицу простых чисел, включающую простое число 415194725837th. Однако это не проблема: не требуется, чтобы f и f−1 были эффективно вычислимы, требуется только, чтобы они существовали. А поскольку мы знаем, что существует бесконечно много простых чисел, мы знаем, что всегда можем найти p(xn) и p(kn).
Вот другая кодировка, которую можно тривиально вычислить вручную:
Пусть f(xn, kn) будет интеркаляцией цифр представлений xn и kn в произвольном основании больше 1. (На самом деле не имеет значения, какое основание вы выберете для представления, если вы Другими словами, это не обязательно должны быть буквенные цифры, т. е. десятичные числа, они также могут быть двоичными, троичными, восьмеричными, шестнадцатеричными, шестидесятеричными, с основанием 64, основанием 85 или основанием 123456789.) Чтобы иметь дело с начальными нулями, мы добавляем одну единицу.
Затем xn−1 и kn−1 можно восстановить из kn, удалив 1 и извлекая чередующиеся цифры.
Пример с основанием 10 для x1 = 4, x2 = 8, x3 = 15, x4 = 16, x5 = 23 и k1 = 42:
- f(4, 42) = 10442
- f(8, 10442) = 10100040482
- f(15, 10100040482) = 10100010000000400041852
- f(16, 10100010000000400041852) = 10100010000000100000000000000040000000401081562
- f(23, 10100010000000100000000000000040000000401081562) = 101000100000001000000000000000100000000000000000000000000000000004000 00000000000040001000801052632
И для того, чтобы обратить его:
- f−1(10100010000000100000000000000010000000000000000000000000000000004000000000000000040001000801052632)
- Снять опережающий 1: 0100010000000100000000000000010000000000000000000000000000000004000000000000000040001000801052632
- Возьмите каждую чередующуюся цифру:
- х5 = 0000000000000000000000000000000000000000000000023
- k5 = 10100010000000100000000000000040000000401081562
- f−1(10100010000000100000000000000040000000401081562)
- Отсечь ведущую 1: 0100010000000100000000000000040000000401081562
- Возьмите каждую чередующуюся цифру:
- х4 = 000000000000000000000016
- k4 = 10100010000000400041852
- ж−1(10100010000000400041852)
- Отсечь ведущую 1:0100010000000400041852
- Возьмите каждую чередующуюся цифру:
- х3 = 00000000015
- к3 = 10100040482
- ж−1(10100040482)
- Зачищаем ведущую 1:0100040482
- Возьмите каждую чередующуюся цифру:
- х2 = 00008
- к2 = 10442
- ж−1(10442)
- Отсечь ведущее 1:0442
- Возьмите каждую чередующуюся цифру:
- х1 = 04
- к1 = 42
- ж−1(42)
- Удалите ведущую единицу: ее нет, поэтому мы знаем, что это не может быть результатом f.
Возможно, что k1 начинается с 1 и имеет нечетное количество цифр, и в этом случае он будет ошибочно идентифицирован как допустимая кодировка. Например, если k1 = 123, то f−1(123) = (2, 3), поэтому мы придем к ложному выводу, что была нулевая итерация с x0 = 2 и k0 = 3. Но умея различать kn, которые являются результатом применения f из k1, которые являются начальными входными данными, не являются обязательными, так что это не проблема.
Я не думал об оптимизации размера кодировки. Должно быть тривиально, чтобы найти лучший. Однако должно быть очевидно, что вывод всегда должен быть больше, чем предыдущий, поскольку вывод должен содержать всю информацию обо всех предыдущих итерациях. Таким образом, каким бы умным ни было кодирование, как бы хорошо вы его ни сжимали, информационная сложность вывода должна быть не меньше суммы информационных сложностей входных данных, а это означает, что информационная сложность вывода каждая итерация должна быть не меньше предыдущей.
Спасибо, теперь я знаю, что это возможно! Но разве нет чего-то, что не росло бы с такой скоростью?