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

一尘不染

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

algorithm

我正在尝试获取21字节的数据，该数据唯一地标识交易并将其存储在16字节的char数组中。我很难为此找到合适的算法。

我要压缩的交易ID由2个字段组成：

18个字母数字字符，由ASCII字符0x20至0x7E（含）组成。（32-126）
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中的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（包括ASCII码）。

阅读 349

2020-07-28

共1个答案

一尘不染

如果您在0-127范围内有18个字符，在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 ++，可以使用一个大的整数库。

当然，您将需要一个等效的解码功能，原理是相同的-操作以相反的顺序执行。

2020-07-28