Streaming Entropy：计数增量、滑动窗口与数值误差

题目重点：每次增删token维护经验分布的Shannon熵，避免扫描全部类别。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练目标是经验离散token分布H=−Σp log2p，单位bits；不是神经模型cross entropy、条件熵或估计未知真实分布。题名本身不能确定这些合同。
add一条样本、remove一条已存在样本；空样本返回0作为API约定。存Counter、total N及W=Σc log2c，0log0取0。

解题路线

代入p=c/N得到H=log2N−W/N。某token计数old→new时，只修正W的两个项，N同步加减，从而不用每次扫描所有token。
删除最后一条该类别样本后移除Counter key，避免内存随曾出现的类别无限增长。不存在的remove报错且状态不变；滑动窗口需要额外deque记被淘汰token，Entropy对象本身不保存事件顺序。
浮点累计会产生微小漂移，max(0,H)只消除接近零的负数，不是纠错算法。长流可定期从Counter重新求W或使用补偿求和；独立验证直接由p计算熵并用绝对误差界对比。
若类别来自连续值，必须先定义量化/bin，否则每个不同数值视独立token，熵会反映精度选择。经验熵有有限样本偏差，不能据此承诺真实分布熵无偏或将bits乘样本数当精确压缩文件大小。

手动走一遍

a,a,b,b，N4、W4，H2−1=1bit；全部是a时H0。a,a,b，p2/3和1/3，熵约0.9183bit；移除b后变0。窗口每入新token并移除过期token，再读bits。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import Counter
from math import log2
class Entropy:
    def __init__(self):self.counts=Counter();self.total=0;self.weighted=0.0
    def add(self,token):
        old=self.counts[token];new=old+1
        self.weighted+=new*log2(new)-(old*log2(old) if old else 0)
        self.counts[token]=new;self.total+=1
    def remove(self,token):
        old=self.counts[token]
        if not old:raise ValueError("absent token")
        new=old-1;self.weighted+=(new*log2(new) if new else 0)-old*log2(old)
        if new:self.counts[token]=new
        else:del self.counts[token]
        self.total-=1
    def bits(self):return 0.0 if self.total==0 else max(0.0,log2(self.total)-self.weighted/self.total)

复杂度

每次增删/读取平均O(1)计数操作，空间O(V)当前不同token；log和浮点算术按机器精度。滑动窗口另外O(window)内存，重建W为O(V)。

易错点与追问

容易失分的边界

直接对累计count求−c logc不是归一化熵。
删除后N未同步会产生伪熵，log(0)也需分支处理。
只知道题名不能断言要求字符、词、概率向量或分布式滑窗。

继续深挖

多个分片如何合并Counter并避免简单平均熵的错误？
要求只用固定小内存，近似计数误差怎样传到熵估计？