4

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

有没有一种通用的方法可以做到这一点，或者有一些方法可以做到这一点，以便恢复整数仍然是可能的？我在这里问数学方面，但我会用 PHP 编程，我最近开始用 php 编程。

编辑：

我正在考虑分配一个屏蔽位并以一种方式使用它来生成更少数量的字符。我知道范围是不够的，这就是我专注于使用数学技巧或表示方式的原因。62 基地是我已经申请但没有解决的想法。

4

3 回答 3

5

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

您不能将 14 位数字的等效数量的值填充到 5 个字符的 base 62 字符串中。根本不可能唯一地表达每个可能的值。请参阅http://en.wikipedia.org/wiki/Pigeonhole_principle。即使是带有 7 个字符的 base 64 也是不够的（只有 4,398,046,511,104 个可能的值）。事实上，如果您定位一个 5 个字符的短字符串，则需要使用基本的 631 字母表（631 5 = 100,033,806,792,151）进行补偿。

即使压缩也无济于事。这意味着需要将两个或多个数字压缩为相同的压缩字符串（因为没有足够的可能的唯一压缩值），这在逻辑上意味着不可能将它们解压缩为两个不同的值。

为了简单地说明这一点：假设我的字母表和目标“字符串长度”由一位组成。那一位可以是0or 1。它可以表达 2 个唯一的可能值。假设我有一个压缩算法，可以将任何东西压缩到这一位。...我怎么可能用两个可能的值从那一位中解压缩 100,000,000,000,000 个唯一值？如果您解决了这个问题，带宽和存储问题将立即消失，您将成为亿万富翁。

于 2013-10-11T09:31:46.910 回答
2

使用 95 个可打印的 ASCII 字符，您可以切换到 base 95 编码而不是 62：

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

这样一个长度的整数字符串X可以压缩成长度为Y95 的字符串，其中

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

这是相当不错的压缩。所以从长度 12 到 6。如果压缩的目的是通过使用 JSON 来节省带宽，那么 base 92 可能是不错的选择（不包括",\,/在 JSON 中转义的）。

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

当然，除非您知道整数的结构。例如，如果它们有很多零，您可以基于这些知识进行压缩以获得更好的结果。

于 2013-11-20T23:57:20.083 回答
1

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

如果您强制输出集的基数小于输入集的基数，您将遇到冲突（即更多的输入字符串被“压缩”为相同的压缩二进制字符串）。压缩算法应该是可逆的，对吧？:)

于 2013-10-11T10:02:29.313 回答