Changeset 3123

Timestamp:

May 9, 2013, 5:26:33 PM (6 years ago)

Author:

ksherdy

Message:

Check-in rough notes only.

Location:

docs/Working/re

Files:

• re-main.aux (modified) (1 diff)
• re-main.bbl (added)
• re-main.blg (added)
• re-main.log (modified) (2 diffs)
• re-main.pdf (modified) (previous)
• re-main.tex (modified) (4 diffs)
• re-main.tex.backup (added)
• reference.bib (added)

docs/Working/re/re-main.aux

@@ -1 +1 @@
 \relax 
+\citation{aho2007}
 \@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
 \newlabel{Introduction}{{1}{1}}
-\@writefile{toc}{\contentsline {section}{\numberline {2}Background}{1}}
-\newlabel{Background}{{2}{1}}
-\@writefile{toc}{\contentsline {section}{\numberline {3}Methodology}{1}}
-\newlabel{Methodology}{{3}{1}}
-\@writefile{toc}{\contentsline {section}{\numberline {4}Experimental Results}{1}}
-\newlabel{results}{{4}{1}}
-\@writefile{toc}{\contentsline {section}{\numberline {5}Conclusion and Future Work}{1}}
-\newlabel{conclusion}{{5}{1}}
+\citation{kleene1951representation}
+\bibstyle{acm}
+\bibdata{reference}
+\bibcite{aho2007}{1}
+\bibcite{kleene1951representation}{2}
+\@writefile{toc}{\contentsline {section}{\numberline {2}Background}{2}}
+\newlabel{Background}{{2}{2}}
+\@writefile{toc}{\contentsline {section}{\numberline {3}Methodology}{2}}
+\newlabel{Methodology}{{3}{2}}
+\@writefile{toc}{\contentsline {section}{\numberline {4}Experimental Results}{2}}
+\newlabel{results}{{4}{2}}
+\@writefile{toc}{\contentsline {section}{\numberline {5}Conclusion and Future Work}{2}}
+\newlabel{conclusion}{{5}{2}}

docs/Working/re/re-main.log

@@ -1 @@
-This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian) (format=pdflatex 2012.10.7)  7 MAY 2013 18:03
+This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian) (format=pdflatex 2012.10.7)  9 MAY 2013 16:27
 entering extended mode
  %&-line parsing enabled.
@@ -249 +249 @@
 \openout1 = `re-main.aux'.
 
-LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 17.
-LaTeX Font Info:    ... okay on input line 17.
-LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 17.
-LaTeX Font Info:    ... okay on input line 17.
-LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 17.
-LaTeX Font Info:    ... okay on input line 17.
-LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 17.
-LaTeX Font Info:    ... okay on input line 17.
-LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 17.
-LaTeX Font Info:    ... okay on input line 17.
-LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 17.
-LaTeX Font Info:    ... okay on input line 17.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <12> on input line 20.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <8> on input line 20.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <6> on input line 20.
+LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 20.
+LaTeX Font Info:    ... okay on input line 20.
+LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 20.
+LaTeX Font Info:    ... okay on input line 20.
+LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 20.
+LaTeX Font Info:    ... okay on input line 20.
+LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 20.
+LaTeX Font Info:    ... okay on input line 20.
+LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 20.
+LaTeX Font Info:    ... okay on input line 20.
+LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 20.
+LaTeX Font Info:    ... okay on input line 20.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <12> on input line 23.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <8> on input line 23.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <6> on input line 23.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <7> on input line 47.
+LaTeX Font Info:    External font `cmex10' loaded for size
+(Font)              <5> on input line 47.
  [1
 
-{/var/lib/texmf/fonts/map/pdftex/updmap/pdftex.map}] (./re-main.aux) ) 
+{/var/lib/texmf/fonts/map/pdftex/updmap/pdftex.map}] (./re-main.bbl) [2]
+(./re-main.aux) ) 
 Here is how much of TeX's memory you used:
- 442 strings out of 493848
- 4315 string characters out of 1152823
- 52050 words of memory out of 3000000
- 3776 multiletter control sequences out of 15000+50000
- 7887 words of font info for 28 fonts, out of 3000000 for 9000
+ 455 strings out of 493848
+ 4467 string characters out of 1152823
+ 54050 words of memory out of 3000000
+ 3784 multiletter control sequences out of 15000+50000
+ 8534 words of font info for 30 fonts, out of 3000000 for 9000
  714 hyphenation exceptions out of 8191
  23i,6n,19p,165b,199s stack positions out of 5000i,500n,10000p,200000b,50000s
-</usr/sha
-re/texmf-texlive/fonts/type1/public/amsfonts/cm/cmbx12.pfb></usr/share/texmf-te
-xlive/fonts/type1/public/amsfonts/cm/cmbx9.pfb></usr/share/texmf-texlive/fonts/
-type1/public/amsfonts/cm/cmr10.pfb></usr/share/texmf-texlive/fonts/type1/public
-/amsfonts/cm/cmr12.pfb></usr/share/texmf-texlive/fonts/type1/public/amsfonts/cm
-/cmr17.pfb>
-Output written on re-main.pdf (1 page, 57666 bytes).
+</usr/share/texmf-texlive/fonts/type1/public/amsfonts/cm/cmbx1
+2.pfb></usr/share/texmf-texlive/fonts/type1/public/amsfonts/cm/cmbx9.pfb></usr/
+share/texmf-texlive/fonts/type1/public/amsfonts/cm/cmcsc10.pfb></usr/share/texm
+f-texlive/fonts/type1/public/amsfonts/cm/cmmi7.pfb></usr/share/texmf-texlive/fo
+nts/type1/public/amsfonts/cm/cmr10.pfb></usr/share/texmf-texlive/fonts/type1/pu
+blic/amsfonts/cm/cmr12.pfb></usr/share/texmf-texlive/fonts/type1/public/amsfont
+s/cm/cmr17.pfb></usr/share/texmf-texlive/fonts/type1/public/amsfonts/cm/cmr7.pf
+b></usr/share/texmf-texlive/fonts/type1/public/amsfonts/cm/cmr9.pfb></usr/share
+/texmf-texlive/fonts/type1/public/amsfonts/cm/cmti10.pfb>
+Output written on re-main.pdf (2 pages, 132063 bytes).
 PDF statistics:
- 26 PDF objects out of 1000 (max. 8388607)
+ 49 PDF objects out of 1000 (max. 8388607)
  0 named destinations out of 1000 (max. 500000)
  1 words of extra memory for PDF output out of 10000 (max. 10000000)

docs/Working/re/re-main.tex

@@ -2 +2 @@
 \usepackage[utf8]{inputenc}
 
+\def \Bitstream{Bit Stream}
+\def \bitstream{bit stream}
+
 %opening
-\title{Fast Regular Expression Matching using Parallel Bit Streams}
+\title{Fast Regular Expression Matching using Parallel \Bitstream{}s}
 \author{
 {Robert D. Cameron} \\
@@ -22 +25 @@
 \begin{abstract}
 
+A data parallel regular expression matching method using the concept of bitstream technology
+is introduced and studied in application to the problem of fast regular expression matching.
+
+The method is based on the concept of parallel
+\bitstream{} technology, in which parallel streams of bits are formed such
+that each stream comprises bits in one-to-one correspondence with the
+character code units of a source data stream.
+
+On processors supporting W-bit addition operations, the method processes W source characters  
+in parallel and performs up to W finite state transitions per clock cycle.
+
+Performance results show a dramatic speed-up over traditional and state-of-the-art alternatives.
+
+
 \end{abstract}
 
@@ -27 +44 @@
 \label{Introduction}
 %\input{introduction.tex}
+
+Given a text T$_{1..n}$ of n characters and a pattern P, the pattern matching problem can be
+stated as follows. Find all the text positions of T that start an occurrence of P.  
+Alternatively, one may want all the final positions of occurrences. Some
+applications require slightly different output such as the line that matches the pattern.
+
+The pattern P can be just a simple string,
+but it can also be, for example, a regular expression. 
+In this paper our focus is regular expression matching.
+
+A regular expression, or pattern, is an expression that specifies a set of strings.
+A regular expression is composed of (i) basic strings and (ii)
+union, concatenation and Kleene closure of other regular expressions.
+To avoid parentheses it is assumed that the Kleene star has the highest priority, 
+next concatenation and then alternation, however, most formalisms provides grouping 
+operators to allow the definition of scope and operator precedence.
+
+Readers unfamiliar with the concept of regular expression matching are referred 
+classical texts such as \cite{aho2007}.
+
+\subsection{Grep}
+
+Regular expression matching is commonly performed using a variety of 
+publically available software tools. Namely, the UNIX grep family, 
+the GNU grep family, agrep, cgrep, sgrep, nrgrep, and Perl regular 
+expressions \cite{Abou-assaleh04surveyof}.
+
+% Grep
+% Unix grep
+% Gnu grep
+% agrep
+% nrgrep
+
+Of particular interest are well-studied and performance oriented 
+Gnu grep, agrep, and nrgrep.
+
+As such, we compare the performance of our parallel \bitstream{} techniques against 
+various grep concentrate on the simpler case of 
+reporting initial or final occurrence positions.
+
+% Background
+
+% History
+
+Regular expresssion matching is an extensively studied problem with a multitude
+of algorithms and software tools developed to the demands of particular problem contexts. 
+
+Historically, the origins of regular expression matching date back to automata theory 
+and formal language theory developed by Kleene in the 1950s \cite{kleene1951representation}.
+
+In 1959, Dana and Scott demonstrated that
+NFAs can be simulated using Deterministic Finite Automata (DFA) in which each DFA
+state corresponds to a set of NFA states.
+
+Thompson, in 1968, is credited with the first construction to convert regular expressions
+to nondeterministic finite automata (NFA) for regular expression matching. 
+
+Thompson’s publication \cite{thompson1968} marked the beginning of a long line of 
+regular expression implementations that construct automata for pattern matching.
+
+The traditional technique [16] to search a regular expression of length m in
+a text of length n is to first convert the expression into a non-deterministic 
+automaton (NFA) with O(m) nodes. It is possible to search the text using the 
+NFA directly in O(mn) worst case time. The cost comes from the fact that
+more than one state of the NFA may be active at each step, and therefore all
+may need to be updated. A more effcient choice is to convert the NFA into a
+DFA. A DFA has only a single active state and allows to search the text at 
+O(n) worst-case optimal. The problem with this approach is that the DFA 
+may have O(2^m) states.
+
+Overall, the general process is first to build a 
+NFA from the regular expression, convert the NFA into a
+DFA, minimize the number of states in the DFA, 
+and finally use the DFA to scan the text.
 
 \section{Background}
@@ -44 +135 @@
 %\input{conclusion.tex}
 
+{
+  \bibliographystyle{acm}
+  \bibliography{reference}
+}
+
 \end{document}