如果已经研究了IDK（如果已对带有重复项的计数合并的外部排序）进行了研究。我确实找到了1983年的论文（见下文）。通常，排序算法是在假设按键对对象进行排序的前提下设计和研究的，因此重复的键具有不同的对象。关于这一点可能已有一些文献，但这是一个非常有趣的问题。可能只是考虑将紧凑型词典与外部合并排序结合使用。

在很少的内存中存储大量字符串的有效字典是一个经过充分研究的问题。大多数有用的数据结构都可以包含每个单词的辅助数据（在我们的示例中为dup计数）。

TL：DR关于有用思想的摘要，因为我在此答案的主体中对很多事情进行了过多的详细讨论：

• 当字典大小达到阈值时（而不是在输入文件的数目固定之后）批处理边界。如果一组5000个字符串中有很多重复项，那么您仍然不会使用太多内存。您可以通过这种方式在第一遍中找到更多重复项。

• 排序批次使得合并 多 快。您可以并且应该合并多于一个，而不是二进制合并。使用PriorityQueue找出哪个输入文件包含您接下来应该执行的行。

• 为了避免在对哈希表中的键进行排序时出现内存使用量激增的情况，请使用可以按顺序遍历键的字典。（即即时排序。）有SortedDictionary<TKey, TValue>（基于二叉树）。这也与等待获取输入字符串的I / O交错处理CPU使用情况。

• 基数将每个批次按第一个字符排序为输出（az，非字母排序在前A，而非字母排序在后z）。或其他可以很好地分配密钥的存储桶选择。为每个基数存储桶使用单独的字典，并在达到内存上限时仅将最大的存储库清空。（比“最大”更好的驱逐试探法是值得的。）

• 调节I / O（尤其是合并时），并检查系统CPU负载和内存压力。相应地调整行为，以确保在服务器最忙时不会造成影响。

• 对于较小的临时文件，这会占用CPU时间，请使用通用前缀编码或lz4。

• 节省空间的字典将为相同的内存上限允许更大的批处理大小（从而允许更大的重复查找窗口）。一个特里（或更好，板蓝根特里）可能是理想的，因为它存储树节点内的字符，仅存储一次共同的前缀。 有向无环字图甚至更紧凑（在不是前缀的常见子字符串之间查找冗余）。将一个用作词典是很棘手的，但可能是可行的（请参阅下文）。

• 利用以下事实：在清空整个字典之前，不需要删除任何树节点或字符串。使用可增长的节点数组和另一个可增长的char数组，该数组将字符串从头到尾打包在一起。（对于Radix Trie（多字符节点）有用，但不适用于每个节点都是单个字符的常规Trie。）

• 根据重复项的分发方式，您可能会或可能不会在第一遍中找到很多重复项。这有一些含义，但是并没有真正改变最终的合并方式。

我假设您有一些目录遍历的想法，它可以有效地为您的代码提供一串字符串，以进行唯一化和计数。因此，我将只说“字符串”或“键”来谈论输入。

修剪掉尽可能多的不必要字符（例如，.xml如果所有字符都丢失.xml）。

在单独的计算机上进行CPU /内存密集型工作可能会很有用，这取决于通过与关键生产服务器的快速网络连接所具有的其他硬件。

您可以在服务器上运行一个简单程序，该程序通过TCP连接将文件名发送到另一台计算机上运行的程序，在该计算机上可以安全地使用更多的内存。服务器上的程序仍然可以处理少量的字典，并将其存储在远程文件系统中。

现在，由于没有其他答案真正将所有内容组合在一起，因此这是我的实际答案：

内存使用量的上限很容易。编写程序以使用恒定的内存上限，而不管输入大小如何。更大的输入将导致更多的合并阶段，而在任何时候都不会消耗更多的内存。

无需查看输入即可对临时文件存储空间进行的最佳估计是一个 非常
保守的上限，假定每个输入字符串都是唯一的。您需要某种方法来估计将有多少个输入字符串。（大多数文件系统都知道它们包含多少个单独的文件，而不必遍历目录树并对其进行计数。）

您可以对重复项的分布进行一些假设，以做出更好的猜测。

如果临时文件的 数量
而不是大小是问题，则可以将多个批次一个接一个地存储在同一输出文件中。可以将长度标头放在每个数据头的开头，以允许逐批跳过，或者将字节偏移量写入单独的数据流。如果大小也很重要，请参阅我的有关使用frcode样式的通用前缀压缩的段落。

正如伊恩·默瑟（Ian
Mercer）在回答中指出的那样，对批次进行分类将使合并效率更高。如果不这样做，您可能会碰到算法无法向前发展的障碍，或者您需要执行以下操作：加载一个批次，扫描另一批次以查找第一批次中的条目，然后使用仅删除可能很少的匹配条目。

不对批次进行排序会使首遍O（N）的时间变得复杂，但是要么必须在以后的某个时刻进行排序，要么后期阶段的情况将变得更糟。您希望对输出进行全局排序，因此，除了RadixSort方法外，还无法避免在某处使用O（N
log N）。

在有限的批处理大小下，需要O（log N）合并步骤，因此您的原始分析通过忽略编写阶段1批处理后需要做什么而错过了方法的O（N log N）复杂性。

适当的设计选择会发生很大变化，具体取决于我们的内存上限是否足够大，以至于在一批内可以找到很多重复项。如果即使像Trie这样的复杂紧凑的数据结构也无济于事，则将数据放入Trie并再次取出以写入批处理将浪费CPU时间。

如果您仍然无法在每个批次中执行大量重复消除操作，则需要进行优化以将可能匹配的键放到下一个阶段。您的第一阶段可以将输入字符串按第一个字节分组，最多可分为252个左右的输出文件（并非所有256个值都是合法的文件名字符），也可以分为27个左右的输出文件（字母+
misc），或26 + 26 + 1适用于大写/小写+非字母。临时文件可以省略每个字符串的公共前缀。

那么大多数这些第一阶段批次应具有更高的重复密度。实际上，在任何情况下，这种向输出桶中输入的基数分布都是有用的，请参见下文。

您仍应按块对第一阶段的输出进行排序，以使下一遍为同一RAM提供更大的dup-find窗口。

我将花更多的时间在该域上，在用完约100MiB的RAM或您选择的上限之前，您可以在初始流中找到有用的重复项。

显然，我们将字符串添加到某种字典中，可以快速查找和计数重复项，而只需要为唯一字符串集提供足够的存储空间。仅存储字符串 然后
对其进行排序会大大降低效率，因为如果不进行即时重复检测，我们会更快达到RAM限制。

为了最大程度地减少阶段2的工作，阶段1应该找到并计算尽可能多的重复项，以减少p2数据的总大小。减少阶段2的合并工作量也很好。
较大的批处理对这两个因素都有帮助
，因此在阶段1中尽可能安全地接近内存上限非常有用。当您的内存消耗接近您选择的上限时，请不要在一定数目的输入字符串之后编写批处理。重复项被计数并丢弃，并且不占用任何额外的存储空间。

准确的内存记帐的一种替代方法是跟踪字典中的唯一字符串，这很容易（并且由库实现为您完成）。累积添加的字符串的长度也可以使您很好地估计用于存储字符串的内存。或者只是对字符串长度分布做一个假设。首先将哈希表的大小设置为正确的大小，以便在添加元素时不必增加哈希表的大小，因此当哈希表的60％满（负载系数）之类的东西停止时，它就停止了。

对于给定的内存限制，字典的节省空间的数据结构会增加我们的查找窗口。当哈希表的负载因数过高时，哈希表的效率将大大降低，但是哈希表本身仅需要存储指向字符串的指针。它是最熟悉的字典，并具有库实现。

我们知道一旦看到足够的唯一键，我们将希望对批处理进行排序，因此使用可以按排序顺序遍历的字典可能很有意义。 动态排序很有意义，因为密钥会慢慢进入
，受磁盘IO的限制，因为我们正在从文件系统元数据中读取数据。缺点是，如果我们看到的大多数键都是重复键，则我们要执行很多O（log
batchsize）查找，而不是很多O（1）查找。而且当字典很大时，键很可能是重复键，因此大多数O（log
batchsize）查询的批处理大小将接近max，而不是均匀地分布在0和max之间。无论键是否唯一，一棵树都要为每次查找付出O（log
n）的排序开销。哈希表仅在删除重复项后才支付排序费用。因此对于一棵树来说，它是O（total_keys * log
unique_keys），哈希表是O（unique_keys * log unique_keys）来对批次进行排序。

将最大负载因子设置为0.75或某种东西的哈希表可能非常密集，但是KeyValuePair在写出批处理之前必须对s
进行排序可能会阻碍使用标准Dictionary。您不需要字符串的副本，但是最终可能会将所有指针（ref）复制到暂存空间以进行非就地排序，并且可能还包括在排序之前将它们从哈希表中删除时。（或者不是指针，而是KeyValuePair，以避免不得不返回并在哈希表中查找每个字符串）。如果大内存消耗的短暂峰值是可以忍受的，并且不会导致您将/页面交换到磁盘，则可能会很好。如果可以在哈希表使用的缓冲区中进行就地排序，则可以避免这种情况，但是我怀疑标准库容器会发生这种情况。

在不使用速度键的情况下，不断使用CPU来维持排序的字典的细流效果可能比不经常使用CPU突发来对批处理的所有键进行排序的方法要好，除了可以消耗大量的内存。

.NET标准库具有SortedDictionary<TKey, TValue>，文档说是用二叉树实现的。我没有检查它是否具有重新平衡功能或使用红黑树来保证O（log
n）最坏情况的性能。我不确定会有多少内存开销。如果这是一项一次性的任务，那么我绝对建议您使用它来快速，轻松地实现它。以及用于重复使用的更优化设计的第一个版本。除非找到一个不错的Tries库实现，否则您可能会发现它已经足够好了。

高效内存排序字典的数据结构

输出字典的内存效率越高，在必须写出批处理并删除字典之前，我们可以找到更多的重复。另外，如果它是排序字典，即使找不到重复项，我们的批次也可以更大。

数据结构选择的次要影响是，我们在关键服务器上运行时会生成多少内存流量。排序数组（具有O（log
n）查找时间（二进制搜索）和O（n）插入时间（随机播放元素以腾出空间））将是紧凑的。但是，这不仅会很慢，而且会在很多时候饱和内存带宽。与100％CPU使用率搜索二叉树相比，100％CPU使用率这样做对服务器性能的影响更大。在加载当前节点之前，它不知道从哪个位置加载下一个节点，因此无法传递内存请求。在树搜索中，分支对比较的错误预测还有助于降低所有内核共享的内存带宽的消耗。（是的，某些100％CPU使用率的程序比其他程序差！）

如果清空我们的字典不会在清空它时使内存碎片化，那就太好了。但是，树节点的大小将保持不变，因此一堆分散的孔将可用于将来的树节点分配。但是，如果我们为多个基数存储桶有单独的字典（请参见下文），则与其他字典相关联的键字符串可能会与树节点混合在一起。这可能会导致malloc很难重用所有释放的内存，从而可能使实际的操作系统可见内存使用量增加一小部分。（除非C＃运行时垃圾收集进行压缩，否则将处理碎片。）

由于在清空字典并将其全部删除之前，您不需要删除节点，因此可以将Tree节点存储在可增长的数组中。因此，内存管理仅需跟踪一个大分配，与单独分配每个节点的malloc相比，减少了记账开销。代替真实指针，左/右子指针可以是数组索引。这样一来，您只能使用16位或24位。（堆是存储在数组中的另一种二叉树，但不能有效地用作字典。它是一棵树，但不是
搜索 树）。

存储字典的字符串键通常将每个String作为一个单独分配的对象完成，并在数组中指向它们。再说一次，在您准备删除它们之前，无需删除，增长甚至修改它们，您可以将它们从头到尾打包在char数组中，并在每个末尾添加一个终止的零字节。这再次节省了很多记账工作，并且还使跟踪字符串所使用的内存量变得容易，从而使您可以安全地接近所选的内存上限。

Trie / DAWG可实现更紧凑的存储

为了更密集地存储一组字符串，我们可以消除存储每个字符串的所有字符的冗余，因为可能有很多公共前缀。

一个特里存储在树形结构中的字符串，使您共同前缀压缩。可以按排序顺序遍历它，因此它可以即时进行排序。每个节点的子节点数与集合中不同的下一字符数相同，因此它不是二叉树。可以在此SO答案中找到AC＃Trie部分实现（未写删除），此问题类似于此问题，但不需要批处理/外部排序。

Trie节点可能需要存储许多子指针，因此每个节点可能很大。或者，每个节点都可以是可变大小的，如果C＃允许的话，可以在节点内部保存nextchar：ref对的列表。或如Wikipedia文章所述，一个节点实际上可以是链接列表或二进制搜索树，以避免浪费很少的子节点。（一棵树的下层将有很多这样的功能。）需要用词尾标记/节点来区分不是分开的字典条目的子字符串和是分开的子字符串。我们的计数字段可以达到这个目的。Count
= 0表示在此结尾的子字符串不在字典中。count> = 0表示是。

更为紧凑的Trie是“ 基数树”或“
PATRICIA树”，它在每个节点上存储多个字符。

这种想法的另一个扩展是确定性非循环有限状态自动机（DAFSA），有时也称为有向非循环字图（DAWG），但请注意，DAWG维基百科文章是关于同名的另一件事。我不确定DAWG是否可以按顺序遍历以在末尾取出所有密钥，并且正如Wikipedia指出的那样，存储关联数据（如重复计数）需要进行修改。我也不确定是否可以逐步构建它们，但是我认为您可以进行查询而无需压缩。新添加的条目将像Trie一样存储，直到压缩步骤每128个新键将它们合并到DAWG中。（或者，对于较大的DAWG，不那么频繁地运行压缩，因此您不必做太多事情，例如在必须增长哈希表时将其大小加倍，而不是线性增长以分摊昂贵的操作。）

您可以通过在没有任何分支/收敛的情况下将多个字符存储在单个节点中来使DAWG更加紧凑。
该页面还提到了用于紧凑型DAWG的霍夫曼编码方法，并提供了其他一些链接和文章引用。

JohnPaulAdamovsky的DAWG实现（用C语言编写）看起来不错，并描述了它使用的一些优化。我没有仔细看，看它是否可以将字符串映射为计数。经过优化，可以将所有节点存储在阵列中。
对于1TB文本问题中的重复计数单词的此答案建议使用DAWG，并具有几个链接，但是我不确定它的用处。

批处理：第一个字符为基数

您可以启用RadixSort，并为每个起始字符保留单独的字典（或对于z之前排在首位的非字母，z之后排在首的非字母）。每个字典都写出一个不同的临时文件。如果您有多个可用于MapReduce方法的计算节点，这将是将合并工作分配到计算节点的方法。

这允许进行有趣的修改：而不是一次写入所有基数桶，而 仅将最大的字典作为批次写入
。这样可以防止每次您将少量批次放入一些存储桶中。这将减小每个存储桶中合并的宽度，从而加快了阶段2的速度。

对于二叉树，这使每棵树的深度减少了大约log2（num_buckets），从而加快了查找速度。对于Trie，这是多余的（ 每个
节点使用下一个字符作为基数对子树进行排序）。使用DAWG时，这实际上会损害您的空间效率，因为您将失去寻找起点不同但共享部分不同的字符串之间的冗余的机会。

如果有几个不经常碰到的水桶保持增长，但这样做的潜力可能很差，但通常不会成为最大的水桶。它们可能会占用您总内存的很大一部分，从而从常用存储桶中提取少量数据。您可以实现一个更智能的驱逐算法，该算法记录存储桶（词典）上一次被清空的时间。一个存储桶的NeedsEmptying得分将是大小和年龄的乘积。或某些年龄函数，例如sqrt（age）。记录自上次清空以来每个存储桶找到多少重复项的某种方法也是有用的。如果您在输入流中某个存储桶中有很多重复的位置，那么您最后要做的就是经常清空它。也许每次您在存储桶中找到重复项时，都要增加一个计数器。看看年龄与骗子的比率。当它们的大小开始增加时，坐在那里的低使用率的存储桶很容易找到将RAM从其他存储桶中带走的方式。如果发现很多重复项，则即使它们是当前最大的值，它们也可能会保留下来。

如果用于跟踪年龄和重复数据的数据结构是数组结构，则(last_emptied[bucket] - current_pos) / (float)dups_found[bucket]可以使用矢量浮点数有效地进行除法。一整数除法慢于一FP除法。一个FP分区的速度与4个FP分区的速度相同，并且如果您像这样轻松进行编译，则希望编译器可以自动矢量化。

填充多个存储桶之间有很多工作要做，因此除非您使用 大量 存储桶，否则划分工作将是一个小小的麻烦。

选择如何存储

使用良好的驱逐算法，理想的存储桶选择将在某些存储桶中将很少有重复项的密钥放在一起，而在其他存储桶中将具有很多重复项的桶放在一起。如果您知道数据中的任何模式，这将是一种利用它的方法。有一些存储桶大多是低负载的，这意味着所有这些唯一的密钥都不会将有价值的密钥冲走到输出批处理中。一种驱逐算法，根据每个唯一键找到的重复数来查看存储桶的价值，即使它们的大小逐渐增加，它也会自动找出哪些存储桶是有价值的和值得保留的。

有 很多
方法可以将您的琴弦扎入桶中。有些人将确保存储桶中的每个元素的比较少于后面的存储桶中的每个元素，因此轻松生成完整排序的输出。有些不会，但是还有其他优点。桶选择之间会有折衷，所有选择均取决于数据：

• 擅长在第一遍中找到很多重复项（例如，通过将高重复模式与低重复模式分离）
• 在各个存储桶之间均匀地分配批次数量（因此，没有一个存储桶具有在第二阶段中需要多阶段合并的大量批次）以及其他因素。
• 与数据集上的逐出算法结合使用时，会产生不良行为。
• 产生全球分类输出所需的桶间合并数量。此重要性的大小取决于唯一字符串的总数，而不是输入字符串的数目。

我敢肯定，聪明的人已经想到了在我之前存储字符串的好方法，因此，如果按首字符的明显方法不理想，那么这可能值得研究。这种特殊的用例（在消除/计数重复项的同时进行排序）并不典型。我认为大多数排序工作只考虑保留重复项的排序。因此，您可能找不到很多可以帮助为重复计数外部排序选择好的存储桶算法的东西。无论如何，这将取决于数据。

进行分桶操作的一些具体选项为：基数=前两个字节在一起（仍组合大写/小写，并组合非字母字符）。或者Radix
=哈希码的第一个字节。（需要全局合并以产生排序的输出。）或Radix = (str[0]>>2) << 6 + str[1]>>2。即忽略前2个字符的低2位，放在[abcd][abcd].*一起[abcd][efgh].*，等等，这也需要在一些存储桶组之间合并排序结果。例如daxxx将在第一个存储桶中，但aexxx将在第二个存储桶中。但是，只有具有相同第一个字符高位的存储桶才需要相互合并，以产生排序后的最终输出。

一种处理存储桶选择的想法，可以很好地进行重复查找，但需要在存储桶之间进行合并排序：编写phase2输出时，将其以第一个字符作为基数进行存储桶化以产生所需的排序顺序。每个阶段1存储桶将输出分散到阶段2存储桶中，作为全局排序的一部分。处理完所有可以包含以开头的字符串的phase1批处理之后，a将aphase2-bucket合并到最终输出中并删除这些临时文件。

基数=前2个字节（与非字母组合）将构成28 2 =
784个存储桶。使用200MiB的RAM，平均输出文件大小仅为256k。一次只清空一个存储桶将使该数量最少，而且通常会获得较大的批次，因此这可以工作。（您的驱逐算法可能会遇到一个病理情况，使它保留很多大桶，并为新桶写了一系列小批量。如果不仔细测试，可能会启发聪明的试探法。）

打包到同一输出文件中的多个批次可能对许多小存储桶最有用。您将有784个输出文件，每个文件包含一系列批次。希望您的文件系统具有足够的连续可用空间，并且足够聪明，可以很好地完成分散少量小写操作到多个文件时的碎片处理。

合并：

在合并阶段，对于排序的批次，我们不需要字典。只需从批次中具有最低价的下一行开始，将重复的内容组合在一起即可。

MergeSort通常会合并对，但是在进行外部排序（例如，磁盘->磁盘）时，通常会使用更宽的输入，以避免多次读取和重写输出。打开25个输入文件以合并为一个输出文件应该没问题。使用PriorityQueue的库实现（通常实现为Heap）从许多排序列表中选择下一个输入元素。也许以字符串为优先级添加输入行，并以有效负载添加计数和输入文件号。

如果您在第一遍中使用了按基数分配基数，则将所有a批次合并到最终输出文件中（即使此过程需要多个合并阶段），然后合并所有b批次，等等。
您不需要检查“从开始使用”a存储桶中的任何批次与其他任何存储桶中的批次，因此可以节省 很多
合并工作，尤其是。如果您的密钥按第一个字符分配得当。

最小化对生产服务器的影响：

合并期间限制磁盘I / O，以避免在磁盘预取会产生巨大的I / O队列读取深度时使服务器瘫痪。限制I /
O而不是缩小合并范围可能是一个更好的选择。如果服务器忙于正常工作，则可能会出现问题。即使您只读取几个文件，也不会进行大量的顺序读取。

运行时偶尔检查系统负载。如果温度很高，请睡一秒钟，然后再做更多工作并再次检查。如果确实很高，在平均负载下降之前（检查之间睡眠30秒），不要再做任何工作。

还要检查系统内存使用情况，如果生产服务器上的内存不足，请降低批处理阈值。（或者，如果确实很紧，则冲洗部分批次并入睡，直到内存压力降低为止。）

如果临时文件的大小是个问题，则可以执行updated/locate中的frcode之类的通用前缀压缩，以显着减小字符串排序列表的文件大小。可能在批处理中使用区分大小写的排序，但是不区分大小写的转换。因此a存储桶中的每个批次都将具有所有As，然后具有所有as。甚至LZ4都可以即时对其进行压缩/解压缩。计数使用十六进制，而不是十进制。它更短，并且编码/解码更快。

/在键和计数之间使用不是合法文件名字符的分隔符，例如。字符串解析在合并阶段可能会占用大量CPU时间，因此值得考虑。如果您可以将字符串留在每个文件的输入缓冲区中，然后仅将PQueue指向它们，那可能很好。（并告诉您字符串来自哪个输入文件，而无需单独存储。）

性能调优：

如果最初的未排序字符串可用得非常快，那么散列表适合CPU
L3高速缓存中的字典的散列表可能会是一个胜利，除非更大的窗口可以包含更大比例的键并找到更多的重复项。取决于说100k文件中典型的重复次数。在读取时在RAM中构建小批量的批次，然后将它们合并为磁盘批次。这可能比进行大型内存快速排序更为有效，因为在您初次阅读输入之前，您无法随机访问输入。

由于I / O可能会受到限制，因此不适合CPU数据高速缓存的大批量可能是一个胜利，因为它可以查找更多重复项，并且（极大地？）减少了要完成的合并工作量。

在从操作系统获取的每个文件名块之后，每个子目录或其他内容之后，检查散列表的大小/内存消耗可能比较方便。只要您选择一个保守的大小范围，并且确保不进行检查就不会太久，就不必费力检查每个迭代。

1983年的这篇论文研究了外部合并排序，以消除遇到的重复项，并建议使用哈希函数和位图消除重复项。使用长输入字符串时，存储MD5或SHA1散列以进行重复消除可节省大量空间。

我不确定他们对位图的想法是什么。要具有足够的耐碰撞性，而又无需返回原始字符串就可以使用，则将需要太多位的哈希码来索引合理大小的位图。（例如，MD5是128位哈希）。