首先-發生並行字符串匹配算法

爲了達到前面，這是功課。這就是說，它是非常開放的，我們甚至幾乎沒有指導如何開始思考這個問題（或者一般的並行算法）。我想在正確的方向和指針不是一個完整的解決方案。任何有助於閱讀的閱讀材料都會非常出色。首先-發生並行字符串匹配算法

我正在研究一種有效的方法，以使用並行算法在大量文本中匹配模式的第一次出現。該模式是簡單的字符匹配，不涉及正則表達式。我設法想出了一個找到所有的比賽的可能方式，但那需要我查看所有比賽並找到第一個。

所以問題是，我會有更多的成功打破進程之間的文本和掃描的方式？或者最好是在第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

首先-發生並行字符串匹配算法

回答

相關問題