Xor*_*lev 8 language-agnostic algorithm parallel-processing string-matching
要预先,这是功课.话虽如此,它是非常开放的,我们几乎没有关于如何开始考虑这个问题(或一般的并行算法)的指导.我想指向正确的方向,而不是完整的解决方案.任何可能有帮助的阅读都会很好.
我正在研究一种有效的方法,使用并行算法匹配大量文本中第一次出现的模式.模式是简单的字符匹配,不涉及正则表达式.我已经设法找到了找到所有比赛的可能方法,但那要求我查看所有比赛并找到第一个比赛.
所以问题是,我是否会在流程和扫描方式之间取得更多成功？或者最好是进行某种类型的进程同步搜索,其中第j个进程搜索模式的第j个字符？如果所有进程都为其匹配返回true,则进程将改变它们在匹配所述模式中的位置并再次向上移动,继续直到所有字符都已匹配,然后返回第一个匹配的索引.
到目前为止我所拥有的是非常基本的,而且很可能不起作用.我不会实现这一点,但任何指针都将不胜感激.
使用p个处理器,长度为t的文本,长度为L的模式,以及使用的L个处理器的上限:
for i=0 to t-l:
for j=0 to p:
processor j compares the text[i+j] to pattern[i+j]
On false match:
all processors terminate current comparison, i++
On true match by all processors:
Iterate p characters at a time until L characters have been compared
If all L comparisons return true:
return i (position of pattern)
Else:
i++
给定长度为 L 的模式，并在 P 个处理器上搜索长度为 N 的字符串，我只会将字符串拆分到处理器上。每个处理器将采用长度为 N/P + L-1 的块，最后的 L-1 与属于下一个处理器的字符串重叠。然后每个处理器将执行boyer moore（两个预处理表将共享）。当每个完成时，他们将结果返回给第一个处理器，它维护一个表
Process Index
1 -1
2 2
3 23
在所有进程都响应之后（或者稍微考虑一下您可以提前逃逸），您返回第一个匹配项。这应该平均为 O(N/(L*P) + P)。
让第 i 个处理器匹配第 i 个字符的方法需要太多的进程间通信开销。
编辑：我意识到您已经有了解决方案，并且正在寻找一种无需找到所有解决方案的方法。好吧，我真的不认为这种方法是必要的。你可以想出一些早期的转义条件，它们并不难，但我认为它们一般不会提高你的表现（除非你对文本中匹配的分布有一些额外的了解）。
恐怕断了弦不行。
一般来说，早期转义很困难，因此最好将文本分成几部分。
但是让我们先请 Herb Sutter 在Dr Dobbs上解释使用并行算法进行搜索。这个想法是利用分布的非均匀性来获得早期回报。当然萨特对任何比赛都感兴趣，这不是手头的问题，所以让我们适应一下。
这是我的想法，假设我们有：
Np 处理器max是一个块应该包含的最大字符数，可能比M模式的长度大一个数量级。现在，您想要的是将您的文本分成k相等的块，其中kis 最小且size(chunk)最大但低于max.
然后，我们有一个经典Producer-Consumer模式：p进程被输入文本块，每个进程在它接收的块中寻找模式。
早期逃生是通过有一面旗帜来完成的。您可以设置在其中找到模式的块的索引（及其位置），或者您可以只设置一个布尔值，并将结果存储在进程本身中（在这种情况下，您必须经历所有进程一旦停止）。关键是每次请求块时，生产者都会检查标志，如果找到匹配项，则停止提供进程（因为进程已按顺序获得块）。
让我们举个例子，有 3 个处理器：
[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ]
x x
块6和8都包含字符串。
生产者首先将 1、2 和 3 喂给进程，然后每个进程将按照自己的节奏推进（这取决于搜索的文本和模式的相似性）。
假设我们8先在 中找到模式，然后再在 中找到它6。然后正在处理的进程7结束并尝试获取另一个块，生产者停止它 --> 这将无关紧要。然后处理的过程6结束，结果，因此我们知道第一次出现在6，我们有它的位置。
关键是你不想看整个文本！太浪费了！