  Regular expressions and automata models with capture variables are core tools
in rule-based information extraction. These formalisms, also called regular
document spanners, use regular languages in order to locate the data that a
user wants to extract from a text document, and then store this data into
variables. Since document spanners can easily generate large outputs, it is
important to have good evaluation algorithms that can generate the extracted
data in a quick succession, and with relatively little precomputation time.
Towards this goal, we present a practical evaluation algorithm that allows
constant delay enumeration of a spanner's output after a precomputation phase
that is linear in the document. While the algorithm assumes that the spanner is
specified in a syntactic variant of variable set automata, we also study how it
can be applied when the spanner is specified by general variable set automata,
regex formulas, or spanner algebras. Finally, we study the related problem of
counting the number of outputs of a document spanner, providing a fine grained
analysis of the classes of document spanners that support efficient enumeration
of their results.
