dgim算法的python实现:压缩数据结构以估计布尔流最后n个元素中的“true”个数。
dgim的Python项目详细描述
DGIM算法的Python实现: 一种紧凑的数据结构,用于估计布尔流最后n个元素中的true语句数。
功能
- 布尔流最后n个元素中“true”语句数的估计
- 内存占用率低。
- 可调错误率(错误率越低,内存占用率越高)
应用程序
当处理大量数据流时,如点击流、服务器日志、财务流。 通常需要维护关于n个最新元素的统计信息。 如果n很大或者有许多流要处理,则无法存储 n个最新元素。
在这种情况下,如果处理的流是布尔型的, dgim算法可以帮助您估计true语句的数量 在最后的元素中。
例如,如果流是由服务器日志组成的, DGIM算法可以估计来自搜索引擎的访问比例。 (与直接访问或通过付费搜索访问不同)
安装
在命令行:
$ pip install dgim
用法
示例代码:
from dgim import Dgim dgim = Dgim(N=32, error_rate=0.1) for i in range(100): dgim.update(True) dgim_result = dgim.get_count() # 30 (exact result is 32)
许可证
该项目是根据bsd许可证授权的。
如何贡献
- 检查打开的问题或打开一个新的问题,开始围绕功能想法或错误的讨论。
- 在github上分叉the repository,开始对master分支(或其分支)进行更改。
- 编写一个测试,显示错误已修复或功能按预期工作。
- 发送一个pull请求并对维护程序进行bug操作,直到它被合并并发布。:)确保将自己添加到AUTHORS。
参考文献
- 达特、梅厄等。“在滑动窗口上维护流统计信息。” 暹罗计算杂志31.6(2002):1794-1813。
- 拉贾拉曼、阿南德和杰弗里·大卫·乌尔曼。大量数据集的挖掘。剑桥大学出版社,2011年。第四章。http://infolab.stanford.edu/~ullman/mmds/ch4.pdf
- 海量数据集的挖掘coursera mooc:http://infolab.stanford.edu/~ullman/mmds/ch4.pdf
历史记录
0.2.0(2015-01-05)
- 改进的文档
- 将大多数方法和属性设为私有。
0.1.0(2015-01-04)
- pypi上的第一个版本。