5

一个古老的英国信息学奥林匹克问题（3c）询问字母表的最小明确编码方案（仅使用两个符号 - 因此是二进制）是什么。据我所知，答案是 130 - 存储每个字母需要 5 位，因为 2^4 < 26。字母表有 26 个字符，因此编码方案是 5*26 位长。但是，标记方案声明可以使用 124 位。这么长的编码方案是什么？

4

2 回答 2

2

这里的诀窍是不使用固定长度的编码（正如您所指出的，ld(26) 介于 4 和 5 之间，因此我们在 5 位编码方案中有未使用的块），而是改变我们的长度数据字，因此我们为每个字母获得优化的位数。

在创建 32 种组合的表时，我们可以为每个值分配字母 AZ，A 从 00000 开始，B = 00001 等等。Z 将为 11001 - 其余 (11010…11111) 将不使用。

现在它变得有点棘手。我们最后有六个组合没有使用，但我们不能简单地放弃它们，因为没有“半点信息”这样的东西。因此，我们需要分配六个组合，以便我们可以删除每个组合的最后一位。例子：

10100 = U，10101 = V

变成

10100 = U，10110 = V

其他组合相应地移动，因此最后六个字母中的每个字母的最后一位都是“0”。那么这个位可以去掉，所以我们以这些字母结尾：

00000 = A, 00001 = B, ..., 10011 = T, 1010 = U, 1011 = V, 1100 = W, 1101 = X, 1110 = Y, Z = 1111

重要提示：虽然这个方案是无前缀的（即没有组合是另一个更长组合的开始），因此是明确的，但它不是自同步的，所以我们不能只是潜入编码字符流并肯定得到正确的输出. 这将需要一个不包含在任何其他字母中的同步“字符”——但这是不可能的，因为这是一个无冗余方案。

于 2014-08-28T18:42:12.357 回答
2

我认为这有效：

a - 0010
b - 0011
c - 0100
d - 0101
e - 0110
f - 0111
g - 10000
h - 10001
i - 10010
j - 10011
k - 10100
l - 10101
m - 10110
n - 10111
o - 11000
p - 11001
q - 11010
r - 11011
s - 11100
t - 11101
u - 11110
v - 11111
w - 00000
x - 00001
y - 00010
z - 00011

这是明确的。如果一个符号以两个或更少的零开头，它的长度为 4。如果它以 1 开头，它的长度为 5。如果它以它开头，000那么它的长度也是 5。

我从 a 到 h 的长度为 4 开始，使用 0 作为第一个符号来得到这个想法。然而，像这样的方案是短两个符号（如果长度完全由第一个符号预测），所以我寻找一种方法将四个符号代码的数量减少两个......并注意到这0000是0001唯一的两个有一个三倍0。两位给你四个字符，其余的是一个明确的编码方案:)

6 * 4 + 20 * 5 = 124

或者

4 + 16 + 6 = 26

于 2014-08-28T17:52:46.250 回答