代码之家 › 专栏 › 技术社区 › John Dibling

将21个字母数字字符压缩到16字节

algorithm c++

John Dibling · 技术社区 · 15 年前

我试图获取21字节的数据,这些数据唯一地标识一笔交易,并将其存储在16字节的内存中 char

我试图压缩的交易ID由两个字段组成:

18个字母数字字符由ASCII字符组成 0x20至0x7E,包括在内(32-126)
3个字符的数字字符串“000”到“999”

因此,包含这些数据的C++类看起来是这样的:

class ID
{
public:
    char trade_num_[18];
    char broker_[3];
};

这些数据需要存储在一个16- 烧焦 数据结构,如下所示:

class Compressed
{
public:
    char sku_[16];    
};

我试图利用这个事实 trade_num_ 只有0-127每个字符中有1个未使用的位。类似地,二进制中的999是11111000111,这只比2字节字少了10位——6位。但是当我计算出我能压缩多少的时候,我能压缩的最小值是17字节;一个字节太大。

有什么想法吗?

顺便说一句, 交易数量_ 用词不当。它可以包含字母和其他字符。说明书上是这么说的。

编辑:很抱歉给你带来了困惑。这个 交易数量_ 字段实际上是18字节而不是16字节。在我发布这个帖子后,我的网络连接中断了,直到现在我才回到这个帖子。

EDIT2:我认为对数据集做一个假设是安全的。对于trade\ num\字段,我们可以假设不可打印的ASCII字符0-31将不存在。ASCII码127或126(~)也不会。所有其他的可能都存在,包括大小写字母、数字和标点符号。这将在指定的集合中留下总共94个字符 交易数量_

8 回复 | 直到 15 年前

Mark Byers 15 年前

如果你有18个字符在0-127范围内,一个数字在0-999范围内,并尽可能压缩它,那么它将需要17个字节。

>>> math.log(128**18 * 1000, 256)
16.995723035582763

您可以利用某些字符很可能未被使用这一事实。特别是不太可能有任何低于值32的字符,127也可能没有使用。如果你能再找到一个未使用的字符,那么你可以先把字符转换成基94,然后把它们尽可能地压缩成字节。

>>> math.log(94**18 * 1000, 256)
15.993547951857446

这个可容纳16个字节!

示例代码

下面是一些用Python编写的示例代码(但是以非常命令式的风格编写,以便非Python程序员能够轻松理解)。我假设没有波浪线( ~ )在输入中。如果有,在编码字符串之前,应该用另一个字符替换它们。

def encodeChar(c):
    return ord(c) - 32

def encode(s, n):
    t = 0
    for c in s:
        t = t * 94 + encodeChar(c)
    t = t * 1000 + n

    r = []
    for i in range(16):
        r.append(int(t % 256))
        t /= 256

    return r

print encode('                  ', 0)    # smallest possible value
print encode('abcdefghijklmnopqr', 123)
print encode('}}}}}}}}}}}}}}}}}}', 999)  # largest possible value

输出:

[  0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0]
[ 59, 118, 192, 166, 108,  50, 131, 135, 174,  93,  87, 215, 177,  56, 170, 172]
[255, 255, 159, 243, 182, 100,  36, 102, 214, 109, 171,  77, 211, 183,   0, 247]

这个算法使用Python处理大量数据的能力。若要将此代码转换为C++,可以使用大整数库。

你当然需要一个等价的解码函数,原理是一样的-操作是按相反的顺序执行的。

Nordic Mainframe 15 年前

这使得(18*7+10)=136位,或17字节。你写的 trade_num 是字母数字吗?如果这意味着通常的一组字符,那么每个字符只有6位,需要(18*6+10)=118位=15字节。

或者,来自另一个方向:你有128位的存储空间,你需要~10位的数字部分,所以还有118位的贸易数字。18个字符意味着118/18=6.555位每字符,这意味着你只能有空间编码2 6.555=94个不同字符**除非 trade\ num中有一个隐藏的结构,我们可以利用它来节省更多的比特。

liori 15 年前

假设您只需要 allowedchars ,最多94个字符。这是python,但它的编写尽量避免使用花哨的快捷方式,这样您就可以更轻松地将其翻译成目标语言。然而,它假设 number 变量可以包含多达2×128的整数——在C++中,你应该使用某种大数类。

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

def compress(code):
    alphanumeric = code[0:18]
    number = int(code[18:21])

    for character in alphanumeric:
        # find returns index of character on the allowedchars list
        number = alphabase*number + allowedchars.find(character)

    compressed = ''
    for i in xrange(16):
        compressed += chr(number % 256)
        number = number/256

    return compressed

def decompress(compressed):
    number = 0

    for byte in reversed(compressed):
        number = 256*number + ord(byte)

    alphanumeric = ''
    for i in xrange(18):
        alphanumeric = allowedchars[number % alphabase] + alphanumeric
        number = number/alphabase

    # make a string padded with zeros
    number = '%03d' % number

    return alphanumeric + number

Svisstack 15 年前

您可以在~~ 15字节(14字节和6位)内完成。

对于中的每个字符 trace_num_ 如果要将ascii保存为7位,则可以保存1位。

然后你有2个字节的空闲空间和2个比特,你必须有5个。

让我们获取数字信息,每个字符可以是10个值(0到9)中的一个。然后你必须有4位来保存这个字符,要保存数字你必须有1个字节和4位,然后你保存这个字符的一半。

你一定有5个。

qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM1234567890[] 您可以将每个字符保存为6位。接下来是2个字节和2个位。

现在您还有6个字节,您的字符串可以保存在15个字节+ 空终止=16字节。

如果你把数字保存为10字节的整数。你可以把它分成14字节和6位。

KennyTM 8 年前

有 95 空格(0x20)和颚化符(0x7e)之间的字符(其他答案中的94个出现了off-by-1错误)。

因此,不同id的数目是95 ¹⁸ ×1000 = 3.97×10 ³⁸ .

但这种压缩结构只能容纳(2 ) = 3.40×10 ³⁸ 不同的值。

因此,不可能用该结构表示所有ID,除非:

的15位数字中有1个未使用的字符 trade_num_ ,或
一位数字中有14个未使用的字符 ,或
你用的是PDP-10 9-bit char .

Jay 15 年前

关键问题是:

在你的帖子里似乎有些矛盾,不管是16个字符还是18个字符。你需要澄清一下。你说总数是21,由16+3组成-(

输出的16字节必须是可打印字符,还是基本上是二进制数?

更新原始帖子后编辑:

在这种情况下,如果输出可以是字符集中的任何字符,就有可能。如果只能打印字符,就不是了。

数学上的可能性的证明是很简单的。18个字符中的每个字符有94个可能值,3个字符中的每个字符有10个可能值。可能的组合总数=94^18*10^3~=3.28E35。这需要128位。2^127~=1.70e38,太小了,2^128~=3.40e38,够大了。128位是16字节,所以如果我们能使用每一个可能的位组合,它将几乎不适合。

考虑到紧密配合,我认为生成值的最实际方法是将其视为一个双长数,然后通过一个算法运行输入,为每个可能的输入生成一个唯一的整数。

从概念上讲,假设我们有一个16字节长的“大整数”数据类型。算法如下:

huge out;
for (int p=0;p<18;++p)
{
  out=out*94+tradenum[p]-32;
}
for (int p=0;p<3;++p)
{
  out=out*10+broker[p]-'0';
}

// Convert output to char[16]
unsigned char[16] out16;
for (int p=15;p>=0;--p)
{
  out16[p]=huge&0xff;
  huge=huge>>8;
}

return out16;

当然,我们在C中没有“巨大”的数据类型。你使用纯C还是C++?C++中没有大数类吗?对不起,我一段时间没有做C++了。如果没有,我们可以很容易地创建一个小库来实现一个巨大的。

EboMike 15 年前

如果它只能包含字母,那么每个字符的可能性就不到64个(26个大写字母,26个小写字母,剩下12个用于空格、终止符、下划线等)。如果每个字符有6位,你应该在15个字符内到达那里。假设你不支持特殊字符。

Octoberdan 15 年前

使用前10位作为3个字符的数字字符串(对这些位进行编码,就像它们代表一个数字一样,然后在解码时适当地填充零)。

好吧,这就剩下118位和16个字母数字字符要存储了。

0x00到0x7F(如果您的意思是包含在内)包含128个可能的字符来表示。这意味着每个字符可以由7位的组合来识别。提出一个索引,将这7位所代表的每个数字映射到实际字符。要用这种方式表示16个“字母数字”字符,总共需要112位。

我们现在有122位(或15.25字节)代表我们的数据。添加一个复活节彩蛋来填充剩余的未使用的位,您就拥有了16个字符的数组。