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

Question

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

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

以下是一些示例：

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

---

最初，我试图对20位使用Huffman编码，因为Huffman编码可以将20位缩减至约10位，但是存储表需要超过9位。

以下是一个示例，展示了01230经过Huffman编码后从20位变为10位：

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位（五个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％ 减少）时效果最好，但是我认为在 9 比特或更少的空间里存储表格是不可能的。

---

对于长度为60比特的字符串而言，最坏情况下仍然存在至少3个重复项，在平均情况下，重复项数量更多（这是我的假设）。由于至少存在3个重复项，因此在60比特的连续运行中最多只能有12个符号。

由于存在重复项和符号数量少于16个，我不禁觉得可以使用某种类型的压缩。

- ParoX

---

@MarkAdler 我更新了问题，并提供了一个将 01230 从20位转换为10位的示例。这里的10位只是编码，不包括表格（否则似乎会突破香农极限）。 - ParoX

你是想要压缩60个比特还是60*N个比特？ - ajm

Answer 1

如果我只是简单地计算至少有两个十六进制数相等的20位值的数量，那么它们的数量为524,416。略多于2¹⁹。因此，你可能节省的最大值不到20位中的一位。

似乎并不值得。

- Mark Adler

Answer 2

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

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

这些是选项：

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%。

- Itchy

---

谢谢，这个技巧非常聪明，正是我在寻找的那种直觉。 - ParoX

Answer 3

如果您想先去除重复项，请执行此操作，然后查看页面底部的链接。如果您不想去除重复项，则仍需查看页面底部的链接。

Array.prototype.contains = function(v) {
  for (var i = 0; i < this.length; i++) {
    if (this[i] === v) return true;
  }
  return false;
};

Array.prototype.unique = function() {
  var arr = [];
  for (var i = 0; i < this.length; i++) {
    if (!arr.contains(this[i])) {
      arr.push(this[i]);
    }
  }
  return arr;
}

var duplicates = [1, 3, 4, 2, 1, 2, 3, 8];
var uniques = duplicates.unique(); // result = [1,3,4,2,8]

console.log(uniques);

如果您想缩短需要处理的代码，您可以尝试使用Smaz。

Smaz是一个简单的压缩库，适用于压缩字符串。

如果这不起作用，那么您可以看看这个：

http://ed-von-schleck.github.io/shoco/

Shoco是一个用于压缩和解压短字符串的C库。它非常快速和易于使用。默认的压缩模型针对英文单词进行了优化，但您可以根据特定的输入数据生成自己的压缩模型。

如果可以，请告诉我！

- Promaster