У меня очень большое целое число 12-14 цифр, и я хочу зашифровать / сжать это до буквенно-цифрового значения, чтобы целое число можно было восстановить позже из буквенно-цифрового значения. Я попытался преобразовать это целое число с использованием базы 62 и попытался сопоставить эти значения с a-zA-Z0-9
, но значение, генерируемое из этого, равно 7 символам. Эта длина еще достаточно длинная, и я хочу преобразовать ее примерно в 4-5 символов.
Есть ли общий способ сделать это или какой-то метод, в котором это можно сделать, чтобы восстановить целое число все равно было бы возможно? Я задаю здесь математические аспекты, но я бы программировал это на PHP, и я недавно начал программировать на php.
Я думал о назначении маскирующего бита и использовании этого для создания меньшего количества символов. Я осознаю тот факт, что диапазона недостаточно, и именно поэтому я сосредоточился на использовании математического трюка или способа представления. База 62 была Идеей, которую я уже применял, но не работает.
14-значные десятичные числа могут выражать 100 000 000 000 000 значений (10 14 ).
5 символов из 62-символьного алфавита могут выражать 916,132,832 значения (62 5 ).
Вы не можете втиснуть эквивалентное число значений 14-значного числа в строку с 5 символами base 62. Просто невозможно выразить каждое возможное значение однозначно. См. http://en.wikipedia.org/wiki/Pigeonhole_principle . Даже базы 64 с 7 символами недостаточно (только 4 398 046 511 104 возможных значений). Фактически, если вы нацеливаете короткую строку на 5 символов, вам нужно будет скомпенсировать, используя базовый алфавит 631 (631 5 = 100,033,806,792,151).
Даже сжатие не помогает. Это означало бы, что двум или более числам нужно будет сжать одну и ту же сжатую строку (потому что не хватает возможных уникальных сжатых значений), что логически означает, что невозможно разжать их на два разных значения.
Чтобы проиллюстрировать это очень просто: Скажем, мой алфавит и целевая «длина строки» состоит из одного бита . Этот бит может быть 0
или 1
. Он может выражать 2 уникальных возможных значения. Скажем, у меня есть алгоритм сжатия, который сжимает все и вся в этот бит. … Как я могу разобрать 100 000 000 000 000 уникальных значений из этого одного бита с двумя возможными значениями? Если вы решите эту проблему, проблемы с пропускной способностью и хранением немедленно исчезнут, и вы станете миллиардером.
С 95 печатными ASCII-символами вы можете переключиться на кодировку base 95 вместо 62:
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
Таким образом, целая строка длины X
может быть сжата в длину Y
base 95 string, где
Y = X * log 10/ log 95 = roughly X / 2
который является довольно хорошим сжатием. Итак, с длиной 12 вы доходите до 6. Если целью сжатия является сохранение полосы пропускания с помощью JSON, то базовый 92 может быть хорошим выбором (исключая ",\,/
которые становятся экранированными в JSON).
Конечно, вы можете получить лучшее сжатие, но цена для оплаты – это больший алфавит. Просто замените 95 в приведенной выше формуле на количество символов.
Если, конечно, вы не знаете структуру целых чисел. Например, если у них много нулей, вы можете основывать свое сжатие на этих знаниях, чтобы получить гораздо лучшие результаты.
потому что принцип голубя вы получите некоторые значения, которые будут сжаты и другие значения, которые будут расширены. Просто невозможно создать алгоритм сжатия, который сжимает каждую возможную строку ввода (т. Е. В вашем случае ваши номера).
Если вы вынудите мощность выходного набора меньше, чем мощность входного набора, вы получите столкновение (т. Е. Большее количество строк ввода будет «сжато» в одну и ту же сжатую двоичную строку). Алгоритм сжатия должен быть обратимым, верно? 🙂