rlm*_*lms 5 binary encoding character-encoding information-theory
旧的英国信息学奥林匹克问题(3c)询问字母表中最小的明确编码方案(仅使用两个符号 - 因此是二进制).据我所知,答案是130 - 5位需要存储每个字母,如2 ^ 4 <26.字母表有26个字符,因此编码方案长5*26位.但是,标记方案表明可以使用124位.那么长的编码方案是什么？
我认为这有效：
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