在非常大的文件中快速搜索字符串

Question

在包含字符串的文件中搜索行的最快方法是什么。我有一个包含要搜索的字符串的文件。这个小文件(smallF)包含大约50000行，看起来像：

字符串到搜索1
字符串到搜索2
串到搜索3

我必须在一个更大的文件中搜索所有这些字符串(大约有1亿行)。如果此较大文件中的任何一行包含搜索字符串，则打印该行。

到目前为止，我想出的最好的方法是

grep -F -f smallF largeF

但这不是很快。smallF中只有100个搜索字符串，大约需要4分钟。对于超过50000个搜索字符串，这将花费大量时间。

有没有更有效的方法？

Answer 1

我曾经注意到，使用-E或多个-e参数比使用-f更快。请注意，这可能不适用于您的问题，因为您正在较大的文件中搜索50000字符串。然而，我想向你展示什么可以做，什么可能值得测试：

以下是我详细注意到的内容：

用随机字符串填充1.2GB文件。

>ls -has | grep string
1,2G strings.txt
>head strings.txt
Mfzd0sf7RA664UVrBHK44cSQpLRKT6J0
Uk218A8GKRdAVOZLIykVc0b2RH1ayfAy
BmuCCPJaQGhFTIutGpVG86tlanW8c9Pa
etrulbGONKT3pact1SHg2ipcCr7TZ9jc
.....

现在我想搜索字符串"；ab"cd"；以及"；ef"；使用不同的grep方法：

1. 使用不带标志的grep，一次搜索一个：

grep "ab" strings.txt > m1.out  
2,76s user 0,42s system 96% cpu 3,313 total

grep "cd" strings.txt >> m1.out  
2,82s user 0,36s system 95% cpu 3,322 total

grep "ef" strings.txt >> m1.out  
2,78s user 0,36s system 94% cpu 3,360 total

因此，搜索总共需要将近10秒。

2. 在search.txt 中使用带有-f标志的grep和搜索字符串

   >cat search.txt
   ab
   cd
   ef
   >grep -F -f search.txt strings.txt > m2.out  
   31,55s user 0,60s system 99% cpu 32,343 total
   

由于某些原因，这几乎需要32秒。

3. 现在使用-e的多种搜索模式

   grep -E "ab|cd|ef" strings.txt > m3.out  
   3,80s user 0,36s system 98% cpu 4,220 total
   

   或

   grep --color=auto -e "ab" -e "cd" -e "ef" strings.txt > /dev/null  
   3,86s user 0,38s system 98% cpu 4,323 total
   

使用-E的第三种方法只花了4.22秒来搜索文件。

现在让我们检查结果是否相同：

cat m1.out | sort | uniq > m1.sort  
cat m3.out | sort | uniq > m3.sort
diff m1.sort m3.sort
#

diff不产生输出，这意味着找到的结果是相同的。

也许想试试，否则我建议你看看线程"最快可能grep"；，见赛勒斯的评论。

Answer 2

您可能想尝试sift或ag。sift特别列出了一些与grep相比令人印象深刻的基准测试。

Answer 3

注意：我意识到以下不是基于bash的解决方案，但考虑到您的搜索空间很大，有必要使用并行解决方案

---

如果您的机器有多个核心/处理器，您可以在Pythran中调用以下函数来并行搜索：

#!/usr/bin/env python
#pythran export search_in_file(string, string)
def search_in_file(long_file_path, short_file_path):
_long = open(long_file_path, "r")
#omp parallel for schedule(guided)
for _string in open(short_file_path, "r"):
if _string in _long:
print(_string)
if __name__ == "__main__":
search_in_file("long_file_path", "short_file_path")

注意：在幕后，Pythran使用Python代码，并试图将其积极编译成非常快的C++。