快速数据抽取算法

Question

我有2个utf-8文本文件。在文件的每一行中都有一个字符串，它可以包含特定于语言的字符，如µ、？、ą，ę。字符串的顺序和长度是随机的，并且可以重复。在第一个文件中，至少有3mln行(很容易超过1MLD的行数)。第二个文件较小，它通常有大约40万行(但也可以更大)。

我需要创建一个新文件，其中包含来自文件一的条目，其中删除了出现在文件二和所有重复条目中的条目。

目前，我正在对两个文件进行排序，并删除重复的条目。接下来，我将它们写入到新文件中，同时检查它们是否出现在第二个文件中。

有没有更快的方法来做这件事？

编辑

记忆力是个问题。我不会将这个字符串复制到内存中，而是对文件进行操作。我的朋友建议不要复制到内存，而是在文件流上工作。在此之后，执行时间会显着下降。

计算机管理员不想在上面安装数据库。

在对我的代码进行排序后，像这样在循环中运行：

if stringFromFile1 < stringFromFile2 then writeToFile3 and get next stringFromFile1
else if stringFromFile1 == stringFromFile2 then dropStringFromFile1 and get next stringFromFile1
else if stringFromFile1 > stringFromFile2 then get next stringFromFile2 and go to line 1

Answer 1

如果您有一个可用的数据结构，比如哈希集，那么只需迭代文件并添加每一行即可。集合不允许重复，而哈希集应该为您提供一种检查元素是否已经存在的恒定方法(至少在Java语言中，add方法检查元素是否存在，如果不存在，它会在固定时间内将元素添加到集合中)。

一旦您遍历了这两个文件，您就可以遍历哈希集并将其内容存储到文件中。这将为您提供一个可以在线性时间内实现的算法。

忘了提一下:我假设您对内存消耗没有限制。如果这样做，您可能希望尝试将每行保存到数据库中，并将每行的散列用作主键。插入具有两个主键的元素应该会失败，从而确保数据库中有唯一的字符串。一旦完成插入，就可以从数据库中检索这些值并将其存储到一个文件中。

Answer 2

我的建议是对文件二进行预处理，并由它形成树形结构。例如，假设你有这样的文件二：

bad
bass
absent

那么你的树结构应该是这样的：

BEGIN -> b -> a -> d -> END
|             |
|             + -> s -> s -> END
|
+-> a -> b -> s -> e -> n -> t -> END

END指定单词分隔符(可以是空格、换行符或其他什么)

然后你打开一个文件到文件流中，一个字节一个字节地读出它。一旦你遇到文件的开头或者在分隔符之后选择下一个字符，你就开始遍历你的树。如果使用流字节数，您可以将其遍历到END，这意味着您找到了匹配的单词，您应该丢弃它。如果不是，则该单词是唯一的，不需要删除。如果发现唯一，则必须将该单词添加到树结构中，以丢弃其进一步的重复。

树结构将占用大量内存，但无论如何它都比在某种类型的数组中保存唯一字要少

Answer 3

有许多可能的优化。

正如Roman Saveljev所建议的，你可以在内存中保留一个trie结构。根据数据的熵，它可以很容易地放入内存。

当第二个文件被排序时，你可以运行二进制搜索来检查记录是否在那里(如果你还没有这样做的话)。

您还可以在内存中保留一个Bloom Filter，以便轻松地检查那些没有复制的记录，从而避免每次都去磁盘。