9

率直に言って、これは宿題です。そうは言っても、それは非常にオープンエンドであり、この問題（または一般的な並列アルゴリズム）について考え始める方法についてのガイダンスはほとんどありません。完全な解決策ではなく、正しい方向へのポインタが欲しいのですが。役立つかもしれないどんな読書も同様に素晴らしいでしょう。

私は、並列アルゴリズムを使用して、大量のテキストで最初に出現するパターンを一致させる効率的な方法に取り組んでいます。パターンは単純な文字マッチングであり、正規表現は含まれていません。私はなんとかすべての一致を見つけるための可能な方法を思いついたが、それは私がすべての一致を調べて最初のものを見つけることを必要とする。

だから問題は、プロセス間でテキストを分割し、そのようにスキャンすることにもっと成功するでしょうか？または、j番目のプロセスがパターンのj番目の文字を検索する、ある種のプロセス同期検索を行うのが最善でしょうか？その後、すべてのプロセスが一致に対してtrueを返す場合、プロセスは上記のパターンに一致する位置を変更して再び上に移動し、すべての文字が一致するまで続行してから、最初の一致のインデックスを返します。

私がこれまでに持っているものは非常に基本的なものであり、おそらく機能しません。私はこれを実装しませんが、どんなポインタでもいただければ幸いです。

pプロセッサ、長さtのテキスト、長さLのパターン、および使用されるLプロセッサの上限の場合：

i = 0からtlの場合：
    j = 0からpの場合：
        プロセッサjは、text [i+j]をpattern[i+j]と比較します
            誤一致の場合：
                すべてのプロセッサが現在の比較を終了します、i ++
            すべてのプロセッサによる真の一致：
                L文字が比較されるまで、一度にp文字を繰り返します
                すべてのL比較がtrueを返す場合：
                    return i（パターンの位置）
                そうしないと：
                    i ++
4

2 に答える 2

5

ひもを壊してもうまくいかないのではないかと思います。

一般的に言って、早期のエスケープは難しいので、テキストをチャンクに分割したほうがよいでしょう。

しかし、最初にドブス博士で並列アルゴリズムを使用した検索について説明するようにハーブサッターに依頼しましょう。アイデアは、分布の不均一性を使用して早期にリターンを得るというものです。もちろん、Sutterはどんな試合にも興味がありますが、それは目前の問題ではないので、適応しましょう。

これが私の考えです、私たちが持っているとしましょう：

  • 長さのテキストN
  • pプロセッサー
  • ヒューリスティック：チャンクに含める必要のある文字の最大数であり、おそらくパターンの長maxさよりも1桁大きくなります。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-26T13:25:32.253 に答える
5

長さ L のパターンが与えられ、長さ N の文字列を P 個のプロセッサで検索すると、文字列を複数のプロセッサに分割するだけです。各プロセッサは長さ N/P + L-1 のチャンクを取り、最後の L-1 は次のプロセッサに属する文字列と重複します。次に、各プロセッサがボイヤームーアを実行します (2 つの前処理テーブルが共有されます)。それぞれが終了すると、テーブルを維持する最初のプロセッサに結果を返します。

Process Index
   1    -1
   2    2
   3    23

すべてのプロセスが応答した後 (または、少し考えれば早期に脱出できます)、最初の一致を返します。これは平均で O(N/(L*P) + P) になるはずです。

i 番目のプロセッサを i 番目の文字に一致させるアプローチでは、プロセス間通信のオーバーヘッドが大きくなりすぎます。

編集：あなたはすでに解決策を持っていることを認識しており、すべての解決策を見つける必要なく方法を考え出しています。まあ、私はこのアプローチが本当に必要だとは思わない。いくつかの初期のエスケープ条件を考え出すことができますが、それらはそれほど難しくありませんが、一般的にパフォーマンスがそれほど向上するとは思いません (テキスト内の一致の分布に関する追加の知識がない限り)。

于 2010-02-22T22:18:21.327 に答える