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

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

恐怕断了弦也不行。

一般来说，早期转义很困难，所以最好将文本分成 block 。

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

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

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

现在，您想要的是将文本分成 k 个相等的 block ，其中 k 是最小的，size(chunk) 是最大但低于 max。

然后，我们有一个经典的 Producer-Consumer 模式:p 进程接收到文本 block ，每个进程在它接收到的 block 中寻找模式.

早期逃逸是通过有一个标志来完成的。您可以设置在其中找到模式(及其位置)的 block 的索引，或者您可以只设置一个 bool 值，并将结果存储在进程本身中(在这种情况下，您必须遍历所有进程一旦停止)。关键是，每次请求 block 时，生产者都会检查标志，如果找到匹配项，则停止向进程提供数据(因为进程已按顺序获得 block )。

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

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

block 6 和 8 都包含字符串。

producer会先把1、2、3喂给process，然后每个process会按照自己的节奏推进(取决于搜索到的文本和pattern的相似度)。

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

关键思想是你不想看整个文本!太浪费了!