First-Occurrence Parallel String Matching Algorithm

Question

To be up front, this is homework. That being said, it's extremely open ended and we've had almost zero guidance as to how to even begin thinking about this problem (or parallel algorithms in general). I'd like pointers in the right direction and not a full solution. Any reading that could help would be excellent as well.

I'm working on an efficient way to match the first occurrence of a pattern in a large amount of text using a parallel algorithm. The pattern is simple character matching, no regex involved. I've managed to come up with a possible way of finding all of the matches, but that then requires that I look through all of the matches and find the first one.

So the question is, will I have more success breaking the text up between processes and scanning that way? Or would it be best to have process-synchronized searching of some sort where the j'th process searches for the j'th character of the pattern? If then all processes return true for their match, the processes would change their position in matching said pattern and move up again, continuing until all characters have been matched and then returning the index of the first match.

What I have so far is extremely basic, and more than likely does not work. I won't be implementing this, but any pointers would be appreciated.

With p processors, a text of length t, and a pattern of length L, and a ceiling of L processors used:

 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

Given a pattern of length L, and searching in a string of length N over P processors I would just split the string over the processors. Each processor would take a chunk of length N/P + L-1, with the last L-1 overlapping the string belonging to the next processor. Then each processor would perform boyer moore (the two pre-processing tables would be shared). When each finishes, they will return the result to the first processor, which maintains a table

Process Index
   1    -1
   2    2
   3    23

After all processes have responded (or with a bit of thought you can have an early escape), you return the first match. This should be on average O(N/(L*P) + P).

The approach of having the i'th processor matching the i'th character would require too much inter process communication overhead.

EDIT: I realize you already have a solution, and are figuring out a way without having to find all solutions. Well I don't really think this approach is necessary. You can come up with some early escape conditions, they aren't that difficult, but I don't think they'll improve your performance that much in general (unless you have some additional knowledge the distribution of matches in your text).

Answer 2

I am afraid that breaking the string will not do.

Generally speaking, early escaping is difficult, so you'd be better off breaking the text in chunks.

But let's ask Herb Sutter to explain searching with parallel algorithms first on Dr Dobbs. The idea is to use the non-uniformity of the distribution to have an early return. Of course Sutter is interested in any match, which is not the problem at hand, so let's adapt.

Here is my idea, let's say we have:

• Text of length N
• p Processors
• heuristic: max is the maximum number of characters a chunk should contain, probably an order of magnitude greater than M the length of the pattern.

Now, what you want is to split your text into k equal chunks, where k is is minimal and size(chunk) is maximal yet inferior to max.

Then, we have a classical Producer-Consumer pattern: the p processes are feeded with the chunks of text, each process looking for the pattern in the chunk it receives.

The early escape is done by having a flag. You can either set the index of the chunk in which you found the pattern (and its position), or you can just set a boolean, and store the result in the processes themselves (in which case you'll have to go through all the processes once they have stop). The point is that each time a chunk is requested, the producer checks the flag, and stop feeding the processes if a match has been found (since the processes have been given the chunks in order).

Let's have an example, with 3 processors:

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

The chunks 6 and 8 both contain the string.

The producer will first feed 1, 2 and 3 to the processes, then each process will advance at its own rhythm (it depends on the similarity of the text searched and the pattern).

Let's say we find the pattern in 8 before we find it in 6. Then the process that was working on 7 ends and tries to get another chunk, the producer stops it --> it would be irrelevant. Then the process working on 6 ends, with a result, and thus we know that the first occurrence was in 6, and we have its position.

The key idea is that you don't want to look at the whole text! It's wasteful!