我有一个包含 100 万个符号及其预期频率的表格。
我想通过为每个符号分配一个唯一(和前缀唯一)可变长度位字符串来压缩这些符号的序列,然后将这些符号连接在一起以表示序列。
我想分配这些位串,以便最小化编码序列的预期位长度。
例如,如果符号和预期频率为:
foo 0.5
bar 0.25
baz 0.25
比最好的编码之一是:
foo 0
bar 10
baz 11
所以"foobarbazfoo"翻译为010110。
我可以通过什么算法将预期频率表转换为最佳编码方案?
你描述的是熵编码。 一个流行且易于实现的选项是霍夫曼编码,但还有其他选项。