Frage Erstes Auftreten Parallel String Matching Algorithm


Um vorne zu sein, das ist Hausaufgaben. Abgesehen davon ist es extrem offen und wir hatten fast keine Anleitung, wie man überhaupt über dieses Problem (oder parallele Algorithmen im Allgemeinen) nachdenkt. Ich hätte gerne Hinweise in die richtige Richtung und keine vollständige Lösung. Jede Lesung, die helfen könnte, wäre auch hervorragend.

Ich arbeite an einer effizienten Möglichkeit, das erste Auftreten eines Musters in einer großen Menge von Text mit einem parallelen Algorithmus zu vergleichen. Das Muster ist ein einfacher Zeichenabgleich, kein Regex beteiligt. Es ist mir gelungen, einen möglichen Weg zu finden alle der Spiele, aber das erfordert dann, dass ich durch alle Spiele schaue und das erste finde.

Die Frage ist also, ob ich mehr Erfolg darin haben werde, den Text zwischen Prozessen zu trennen und so zu scannen? Oder wäre es am besten, eine prozesssynchrone Suche zu haben, bei der der j-te Prozess nach dem j-ten Charakter des Musters sucht? Wenn dann alle Prozesse true für ihre Übereinstimmung zurückgeben, würden die Prozesse ihre Position ändern, indem sie mit dem Muster übereinstimmen, und wieder aufwärts gehen, so lange fortfahren, bis alle Zeichen übereinstimmend sind, und dann den Index der ersten Übereinstimmung zurückgeben.

Was ich bisher habe, ist extrem einfach und funktioniert höchstwahrscheinlich nicht. Ich werde das nicht implementieren, aber alle Hinweise wären willkommen.

Bei p-Prozessoren werden ein Text der Länge t und ein Muster der Länge L und eine Obergrenze der verwendeten L-Prozessoren verwendet:

 für i = 0 bis t-1:
    für j = 0 bis p:
        Prozessor j vergleicht den Text [i + j] mit dem Muster [i + j]
            Bei falscher Übereinstimmung:
                Alle Prozessoren beenden den aktuellen Vergleich, i ++
            Bei True Match von allen Prozessoren:
                Wiederhole p Zeichen gleichzeitig, bis L Zeichen verglichen wurden
                Wenn alle L-Vergleiche wahr sind:
                    Rückgabe i (Position des Musters)
                Sonst:
                    i ++

7
2018-02-22 22:00


Ursprung


Antworten:


Ich fürchte, dass das Brechen der Saite nicht ausreichen wird.

Im Allgemeinen ist ein frühes Ausbrechen schwierig, daher sollten Sie den Text besser in Blöcken aufteilen.

Aber lassen Sie uns Herb Sutter bitten, das Suchen mit parallelen Algorithmen zuerst zu erklären Dr. Dobbs. Die Idee ist, die Ungleichförmigkeit der Verteilung zu verwenden, um eine frühe Rückkehr zu haben. Natürlich interessiert sich Sutter für jedes Match, das ist nicht das Problem, also passen wir uns an.

Hier ist meine Idee, sagen wir, wir haben:

  • Text der Länge N
  • p Prozessoren
  • Heuristik: max ist die maximale Anzahl von Zeichen, die ein Chunk enthalten sollte, wahrscheinlich eine Größenordnung größer als M die Länge des Musters.

Nun, was Sie wollen, ist Ihren Text zu teilen k gleiche Stücke, wo k ist minimal und size(chunk) ist maximal noch minderwertig max.

Dann haben wir eine klassische Producer-Consumer Muster: die p Prozesse werden mit den Textstücken gefüllt, wobei jeder Prozess nach dem Muster in dem Stück sucht, das er empfängt.

Die frühe Flucht wird getan, indem man eine Flagge hat. Sie können entweder den Index des Chunks festlegen, in dem Sie das Muster (und seine Position) gefunden haben, oder Sie können einfach einen Booleschen Wert festlegen und das Ergebnis in den Prozessen selbst speichern (in diesem Fall müssen Sie alle Prozesse, sobald sie aufhören). Der Punkt ist, dass jedes Mal, wenn ein Chunk angefordert wird, der Produzent das Flag prüft und die Prozesse nicht mehr einspeist, wenn eine Übereinstimmung gefunden wurde (da die Prozesse die Chunks der Reihe nach erhalten haben).

Nehmen wir ein Beispiel mit 3 Prozessoren:

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

Die Brocken 6 und 8 Beide enthalten die Zeichenfolge.

Der Produzent wird zuerst 1, 2 und 3 zu den Prozessen führen, dann wird jeder Prozess in seinem eigenen Rhythmus voranschreiten (es hängt von der Ähnlichkeit des gesuchten Textes und des Musters ab).

Nehmen wir an, wir finden das Muster in 8 bevor wir es finden 6. Dann der Prozess, an dem gearbeitet wurde 7 endet und versucht einen weiteren Brocken zu bekommen, der Produzent stoppt es -> es wäre irrelevant. Dann läuft der Prozess weiter 6 endet, mit einem Ergebnis, und so wissen wir, dass das erste Vorkommen war 6und wir haben seine Position.

Die Schlüsselidee ist, dass Sie nicht den ganzen Text betrachten wollen! Es ist verschwenderisch!


3
2018-02-26 13:25



Bei einem Muster der Länge L und einer Suche in einer Folge von Länge N über P-Prozessoren würde ich die Zeichenfolge einfach auf die Prozessoren aufteilen. Jeder Prozessor würde ein Stück der Länge N / P + L-1 nehmen, wobei das letzte L-1 die zum nächsten Prozessor gehörende Folge überlappt. Dann würde jeder Prozessor boyer moore ausführen (die zwei Vorverarbeitungstabellen würden geteilt werden). Wenn beide fertig sind, geben sie das Ergebnis an den ersten Prozessor zurück, der eine Tabelle verwaltet

Process Index
   1    -1
   2    2
   3    23

Nachdem alle Prozesse geantwortet haben (oder mit ein wenig Nachdenken können Sie schnell entkommen), geben Sie das erste Spiel zurück. Dies sollte im Durchschnitt O (N / (L * P) + P) sein.

Der Ansatz, den i-ten Prozessor mit dem i-ten Zeichen abzustimmen, würde zu viel Kommunikationsaufwand zwischen den Prozessen erfordern.

EDIT: Mir ist klar, dass Sie bereits eine Lösung haben und einen Weg finden, ohne alle Lösungen zu finden. Nun, ich glaube nicht, dass dieser Ansatz notwendig ist. Sie können sich einige frühe Escape-Bedingungen einfallen lassen, sie sind nicht so schwierig, aber ich denke nicht, dass sie Ihre Leistung im Allgemeinen so verbessern werden (es sei denn, Sie haben zusätzliche Kenntnisse über die Verteilung von Übereinstimmungen in Ihrem Text).


3
2018-02-22 22:18