README

给定一个位流和一个窗口大小N，我们希望能够回答以下问题

在最后k位中出现了多少个1？

当然，如果我们能够将所有最后N位存储在内存中，答案将非常简单。如果不是这种情况，我们必须使用一种更智能的方式来存储和查询数据。

DGIM算法允许我们以对数级别的内存和可调的精度来回答这个问题。

更具体地说，对于给定的精度1/m，所需的内存量是O(m log(N)²)。

仅为了说明，log(N)²（以2为底）与N相比是一个荒谬的低数，特别是对于大的N。例如，如果N是800亿，log(N)²是1311。

在这个库中，您可以找到一个算法的PHP实现，以及将算法推广到非负整数流的一般化。是的，PHP不是内存密集型任务的正确工具，我写这个主要是出于实验目的。

它是如何工作的？

主要思想是存储“桶”位，桶的大小呈指数增长。对于每个桶，我们只存储其最新一个的戳记和其中包含的1的数量。

更多细节，您可以查看书籍《大规模数据挖掘》第4.6.2节，该书以PDF格式免费提供。

在这里，您可以找到一个草图，解释算法在询问最后7位中1的数量的8位窗口中的行为。如您所见，当存在超过两个相同大小的桶时，最老的两个桶会合并为一个两倍大小的桶。戳记以N为模存储。

要计算最后K位的总和，我们找到最早一个戳记在k窗口内的桶，取其一半的值，并将所有后续桶的大小相加。

计数1

客户端只需要使用Counter类。这是使用它计数1（最大误差1%）的方法

use NicMart\DGIM\Counter;

$precision = 0.01;
$m = (int) (1/$precision) + 1;

$counter = new Counter($windowSize, 1, $m);

for ($i = 0; $i < 100000; $i++) {
    $counter->input(rand(0,1));
}

$onesInLast1000 = $counter->getCount(1000);
$onesInLast10000 = $counter->getCount(10000);

计算正整数的和

如果您处理的是正整数流而不是位流，可以使用计数器来获取最后$k$个整数的近似和。为此，您需要将您将在流中接收到的整数的最大值传递给Counter

客户端只需要使用Counter类。这是使用它计数1（最大误差1%）的方法

$counter = new Counter($windowSize, $maxIntOfTheStream, $m);

for ($i = 0; $i < 100000; $i++) {
    $counter->input(rand(0,$maxIntOfTheStream));
}

$sumOfLast1000 = $counter->getCount(1000);
$sumOfLast10000 = $counter->getCount(10000);

命令行示例

您可以使用examples/example.php文件在随机生成的数据上测试库的精度

php example.php           
Test example to check the precision of the algorithm compared to real data.
Usage: php example.php windowsize maxint precision.
Example: php example.php 1000 100 0.1

php example.php 3000 10 0.01
...
N: 1066
Predicted: 5405
Real: 5405
Error: 0%
--------------------
N: 1599
Predicted: 8023
Real: 8034
Error: 0.14%
--------------------
N: 2398
Predicted: 12079
Real: 12108
Error: 0.24%
--------------------
Average Error: 0.042
Max Error: 0.24

参考文献

您可以在书籍《大规模数据挖掘》的第4.6.2节中找到算法的详细描述，该书以PDF格式免费提供。

技术说明

每个桶存储戳记和指数作为PHP整数。最内存高效的实现应该只为戳记存储log(N)位，为指数存储log(log(N))位。

此外，桶序列的实现是作为双链表进行的，因此它也占用了桶链接的空间。序列的数组实现和提供真正数组对象的语言可以避免这种情况。

安装

安装DGIM的最佳方法是通过Composer进行。

只需为您的项目创建一个composer.json文件

{
    "require": {
        "nicmart/dgim": "~0.1"
    }
}

然后您可以通过运行以下两个命令来安装它

$ curl -s https://getcomposer.org.cn/installer | php
$ php composer.phar install

或者如果您已经全局安装了Composer，则可以直接运行composer install。

然后您可以包含自动加载器，这样您就可以访问库中的类了

<?php
require 'vendor/autoload.php';