Pierwsza Występowanie Parallel String Matching Algorithm

Question

być na przód, to jest praca domowa. To powiedziawszy, jest bardzo otwarty i prawie nie mamy wskazówek, jak zacząć myśleć o tym problemie (lub ogólnie o algorytmach równoległych). Chciałbym wskaźników we właściwym kierunku i nie jest pełnym rozwiązaniem. Każde czytanie, które mogłoby pomóc, byłoby również doskonałe.

pracuję na skuteczny sposób, aby dopasować pierwsze wystąpienie wzorca w dużej ilości tekstu przy użyciu algorytmu równoległego. Wzorzec jest prostym dopasowaniem znaków, nie ma w tym przypadku wyrażenia regularnego. Udało mi się wymyślić możliwy sposób znalezienia wszystkich z meczów, ale to wymaga ode mnie sprawdzenia wszystkich meczów i znalezienia pierwszego.

Więc pytanie brzmi, będę miał więcej sukcesów łamanie tekstu między procesami i skanowanie w ten sposób? A może najlepiej byłoby przeprowadzić zsynchronizowane z procesem wyszukiwania, w którym j'th proces szuka j'th znaku wzorca? Jeśli wtedy wszystkie procesy zwrócą wartość true dla ich dopasowania, procesy zmieniłyby swoją pozycję w dopasowaniu wspomnianego wzorca i ponownie ruszyłyby w górę, kontynuując dopóki wszystkie znaki nie zostaną dopasowane, a następnie zwracając indeks pierwszego dopasowania.

To, co do tej pory miałem, jest bardzo proste i najprawdopodobniej nie działa. Nie będę tego realizował, ale wszelkie wskazówki będą mile widziane.

procesory P, tekście długość T, i wzór o długości L, a sufit procesorów L używany:

 
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

Obawiam się, że przerwanie łańcucha nie nastąpi.

Ogólnie rzecz biorąc, na początku wyciek jest trudne, tak by być lepiej łamanie tekstu w kawałkach.

Ale zapytajmy Herb Sutter, aby wyjaśnił wyszukiwanie algorytmów równoległych najpierw na Dr Dobbs. Chodzi o to, aby nierównomierność dystrybucji zapewnić szybki powrót. Oczywiście Sutter jest zainteresowany każdym meczem, co nie jest problemem, więc dostosujmy się.

Oto mój pomysł, powiedzmy mamy:

• Tekst o długości N
• p Procesory
• heurystyczny: max jest maksymalna liczba znaków klocek powinien zawierać, prawdopodobnie o rząd wielkość większa niż M długość wzoru.

Teraz to, co chcesz podzielić tekst na k równych kawałków, gdzie k jest minimalna i maksymalna size(chunk) jest jeszcze gorsze max.

Następnie mamy klasyczny wzór Producer-Consumer: procesy p są podawane z kawałkami tekstu, każdy proces szuka wzoru w otrzymanej porcji.

Wczesna ucieczka polega na posiadaniu flagi. Możesz albo ustawić indeks porcji, w której znalazłeś wzorzec (i jego położenie), albo możesz po prostu ustawić wartość logiczną i zapisać wynik w samych procesach (w takim przypadku będziesz musiał przejść przez wszystkie procesy po ich zatrzymaniu). Chodzi o to, że za każdym razem, gdy żąda się kawałka, producent sprawdza flagę i przestaje podawać procesy, jeśli znaleziono dopasowanie (ponieważ procesy otrzymały porcje w kolejności).

Rzućmy przykład, z 3 procesory:

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

Kawałki 6 i 8 oba zawierają ciąg.

Producent najpierw wprowadzi 1, 2 i 3 do procesów, następnie każdy proces będzie postępował we własnym rytmie (zależy to od podobieństwa wyszukiwanego tekstu i wzorca).

Załóżmy, że znaleźliśmy wzór w 8, zanim znajdziemy go w 6. Następnie proces, który działał na 7 kończy się i próbuje zdobyć kolejną porcję, producent zatrzymuje to -> byłoby to nieistotne. Następnie proces pracujący nad 6 kończy się wynikiem, a tym samym wiemy, że pierwsze wystąpienie było w 6, a my mamy jego położenie.

Kluczową ideą jest to, że nie chcesz patrzeć na cały tekst! To marnotrawstwo!

Answer 2

Biorąc pod uwagę wzór o długości L, a wyszukiwanie w ciągu długości N nad procesorami P Chciałbym po prostu podzielić ciąg na procesory. Każdy procesor miałby fragment długości N/P + L-1, a ostatni L-1 nakładałby się na ciąg należący do następnego procesora. Następnie każdy procesor wykona boyer moore (dwie tablice przetwarzania wstępnego zostaną udostępnione). Kiedy każdy kończy, wrócą wynik do pierwszego przetwórcy, który utrzymuje tablicę

Process Index 
    1 -1 
    2 2 
    3 23 

Po odpowiedziały wszystkie procesy (lub z odrobiną myślenia można mieć wczesną ucieczkę), wrócisz pierwszy mecz . Powinno to być średnio O (N/(L * P) + P).

Podejście mające i'th procesor odpowiadający i'th postać wymagałoby zbyt między obciążenie komunikacji procesu.

EDIT: Zdaję sobie sprawę, masz już rozwiązanie, i zastanawianie się sposób, bez konieczności, aby znaleźć wszystkie rozwiązania. Cóż, nie sądzę, że takie podejście jest konieczne. Możesz wymyślić kilka wczesnych warunków ucieczki, nie są one takie trudne, ale nie sądzę, że poprawią one twoją wydajność w ogóle (chyba że masz dodatkową wiedzę na temat rozkładu meczów w tekście).