Method and Apparatus for Regular Expression Processing with Parallel Bit Streams

摘要

One embodiment of the present invention is a method for increasing the speed of a computer in identifying occurrences of strings in a character stream that match a string pattern involving repetitions of characters of a particular character class. The method uses a parallel bit stream processing module of the computer, which processing module includes a processor equipped with parallel processing instructions, to form a plurality of parallel property bit streams Pj.

主权项

1. A method for increasing the speed of a computer in identifying occurrences of strings in a character stream that match a string pattern involving repetitions of characters of a particular character class, the method comprises:
in a parallel bit stream processing module of the computer, which processing module includes a processor equipped with parallel processing instructions, in response to the character stream, using the parallel processing instructions to form a plurality of parallel property bit streams Pj wherein each of the parallel property bit streams consists of a stream of bit values Pj(i) such that Pj(i) is a property associated with code unit C(i) of the character stream and each parallel processing instruction produces a plurality of bit values Pj (i), and segments the parallel property bit streams into blocks, each block consisting of bit values Pj (i) at a multiplicity of positions i; operating on the blocks with bitwise logic operations and/or shifting operations to form a character class bit stream to identify positions in the character stream that have members of the particular character class; obtaining a cursor bit stream identifying starting positions for simultaneous string matches; adding the cursor bit stream to the character class bit stream to produce a temporary bitstream; and applying bitwise logic to the temporary bit stream and the character class bit stream to produce an output cursor stream whose one bits exclusively identify the end points following each string match.