Compressed Structures for Partial Derivative Automata Constructions

The partial derivative automaton (${{𝒜}}_{\mathrm{\text{PD}}}$) is an elegant simulation of a regular expression. Although it is, in general, smaller than the position automaton (${{𝒜}}_{\mathrm{\text{POS}}}$), the algorithms that build ${{𝒜}}_{\mathrm{\text{PD}}}$ in quadratic worst-case time first compute ${{𝒜}}_{\mathrm{\text{POS}}}$. Asymptotically, and on average for the uniform distribution, the size of ${{𝒜}}_{\mathrm{\text{PD}}}$ is half the size of ${{𝒜}}_{\mathrm{\text{POS}}}$, being both linear on the size of the expression. We address the construction of ${{𝒜}}_{\mathrm{\text{PD}}}$ efficiently, on average, avoiding the computation of ${{𝒜}}_{\mathrm{\text{POS}}}$. The expression and the set of its partial derivatives are represented by a directed acyclic graph with shared common subexpressions. We develop an algorithm for building ${{𝒜}}_{\mathrm{\text{PD}}}$s from expressions in strong star normal form of size $n$ that runs, on average, in time that asymptotically behaves as $n^{3/2}\sqrt[4]{\mathrm{\text{log}}(n)}$, and space as $n^{3/2}/{(\mathrm{\text{log}}n)}^{3/4}$. Empirical results corroborate its good practical performance.