如何用C++高效去除超大文本文件中的非相邻重复行？

问题背景 #

手里有个比内存大10-50倍的文本文件，每行长度不定，要删掉所有重复行，只留第一次出现的那行。Linux自带的uniq只能去相邻重复的，完全满足不了；之前写的纯内存版用std::unordered_set存行，结果内存直接炸了，根本撑不住去重后的总行数。

靠谱的解决办法 #

办法1：布隆过滤器+磁盘键值库（保住原行顺序） #

这个方法用内存占用极小的布隆过滤器先筛掉绝大多数重复行，再用磁盘上的键值数据库存已经出现过的行，既省内存又能准确去重，还能保住原来的行顺序。

核心逻辑

1. 布隆过滤器快速预判：布隆过滤器占内存特别小，能快速判断当前行有没有可能已经出现过——要是它说已经出现，那大概率真的重复了，直接跳过；要是说没出现，再去磁盘确认。
2. 磁盘键值库精准校验：用RocksDB或者LevelDB这种键值库存在磁盘上的已出现行，布隆过滤器说没出现的行，去库里查一遍：
   • 真没出现的话，就写到输出文件里，同时把这行加到布隆过滤器和键值库里。
   • 已经存在的话，直接跳过。

代码示例（C++ + RocksDB）

#include <iostream>
#include <fstream>
#include <string>
#include <bloom_filter.hpp> // 可使用libbloom这类第三方布隆过滤器库
#include <rocksdb/db.h>

int main() {
    // 初始化RocksDB，数据存在当前目录的line_store文件夹
    rocksdb::DB* db;
    rocksdb::Options options;
    options.create_if_missing = true;
    rocksdb::Status status = rocksdb::DB::Open(options, "./line_store", &db);
    if (!status.ok()) {
        std::cerr << "RocksDB打开失败: " << status.ToString() << std::endl;
        return 1;
    }

    // 初始化布隆过滤器：预估1亿条唯一行，误判率0.01%
    bloom_filter bloom(100000000, 0.0001);

    std::ifstream in_file("large_input.txt");
    std::ofstream out_file("deduplicated_output.txt");
    std::string line;

    while (std::getline(in_file, line)) {
        // 先过布隆过滤器，快速筛掉重复行
        if (bloom.contains(line.c_str(), line.size())) {
            continue;
        }

        // 布隆过滤器预判未出现，去RocksDB查真实状态
        std::string dummy_val;
        status = db->Get(rocksdb::ReadOptions(), line, &dummy_val);
        if (status.IsNotFound()) {
            // 确实是新行，写入输出并更新过滤器和数据库
            out_file << line << std::endl;
            bloom.add(line.c_str(), line.size());
            db->Put(rocksdb::WriteOptions(), line, ""); // 仅存键即可，值可忽略
        }
        // 若查到已存在，直接跳过
    }

    // 清理资源
    delete db;
    in_file.close();
    out_file.close();
    return 0;
}

办法2：哈希分桶法（保住顺序，但步骤麻烦） #

要是不能用第三方库，就把大文件拆成一个个小桶，逐个处理完再合并，不过要保住原顺序得额外做标记。

核心逻辑

1. 哈希分桶：遍历原文件，给每行算个哈希值，把行写到对应编号的临时小文件里（比如bucket_0到bucket_99）——相同的行肯定会进同一个桶，这样每个桶的大小就能控制在内存能装下的范围。
2. 桶内去重：对每个小桶用内存哈希表去重，只留桶里第一次出现的行，写到临时结果文件里。
3. 按原顺序合并：再重新遍历一遍原文件，对每行去对应的桶结果文件里查，要是这行在结果里存在还没被输出过，就写到最终文件里，同时标记为已输出。

注：这个方法要额外存每行的输出标记，适合不能用第三方库的场景，但步骤比较繁琐。

办法3：外部排序去重（不管顺序的话最快） #

要是不在乎原文件的行顺序，直接用Linux的sort命令就行，它会自动处理磁盘临时文件，根本不用自己写代码：

sort -u --buffer-size=2G large_input.txt > deduplicated_output.txt

--buffer-size是给排序分配的内存大小，比如设成2G，根据你的实际内存调整；-u参数会自动帮你去重。

方案对比 #

内容的提问来源于stack exchange，提问作者Arty