Changeset 3135 for docs


Ignore:
Timestamp:
May 13, 2013, 3:20:24 PM (6 years ago)
Author:
ksherdy
Message:

Minor edit.

Location:
docs/Working/re
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/re-main.tex

    r3126 r3135  
    8888when a partially successful search path fails.
    8989
    90        
    9190The remainder of this paper is organized as follows.
    92 
    9391Section~\ref{Background} presents background material on classic
    9492regular expression pattern matching techniques and provides insight into the
    95 efficiency of traditional regular expression software tools.
    96 
    97 Section~\ref{Parallel Bitwise Data Streams} describes out data parallel
     93efficiency of traditional regular expression software tools. Next,
     94Section~\ref{Data Parallel Bitstreams} describes our data parallel
    9895regular expression matching techniques.
    99 
    10096Section~\ref{Compiler Technology}
    101 
    10297Section~\ref{Methodology} describes the evaluation framework and Section~\ref{Experimental Results}
    10398presents a detailed performance analysis of our data parallel bitstream techniques against
    10499Gnu grep, agrep, and nr-grep.
    105 
    106100Section~\ref{Conclusion} concludes the paper.
    107101
     
    127121regular expression implementations that construct automata for pattern matching.
    128122
    129 The traditional technique [16] to search a regular expression of length m in
    130 a text of length n is to first convert the expression into a non-deterministic
    131 automaton (NFA) with O(m) nodes. It is possible to search the text using the
    132 NFA directly in O(mn) worst case time. The cost comes from the fact that
    133 more than one state of the NFA may be active at each step, and therefore all
    134 may need to be updated. A more effcient choice is to convert the NFA into a
    135 DFA. A DFA has only a single active state and allows to search the text at
    136 O(n) worst-case optimal. The problem with this approach is that the DFA
    137 may have O($2^m$) states.
    138 
    139 In general, the general process is first to build a
    140 NFA from the regular expression and simulate the NFA on text input,
    141 or alternatively to convert the NFA into a
    142 DFA, optionally minimize the number of states in the DFA,
    143 and finally simulate the DFA on text input.
     123Following Thompson's approach, a regular expression of length m is first converted
     124to an NFA with O(m) nodes. It is possible to search a text of length n using the
     125NFA directly in O(mn) worst case time. Alternatively, a more effcient choice
     126is to convert the NFA into a DFA. A DFA has only a single active state and
     127allows to search the text at O(n) worst-case optimal. It is well known that the
     128conversion of the NFA to the DFA may result in the state explosion problem.
     129That is the resultant DFA may have O($2^m$) states.
    144130
    145131\section{Parallel Bitwise Data Streams}
  • docs/Working/re/re-main.tex.backup

    r3126 r3135  
    22\usepackage[utf8]{inputenc}
    33
    4 \def \Bitstream{Bit Stream}
    5 \def \bitstream{bit stream}
    6 
    74%opening
    8 \title{Fast Regular Expression Matching using Parallel \Bitstream{}s}
     5\title{Fast Regular Expression Matching using Parallel Bitstreams}
    96\author{
    107{Robert D. Cameron} \\
     
    2926
    3027The method is based on the concept of parallel
    31 \bitstream{} technology, in which parallel streams of bits are formed such
     28bitstream technology, in which parallel streams of bits are formed such
    3229that each stream comprises bits in one-to-one correspondence with the
    3330character code units of a source data stream.
     
    9188when a partially successful search path fails.
    9289
    93        
    9490The remainder of this paper is organized as follows.
    95 
    9691Section~\ref{Background} presents background material on classic
    9792regular expression pattern matching techniques and provides insight into the
    98 efficiency of traditional regular expression software tools.
    99 
    100 Section~\ref{Bitwise Parallel Data Streams} describes out data parallel
     93efficiency of traditional regular expression software tools. Next,
     94Section~\ref{Data Parallel Bitstreams} describes our data parallel
    10195regular expression matching techniques.
    102 
    10396Section~\ref{Compiler Technology}
    104 
    10597Section~\ref{Methodology} describes the evaluation framework and Section~\ref{Experimental Results}
    106 presents a detailed performance analysis of our data parallel \bitstream{} techniques against
     98presents a detailed performance analysis of our data parallel bitstream techniques against
    10799Gnu grep, agrep, and nr-grep.
    108 
    109 Section~\ref{conclusion} concludes the paper.
     100Section~\ref{Conclusion} concludes the paper.
    110101
    111102\section{Background}
     
    130121regular expression implementations that construct automata for pattern matching.
    131122
    132 The traditional technique [16] to search a regular expression of length m in
    133 a text of length n is to first convert the expression into a non-deterministic
    134 automaton (NFA) with O(m) nodes. It is possible to search the text using the
    135 NFA directly in O(mn) worst case time. The cost comes from the fact that
    136 more than one state of the NFA may be active at each step, and therefore all
    137 may need to be updated. A more effcient choice is to convert the NFA into a
    138 DFA. A DFA has only a single active state and allows to search the text at
    139 O(n) worst-case optimal. The problem with this approach is that the DFA
    140 may have O(2^m) states.
    141 
    142 In general, the general process is first to build a
    143 NFA from the regular expression and simulate the NFA on text input,
    144 or alternatively to convert the NFA into a
    145 DFA, optionally minimize the number of states in the DFA,
    146 and finally simulate the DFA on text input.
    147 
     123Following Thompson's approach, a regular expression of length m is first converted
     124to an NFA with O(m) nodes. It is possible to search a text of length n using the
     125NFA directly in O(mn) worst case time. Alternatively, a more effcient choice
     126is to convert the NFA into a DFA. A DFA has only a single active state and
     127allows to search the text at O(n) worst-case optimal. The problem with this
     128approach is that the DFA may have O($2^m$) states.
    148129
    149130
    150131\section{Parallel Bitwise Data Streams}
    151132\label{Parallel Bitwise Data Streams}
    152 
    153133
    154134\section{Compiler Technology}
     
    177157
    178158\section{Experimental Results}
    179 \label{results}
     159\label{Experimental Results}
    180160%\input{results.tex}
    181161
    182 \section{Conclusion and Future Work}
    183 \label{conclusion}
     162\section{Conclusion}
     163\label{Conclusion}
    184164%\input{conclusion.tex}
    185165
Note: See TracChangeset for help on using the changeset viewer.