如何为特定字母生成永不重叠的唯一二进制代码

Question

所以，我正在尝试解决关于解码一些霍夫曼压缩消息的挑战，而不知道用于压缩的代码树。

不过我知道邮件中使用的字母表。
所以我的想法是尝试暴力破解它，但我的算法技能有点欠缺。

我想我会尝试以所有可能的组合为字母生成代码。 但问题是，代码（二进制）永远无法隐藏彼此。

举个例子：

Letter	Code
A	0100
B	1111
C	1011

但是不可能有任何其他代码以上述任何一个开头，因为它们最终会隐藏彼此。

因此，对于 40 个字符的字母表，我想创建唯一的、非隐藏位代码。
我不知道从哪里开始。任何提示表示赞赏。

• 有没有我不知道（很可能）的智能算法？
• 是不是叫什么我不认识的，可以帮我找一下吗？
• 关于如何以任何方式实际创建它的任何提示？

Answer 1

如果我误解了你的问题，请告诉我。

二进制数与十进制数一对一映射，因此您可以用长度为 1 的二进制数覆盖两个字符的字母表，长度为 2 的四个字符，等等。

因此对于 40 个字符的字母表，您需要长度为 6 的二进制代码。然后如果您将它们放在列表中：

alphabet = ['A', 'B', 'C', ...]

您可以通过

获取映射

mapping = {alphabet[i]: format(i, "b").zfill(6) for i in range(len(alphabet))}

{'A': '000000', 'B': '000001', 'C': '000010', ...}

Answer 2

我认为您无法枚举所有可能的编码。我可以很容易地想出一个方案来生成超过 2^39 种不同的编码，而这些编码中的每一种都有 40 种！给字母分配代码的不同方式。

设x为一个随机的40位字符串。看看

~x[0]
x[0:1] + ~x[1]
x[0:2] + ~x[2]
x[0:3] + ~x[3]
....
x[0:39] + ~x[39]
x[0:40]

这是任何值的前缀代码 x。