4 \usepackage{../graphics} |
4 \usepackage{../graphics} |
5 \usepackage{../data} |
5 \usepackage{../data} |
6 |
6 |
7 |
7 |
8 \begin{document} |
8 \begin{document} |
9 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018} |
9 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019} |
10 |
10 |
11 |
11 |
12 \section*{Handout 2 (Regular Expression Matching)} |
12 \section*{Handout 2 (Regular Expression Matching)} |
13 |
13 |
14 This lecture is about implementing a more efficient regular expression |
14 This lecture is about implementing a more efficient regular expression |
15 matcher (the plots on the right below)---more efficient than the |
15 matcher (the plots on the right below)---more efficient than the |
16 matchers from regular expression libraries in Ruby, Python and Java |
16 matchers from regular expression libraries in Ruby, Python, JavaScript |
17 (the plots on the left). The first pair of plots shows the running time |
17 and Java (the plots on the left). For this consider some experimental |
18 for the regular expression $(a^*)^*\cdot b$ and strings composed of |
18 data: The first pair of plots shows the running time for the |
19 $n$ \pcode{a}s (meaning this regular expression actually does not |
19 regular expression $(a^*)^*\cdot b$ and strings composed of $n$ |
20 match the strings). The second pair of plots shows the running time for |
20 \pcode{a}s (meaning this regular expression actually does not match |
21 the regular expressions $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and strings |
21 the strings). The second pair of plots shows the running time for the |
22 also composed of $n$ \pcode{a}s (this time the regular expressions |
22 regular expressions $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and strings also |
23 match the strings). To see the substantial differences in the left |
23 composed of $n$ \pcode{a}s (this time the regular expressions match |
24 and right plots below, note the different scales of the $x$-axes. |
24 the strings). To see the substantial differences in the left and |
|
25 right plots below, note the different scales of the $x$-axes. |
25 |
26 |
26 |
27 |
27 \begin{center} |
28 \begin{center} |
28 Graphs: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$ |
29 Graphs: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$ |
29 \begin{tabular}{@{}cc@{}} |
30 \begin{tabular}{@{}cc@{}} |
39 ytick={0,5,...,30}, |
40 ytick={0,5,...,30}, |
40 scaled ticks=false, |
41 scaled ticks=false, |
41 axis lines=left, |
42 axis lines=left, |
42 width=5cm, |
43 width=5cm, |
43 height=5cm, |
44 height=5cm, |
44 legend entries={Java 8, Python}, |
45 legend entries={Java 8, Python, JavaScript}, |
45 legend pos=north west, |
46 legend pos=north west, |
46 legend cell align=left] |
47 legend cell align=left] |
47 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; |
48 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; |
48 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
49 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
|
50 \addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; |
49 \end{axis} |
51 \end{axis} |
50 \end{tikzpicture} |
52 \end{tikzpicture} |
51 & |
53 & |
52 \begin{tikzpicture}[baseline=(current bounding box.north)] |
54 \begin{tikzpicture}[baseline=(current bounding box.north)] |
53 \begin{axis}[ |
55 \begin{axis}[ |