首次出现并行字符串匹配算法

Question

坦白说，这是家庭作业。话虽这么说，它是极其开放的，并且对于如何开始思考这个问题（或一般的并行算法），我们的指导几乎为零。我想要正确方向的指针，但不是完整的解决方案。任何有帮助的读物也将是极好的。

我正在研究一种有效的方法，使用并行算法来匹配大量文本中模式的第一次出现。该模式是简单的字符匹配，不涉及正则表达式。我设法找到一种可能的方法来查找所有匹配项，但这需要我查看所有匹配项并找到第一个匹配项。

所以问题是，我能否更成功地在进程之间分解文本并以这种方式进行扫描？或者最好进行某种进程同步搜索，其中第 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++

Answer 1

给定长度为 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 个字符的方法将需要太多的进程间通信开销。

编辑：我意识到你已经有了一个解决方案，并且正在找出一种方法，而不必找到所有解决方案。嗯，我真的不认为这种方法是必要的。您可以想出一些早期的转义条件，它们并不那么困难，但我认为它们一般不会提高您的性能（除非您对文本中匹配的分布有一些额外的了解）。

Answer 2

恐怕断了弦也不行。

一般来说，早期转义是很困难的，所以你最好将文本分成几块。

但是，让我们首先请 Herb Sutter 在 Dr Dobbs 上解释使用并行算法进行搜索。这个想法是利用分布的不均匀性来获得早期回报。当然，萨特对任何比赛都感兴趣，这不是眼前的问题，所以让我们适应一下。

这是我的想法，假设我们有：

• 长度为 N
• p 的文本 处理器
• 启发式： max 是一个块应包含的最大字符数，可能比模式长度 M 大一个数量级。

现在，您想要的是将文本分割为 k 相等的块，其中 k 是最小的，而 size(chunk) 是最大但较差的至最大值。

然后，我们有一个经典的生产者-消费者模式：p 进程被提供文本块，每个进程在它接收到的块中查找模式。

早期的逃脱是通过旗帜来完成的。您可以设置在其中找到模式（及其位置）的块的索引，或者您可以仅设置一个布尔值，并将结果存储在进程本身中（在这种情况下，您必须遍历所有进程一旦停止）。要点是，每次请求一个块时，生产者都会检查该标志，如果发现匹配，则停止向进程提供数据（因为进程已按顺序获得了块）。

让我们举个例子，有 3 个处理器：

[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ]
                      x       x

块 6 和 8 都包含字符串。

生产者首先将 1、2 和 3 喂给进程，然后每个进程将按照自己的节奏前进（这取决于搜索到的文本和模式的相似度）。

假设我们先在 8 中找到该模式，然后再在 6 中找到该模式。然后正在处理 7 的进程结束并尝试获取另一个块，生产者停止它 -->这是无关紧要的。然后，6 上的处理结束，并产生结果，因此我们知道第一个出现在 6 中，并且我们知道了它的位置。

关键的想法是你不想看全文！太浪费了！