从两个文件中查找常用单词

Question

给定两个包含单词列表(大约百万个)的文件，我们需要找出共同的单词。

使用一些有效的算法，也没有足够的内存可用(一百万，当然不)..如果可能的话，一些基本的C编程代码会有所帮助。

未对文件进行排序。我们可以使用某种算法。请用基本代码来支持它...

排序外部文件......在可用内存最少的情况下，如何用C编程实现它呢？

任何人都可以对文件进行外部排序...请分享一些这方面的代码。

Answer 1

还有另一种方法。

通用。首先，请注意，按顺序执行此操作将获取O(N^2)。对于N=1,000,000，这是一个很大的问题。对每个列表进行排序需要O(N*log(N))；然后，您可以通过对文件进行来一次性找到交叉点(见下文)。所以总数是O(2N*log(N) + 2N) = O(N*log(N))。

对文件进行排序的。现在，让我们解决一个事实，即处理文件比处理内存慢得多，特别是在对需要移动内容的位置进行排序时。解决这个问题的一种方法是-决定可以加载到内存中的块的大小。一次加载一个文件块，有效地对其进行排序并保存到一个单独的临时文件中。排序的块可以在一次遍历中合并成一个排序的文件(同样，见下文)。

。当你有两个排序的列表(文件或非文件)时，你可以很容易地将它们合并成一个排序的列表:有2个“指针”，最初指向每个列表中的第一个条目。在每个步骤中，比较指针所指向的值。将较小的值移动到合并列表(您正在构造的列表)，并将其指针前移。

您可以轻松地修改合并算法，使其找到交叉点-如果指向的值相等，则将其移动到结果中(考虑您希望如何处理重复项)。

对于合并两个以上的列表(就像上面的文件排序一样)，您可以推广使用k指针的算法。

Answer 2

如果您有足够的内存将第一个文件完全读入内存，我建议将其读入字典(该单词的word ->索引)，循环第二个文件中的单词，并测试该单词是否包含在该字典中。今天对一百万个单词的记忆并不多。

如果没有足够的内存，请将第一个文件拆分成适合内存的块，然后按照我上面所说的对每个块执行操作。例如，用前100.000个单词填充字典，找到该部分的每个常用单词，然后第二次读取文件，提取单词100.001到200.000，找到该部分的常用单词，依此类推。

现在最难的部分是:你需要一个字典结构，你说的是"basic C“。当您愿意使用"basic C++“时，可以使用常见编译器供应商提供的hash_map数据结构作为标准库的扩展。在basic C中，你也应该尝试使用现成的库，阅读this SO post找到一个似乎支持它的自由库的链接。

Answer 3

您的问题是:给定两个项目集，找到相互作用(两者共有的项目)，同时保持在RAM不足的约束内(小于任何集合的大小)。

由于查找交互需要比较/搜索另一个集合中的每个项目，因此您必须有足够的RAM来存储至少一个集合(较小的那个)，才能拥有有效的算法。

假设您知道交互比这两个集合都小得多，并且完全可以放在可用内存中--否则，您将不得不进一步将结果刷新到磁盘。

如果您在内存限制下工作，请将较大的集合划分为适合1/3可用内存的部分。然后将较小的集合划分为适合第二个1/3的部分。剩余的1/3内存用于存储结果。

通过查找较大集合的分区的最大值和最小值进行优化。这就是您要比较的集合。然后，当加载较小集合的相应分区时，跳过最小-最大范围之外的所有项目。

首先通过双循环找到两个分区的相互作用，将公共项存储到结果集中，并从原始集中删除它们，以便在循环中进一步进行比较。

然后用第二个分区替换较小集中的分区(跳过最小-最大值之外的项目)。重复一遍。请注意，较大集合中的分区减少了--公共项已被删除。

遍历整个较小的集合后，对较大集合的下一个分区重复操作。

现在，如果您不需要保留两个原始文件集(例如，您可以覆盖这两个文件)，那么您还可以通过从磁盘中删除公共项来进一步优化。这样，这些项就不再需要在进一步的分区中进行比较。然后，您可以通过跳过已删除的集合来划分集合。