java - 给定两个文件，在文件 1 中找到单词，但在文件 2 中找不到

Question

给定两个文件，想出一个算法/程序来查找文件 1 中的单词，而不是文件 2 中的单词。
请注意，文件中的单词未按排序顺序。

这是我的思考过程:

• 第1步:读取file2中的单词并将其添加到HashSet
• 第 2 步:读取 file1 并检查 file1 的某个词是否“不”存在于 HashSet 中。然后将其添加到文件 1 中存在但文件 2 中不存在的单词列表中。

如果两个文件中的单词数都在 100 或 1000 以内，则该算法可以正常工作。
但是，如果两个文件都很大(十亿字)，那么这个解决方案就行不通了，所以我想出了一个改进的解决方案:

• 第 1 步:逐字读取文件 2 并按字母顺序对单词排序 为单词分配桶，为所有以“a”开头的单词说一个桶。

所以 map 看起来像这样 ['a':{'ample','and'...}]。这将帮助我在 log(n) 时间复杂度内搜索存储桶，然后搜索 log(n) 以查找单词是否包含在排序列表中。

• 第 2 步:读取 file1 并检查 file1 的单词是否没有桶或不在桶中包含的列表中。

这个解决方案会奏效，但我相信仍有改进的余地。
如何进一步改进此解决方案？

Answer 1

一个可能的解决方案是使用一些 external sort对两个文件进行排序，然后并行迭代它们以找到仅出现在文件 1 中的单词:

伪代码(排序后):

iter1 = 0
iter2 = 0
while iter1 < file1.length:
    if file1[iter1] == file2[iter2]:
         iter1 = iter1 + 1
         iter2 = iter2 + 1
    else if file1[iter1] > file2[iter2]:
         iter2 = iter2 + 1
    else: //we know for sure the item is only in file1
         iter1 = iter1 + 1
         yield file1[iter1]

此解决方案需要 O(nlogn) 时间，并且所需空间非常小(外部排序所需的空间量)。

另请注意，此问题是 element distinctness problem 的变体，所以很可能它在使用基于比较的算法时具有 Omega(nl0gn) 的下限，或者在使用哈希时具有 Omega(n) 时间 + 空间。