整数压缩

Question

如何将一行整数压缩成更短的整数？

例如输入：'1 2 4 9 8 5 2 7 6 2 3 4' -> 算法 -> 输出：'X Y Z'

反过来能取回来吗？ ('X Y Z' -> '1 2 4 9 8 5 2 7 6 2 3 4')

输入最多包含 12 位数字，仅限数字。输出可以是字母数字，最多应为 3-4 位数字。

提前致谢。

编辑：各输入数字0-9；输出 0-9a-Z

Answer 1

除非您的输入来自特定域，其中许多输入是 unlikely/unacceptable - 您不能这样做。

您可以用 4 个字母数字字符对 62^4~=1.4*10^7 个不同的系列进行编码。
另一方面，12位数字的输入可以有10^12种可能的不同输入。

来自 pigeonhole principle - 必须有 2 个 "compressions" 映射到相同的输入。

但是，由于您需要重新创建原始序列，因此您无法区分两个相同的压缩。

所以这样的压缩不存在。

事实上，要将一个 12 位数字压缩成 4 个字符，您将需要字符大小为 1000 的字母表：

x^4 = 10^12, x>0
x = 1000

Answer 2

首先，您可以通过一些库使用任何现有的压缩算法。但是知道您的输入非常专业，您也可以编写适合您情况的特殊算法。

但是让我们先分析一下你能把这个输入压缩到什么程度。为简化起见，我将首先考虑从 0 到 9 正好压缩 12 位数字（但是您没有明确写出输入范围是什么）。有 10^12 种可能的组合，略小于 2^40。所以你基本上想要做的是压缩 40 位。

现在让我们分析一下如何压缩这40位。如果您将字母数字理解为 [0-9A-Z]，则可以使用 36 个字符。每个字符可以编码 log_2(36)=5.1 位。因此，编码您的 40 位需要 8 个字母数字字符。

更好的选择是使用 base64。在这里，你有 64 个字符，这意味着每个字符可以编码 6 位，所以你可以只用 40/6=6.666 => 7 个字符对你的输入进行编码。

如果考虑将输入压缩为二进制，显然需要 40 位。这可以用 5 个 8 位 ASCII 字符、2 个 32 位整数或 1 个 64 位整数来编写。但是，这可能不是您想要实现的。

结论：你不能随意压缩数据，你想压缩的数据也不能压缩到你想压缩的程度。

举个例子，要将0到9的12个数字编码成ASCII字符，你可以简单地将它们打印成一个大数，再转换成二进制，然后把这个二进制数分成8位进行转换到 ASCII 字符。

示例：

Input: 1 2 4 9 8 5 2 7 6 2 3 4
One number: 124985276234
Binary: 1110100011001101100111111011101001010
Grouped: 11101 00011001 10110011 11110111 01001010
ASCII: <GS><EM>��J

请注意，某些 ASCII 符号不可打印。如果这对您很重要，您将不得不使用替代编码，例如 base 64，它只有 64 个不同的字符，但它们都是可打印的。

Answer 3

类似讨论 Compressing a set of large integers

PHP Compress array of bits into shortest string possible

$val = pack('H*', "124985276234");
echo '#'. $val . '#';
print_r(unpack('H*', $val));
die;

#Issue
00011001 => 25
11001    => 25

我试图实现 @Misch algorithm in PHP but some bits when use decbin was wrong and give me bad results when unpacking. Then found pack 函数及其类似的工作。但是解压时0到9的数字是错误的，9000000测试8090899是解压错误值没有发现碰撞。

set_time_limit(0);
ini_set('memory_limit', '5000M');
ini_set("max_execution_time",0);

$collision = [];
$err = [];
for ($i=0; $i < 9000000; $i++) { 

    $packed = pack('H*', $i);
    $unpacked = unpack('H*', $packed)[1];

    if ( array_key_exists($i, $collision) ) {
        die("Collision:". $i .' !!!!'. $packed .'!!!!'. $unpacked);
    }

    if ( $i != $unpacked ) {
        $e =  "Collision2:". $i .' !!!!'. $packed .'!!!!'. $unpacked . "\n";
        #echo $e;
        $err[] = $e;
    }
    $collision[] = $packed;

    #echo '#'. $i .'#' . $unpacked . '#' . $unpacked . "#\n";
}

整数压缩

Compression of Integers

compression

algorithm

math

integer

示例：