压缩整数

eni*_*969 3 compression algorithm math integer

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

例如输入:'1 2 4 9 8 5 2 7 6 2 3 4' - >算法 - >输出:'XYZ'

并可以反过来得到它?('XYZ' - >'1 2 4 9 8 5 2 7 6 2 3 4')

输入最多包含12位数字,仅限数字.输出可以是字母数字,最大为3-4位.

提前致谢.

编辑:每个输入数字0-9; 输出0-9a-Z

ami*_*mit 8

除非您的输入来自特定域,其中许多输入不太可能/不可接受 - 否则您无法做到.

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

鸽笼原理 - 必须有2个"压缩"映射到相同的输入.

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

所以这种压缩不存在.

实际上,要将12位数字压缩为4个字符,您将需要字符大小为1000的字母:

x^4 = 10^12, x>0
x = 1000
Run Code Online (Sandbox Code Playgroud)


Mis*_*sch 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
Run Code Online (Sandbox Code Playgroud)

请注意,某些ASCII符号不可打印。如果这对您很重要,则必须使用其他编码,例如base 64,该编码只有64个不同的字符,但它们都可以打印。