大数据DGIM算法,C语言实现代码

野性酷女 2022-05-27 05:20 192阅读 0赞

对于该查询，若空间足够，可以通过空间复杂度O(N)，时间复杂度O(1)的简单的加减得到查询结果。所以这里要讨论的是对于N非常大的情况，即假设由于存储空间有限，我们不能存储整个窗口的数据。

根据滑动窗口共有2N种表示简单推算，任何能给出确切结果的算法都需要O(N)的空间，即该问题必须寻找近似算法。Datar-Gionis-Indyk-Motwani Algorithm（DGIM算法）是其中一种：该算法仅使用O(log2N)的空间，时间复杂度为O(logN)。     首先假设对于二进制流，其中每个位可以用一个时间戳（timestamp）标志该位进入流的时间（对于大小为N的滑动窗口，该时间戳可以用O(logN)位表示）。
    
    
    
     DGIM算法利用桶（bucket）对滑动窗口进行划分，每个桶保存以下信息：

桶的最右边位即最后进入流的位的时间戳；  
桶的大小，即桶中1的个数，该数目位2的幂。  
对于以上信息，保存时间戳需要logN的空间，保存桶的大小需要loglogN的空间。

使用桶对滑动窗口进行划分时遵循以下5条规则：

桶最右边的位必须是1；  
1个位最多属于1个桶；  
每种大小的桶有1个或者两个（从1到最大的桶的大小）；  
每个桶的大小是2的幂；  
桶的大小从右到左非降序排列；  
举例：  
![这里写图片描述][70]

DGIM算法中数据结构的更新：

每一个新的位进入滑动窗口后，最左边一个位从窗口中移出（同时从桶中移出）；如果最左边的桶的时间戳是当前时间戳减去N（也就是说桶里已经没有处于窗口中的位），则放弃这个桶；  
对于新加入的位，如果其为0，则无操作；否则建立一个包含新加入位的大小为1的桶；  
由于新增一个大小为1的桶而出现3个桶大小为1，则合并最左边的两个桶为一个大小为2的桶；合并之后可能出现3个大小为2的桶，则合并最左边两个大小为2的桶得到一个大小为4的桶……依次类推直到到达最左边的桶。  
举例（上图中最右边进入一个新的1后的结果）：  
![这里写图片描述][70 1]

可以给出DGIM的存储开销：桶的个数O(logN)，每个桶可以用O(logN)空间表示，保存表示一个窗口的所有桶所占的空间为O(log2N)。

对于查询，首先寻找含最近k个位的拥有最大时间戳的桶b，查询结果为在k个为中所有桶的大小，加上b的大小的一半。一次查询的时间复杂度为O(logN)。
    
    该估计值误差（fractional error）的上下限为：

至少是正确值的50%：最差情况b中都是1，估计误差值是b的一半。  
最多超过正确值的50%：最差情况b只有最右边一位为1。

下面是c语言实现代码

#include "stdio.h"
    #include "stdlib.h"
    
    typedef struct
    {
        int size;
        int time_stamp;
    }BucketNode,*Bucket;
    
    int count_bucket = 0;
    
    void merge(Bucket buc,int n);
    void estimate(Bucket buc,int count_window,int n);
    void accurate(int *slip_window,int count_window);
    
    int main()
    {
        int data;    //接收数据流
        int n = 1;    //时间戳
        int t;    //需要输入的任意时刻
        int i;
    
        Bucket buc  = (Bucket)malloc(50 * sizeof(BucketNode));    //桶_结构体指针数组
    
        int count_window;    //滑动窗口大小
        int *slip_window;    //滑动窗口数组
        FILE *fp;
    
        printf("请输入滑动窗口大小：\n");
        scanf("%d",&count_window);    //输入滑动窗口大小
        slip_window = (int *)malloc(count_window * sizeof(int));    //滑动窗口数组分配空间
    
        printf("请输入时刻：\n");
        scanf("%d",&t);
    
        fp = fopen("01stream.txt","r");    //打开文件
        while(1)
        {
            fscanf(fp,"%d",&data);    //读取一个数据
            if(feof(fp))
            {
                break;
            }
    
            *(slip_window + (n+1)% count_window) = data;    //把data数据放到滑动窗口数组中
    
            if(data == 1)    //如果读到的是1 创建新桶
            {
                buc[count_bucket].size = 1;
                buc[count_bucket].time_stamp = n;
    
                if(count_bucket > 1) 桶总数目大于2的时候才有可能合并
                {
                    merge(buc,count_bucket);    //合并 
                }
                count_bucket++;   //创建新桶，所以桶数目加1
    
            }
            n++;    //时间戳加1
            if(n == t + 1)
            {
                break;
            }
        }
        printf("字符流个数：%d\n",n - 1);
        printf("桶数目:%d\n",count_bucket);    //桶总数
        fclose(fp);
    
        for (i = 0; i < count_bucket; i++)
        {
            printf("第%2d桶 桶大小:%5d 时间戳：%d\n",i,buc[i].size,buc[i].time_stamp);
        }
    
        estimate(buc,count_window,n-1);
        accurate(slip_window,count_window);
    
    }
    
    //合并
    void merge(Bucket buc,int n)
    {
        int i,j;
        for(i = n; i > 1; i--)
        {
            if( (buc[i].size == buc[i-1].size) && (buc[i-1].size == buc[i-2].size) )
            {
                buc[i - 2].size *= 2;
                buc[i - 2].time_stamp = buc[i - 1].time_stamp;
                buc[i - 1]= buc[i];
                for(j = i;j < count_bucket; j++)
                {
                    buc[j] = buc[j+1];
                }
                count_bucket--;
            }
        }
    }
    
    //估算
    void estimate(Bucket buc,int count_window,int n)
    {
        int i;
        int sum = 0;
        for(i = count_bucket; i > 0; i--)
        {
            if(buc[i].time_stamp > n - count_window)
            {
                sum += buc[i].size;
            }
            else
            {
                sum -= (buc[i+1].size)/2;
                break;
            }
        }
    
        printf("估算滑动窗口内1_bit个数：%d\n",sum);
    }
    
    
    //精确计算窗口1个数
    void accurate(int *slip_window,int count_window)
    {
        int n = 0,i;
        for(i = 0; i < count_window; i++)
        {
            if(*(slip_window + i) == 1)
            {
                n++;
            }
        }
        printf("滑动窗口内1_bit精确个数为：%d\n",n);
    
    }

运行：  
![这里写图片描述][70 2]

[70]: /images/20220527/8739d366092c44f787f0f1b3eefcc6dd.png
[70 1]: /images/20220527/84e164690eb54db9bc66a3ae0ecf4a86.png
[70 2]: /images/20220527/cc937c271f374848b49e779f4f418e51.png