EUVIMEDEUVIMED entdecken
Crossref

Optimal Enumeration of Regular Pattern Matches

Paweł Gawrychowski, Florin Manea, Paul Sarnighausen-Cahn, Stefan Siemer

Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-25

DOI: 10.1145/3801908 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Paweł Gawrychowski und 3 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Gefördert von: German Research Foundation, Polish National Science Centre.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Enumerating all matches of a regular expression with capture variables (variable regex, for short) to a document is a fundamental task in textual information extraction, e.g., in connection to document spanners. State-of-the-art results [Amarilli et al., ACM TODS 2021] show how the matches of a variable regex, representable by a sequential variable-set automaton, to a document can be enumerated with delay constant in the size of the document and polynomial in the size of the query, after a preprocessing requiring time linear in the size of the document and polynomial in the size of the query. However, the polynomial dependency on the size of the query in both the delay and the preprocessing is actually quite high: at least quadratic. We consider here the matching problem for regular expressions with capture variables which can be represented as regular patterns: w 0 x 0 w 1 x 1 #8230;s w k x k w k +1, where, for i ∈ {0, … k +1}, w i is a string of terminal letters and, for i in {0,…, k }, x i is a variable. This problem naturally lies in the intersection of information extraction and stringology, as it can also be seen as computing all the ways in which k +1 given strings w 0 ,…,w k +1 occur, in this order and without overlaps, in a given text T . We provide an optimal enumeration algorithm for this problem. After a preprocessing requiring linear time in the size of the document T and the size of the query pattern α, we can enumerate all matches with worst-case constant delay (in combined complexity, i.e., both in the document- and the query-size).

Förderung

  • German Research Foundation
  • Polish National Science Centre

Zitieren

APA

Gawrychowski, P., Manea, F., Sarnighausen-Cahn, P., & Siemer, S. (2026). Optimal Enumeration of Regular Pattern Matches. Proceedings of the ACM on Management of Data, 4(2), 1-25. https://doi.org/10.1145/3801908

Vancouver

Gawrychowski P, Manea F, Sarnighausen-Cahn P, Siemer S. Optimal Enumeration of Regular Pattern Matches. Proceedings of the ACM on Management of Data. 2026;4(2):1-25. doi:10.1145/3801908

BibTeX
@article{Gawrychowski2026,
  author = {Gawrychowski, Paweł and Manea, Florin and Sarnighausen-Cahn, Paul and Siemer, Stefan},
  title = {Optimal Enumeration of Regular Pattern Matches},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {2},
  pages = {1--25},
  doi = {10.1145/3801908}
}
Kostenlos starten →