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++第二個文件

回答

相關問題