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

Initial bitwise example, table placeholder

File:
1 edited

Legend:

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

    r4472 r4488  
    6767
    6868
     69\begin{figure}
     70\begin{center}
     71\begin{tabular}{cr}\\
     72input data  & \verb`dead dreams defeated.`\\
     73$M_1 = {\text{Advance}}({\text{\tt [d]}})$ & \verb`.1..1.1......1......1`\\
     74$M_2 = {\text{MatchStar}}(M_1, {\text{\tt [a-z]}})$ & \verb`.1111.111111.11111111`\\
     75$M_3 = {\text{Advance}}(M_2 \wedge {\text{\tt [e]}})$ & \verb`..1.....1.....1.1..1.`\\
     76$M_4 = {\text{Advance}}(M_3 \wedge {\text{\tt [d]}})$ & \verb`....................1`
     77\end{tabular}
     78\end{center}
     79\caption{Matching with Bitwise Data Parallelism}\label{fig:bitwisematch}
     80\end{figure}
     81
     82
     83The central concept in regular expression matching is that of marker bitstreams.
     84At each step in the matching process, a marker bitstream indicates the matches
     85that have been found to this point.   The bitwise matching method uses the
     86operations Advance to move an entire stream of markers one step forward, and MatchStar
     87to find all positions matched after a character class repetition.
     88For example,
     89Figure \ref{fig:bitwisematch} shows how the regular expression {\tt d[a-z]*ed} is matched
     90against some input text using bitwise methods. 
     91In the first step the character class stream
     92{\tt [d]} is matched and the results advanced one position to produce marker bitstream $M_1$.   Four match results are now in play
     93simultaneously. 
     94The next step applies the
     95MatchStar operation to find all the matches that may then be reached with the Kleene-* repetition
     96{\tt [a-z]*} ($M_2$).  We now have pending matches at almost all possible positions.   However, most of
     97the positions are filtered out with the match to {\tt [e]} in the computation of $M_3$.
     98The final step produces marker stream $M_4$ indicating that single position at which the entire regular expression is matched.
     99
     100
     101
    69102\comment{
    70103
Note: See TracChangeset for help on using the changeset viewer.