24小时热门版块排行榜

返回列表

袁飞燕

铁虫 (初入文坛)

应助: 0 (幼儿园)
金币: 34.4
帖子: 10
在线: 16.9小时
虫号: 4413787
注册: 2016-02-18
专业: 生物化学

[求助] 求助！关于Misra-Gries 算法和数据流的两道题！万分感谢！

求助两道计算题，请各路大神帮忙看看！
1. 假设有一个包含 90 个数据的数据流，该数据流一共有 5 个不同的元素，即
（x1, x2, x3, x4, x5），其中 x1 出现的频率为 50， x2 出现的频率为 10， x3 出
现的频率为 10， x4 出现的频率为 10， x5 出现的频率为 10。考虑在该数据流

上运行参数为 k=2 的 Misra-Gries 算法，尝试解决以下问题：
(a) 数据流中的数据以怎样的到达顺序可以使得元素 x1 的计数最大（也就是
Misra-Gries 算法在最终状态下 x1 的计数最大）？该最大的计数值是多少？
(b) 数据流中的数据以怎样的到达顺序可以使得元素 x1 的计数最小（也就是
Misra-Gries 算法在最终状态下 x1 的计数最小）？该最小的计数值是多少？

2. 假设有两个数据流 E1 和 E2，其中 E1 包含 n1 个数据， E2 包含 n2 个数据。
令 E 为 E1 和 E2 合并后的数据流，即 E={E1, E2}。例如， E1={a, b, a, c}， E1={a,
b, c, c, d}，那么 E= { a, b, a, c, a, b, c, c, d}。考虑两个蓄水池采样算法，分别对
数据流 E1 和 E2 进行采样。两个采样算法的蓄水池大小都为 k (k<n1, k<n2)，
也即对于每个数据流，我们可以得到 k 个均匀的样本。请设计一个样本合并
算法将这 2k 个样本进行合并，得到 k 个合并流 E 中的均匀样本？并证明得到
的 k 个样本中的任何一个样本数据被抽取的概率为 k/(n1+n2)。

回复此楼