1 要解决的问题
对于二进制数据流S，设置一个滑动窗口N，统计N中最后k位中1的数目
问题：
- S非常大，不可能放在内存中计算
- N非常大，以至于二进制数据流的 最后N位无法在内存中(甚至无法在硬 盘中)存放
2 算法原理
2.1 将窗口划分为多个桶
- 每个桶中1的数目必须是2的幂
- 从右向左，桶的大小(桶内1的数目)呈指数级增长
-
相同大小的桶只能有一到两个
image.png
2.2 桶的更新过程
- 当一个新的数据位到达，检查最左边 桶(最早的桶)。如果该桶最右边位的时间戳已经达到当前时间戳减去N， 那么该桶的所有1不再在窗口之内。删除该桶
- 接下来查看新到达的数据位是0，还是1。
- 如果是0，则不需要做任何处理
-
如果是1
(a). 基于当前时间戳创建一个大小为1的新桶
(b). 如果此时有3个大小为1的桶，将最左边(最 早)的两个大小为1的桶合并为一个大小为2的桶
(c). 如果此时有3个大小为2的桶，将最左边(最早) 的两个大小为2的桶合并为一个大小为4的桶
(d). And so on ...
image.png
2.3 查询应答
估计最近N位中桶1的数目，对最近N位中桶的大小进行求和，减去最左边桶的大小的一半
3 算法实现
1）维护一个数据结构：将二进制分组，每组中1的个数是2的次幂，从右至左组的都是非递减的，只须记录每组的两端的位置即可。类似于 等比数列
2）这样组的个数有O(log(2, N))，记录组的一端位置，所需空间log(2, N)位。则统计整个窗口所占内存为O( (log(2, N)) ^ 2 )
3）求解：估计1的个数：比较每组两端的位置与k的大小，找到k值所在的组b，累加之前组的大小及组b的一半大小。
4 数据结构
每一个新的位进入滑动窗口后，最左边一个位从窗口中移出（同时从桶中移出）；如果最左边的桶的时间戳是当前时间戳减去N（也就是说桶里已经没有处于窗口中的位），则放弃这个桶；对于新加入的位，如果其为0，则无操作；否则建立一个包含新加入位的大小为1的桶；由于新增一个大小为1的桶而出现3个桶大小为1，则合并最左边的两个桶为一个大小为2的桶；合并之后可能出现3个大小为2的桶，则合并最左边两个大小为2的桶得到一个大小为4的桶……依次类推直到到达最左边的桶
参考链接：https://www.zhihu.com/question/37511567/answer/154056206
