Changeset 4553 for docs


Ignore:
Timestamp:
May 14, 2015, 2:37:24 PM (4 years ago)
Author:
cameron
Message:

matching equations

Location:
docs/Working/icGrep
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/icGrep/background.tex

    r4506 r4553  
    4949simultaneously.   A set of parallel bit streams is computed, with each bit
    5050position corresponding to one code-unit position within input character stream.
     51Each bit stream may be considered an $L$-bit integer, where $L$ is the length
     52of the input stream.
    5153{\em Character class streams}, such as {\tt [d]} for the stream that marks the
    5254position of ``d'' characters and {\tt [a-z]} for the stream of lower case
     
    5759process a {\em marker} bit stream identifies the full set of positions
    5860within the input data stream that match the regular expression to this point.
     61
     62Consider the following simplified definition of regular expressions
     63A regular expression may be a character class $C$ or formed by
     64composition.  If $R$ and $S$ are regular expressions, then the concatenation $RS$ is the regular
     65expression standing for the set of all strings formed by concatenating
     66one string from $R$ and one string from $S$, $R|S$ is the alternation
     67standing for the union of the sets of strings from $R$ and $S$, and
     68$R*$ is the Kleene-star closure consists of the set of strings
     69formed from 0 or more occurrences of strings from $R$.
     70
     71Bitwise 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
     73ones, i.e., $m_0 = 2^{L} - 1$. Matches are then computed according to the following
     74equations.
     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, R|S) & = &  \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*}
    5982
    6083
Note: See TracChangeset for help on using the changeset viewer.