Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/33439
Title: | Efficient Enumeration Algorithms for Regular Document Spanners | Authors: | Florenzano, Fernando Riveros, Cristian Ugarte, Martín VANSUMMEREN, Stijn Vrgoc, Domagoj |
Issue Date: | 2020 | Publisher: | Association for Computing Machinery | Source: | ACM TRANSACTIONS ON DATABASE SYSTEMS, 45 (1) , p. 1 -42 (Art N° 3) | Abstract: | 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 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 efficient evaluation algorithms that can generate the extracted data in a quick succession, and with relatively little precomputation time. Toward this goal, we present a practical evaluation algorithm that allows output-linear delay enumeration of a spanner's result after a precomputation phase that is linear in the document. Although 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 and provide a fine-grained analysis of the classes of document spanners that support efficient enumeration of their results. | Keywords: | Information extraction;spanners;enumeration delay;automata;capture variables | Document URI: | http://hdl.handle.net/1942/33439 | ISSN: | 0362-5915 | e-ISSN: | 1557-4644 | DOI: | 10.1145/3351451 | ISI #: | WOS:000583687500004 | Category: | A1 | Type: | Journal Contribution |
Appears in Collections: | Research publications |
Show full item record
WEB OF SCIENCETM
Citations
12
checked on Sep 20, 2024
Page view(s)
40
checked on Jul 31, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.