搜索多个字符串

Question

我知道在文件中查找一个字符串的有效方法(kmp),或文件中的各种字符串(trie)

但是,多年以来,我一直想知道是否有一种方法(并且在某种程度上认为这是不可能的)来搜索多个文件的多个字符串

假设我有一百万个文件,我想回答诸如"查找具有字符串"香蕉","摩托艇"和"白狐""的查询.什么是有效的算法？有吗？

当然,可以在线性时间内搜索要搜索的文件大小.但对于大量的大文件来说,这似乎是不可行的.谷歌的存在似乎表明实际上有一个非常快的算法来做到这一点.也许甚至一个这样的问题,即每个查询只取决于查询大小,而不是文本大小的数据库(当然,这样的算法会涉及输入文件的一些预处理)

我认为必须有一个这样的算法(谷歌做它!)但我的搜索没有发现任何东西.

Answer 1

由于没有其他人回答，我将以我简单的想法开始滚动，希望聪明的人能进一步提供帮助。

好的，首先，只需将 1,000,000 个文件拆分到多个服务器上，就可以轻松并行化，因为前 250,000 个文件（如果说您有 4 个服务器）可以独立于其余文件进行搜索。

然后，假设您的文档以“.txt”结尾，每个服务器都可以运行类似的内容：

#!/bin/bash
find . -name "*.txt" | while IFS= read a
do
  grep -l banana "$a" | while IFS= read b
  do
    grep -l motorboat "$b" | while IFS= read c
    do
      grep -l "the white fox" "$c"
    done
  done
done

通过在常见单词之前搜索稀有单词可以提高性能。

另外，您可以使用 awk 并传入所有 3 个搜索模式，并在找到它们后立即退出，而不是继续处理直到文件末尾。

当然，如果您要执行多个重复查询，则值得预先花费更多时间将文件加载到有效的结构（例如哈希）中。因此，如果您的输入文件包含单词“motorboat”，那么您的散列中将会有一个条目，并且仅通过测试散列中是否存在即可非常快速地测试文件是否包含该单词。然后，这可以修剪需要进入上述方法的文件，并大幅提高性能。

因此，以下代码将解析所有“.txt”文件，并记录每个单词所在的文件。因此，当需要进行搜索时，您只需传入搜索词即可找到包含该单词的文件单词（不一定彼此相邻）并将该文件列表传递给上面的脚本：

#!/usr/bin/perl
use strict;
use warnings;

my %words;

# Load all files ending in ".txt"
my @files=<*.txt>;
foreach my $file (@files){
   print "Loading: $file\n";
   open my $fh, '<', $file or die "Could not open $file";
   while (my $line = <$fh>) {
     chomp $line;
     foreach my $str (split /\s+/, $line) {
        $words{$str}{$file}=1;
     }
   }
   close($fh);
}

foreach my $str1 (keys %words) {
  print "Word: \"$str1\" is in : ";
  foreach my $str2 (keys $words{$str1}) {
    print "$str2 ";
  }
  print "\n";
}

我创建的小测试文件的输出如下：

./go
Loading: a.txt
Loading: b.txt
Loading: c.txt
Loading: d.txt
Word: "the" is in : c.txt d.txt 
Word: "motorboat" is in : b.txt d.txt 
Word: "white" is in : c.txt d.txt 
Word: "banana" is in : c.txt d.txt a.txt 
Word: "fox" is in : c.txt d.txt