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

但是，多年来，我一直想知道是否有一种方法（有时认为不可能）在多个文件中搜索多个字符串

假设我有一百万个文件，我想回答诸如“查找包含字符串“香蕉”、“摩托艇”和“白狐”的文件”之类的查询。什么是有效的算法？有吗？

当然，可以根据要搜索的文件的大小以线性时间进行这样的搜索。但这对于大量大文件来说似乎非常不可行。 谷歌的存在似乎表明实际上有一种非常快的算法可以做到这一点。甚至可能是每个查询仅取决于查询大小，而不是文本大小的数据库（当然，这样的算法将涉及输入文件的一些预处理）

我认为一定有一种这样的算法（谷歌就是这样做的！）但我的搜索什么也没找到。

并行编程

这在大规模上绝对是并行编程的任务：将文件分发到不同的计算单元，让它们搜索，然后收集结果。这实际上就是谷歌所做的，例如他们通过组合数千台商用硬件电脑一次性解决了一些翻译问题。 （尽管他们可能使用其他硬件来获得真实的 Google 搜索结果。）您可以阅读热门文章在互联网上 http://www.zdnet.com/blog/emergingtech/googles-parallel-programming-model/803.

“MapReduce”作为一个概念

例如，谷歌发明了一个名为MapReduce，他们在白皮书中写下了 http://static.googleusercontent.com/media/research.google.com/de//archive/mapreduce-osdi04.pdf。这基本上可以归结为第一步将输入映射到输出（广泛分布）。然后在第二步中将所有小结果减少为一个主要结果。

人们可以这样实现搜索：

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

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

查明给定文本中是否存在给定字符串的问题已在“”这个名称下得到了很好的研究字符串匹配“，例如参见拉宾-卡普算法 https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm or the Knuth-Morris-Karp 算法 https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm （只是为了得到任何东西）。所以实施map相当容易。

对于文件的分发，可以使用许多不同的技术。如果想正确了解分布式文件系统的可能性，可以收集有关 Google 文件系统（GFS）的信息，例如在相应的白皮书中 http://static.googleusercontent.com/media/research.google.com/de//archive/gfs-sosp2003.pdf.

reduce几乎什么都不做，所以这真的很简单。

完成的。

这是 MapReduce 范式的最大优势：一旦理解了 Map 和 Reduce 如何组合成一个结果，实现这两个功能就相当容易了。如果之前实现了 MapReduce 框架，则完全不必担心计算的并行性，否则可能会导致严重的头痛。

其他概念

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

• 可能会因您使用的硬件而异（像 MapReduce 这样的独立 PC，或者它更像是具有数十个 CPU 的超级计算机）。
• 您使用的分布式（或非分布式）文件系统可能会有所不同。
• 改变编程语言是可能的，这也会产生巨大的差异。

如果你对这个研究领域感兴趣，你会发现很多其他的可能性，我相信在不久的将来还会出现更多的可能性，因为分布式系统比以往任何时候都出现得更多，但我希望我能提供一些关于什么是的见解。可能的，需要注意什么，甚至是如何立即实施这一点的方向。