搜索多个字符串

7
我知道在文件中查找一个字符串的高效方法(kmp算法),或者查找多个字符串的方法(trie树)。
但是,多年来,我一直在想是否有一种方式(有时认为不可能)可以搜索多个文件中的多个字符串。
比如说我有一百万个文件,并且我想回答这样的查询:“找到包含“香蕉”,“摩托艇”和“白色狐狸”的文件”。有什么高效的算法吗?是否存在这样的算法?
当然,可以在搜索文件大小的线性时间内进行这样的搜索。但对于大量的大文件来说,这似乎非常不可行。 谷歌的存在似乎表明实际上有一种非常快速的算法可以做到这一点。甚至可能每个查询只取决于查询的大小,而不是文本数据库的大小(当然,这样的算法将涉及输入文件的一些预处理)。
我认为必须有这样的算法(谷歌就是这样做的!),但我的搜索没有发现任何相关信息。
5个回答

3

并行编程

在大规模上,这绝对是一个需要并行编程的任务:将文件分发到不同的计算单元,让它们进行搜索,然后汇总结果。这实际上就是Google所做的事情,例如他们曾经通过组合数千台商用硬件PC来解决某些翻译问题。(虽然他们在实际的Google搜索结果中可能使用其他硬件。)您可以在互联网上阅读流行的文章。

“MapReduce”作为一个概念

例如,Google发明了一种称为MapReduce 的范例,并将其写成了一篇白皮书。基本上,这可以归结为在第一步中将输入映射到输出(广泛分布),然后在第二步中将所有小结果减少为一个主结果。

可以像这样实现搜索:

  • map:将要搜索的关键字与文档一起分发。如果在当前文件中找到搜索词,则从计算节点返回文件名。否则返回空。
  • reduce:从所有节点中收集所有文件名的列表。

(这与他们在论文中提出的“分布式grep”问题实际上是相同的。)

在给定文本中查找给定字符串是否存在的问题已经得到了广泛研究,称为“字符串匹配”,例如Rabin-Karp算法Knuth-Morris-Karp算法(只是为了让您尝试一下任何东西)。因此,实现map非常容易。

对于文件的分发,可以使用许多不同的技术。如果想要了解分布式文件系统的可能性,可以收集有关Google文件系统(GFS)的信息,例如在相应的白皮书中

reduce几乎什么都不做,所以这很容易。

完成。

这就是MapReduce范例的最大优点:一旦理解了如何将map和reduce合并为一个结果,实现这两个函数就非常容易。如果MapReduce框架已经实现了,那么就不必担心计算的并行性——否则可能会引发严重的头痛。

其他概念

这绝对不是唯一可能的概念。

  • 你可以根据自己的需要选择硬件(像MapReduce那样使用独立的个人计算机,还是使用拥有数十个CPU的超级计算机)。
  • 你可以根据自己的需要选择分布式(或非分布式)文件系统。
  • 你可以根据自己的需要选择编程语言,这也会产生很大的影响。

如果你对这个领域感兴趣,你会发现有很多其他的可能性。我相信,在不久的将来,随着分布式系统的兴起,会出现更多的可能性。但我希望我能提供一些关于可能性和注意事项的见解,甚至指导你如何立即实现它。


2

这个问题的表述比较宽泛。任何有效的解决方案都高度依赖于特定的假设。为了讨论起见,我将做出一些你没有明确提到的假设。

模型

假设...

  • f个文件,
  • 这些文件中总共有w个单词,
  • d个唯一的单词(d是覆盖所有文件所需的最小字典大小),
  • 查询中有q个单词,
  • 查询结果集中有r个文件。

我假设q<<d<<f<<w(即每个变量都比其后继变量“数量级更小”),并且进一步假设q基本上是常数,即O(1)。我还假设您主要关心在O(f)O(w)的摊销计算时间中最小化计算时间,愿意为了减少计算时间而投入更多的内存,并且您希望经常进行查询。

请注意,算法的运行时间不能比O(r)更好,因为我们需要输出属于结果集的每个文件。

算法

创建一个基于哈希映射的索引,从单词到文件集合,如下所示:

index = {}
for file in files:
  for word in file:
    index[word] += file

这段代码的时间复杂度为O(w),因为你至少需要查看一遍完整的输入数据,所以已经是最小化了。要查找包含所有query中单词的文件,请运行以下命令:

wordWithLeastFilesMatching = min(query, key=lambda word: len(index[word]))
result = set(index[wordWithLeastFilesMatching])
for word in query:
  result = result.intersection(index[word])
return result

这段代码的运行时间主要取决于需要执行的q个集合交集。在典型情况下,每个集合通常都是O(log(f))大小,各个集合之间的重叠部分适中。在这种情况下,计算时间复杂度为O(log(f))

但是在最坏的情况下,每个集合的大小都是O(f),即使重叠部分(因此r)很小。在这种情况下,计算时间仍然为O(f)


0

将每个文件中的文本分解为一组词元,并捕获与每个词元匹配的文本。将每个词元反向索引到匹配文件的集合中。对于每个搜索术语,转换为词元并返回每个文件中匹配的捕获文本。


0

如果您可以定期将每个文件序列化为一棵 trie,那么您可以根据需要反序列化每个 trie,并在所有 trie 上执行搜索和查询操作。这将非常快速,但当然需要您不断更新文件的 trie 进程。我相信谷歌也以某种方式保持其数据的索引,并且您必须进行一些权衡 - 在这种情况下,在增加性能的同时牺牲内存。


0

由于没有其他人回答,我将用我的简单想法开始讨论,希望有聪明的人能够进一步帮助。

首先,这可以很容易地并行化,只需将100万个文件分配到多台服务器上,例如,如果您有4台服务器,则前250,000个文件可以独立于其余文件进行搜索。

然后,每个服务器都可以运行类似于以下内容的代码,假设您的文档以“.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个搜索模式,并在找到它们全部后立即退出,而不是继续处理直到文件结尾。

当然,如果您要执行多个重复查询,则值得花费更多时间将文件加载到高效的结构(例如哈希)中。因此,如果您的输入文件包含单词“摩托艇”,则哈希表中将有一个条目,并且仅通过测试哈希表中是否存在该单词即可快速测试文件是否包含该单词。这样可以修剪需要进入上述方法的文件,并大大提高性能。

因此,以下代码将解析所有“.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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接