1
实际值 ≤ 估算值 ≤ 实际值 + ε × n

1
package cms
2

3
import (
4
    "encoding/binary"
5
    "hash/fnv"
6
    "math"
7
)
8

9
// CountMinSketch 用 d 行 w 列计数器估算元素频率
10
type CountMinSketch struct {
11
    counters [][]uint32 // d 行 w 列
12
    d        int        // 哈希函数数量（行数）
13
    w        uint       // 每行计数器数量（列数）
14
}
15

16
// New 创建 Count-Min Sketch
17
// epsilon: 误差率，delta: 误差超过阈值的概率
18
func New(epsilon float64, delta float64) *CountMinSketch {
19
    w := uint(math.Ceil(math.E / epsilon))  // 列数
20
    d := int(math.Ceil(math.Log(1 / delta))) // 行数
21
    counters := make([][]uint32, d)
22
    for i := range counters {
23
        counters[i] = make([]uint32, w)
24
    }
25
    return &CountMinSketch{counters: counters, d: d, w: w}
26
}
27

28
// Add 将元素加入 Sketch，计数器加 1
29
func (cms *CountMinSketch) Add(data []byte) {
30
    for i := 0; i < cms.d; i++ {
31
        pos := cms.hash(data, i)
32
        cms.counters[i][pos]++
33
    }
34
}
35

36
// Estimate 估算元素的出现频率
37
func (cms *CountMinSketch) Estimate(data []byte) uint32 {
38
    min := uint32(math.MaxUint32)
39
    for i := 0; i < cms.d; i++ {
40
        pos := cms.hash(data, i)
41
        if cms.counters[i][pos] < min {
42
            min = cms.counters[i][pos] // 取最小值抵消正偏差
43
        }
44
    }
45
    return min
46
}
47

48
// hash 用行索引做种子的双哈希
49
func (cms *CountMinSketch) hash(data []byte, row int) uint {
50
    h := fnv.New128a()
51
    h.Write(data)
52
    binary.Write(h, binary.LittleEndian, uint32(row))
53
    sum := h.Sum(nil)
54
    return uint(binary.BigEndian.Uint64(sum)) % cms.w
55
}

1
class CountMinSketch {
2
  private counters: Uint32Array[];
3
  private seeds: number[];
4

5
  constructor(
6
    private w: number,  // 每行计数器数量
7
    private d: number   // 行数（哈希函数数量）
8
  ) {
9
    this.counters = Array.from({ length: d }, () => new Uint32Array(w));
10
    // 每行用不同的种子生成独立哈希
11
    this.seeds = Array.from({ length: d }, (_, i) =>
12
      (i + 1) * 0x811c9dc5
13
    );
14
  }
15

16
  // 从误差参数创建
17
  static fromError(epsilon: number, delta: number): CountMinSketch {
18
    const w = Math.ceil(Math.E / epsilon);
19
    const d = Math.ceil(Math.log(1 / delta));
20
    return new CountMinSketch(w, d);
21
  }
22

23
  private hash(data: string, row: number): number {
24
    let h = this.seeds[row];
25
    for (let i = 0; i < data.length; i++) {
26
      h = ((h ^ data.charCodeAt(i)) * 0x01000193) >>> 0;
27
    }
28
    return h % this.w;
29
  }
30

31
  // 插入元素，计数器加 1
32
  add(data: string): void {
33
    for (let i = 0; i < this.d; i++) {
34
      this.counters[i][this.hash(data, i)]++;
35
    }
36
  }
37

38
  // 估算元素出现次数，取所有行中的最小值
39
  estimate(data: string): number {
40
    let min = Infinity;
41
    for (let i = 0; i < this.d; i++) {
42
      const count = this.counters[i][this.hash(data, i)];
43
      if (count < min) min = count;
44
    }
45
    return min;
46
  }
47
}
48

49
// 使用示例：ε=0.001, δ=0.01
50
const cms = CountMinSketch.fromError(0.001, 0.01);
51
cms.add("hello");
52
cms.add("hello");
53
cms.add("world");
54
console.log(cms.estimate("hello")); // 2（精确）
55
console.log(cms.estimate("world")); // 1（精确）
56
console.log(cms.estimate("other")); // 0 或 ≥0（可能因碰撞偏大）