Changeset 3411


Ignore:
Timestamp:
Jul 26, 2013, 9:28:33 AM (6 years ago)
Author:
bhull
Message:

Added Match Star description

Location:
docs/Working/re
Files:
4 edited

Legend:

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

    r3156 r3411  
    2424\citation{navarro1998bit}
    2525\citation{Wu92agrep-}
     26\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Bit-parallel Simulation of Automata}{4}}
     27\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Software Tools}{4}}
     28\@writefile{toc}{\contentsline {section}{\numberline {4}Bit-parallel Data Streams}{4}}
     29\newlabel{Bit-parallel Data Streams}{{4}{4}}
     30\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Match Star}{4}}
    2631\bibstyle{acm}
    2732\bibdata{reference}
     
    2934\bibcite{aho2007}{2}
    3035\bibcite{Baeza-yates_anew}{3}
    31 \@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Bit-parallel Simulation of Automata}{4}}
    32 \@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Software Tools}{4}}
    33 \@writefile{toc}{\contentsline {section}{\numberline {4}Bit-parallel Data Streams}{4}}
    34 \newlabel{Bit-parallel Data Streams}{{4}{4}}
    35 \@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Match Star}{4}}
    36 \@writefile{toc}{\contentsline {section}{\numberline {5}Compiler Technology}{4}}
    37 \newlabel{Compiler Technology}{{5}{4}}
    38 \@writefile{toc}{\contentsline {section}{\numberline {6}Methodology}{4}}
    39 \newlabel{Methodology}{{6}{4}}
    40 \@writefile{toc}{\contentsline {section}{\numberline {7}Experimental Results}{4}}
    41 \newlabel{Experimental Results}{{7}{4}}
    42 \@writefile{toc}{\contentsline {section}{\numberline {8}Conclusion}{4}}
    43 \newlabel{Conclusion}{{8}{4}}
    4436\bibcite{boyer1977fast}{4}
    4537\bibcite{cameron2009parallel}{5}
     
    4739\bibcite{cameron2008high}{7}
    4840\bibcite{kleene1951}{8}
     41\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Match Star}}{5}}
     42\newlabel{fig:scan1}{{1}{5}}
     43\@writefile{toc}{\contentsline {section}{\numberline {5}Compiler Technology}{5}}
     44\newlabel{Compiler Technology}{{5}{5}}
     45\@writefile{toc}{\contentsline {section}{\numberline {6}Methodology}{5}}
     46\newlabel{Methodology}{{6}{5}}
     47\@writefile{toc}{\contentsline {section}{\numberline {7}Experimental Results}{5}}
     48\newlabel{Experimental Results}{{7}{5}}
     49\@writefile{toc}{\contentsline {section}{\numberline {8}Conclusion}{5}}
     50\newlabel{Conclusion}{{8}{5}}
    4951\bibcite{lin2012parabix}{9}
    5052\bibcite{navarro2000}{10}
  • docs/Working/re/re-main.blg

    r3156 r3411  
    1 This is BibTeX, Version 0.99c (TeX Live 2009/Debian)
    2 The top-level auxiliary file: re-main.aux
     1This is BibTeX, Version 0.99dThe top-level auxiliary file: re-main.aux
    32The style file: acm.bst
    43Database file #1: reference.bib
    54Warning--empty institution in abou-assaleh2004
    65Warning--empty journal in kleene1951
    7 You've used 15 entries,
    8             2253 wiz_defined-function locations,
    9             617 strings with 6165 characters,
    10 and the built_in function-call counts, 4876 in all, are:
    11 = -- 462
    12 > -- 215
    13 < -- 0
    14 + -- 92
    15 - -- 74
    16 * -- 347
    17 := -- 786
    18 add.period$ -- 44
    19 call.type$ -- 15
    20 change.case$ -- 82
    21 chr.to.int$ -- 0
    22 cite$ -- 17
    23 duplicate$ -- 204
    24 empty$ -- 414
    25 format.name$ -- 74
    26 if$ -- 1032
    27 int.to.chr$ -- 0
    28 int.to.str$ -- 15
    29 missing$ -- 14
    30 newline$ -- 76
    31 num.names$ -- 30
    32 pop$ -- 102
    33 preamble$ -- 1
    34 purify$ -- 67
    35 quote$ -- 0
    36 skip$ -- 130
    37 stack$ -- 0
    38 substring$ -- 253
    39 swap$ -- 54
    40 text.length$ -- 0
    41 text.prefix$ -- 0
    42 top$ -- 0
    43 type$ -- 58
    44 warning$ -- 2
    45 while$ -- 49
    46 width$ -- 17
    47 write$ -- 150
    486(There were 2 warnings)
  • docs/Working/re/re-main.tex

    r3156 r3411  
    232232
    233233%Source: http://en.wikipedia.org/wiki/Backtracking
    234 Backtracking is a general algorithm for finding all solutions to some computational problem,
    235 that incrementally builds candidates to the solutions.
     234%Backtracking is a general algorithm for finding all solutions to some computational problem,
     235%that incrementally builds candidates to the solutions.
     236
     237Match Star takes a marker bitstream and a character class bitstream as input.  It returns all positions that can be reached by advancing the marker bitstream zero or more times through the character class bitstream.
     238
     239Figure one illustrates the Match Star method.  The second and third rows are the input bitstreams: the initial marker position bitstream and the character class bitstream derived from the source data.
     240
     241In the first operation ($T_0$), marker positions that cannot be advanced are temporarily removed from consideration by masking off marker positions that aren't character class positions using bitwise logic.  Next, the temporary marker bitstream is added to the character class bitstream.  $T_1$ has 1s in three types of positions.  There will be a 1 immediately following a block of character class positions that spanned one or more marker positions, at any character class positions that weren't affected by the addition (and are not part of the desired output), and at any marker position that wasn't the first in its block of character class positions.  Any character class positions that have a 0 in $T_1$ were affected by the addition and are part of the desired output.  These positions are obtained and the undesired 1 bits are removed by XORing with the character class stream. $T_2$ is now only missing marker positions that were removed in the first step as well as marker positions that were 1s in $T_1$.  The output marker stream is obtained by ORing $T_2$ with the initial marker stream.
     242
     243\begin{figure}[tbh]
     244\begin{center}
     245\begin{tabular}{cr}\\
     246source data & \verb`--142578---125-231-----127--5394---94761205-`\\
     247$M_0$ & \verb`.......1......1..1..1...1.............1..1..`\\
     248$D = $\verb:[0-9]: & \verb`..111111...111.111.....111..1111...11111111.`\\
     249$T_0 = M_0 \wedge D$ & \verb`.......1.........1......1.............1..1..`\\
     250$T_1 = T_0 + D$ & \verb`.1.........1111.......1..1..1111..1...1...1.`\\
     251$T_2 = T_1 \oplus D$ & \verb`.1111111......1111....111.........1111.111..`\\
     252$M_1 = T_2 \, | \, M_0$ & \verb`.1111111......1111..1.111.........11111111..`
     253\end{tabular}
     254
     255
     256\end{center}
     257\caption{Match Star}
     258\label{fig:scan1}
     259\end{figure}
    236260
    237261\section{Compiler Technology}
Note: See TracChangeset for help on using the changeset viewer.