香农编码

这里讨论二元香农编码

香农编码的编号是从 $p (a_{0}) = 0$ 开始，使用累加概率（加到 j-1 而不是 j）

- lo g_{2} p (a_{i}) \leq k_{i} < 1 - lo g_{2} p (a_{i})

最终的编码过程通过截取二进制的小数后 $k_{i}$ 位来实现

每次截取的时候都不损失的时候效率最高

from math import *
 
a = [0.2, 0.19, 0.18, 0.17, 0.15, 0.1, 0.01]
 
a = sorted(a, reverse=True)
print("H:", sum([-i*log2(i) for i in a]))
 
now = 0
for i in a:
    l = ceil(-log2(i))
    binary_representation = f"{floor(now * (2**l)):b}" # 截取 now 小数点后 l 位内容
    print(i, binary_representation.zfill(l), l, sep='\t')
    now = now + i

now 是累加概率，l 是截取长度（那一个事件的信息量）