大量数据去重：Trie和ExternalSorting

此问题自古以来就非常知名

包含A和B两个大型数据文件，在以行分隔的形式存储了数量巨大的URL信息。请设计一个算法，在内存受限的情况下（不超过512MB），识别同时存在于两个文件中的URL地址。

我们采用的策略虽然有所调整以适应不同场景需求但在核心功能上保持一致

文章目录

• • 空间压缩
  • • 编码
    • 字典树（Trie）

外部排序（External Sorting）
* 排序与去重
* 在Unix系统中使用sort指令
* 两种方式：双线合并（2-Way Merge）与多线合并（K-Way Merge）
* 外部多路合并排序法

* 总结

空间压缩

与之相似，在处理此类资源受限的问题时，在最大限度地压缩空间的同时并非首要选择以损失部分资源为代价——布隆过滤器以牺牲准确性为代价的同时，在随后我们将探讨另一种方法——外排序，则以时间效率为代价作为权衡策略。对于哈希表而言，在实现快速查找功能的同时将每个整型值对应到一个独立的二进制位上——这在某种程度上类似