 Timestamp:
 May 14, 2015, 2:37:24 PM (4 years ago)
 Location:
 docs/Working/icGrep
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

docs/Working/icGrep/background.tex
r4506 r4553 49 49 simultaneously. A set of parallel bit streams is computed, with each bit 50 50 position corresponding to one codeunit position within input character stream. 51 Each bit stream may be considered an $L$bit integer, where $L$ is the length 52 of the input stream. 51 53 {\em Character class streams}, such as {\tt [d]} for the stream that marks the 52 54 position of ``d'' characters and {\tt [az]} for the stream of lower case … … 57 59 process a {\em marker} bit stream identifies the full set of positions 58 60 within the input data stream that match the regular expression to this point. 61 62 Consider the following simplified definition of regular expressions 63 A regular expression may be a character class $C$ or formed by 64 composition. If $R$ and $S$ are regular expressions, then the concatenation $RS$ is the regular 65 expression standing for the set of all strings formed by concatenating 66 one string from $R$ and one string from $S$, $RS$ is the alternation 67 standing for the union of the sets of strings from $R$ and $S$, and 68 $R*$ is the Kleenestar closure consists of the set of strings 69 formed from 0 or more occurrences of strings from $R$. 70 71 Bitwise data parallel search for substring occurrences matching a regular expression 72 $R$ proceeds as follows. We start with a marker stream $m_0$ consisting of all 73 ones, i.e., $m_0 = 2^{L}  1$. Matches are then computed according to the following 74 equations. 75 \begin{eqnarray*} 76 \mbox{\rm Match}(m, C) & = & \mbox{\rm Advance}(\mbox{\rm CharClass}(C) \wedge m) \\ 77 \mbox{\rm Match}(m, RS) & = & \mbox{\rm Match}(\mbox{\rm Match}(m, R), S) \\ 78 \mbox{\rm Match}(m, RS) & = & \mbox{\rm Match}(m, R) \vee \mbox{\rm Match}(m, S)) \\ 79 \mbox{\rm Match}(m, C*) & = & \mbox{\rm MatchStar}(m, \mbox{\rm CharClass}(C)) \\ 80 \mbox{\rm Match}(m, R*) & = & m \vee \mbox{\rm Match}(\mbox{\rm Match}(m, R) \wedge (\neg m), R*) 81 \end{eqnarray*} 59 82 60 83
Note: See TracChangeset
for help on using the changeset viewer.