algorithm – 搜索多个字符串

概述我知道在文件中查找一个字符串的有效方法(kmp),或文件中的各种字符串(trie) 但是,多年以来,我一直想知道是否有一种方法(并且在某种程度上认为这是不可能的)来搜索多个文件的多个字符串 假设我有一百万个文件,我想回答诸如“查找具有字符串”香蕉“,”摩托艇“和”白狐“”的查询.什么是有效的算法？有吗？ 当然,可以在线性时间内搜索要搜索的文件大小.但对于大量的大文件来说,这似乎是不可行的. 谷歌的 我知道在文件中查找一个字符串的有效方法(kmp),或文件中的各种字符串(trIE)

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

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

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

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

解决方法 并行编程

这在很大程度上肯定是并行编程的任务：将文件分发到不同的计算单元,让它们进行搜索,然后收集结果.这实际上是谷歌所做的,例如他们通过结合千种商用硬件PC解决了一些翻译问题. (虽然他们可能正在使用其他硬件来获取真正的Google搜索结果.)您可以阅读热门文章on the internet.

“MapReduce”作为一个概念

谷歌发明了一个名为MapReduce,which they wrote down in a whitepaper的范例.这基本上归结为在第一步中将输入映射到输出(广泛分布).然后在第二步中将所有小结果减少为一个主要结果.

可以像这样实现搜索：

> map：将文档与关键字一起分发以进行搜索.如果在当前文件中找到搜索词,则从计算节点返回文件名.否则什么都不返回
> reduce：从所有节点收集列表中的所有文件名.

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

找出给定文本中是否存在给定字符串的问题在名称“字符串匹配”下进行了很好的研究,例如参见the Rabin-Karp algorithm或Knuth-Morris-Karp algorithm(只是为了得到任何东西).所以地图的实现相当容易.

对于文件的分发,可以使用许多不同的技术.如果想要了解分布式文件系统的可能性,可以收集有关Google文件系统(GFS)的信息,e.g. in the corresponding whitepaper.

减少几乎什么都不做,所以这很容易.

成品.

这是MapReduce范例的最佳优势：一旦理解了map和reduce如何结合到一个结果,就可以很容易地实现这两个功能.如果之前实现了MapReduce框架,则不必担心计算的并行性 – 否则会导致严重的问题.

其他概念

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

>可以根据您使用的硬件而变化(像MapReduce这样的独立PC,或者它更像是一台拥有数十个cpu的超级计算机).
>可以根据您使用的分布式(或非分布式)文件系统而有所不同.
>可以改变编程语言,这也可以产生巨大的差异.

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

总结

以上是内存溢出为你收集整理的algorithm – 搜索多个字符串全部内容，希望文章能够帮你解决algorithm – 搜索多个字符串所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。