logo标签列表

整数压缩

algorithmmathintegercompression
3

如何将一行整数压缩为更短的内容？例如：输入：'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

输入最多包含12个数字。所以输入将包含最多12个数字，或者每个数字的输入将包含最多12位数？ - Pham Trung
这12个数字中是否有任何已知的系统？它们是否遵循某种模式？你能否生成它们？它们是随机的吗？它们代表什么？ - Lasse V. Karlsen
@PhamTrung 输入最多包含12个数字；每个数字为0-9。 - enigma969
@LasseV.Karlsen 没有系统；没有意义；数字是随机的。 - enigma969
1
然后Amit发表了一个很好的答案：从一般意义上讲，这是不可能的。压缩利用冗余或模式，如果你没有这些，你就不能压缩。你可能会偶然拥有可以压缩的数据，但它会因数据集而异，并且你无法保证它会压缩到3个字节，甚至11个字节。让我这样说吧：如果你能找到一种方法，保证将12个数字的非均匀随机数据压缩到3个数字，那么注册一个专利，你就会变得富有！ - Lasse V. Karlsen
Lemire和Boytsov在这篇论文中调查了解决这个一般问题的最佳方案。实现代码在https://github.com/lemire。 - Michael Foukarakis
3个回答
8

除非您的输入来自特定域，其中许多输入是不太可能/不可接受的-否则您无法执行此操作。

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

根据 鸽巢原理 - 必须存在映射到相同输入的2个“压缩”。

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

因此不存在这样的压缩。

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

x^4 = 10^12, x>0
x = 1000
输出可以是字母数字混合的，所以有36^4种不同的系列。尽管如此，这仍然太小了。 - Hoopje
小写字母也算吗？62^4，但仍然小于64^4，即16M。 - Aki Suihkonen
@Hoopje 是的，我在你评论之前仅几分钟就编辑并提到了它（并在几秒钟后添加了需要多少个字符的解释）。 - amit
接受一些具有超过1000个不同字符的字符集，这是否可能？ - enigma969
5
首先，您可以使用任何现有的压缩算法，通过一些库。但是，由于您的输入非常专业化，您还可以编写适应您情况的特殊算法。
但是，让我们首先分析一下您可以压缩多少输入。为了简化，我将首先考虑从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符号是不可打印的。如果这对您很重要，您需要使用另一种编码方式，例如base64，它只有64个不同的字符，但它们都是可打印的。
5个8位ASCII字符也不错，您能大致解释一下如何实现吗？ - enigma969
1
为您的数字添加可能的ASCII编码算法。 - Misch
0

类似讨论 压缩一组大整数

PHP将位数组压缩为可能的最短字符串

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

#Issue
00011001 => 25
11001    => 25

我尝试在 PHP 中实现@Misch算法，但是使用 decbin 函数时有些位出错了，在解包时给我带来了错误的结果。后来发现 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";
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接