大文件中记录的最高频次

今天看到一个这个题，感觉方法很巧妙，且其中不要求精确统计的方案里用到的 Count-Min Sketch 算法是前段时间刚学到的，于是便记录下来。

大文件中记录的最高频次

有一个几十 GB（例如 100GB）的文本文件，文件中每一行是一条记录，例如 URL、IP 地址或字符串。请统计文件中出现次数最多的前 100 条记录。给出要求精确统计和不要求精确统计的方案

要求精确

步骤 1：大文件拆分（分片）

遍历大文件，按哈希取模把数据分到多个小文件。

对每一行记录，计算 hash(记录) % N，把该行写入对应编号的小文件。
N 的选择：保证每个小文件可以完整放进内存。比如总文件 50G，内存 4G，分成 20 个分片，每个分片 2~3G。

✅关键点：相同的记录一定会分到同一个分片文件，不会被拆分到多个文件。

伪代码示意

打开大文件
while 读取一行 line:
    idx = hash(line) % N
    把 line 追加写到 temp_${idx}.tmp

经过这一步：原来几十 G 大文件变成 N 个小临时文件，相同字符串全部落在同一个小文件。

步骤 2：每个分片内存内统计 Top100

逐个读取每个小分片文件，全部加载到内存：

使用 HashMap<String, Integer> 统计本分片内每条字符串出现次数。
分片内部统计完，用小根堆（最小堆，大小 = 100） 取出当前分片频次最高的前 100 条，写到中间结果文件。

注意：不是把分片全部统计结果输出，只输出分片的 Top100，减少后续归并的数据量。

步骤 3：归并所有分片输出的 Top100 结果，得到全局 Top100

现在有 N 个中间结果文件，每个文件存分片局部 Top100，总数据量：N*100，数据量非常小，可以全部放进内存。

把所有中间结果读到内存 HashMap，累加全局总频次。
再次使用大小为 100 的小根堆，选出全局出现次数最多前 100 条，输出结果。

时间复杂度

分片读取：O (总数据量)
每个分片统计：O (分片行数 * log100)，log100 是常数
归并阶段：O (N*100 log100)，几乎可以忽略

优点：结果 100% 准确；缺点：会产生中间磁盘临时文件，有磁盘 IO 开销。对应大数据框架：Hadoop MapReduce 就是这套思路。

不要求精确

如果不要求结果完全精确，通常就不需要把大文件哈希分片后做精确计数了，可以用流式近似算法：文件只扫描一遍，内存占用固定。

Count-Min Sketch + 小顶堆

Count-Min Sketch (CMS) 可以近似统计每条记录出现的次数。

处理每一条记录时：

用多个不同的哈希函数计算位置。
在对应的计数器上加 1。
查询该记录的近似出现次数。
更新 Top 100 小顶堆。

对于当前记录，更新堆有三种可能情况
- 情况一：已经在堆中，直接更新他在堆中的频次
- 情况二：不在堆中，但堆还没满100，直接把它放进去
- 情况三：不在堆中，且堆已经满100，比较它与堆顶元素频次，如果频次更高则把堆顶元素移除，然后把当前记录放入堆中。

伪代码：

for (String item : file) {
    // 更新近似计数
    cms.add(item);

    // 查询当前元素的近似次数
    long count = cms.estimate(item);

    if (candidateMap.containsKey(item)) {
        // 已经是候选项，更新它在堆中的次数
        updateHeap(item, count);
    } else if (minHeap.size() < 100) {
        // 候选排行榜还没满
        addToHeap(item, count);
    } else if (count > minHeap.peek().count) {
        // 超过当前第 100 名
        Entry removed = minHeap.poll();
        candidateMap.remove(removed.item);

        addToHeap(item, count);
    }
}

Count-Min Sketch 如何估算频率

因此：估算次数 >= 实际次数。误差来源是其他记录发生了哈希冲突。

优点

只需要扫描文件一次
内存固定，不随不同记录数量增长
特别适合海量数据和实时数据流
速度快

缺点

统计值可能偏大
仅使用 Count-Min Sketch，不能直接知道哪些记录是 Top 100
通常还需要一个候选集合或小顶堆