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

Question

我正在尝试获取21个字节的数据,这些数据唯一地标识交易并将其存储在16字节char数组中.我无法为此提出正确的算法.

我正在尝试压缩的交易ID包含2个字段:

1. 18个字母数字字符,由ASCII字符0x20到0x7E组成,包含.(32-126)
2. 一个3个字符的数字字符串"000"到"999"

所以包含这些数据的C++类看起来像这样:

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

这些数据需要存储在16- char数据结构中,如下所示:

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

我试图利用这样一个事实:由于字符trade_num_只有0-127,每个字符中有1个未使用的位.类似地,999二进制是1111100111,它只有10位 - 比2字节字短6位.但是当我弄清楚我能把它压缩多少时,我能做到的最小值是17个字节; 一个字节太大了.

有任何想法吗？

顺便说一句,trade_num_用词不当.它可以包含字母和其他字符.这就是规范所说的.

编辑:抱歉混乱.该trade_num_字段确实是18个字节,而不是16.在我发布此帖子后,我的互联网连接已经死亡,直到现在我才回到这个线程.

EDIT2:我认为对数据集做出假设是安全的.对于trade_num_字段,我们可以假设不存在不可打印的ASCII字符0-31.ASCII码也不是127或126(〜).所有其他人可能都在场,包括大写和小写字母,数字和标点符号.这trade_num_将在集合中留下总共94个字符,包括ASCII代码32到125(包括端点).

Answer 1

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

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

您可以利用某些字符最有可能不被使用的事实.特别是,不可能存在低于值32的任何字符,并且也可能不使用127.如果您还可以找到一个未使用的字符,那么您可以先将字符转换为base 94,然后尽可能地将它们打包到字节中.

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

这恰好适合16个字节!

示例代码

下面是一些用Python编写的示例代码(但是以非常强制的方式编写,以便非Python程序员可以轻松理解).我假设~输入中没有tildes().如果有,你应该在编码字符串之前用另一个字符替换它们.

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++,您可以使用大整数库.

您当然需要等效的解码功能,原理是相同的 - 操作以相反的顺序执行.

Answer 2

这使得(18*7 + 10)= 136位,或17个字节.你写的trade_num是字母数字？如果这意味着通常的[a-zA-Z0-9_]字符集,那么每个字符只有6位,需要(18*6 + 10)= 118位= 15字节.

假设8位= 1个字节

或者,来自另一个方向:您有128位存储,数字部分需要~10位,因此trade_num还剩下118位.18个字符表示每个字符118/18 = 6.555位,这意味着您只能使用空格来编码2个6.555 = 94个不同字符**除非在trade_num中有一个隐藏结构,我们可以利用它来保存更多位.