将大整数编码/压缩为字母数字值


Encoding/Compressing a large integer into alphanumeric value

我有一个非常大的整数,长度为 12-14 位,我想将其加密/压缩为字母数字值,以便以后可以从字母数字值中恢复整数。我尝试使用 62 基数转换这个整数,并尝试将这些值映射到 a-zA-Z0-9 ,但由此生成的值长度为 7 个字符。这个长度仍然足够长,我想转换为大约 4-5 个字符。

是否有一种通用方法可以执行此操作或某种可以执行此操作的方法,以便仍然可以恢复整数?我在这里问数学方面,但我会用PHP编程,我最近开始用php编程。

编辑:

我正在考虑分配一个屏蔽位并以某种方式使用它来生成更少的字符数量。我知道范围还不够,这就是我专注于使用数学技巧或表示方式的原因。62 基础是我已经应用但尚未实现的想法。

14 位十进制数可以表示 100,000,000,000,000 个值 (1014(。
62 个字符的字母表中的 5 个字符可以表示 916,132,832 个值 (625(。

不能将 14 位数字的等效值数塞入以 5 个字符为基数的 62 字符串中。根本不可能唯一地表示每个可能的值。 请参阅 http://en.wikipedia.org/wiki/Pigeonhole_principle。即使是包含 7 个字符的基数 64 也是不够的(只有 4,398,046,511,104 个可能的值(。事实上,如果您的目标是 5 个字符的短字符串,则需要使用基数 631 字母表进行补偿 (6315 = 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 字符串,其中

Y = X * log 10/ log 95 = roughly X / 2

这是相当不错的压缩。所以从长度 12 下降到 6。如果压缩的目的是通过使用 JSON 节省带宽,则 base 92 可能是不错的选择(不包括在 JSON 中转义的",',/(。

当然,您可以获得更好的压缩,但要付出的代价是更大的字母表。只需将上述公式中的 95 替换为符号数即可。

当然,除非你知道整数的结构。例如,如果他们有很多零,你可以根据这些知识进行压缩,以获得更好的结果。

因为鸽子原则你最终会得到一些被压缩的值和其他被扩展的值。根本不可能创建一个压缩算法来压缩每个可能的输入字符串(即在您的情况下是您的数字(。

如果强制输出集的基数

小于输入集的基数,则会出现冲突(即,更多的输入字符串被"压缩"为相同的压缩二进制字符串(。压缩算法应该是可逆的,对吧?:)