c++ - 将 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，包括 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 程序员可以轻松理解)。我假设输入中没有波浪号 (~)。如果有，您应该在编码字符串之前用另一个字符替换它们。

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

你当然需要一个等效的解码函数，原理是一样的——操作是按相反的顺序进行的。