LINUX/C++第二个文件

删除在第一个文件的字符串我想比较字符串的两个文件，并删除一切，这是在文件1文件2，如果它的存在，并将其保存在第三输出文件。我打算为此编写一个C++程序，但最好的办法是O（N^2），Linux中有没有这样的命令？如果不是什么是用C++做的最有效的方法？这些文件具有高达1根1十亿串和10万美元的另一个所以O（N^2）是极其低效LINUX/C++第二个文件

前F1 你好乔希科瑞 SAM 唐

F2 插孔乔希乔伊 SAM NEDA 等

OUTPUTFILE：插孔乔伊 NEDA 等

要清楚，我并不想将它们合并，然后删除重复的，我只希望在文件1串的重复项文件2. 感谢

来源

2013-11-26 Tangleman

如果你有在文件中的字符串十亿，也许是文本文件并不存储这些信息的最佳方式。 – crashmstr

你推荐什么格式？要使用这些非常需要txt文件的程序。所以我有一点空间。 – Tangleman

fgrep是非常方便的这种去除：它会为一组固定字符串grep一个文件。

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

来源

2013-11-26 20:17:43

所以如果我只是添加> fil3将输出到此文件而不是标准输出？因为我不想看到数百万的字符串在终端上弹出！ – Tangleman

是的，应该这样做。 – aust

由于某种原因，这似乎不能正常工作。这样做后，f1有500000个字符串和f2有800000个输出文件只有1400个字符串。如果f2包含所有的f1，它仍然会剩下大约300000个字符串 – Tangleman

您可以使用Aho-Corasick字符串匹配算法解决此任务。它用于跨文本的多关键字搜索，时间复杂度是线性的。这个算法在网上有一些C++的实现。例如this。

此外，对于这一个看上去不错的python library。

不过，我不知道，如果存储的复杂性使用这些源/库的时候是OK。您可能需要从块中读取第一个文件的输入（因为它可能有数十亿个字符）。

来源

2013-11-26 23:26:38 yasen

Aho-Corasick对我来说太过分了。 – RichardPlunkett

@RichardPlunkett嗯，这取决于。如果你只需要匹配整个字符串，那么一个简单的哈希表就可以做到。但是，如果单个文本字可能包含多个重叠的模式字（如“重要”中的“import”，“port”和“ant”），则Aho-Corasick就是解决方案。当我读到这个问题时，我立即将多个字符串匹配和“低效的O（n^2）”与Aho-Corasick相关联。我认为这是一个合适的解决方案，因为可以简单地使用实现它的库。另外，了解这个强大的算法是很好的。 – yasen

那么这些都是巨大的词典，每行一个字符串，肯定会有重叠的模式，因为它有如此庞大的列表。我会研究这个算法，谢谢！ – Tangleman

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

集被实现为与对数成员资格测试时间平衡树。

但是，你应该已经使用了一些数据库系统存储（和填充）的数据。（如PostgreSQL中，MariaDB的，MongoDB中，CouchDB的，....）

来源

2013-11-27 05:54:27

LINUX/C++第二个文件

回答

相关问题