LINUX / C++从第二个文件中删除第一个文件中的字符串

Question

我正在尝试比较两个字符串文件，并从文件2中删除文件1中的所有内容(如果存在)，并将其保存在第三个输出文件中。我打算写一个c++程序，但是我能想到的最好的结果是O(N^2)，Linux中有什么命令可以做到这一点吗？如果不是，使用c++最有效的方法是什么？这些文件在一个文件中最多有10亿个字符串，在另一个文件中有1000万个字符串，因此O(N^2)的效率非常低

前f1你好乔什·科里·山姆·唐

f2杰克·乔希·乔伊·萨姆·内达等

输出文件:杰克、乔伊、奈达等

要清楚的是，我没有试图合并他们，然后删除重复，我只想从文件1中的重复字符串从文件2删除。谢谢

Answer 1

fgrep在这方面很方便:它将grep一个文件作为一组固定的字符串。

fgrep -f f1 -v f2将打印出f2中在f1中找不到的所有行。

Answer 2

您可以使用Aho-Corasick字符串匹配算法来解决此任务。它用于跨文本的多关键字搜索，其时间复杂度是线性的。

网上有一些该算法的C++实现。例如this。

此外，还有一个很好看的python library。

但是，在使用这些源代码/库时，我不确定内存复杂度是否合适。您可能必须以块的形式读取第一个文件中的输入(因为它可能有数十亿个字符)。

Answer 3

您可以编写一个C++ (或Ocaml)程序，该程序读取第一个文件中的所有单词并将它们存储在一组字符串中(在C++中使用std::set<std::string>，在Ocaml中使用module SS = Set.Make(String);; )。填充该集合的复杂度应该是O( n ) (其中n是单词的数量，即集合的基数)。测试一个m个单词的文件，每个单词是否属于该集合是O (m )

集合被实现为具有对数成员资格测试时间的平衡树。

但是，您可能已经使用了一些数据库系统来存储(和填充)数据。(例如PostGreSQL、MariaDB、MongoDB、CouchDB、....)