count-min-sketch.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>

#define WIDTH 1000
#define DEPTH 5

struct CountMinSketch {
    unsigned int table[DEPTH][WIDTH];
    unsigned int seeds[DEPTH];
} ;

static unsigned int djb2(char* key, unsigned int seed, unsigned int width) {
  unsigned long hash = seed;
  unsigned int c;

  while((c = *key++)) {
    hash = ((hash << 5) + hash) + c;
  }

  return hash % width;
};

void init(struct CountMinSketch* cms, int depth) {
    for (int i = 0; i < depth; i++) {
        cms->seeds[i] = rand();
    }
}

void update(struct CountMinSketch* cms, char* key, int depth, int width) {
    for (int i = 0; i < depth; i++) {
        unsigned int idx = djb2(key, cms->seeds[i], width);
        cms->table[i][idx]++;
    }
}

unsigned int estimate(struct CountMinSketch* cms, char* key, int depth, int width) {
    unsigned int m = 0xFFFFFFFF;

    for (int i = 0; i < depth; i++) {
        unsigned int idx = djb2(key, cms->seeds[i], width);

        if (cms->table[i][idx] < m) {
            m = cms->table[i][idx];
        }
    }

    return m;
}

int main() {
    struct CountMinSketch cms = {0};
    init(&cms, DEPTH);

    update(&cms, "apple", DEPTH, WIDTH);
    update(&cms, "apple", DEPTH, WIDTH);
    update(&cms, "orange", DEPTH, WIDTH);
    update(&cms, "apple", DEPTH, WIDTH);

    assert(estimate(&cms, "apple", DEPTH, WIDTH) == 3);
    assert(estimate(&cms, "orange", DEPTH, WIDTH) == 1);
    assert(estimate(&cms, "banana", DEPTH, WIDTH) == 0);

    return 0;
}