# Changeset 4488 for docs/Working/icGrep/background.tex

Ignore:
Timestamp:
Feb 10, 2015, 12:17:27 PM (4 years ago)
Message:

Initial bitwise example, table placeholder

File:
1 edited

### Legend:

Unmodified
 r4472 \begin{figure} \begin{center} \begin{tabular}{cr}\\ input data  & \verbdead dreams defeated.\\ $M_1 = {\text{Advance}}({\text{\tt [d]}})$ & \verb.1..1.1......1......1\\ $M_2 = {\text{MatchStar}}(M_1, {\text{\tt [a-z]}})$ & \verb.1111.111111.11111111\\ $M_3 = {\text{Advance}}(M_2 \wedge {\text{\tt [e]}})$ & \verb..1.....1.....1.1..1.\\ $M_4 = {\text{Advance}}(M_3 \wedge {\text{\tt [d]}})$ & \verb....................1 \end{tabular} \end{center} \caption{Matching with Bitwise Data Parallelism}\label{fig:bitwisematch} \end{figure} The central concept in regular expression matching is that of marker bitstreams. At each step in the matching process, a marker bitstream indicates the matches that have been found to this point.   The bitwise matching method uses the operations Advance to move an entire stream of markers one step forward, and MatchStar to find all positions matched after a character class repetition. For example, Figure \ref{fig:bitwisematch} shows how the regular expression {\tt d[a-z]*ed} is matched against some input text using bitwise methods. In the first step the character class stream {\tt [d]} is matched and the results advanced one position to produce marker bitstream $M_1$.   Four match results are now in play simultaneously. The next step applies the MatchStar operation to find all the matches that may then be reached with the Kleene-* repetition {\tt [a-z]*} ($M_2$).  We now have pending matches at almost all possible positions.   However, most of the positions are filtered out with the match to {\tt [e]} in the computation of $M_3$. The final step produces marker stream $M_4$ indicating that single position at which the entire regular expression is matched. \comment{