diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-12-06 19:10:21 +0100 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-12-06 19:10:21 +0100 |
commit | 9eac34349bdf4a0e7a7c57f62a7c8f97ef93d510 (patch) | |
tree | 48a07561fddcd37620f6d7a5ca4572a9fbda397d | |
parent | 9cf82af367d69ec10170a267f397de324ed09dce (diff) |
Add word figure
-rw-r--r-- | .gitignore | 2 | ||||
-rw-r--r-- | mgr.tex | 25 | ||||
-rw-r--r-- | word.pdf | bin | 0 -> 27577 bytes | |||
-rw-r--r-- | word.pdf_tex | 58 |
4 files changed, 81 insertions, 4 deletions
@@ -3,6 +3,6 @@ *.bcf *.blg *.log -*.pdf +mgr.pdf *.run.xml *.toc @@ -4,6 +4,7 @@ \usepackage{definitions} \usepackage[backend=biber]{biblatex} +\usepackage{graphicx} \addbibresource{mgr.bib} \usepackage{amsmath} @@ -431,12 +432,30 @@ The construction is as follows: \item Repeat steps 3.-5. for each successive color up to $|Q|$. \end{enumerate} -Additionally, for each vertex $i.q$, we store the index of the next copy of $Q$ in -which the path of this vertex's color is broken by a lower color. Put this +\begin{figure} + \centering + \def\svgwidth{\columnwidth} + \input{word.pdf_tex} + \caption{ + The data structure for infix regular queries over word $abaacbc$ and a + simple automaton with 4 states. As shown by the color blotches below the + graph, red is color 1, with the highest priority, green is color 2 with + the next priority, pink is color 3, blue is color 4, with the lowest + priority. + The information from $\breaktable$ is not shown in the figure, but it + amounts to a pointer from each vertex to the last vertex on its + connected single color component. + }\label{word-figure} +\end{figure} + +Additionally, for each vertex $i.q$, we store the index of the next copy of $Q$ +in which the path of this vertex's color is broken by a lower color. Put this information in table $\breaktable$. For example, if $i.q$ is colored with color $c$, and when following the deterministic path from $i.q$, all encountered vertices are colored $c$ until $j.q'$ which is colored $c'$, then we set -$\breaktable[i.q] = j - 1$. +$\breaktable[i.q] = j - 1$. See Figure \ref{word-figure} for a visual +representation of the data structure described for an example word and +automaton. We can compute $\breaktable$ in linear time with a single backwards pass through the colored graph. diff --git a/word.pdf b/word.pdf Binary files differnew file mode 100644 index 0000000..2be51a6 --- /dev/null +++ b/word.pdf diff --git a/word.pdf_tex b/word.pdf_tex new file mode 100644 index 0000000..8589096 --- /dev/null +++ b/word.pdf_tex @@ -0,0 +1,58 @@ +%% Creator: Inkscape 1.1.1 (3bf5ae0d25, 2021-09-20, custom), www.inkscape.org +%% PDF/EPS/PS + LaTeX output extension by Johan Engelen, 2010 +%% Accompanies image file 'word.pdf' (pdf, eps, ps) +%% +%% To include the image in your LaTeX document, write +%% \input{<filename>.pdf_tex} +%% instead of +%% \includegraphics{<filename>.pdf} +%% To scale the image, write +%% \def\svgwidth{<desired width>} +%% \input{<filename>.pdf_tex} +%% instead of +%% \includegraphics[width=<desired width>]{<filename>.pdf} +%% +%% Images with a different path to the parent latex file can +%% be accessed with the `import' package (which may need to be +%% installed) using +%% \usepackage{import} +%% in the preamble, and then including the image with +%% \import{<path to file>}{<filename>.pdf_tex} +%% Alternatively, one can specify +%% \graphicspath{{<path to file>/}} +%% +%% For more information, please see info/svg-inkscape on CTAN: +%% http://tug.ctan.org/tex-archive/info/svg-inkscape +%% +\begingroup% + \makeatletter% + \providecommand\color[2][]{% + \errmessage{(Inkscape) Color is used for the text in Inkscape, but the package 'color.sty' is not loaded}% + \renewcommand\color[2][]{}% + }% + \providecommand\transparent[1]{% + \errmessage{(Inkscape) Transparency is used (non-zero) for the text in Inkscape, but the package 'transparent.sty' is not loaded}% + \renewcommand\transparent[1]{}% + }% + \providecommand\rotatebox[2]{#2}% + \newcommand*\fsize{\dimexpr\f@size pt\relax}% + \newcommand*\lineheight[1]{\fontsize{\fsize}{#1\fsize}\selectfont}% + \ifx\svgwidth\undefined% + \setlength{\unitlength}{1493.00403586bp}% + \ifx\svgscale\undefined% + \relax% + \else% + \setlength{\unitlength}{\unitlength * \real{\svgscale}}% + \fi% + \else% + \setlength{\unitlength}{\svgwidth}% + \fi% + \global\let\svgwidth\undefined% + \global\let\svgscale\undefined% + \makeatother% + \begin{picture}(1,0.50303459)% + \lineheight{1}% + \setlength\tabcolsep{0pt}% + \put(0,0){\includegraphics[width=\unitlength,page=1]{word.pdf}}% + \end{picture}% +\endgroup% |