首先-发生并行字符串匹配算法

为了达到前面，这是功课。这就是说，它是非常开放的，我们甚至几乎没有指导如何开始思考这个问题（或者一般的并行算法）。我想在正确的方向和指针不是一个完整的解决方案。任何有助于阅读的阅读材料都会非常出色。首先-发生并行字符串匹配算法

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

所以问题是，我会有更多的成功打破进程之间的文本和扫描的方式？或者最好是在第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++

来源

2010-02-22 Xorlev

与您提出的算法的问题是，有*方式*处理器之间的通信开销太多。除非模式非常长，否则让每个处理器在特定点处寻找匹配并在最早匹配时终止会更好。 – 2010-02-22 22:09:42

是否指定了PRAM模型？或者你可以承担任何？ L处理器的限制是由你还是问题？ – 2010-02-22 23:02:15

L处理器限制由我指定。我假设内存不共享，因为这是使用MPI的借口。 – Xorlev 2010-02-22 23:10:44

恐怕打破字符串不会。

一般来说，早期逃脱是困难的，所以你最好大块地打破文本。

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

这里是我的想法，让我们说我们有：长

文本N
p处理器
启发：max是块应该包含的最大字符数，大概的顺序幅度大于M模式的长度。

现在，你想要的是你的文字分成k相等的块，其中k是微乎其微，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，我们有它的位置。

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

来源

2010-02-26 13:25:32

+1非常棒的答案。这项任务早已转入，但我很想看看这可以如何工作。我倾向于在几周内过度乐趣和有趣的问题。 :)我确实希望其他人发现这个答案也是有用的，因为它是我见过的最清晰的答案之一。 – Xorlev 2010-02-26 18:33:58

给定长度L的图案，和在长度的串搜索N P处理器我只是将字符串分割处理器。每个处理器将占用一个长度为N/P + L-1的块，最后一个L-1与属于下一个处理器的字符串重叠。然后每个处理器将执行Boyer moore（两个预处理表将被共享）。当每完成，他们将结果返回到第一处理器，其维护一个表

Process Index 
    1 -1 
    2 2 
    3 23

后所有进程已作出回应（或有位的思想，你可以有一个早期退出），返回的第一个匹配。这应该平均为O（N /（L * P）+ P）。

使第i个处理器匹配第i个字符的方法需要太多的进程间通信开销。

编辑：我意识到你已经有一个解决方案，并找出一种方式，而不必找到所有的解决方案。那么我并不认为这种做法是必要的。你可以想出一些早期的逃生条件，但并不那么困难，但我认为他们一般不会提高你的表现（除非你有一些额外的知识来分配你的文本中的匹配）。

来源

2010-02-22 22:18:21

首先-发生并行字符串匹配算法

回答

相关问题