# Changeset 3123 for docs/Working

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

Check-in rough notes only.

Location:
docs/Working/re
Files:
4 added
4 edited

Unmodified
Added
Removed
• ## docs/Working/re/re-main.aux

 r3121 \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

 r3121 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. \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 Output written on re-main.pdf (1 page, 57666 bytes). 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

 r3121 \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} \\ \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} \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} %\input{conclusion.tex} { \bibliographystyle{acm} \bibliography{reference} } \end{document}
Note: See TracChangeset for help on using the changeset viewer.