algorithm - 算法：按预期频率将符号压缩成位串？

Question

我有一个包含 100 万个符号及其预期频率的表格。

我想通过为每个符号分配一个唯一（和前缀唯一）可变长度位字符串来压缩这些符号的序列，然后将它们连接在一起以表示序列。

我想分配这些位串，以使编码序列的预期位长度最小化。

例如，如果符号和预期频率是：

foo 0.5
bar 0.25
baz 0.25

最好的编码之一是：

foo 0
bar 10
baz 11

所以“foobarbazfoo”翻译成010110。

通过什么算法可以将预期频率表转换为最佳编码方案？

Answer 1

您正在描述熵编码。一种流行且易于实现的选项是霍夫曼编码，但还有其他选项。