字母表的明确二进制编码方案

Question

一道古老的英国信息学奥林匹克竞赛问题（3c）询问了只使用两个符号（即二进制）的字母表最小且不含歧义的编码方案是什么。据我所知，答案是130-每个字母需要5位来存储，因为2^4 < 26。字母表有26个字符，所以编码方案长度为5 * 26位。然而，评分方案规定可以使用124位。那么这个长度的编码方案是什么？

- rlms

Answer 1

我认为这个有效：

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

- Jesan Fafon

---

好的答案。一般来说，如果字母表中有N个字母，则最佳无歧义编码的位数由“二进制熵函数”给出：http://oeis.org/A003314 - Paul Boddington

Answer 2

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

创建32个组合表时，我们可以将字母A-Z分配给每个值，其中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

重要提示：虽然此方案是前缀自由的（即没有组合是另一个更长的组合的开头），因此不会有歧义，但它不是自同步的，因此我们不能只偷偷溜进已编码字符的流中并确定地获得正确的输出。这需要具有不包含在任何其他字母中的同步“字符”-但是这不可能，因为这是一种无冗余方案。

- Andreas Wolf

---

更喜欢这个答案，因为它更详细地描述了所有这些背后的想法。此外，我想补充的是，该方法是在任何时候都使0和1的可能性相等（通过尽力“平衡”两者的概率）。正如信息论所示，如果所有产生的符号的概率相等（在这种情况下为50％），则符号（此处为位）的离散源具有每位最大的平均信息（即熵）。 - Marcus Müller