Count-Min Sketch Frequency Estimator

export interface CountMinOptions {
  width?: number;
  depth?: number;
  seeds?: readonly number[];
}

export class CountMinSketch {
  private readonly width: number;
  private readonly depth: number;
  private readonly table: Uint32Array;
  private readonly seeds: readonly number[];
  private total = 0;

  constructor(options: CountMinOptions = {}) {
    const width = options.width ?? 2048;
    const depth = options.depth ?? 5;
    if (!Number.isInteger(width) || width <= 0 || !Number.isInteger(depth) || depth <= 0) {
      throw new RangeError("width and depth must be positive integers");
    }
    this.width = width;
    this.depth = depth;
    this.table = new Uint32Array(width * depth);
    this.seeds = options.seeds ?? Array.from(
      { length: depth },
      (_, index) => Math.imul(index + 1, 0x9e3779b1) >>> 0,
    );
    if (this.seeds.length !== depth) {
      throw new RangeError("seeds length must equal depth");
    }
  }

  add(value: string, count = 1): this {
    if (!Number.isInteger(count) || count < 1) {
      throw new RangeError("count must be a positive integer");
    }
    for (let row = 0; row < this.depth; row += 1) {
      const index = row * this.width + this.hash(value, this.seeds[row]!);
      this.table[index] = (this.table[index]! + count) >>> 0;
    }
    this.total += count;
    return this;
  }

  estimate(value: string): number {
    let minimum = Number.POSITIVE_INFINITY;
    for (let row = 0; row < this.depth; row += 1) {
      minimum = Math.min(
        minimum,
        this.table[row * this.width + this.hash(value, this.seeds[row]!)]!,
      );
    }
    return minimum;
  }

  private hash(value: string, seed: number): number {
    let hash = seed >>> 0;
    for (let index = 0; index < value.length; index += 1) {
      hash ^= value.charCodeAt(index);
      hash = Math.imul(hash, 0x01000193) >>> 0;
    }
    return hash % this.width;
  }

  get count(): number {
    return this.total;
  }
}