压缩 60 位字符串的最佳方法

Question

给定 15 个随机十六进制数（60 位），其中每 20 位运行（5 个十六进制）中总是至少有 1 个重复。

压缩字节的最佳方法是什么？

这里有些例子：

01230 45647 789AA
D8D9F 8AAAF 21052
20D22 8CC56 AA53A
AECAB 3BB95 E1E6D
9993F C9F29 B3130

---

最初，我一直尝试仅在 20 位上使用霍夫曼编码，因为霍夫曼编码可以从 20 位降低到约 10 位，但存储表需要超过 9 位。

这是显示 20 位 -> 10 位的细分 01230

Character   Frequency   Assignment  Space Savings
0           2           0           2×4 - 2×1 = 6 bits
2           1           10          1×4 - 1×2 = 2 bits
1           1           110         1×4 - 1×3 = 1 bits
3           1           111         1×4 - 1×3 = 1 bits

然后我尝试对所有 300 位（5 次 60 位运行）进行霍夫曼编码，这是上面示例中的映射：

Character   Frequency   Assignment  Space Savings
---------------------------------------------------------
a           10          101         10×4 - 10×3 = 10 bits
9           8           000         8×4 - 8×3 = 8 bits
2           7           1111        7×4 - 7×4 = 0 bits
3           6           1101        6×4 - 6×4 = 0 bits
0           5           1100        5×4 - 5×4 = 0 bits
5           5           1001        5×4 - 5×4 = 0 bits
1           4           0010        4×4 - 4×4 = 0 bits
8           4           0111        4×4 - 4×4 = 0 bits
d           4           0101        4×4 - 4×4 = 0 bits
f           4           0110        4×4 - 4×4 = 0 bits
c           4           1000        4×4 - 4×4 = 0 bits
b           4           0011        4×4 - 4×4 = 0 bits
6           3           11100       3×4 - 3×5 = -3 bits
e           3           11101       3×4 - 3×5 = -3 bits
4           2           01000       2×4 - 2×5 = -2 bits
7           2           01001       2×4 - 2×5 = -2 bits

这总体上节省了 8 位，但 8 位不足以存储霍夫曼表。似乎由于数据的随机性，您尝试用霍夫曼编码的位数越多，它的效果就越差。霍夫曼编码似乎在使用 20 位（减少 50%）时效果最好，但 AFAIK 不可能以 9 位或更少位存储表。

---

在 60 位字符串的最坏情况下，仍然至少有 3 个重复项，平均情况下有 3 个以上的重复项（我的假设）。由于至少有 3 个重复，因此在 60 位的运行中您可以拥有的最多符号仅为 12 个。

由于重复加上少于16个符号，我不禁觉得有某种类型的压缩可以使用

Answer 1

如果我把你的问题分成两部分：

1. 如何压缩（完美）随机数据：你不能。每一位都是一些新的熵，压缩算法无法“猜测”。
2. 如何压缩“五个字符中的一个重复项”：可以重复的选项正好有 10 个（见下表）。这基本上就是熵。只需存储它是哪个选项（可能为整行分组）。

这些是选项：

AAbcd = 1    AbAcd = 2    AbcAd = 3    AbcdA = 4    (<-- cases where first character is duplicated somewhere)
             aBBcd = 5    aBcBd = 6    aBcdB = 7    (<-- cases where second character is duplicated somewhere)
                          abCCd = 8    abCdC = 9    (<-- cases where third character is duplicated somewhere)
                                       abcDD = 0    (<-- cases where last characters are duplicated)

所以对于你的第一个例子：

01230 45647 789AA

第一个（01230）是选项4，第二个3和第三个选项0。

您可以通过将每个连续乘以 10 来压缩它： (4*10 + 3)*10 + 0 = 430 并使用除法和取模来解压缩它： 430%10=0, (430/10)%10=3, ( 430/10/10)%10=4。所以你可以这样存储你的号码：

1AE 0123 4567 789A
^^^ this is 430 in hex and requires only 10 bit

三个选项组合的最大数量为 1000，因此 10 位就足够了。

与通常存储这 3 个字符相比，您可以节省 2 位。正如其他人已经评论的那样 - 这可能不值得。对于整条生产线来说，甚至更少：2 位/60 位 = 节省 3.3%。