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

Question

旧的British Informatics Olympiad question (3c) 询问字母表的最小明确编码方案(仅使用两个符号 - 因此是二进制)是什么。据我所知，答案是 130 - 需要 5 位来存储每个字母，因为 2^4 < 26。字母表有 26 个字符，因此编码方案是 5*26 位长。然而，标记方案规定可以使用 124 位。这么长的编码方案是什么？

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。

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

6 * 4 + 20 * 5 = 124

或者

4 + 16 + 6 = 26