{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T13:37:24Z","timestamp":1774964244893,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>In this paper, we present the REmatch system for information extraction. REmatch is based on a recently proposed enumeration algorithm for evaluating regular expressions with capture variables supporting the all-match semantics. It tells a story of what it takes to make a theoretically optimal algorithm work in practice. As we show here, a naive implementation of the original algorithm would have a hard time dealing with realistic workloads. We thus develop a new algorithm and a series of optimizations that make REmatch as fast or faster than many popular RegEx engines while at the same time being able to return all the outputs: a task that most other engines tend to struggle with.<\/jats:p>","DOI":"10.14778\/3611479.3611488","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"2792-2804","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["REmatch: A Novel Regex Engine for Finding All Matches"],"prefix":"10.14778","volume":"16","author":[{"given":"Cristian","family":"Riveros","sequence":"first","affiliation":[{"name":"PUC Chile &amp; IMFD Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicol\u00e1s","family":"Van Sint Jan","sequence":"additional","affiliation":[{"name":"PUC Chile &amp; IMFD Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domagoj","family":"Vrgo\u010d","sequence":"additional","affiliation":[{"name":"PUC Chile &amp; IMFD Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Project Gutenberg. https:\/\/www.gutenberg.org\/. Accessed on 2023-07-21.  [n.d.]. Project Gutenberg. https:\/\/www.gutenberg.org\/. Accessed on 2023-07-21."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. REmatch Website. https:\/\/github.com\/REmatchChile\/REmatch-paper. Accessed on 2023-07-21.  [n.d.]. REmatch Website. https:\/\/github.com\/REmatchChile\/REmatch-paper. Accessed on 2023-07-21."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. Sequence motif. https:\/\/en.wikipedia.org\/wiki\/Sequence_motif. Accessed on 2023-07-21.  [n.d.]. Sequence motif. https:\/\/en.wikipedia.org\/wiki\/Sequence_motif. Accessed on 2023-07-21."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3436487"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Antoine Amarilli Louis Jachiet Martin Mu\u00f1oz and Cristian Riveros. 2022. Efficient Enumeration for Annotated Grammars. In PODS. 291--300.  Antoine Amarilli Louis Jachiet Martin Mu\u00f1oz and Cristian Riveros. 2022. Efficient Enumeration for Annotated Grammars. In PODS. 291--300.","DOI":"10.1145\/3517804.3526232"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Philip Bille and Mikkel Thorup. 2009. Faster Regular Expression Matching. In ICALP. 171--182.  Philip Bille and Mikkel Thorup. 2009. Faster Regular Expression Matching. In ICALP. 171--182.","DOI":"10.1007\/978-3-642-02927-1_16"},{"key":"e_1_2_1_8_1","volume-title":"Basic Local Alignment Search Tool","author":"BLAST","year":"2022","unstructured":"BLAST : Basic Local Alignment Search Tool 2022 . https:\/\/blast.ncbi.nlm.nih.gov\/doc\/blast-help\/downloadblastdata.html. Accessed on 2023-07-21. BLAST: Basic Local Alignment Search Tool 2022. https:\/\/blast.ncbi.nlm.nih.gov\/doc\/blast-help\/downloadblastdata.html. Accessed on 2023-07-21."},{"key":"e_1_2_1_9_1","unstructured":"Boost Regex Library 2022. https:\/\/github.com\/boostorg\/regex. Accessed on 2023-07-21.  Boost Regex Library 2022. https:\/\/github.com\/boostorg\/regex. Accessed on 2023-07-21."},{"key":"e_1_2_1_10_1","unstructured":"Russ Cox. 2007. Regular expression matching can be simple and fast (but is slow in java perl php python ruby ...). https:\/\/swtch.com\/~rsc\/regexp\/regexp1.html. Accessed on 2023-07-21.  Russ Cox. 2007. Regular expression matching can be simple and fast (but is slow in java perl php python ruby ...). https:\/\/swtch.com\/~rsc\/regexp\/regexp1.html. Accessed on 2023-07-21."},{"key":"e_1_2_1_11_1","unstructured":"Russ Cox. 2010. Regular expression matching in the wild. https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html. Accessed on 2023-07-21.  Russ Cox. 2010. Regular expression matching in the wild. https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html. Accessed on 2023-07-21."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3484622.3484624"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Johannes Doleschal Benny Kimelfeld Wim Martens Yoav Nahshon and Frank Neven. 2019. Split-Correctness in Information Extraction. In PODS. 149--163.  Johannes Doleschal Benny Kimelfeld Wim Martens Yoav Nahshon and Frank Neven. 2019. Split-Correctness in Information Extraction. In PODS. 149--163.","DOI":"10.1145\/3294052.3319684"},{"key":"e_1_2_1_14_1","first-page":"19","article-title":"Enhancing Regular Expressions for Polish Text Processing","volume":"10","author":"Dorosz Krzysztof","year":"2009","unstructured":"Krzysztof Dorosz and Anna Szczerbinska . 2009 . Enhancing Regular Expressions for Polish Text Processing . Computer Science 10 (2009), 19 -- 36 . Krzysztof Dorosz and Anna Szczerbinska. 2009. Enhancing Regular Expressions for Polish Text Processing. Computer Science 10 (2009), 19--36.","journal-title":"Computer Science"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3351451"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3064000"},{"key":"e_1_2_1_18_1","unstructured":"Jeffrey E.F. Friedl. 2006. Mastering regular expressions. O'Reilly.  Jeffrey E.F. Friedl. 2006. Mastering regular expressions. O'Reilly."},{"key":"e_1_2_1_19_1","volume-title":"The PROSITE database. https:\/\/ftp.expasy.org\/databases\/prosite\/prosite.dat","author":"The","unstructured":"The Swiss-Prot group. 2022. The PROSITE database. https:\/\/ftp.expasy.org\/databases\/prosite\/prosite.dat . World Wide Web Consortium . The Swiss-Prot group. 2022. The PROSITE database. https:\/\/ftp.expasy.org\/databases\/prosite\/prosite.dat. World Wide Web Consortium."},{"key":"e_1_2_1_20_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"1979","unstructured":"John E. Hopcroft and Jeffrey D . Ullman . 1979 . Introduction to Automata Theory, Languages and Computation. Addison-Wesley . John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison-Wesley."},{"key":"e_1_2_1_21_1","unstructured":"How can I match overlapping strings with regex? 2014. https:\/\/stackoverflow.com\/questions\/20833295\/how-can-i-match-overlapping-strings-with-regex\/33903830. Accessed on 2023-07-21.  How can I match overlapping strings with regex? 2014. https:\/\/stackoverflow.com\/questions\/20833295\/how-can-i-match-overlapping-strings-with-regex\/33903830. Accessed on 2023-07-21."},{"key":"e_1_2_1_22_1","unstructured":"How to find overlapping matches with a regexp? 2013. https:\/\/stackoverflow.com\/questions\/11430863\/how-to-find-overlapping-matches-with-a-regexp. Accessed on 2023-07-21.  How to find overlapping matches with a regexp? 2013. https:\/\/stackoverflow.com\/questions\/11430863\/how-to-find-overlapping-matches-with-a-regexp. Accessed on 2023-07-21."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Muhammad Idris Mart\u00edn Ugarte and Stijn Vansummeren. 2017. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In SIGMOD. 1259--1274.  Muhammad Idris Mart\u00edn Ugarte and Stijn Vansummeren. 2017. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In SIGMOD. 1259--1274.","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00590-9"},{"key":"e_1_2_1_25_1","unstructured":"IEEE and The Open Group. 2018. https:\/\/pubs.opengroup.org\/onlinepubs\/9699919799\/basedefs\/V1_chap09.html. Accessed on 2023-07-21.  IEEE and The Open Group. 2018. https:\/\/pubs.opengroup.org\/onlinepubs\/9699919799\/basedefs\/V1_chap09.html. Accessed on 2023-07-21."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/364175.364185"},{"key":"e_1_2_1_27_1","unstructured":"JPCRE2 C++ wrapper for PCRE2 library 2022. https:\/\/github.com\/jpcre2\/jpcre2. Accessed on 2023-07-21.  JPCRE2 C++ wrapper for PCRE2 library 2022. https:\/\/github.com\/jpcre2\/jpcre2. Accessed on 2023-07-21."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Stephen C Kleene etal 1956. Representation of events in nerve nets and finite automata. Automata studies 34 (1956) 3--41.  Stephen C Kleene et al. 1956. Representation of events in nerve nets and finite automata. Automata studies 34 (1956) 3--41.","DOI":"10.1515\/9781400882618-002"},{"key":"e_1_2_1_29_1","first-page":"1","article-title":"MSO queries on trees: enumerating answers under updates","volume":"67","author":"Losemann Katja","year":"2014","unstructured":"Katja Losemann and Wim Martens . 2014 . MSO queries on trees: enumerating answers under updates . In CSL-LICS. 67 : 1 -- 67 :10. Katja Losemann and Wim Martens. 2014. MSO queries on trees: enumerating answers under updates. In CSL-LICS. 67:1--67:10.","journal-title":"CSL-LICS."},{"key":"e_1_2_1_30_1","volume-title":"Sims Martin Haspelmath","author":"Andrea","year":"2010","unstructured":"Andrea D. Sims Martin Haspelmath . 2010 . Understanding Morphology. Hodder Education . Andrea D. Sims Martin Haspelmath. 2010. Understanding Morphology. Hodder Education."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Francisco Maturana Cristian Riveros and Domagoj Vrgoc. 2018. Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity. In PODS. 125--136.  Francisco Maturana Cristian Riveros and Domagoj Vrgoc. 2018. Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity. In PODS. 125--136.","DOI":"10.1145\/3196959.3196968"},{"key":"e_1_2_1_32_1","first-page":"1","article-title":"Streaming Enumeration on Nested Documents","volume":"19","author":"Mu\u00f1oz Martin","year":"2022","unstructured":"Martin Mu\u00f1oz and Cristian Riveros . 2022 . Streaming Enumeration on Nested Documents . In ICDT. 19 : 1 -- 19 :18. Martin Mu\u00f1oz and Cristian Riveros. 2022. Streaming Enumeration on Nested Documents. In ICDT. 19:1--19:18.","journal-title":"ICDT."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1120-3"},{"key":"e_1_2_1_34_1","unstructured":"Oniguruma - a modern and flexible regular expressions library 2022. https:\/\/github.com\/kkos\/oniguruma. Accessed on 2023-07-21.  Oniguruma - a modern and flexible regular expressions library 2022. https:\/\/github.com\/kkos\/oniguruma. Accessed on 2023-07-21."},{"key":"e_1_2_1_35_1","unstructured":"PCRE - Perl Compatible Regular Expressions 2022. https:\/\/www.pcre.org\/. Accessed on 2023-07-21.  PCRE - Perl Compatible Regular Expressions 2022. https:\/\/www.pcre.org\/. Accessed on 2023-07-21."},{"key":"e_1_2_1_36_1","unstructured":"PCRE2 - Perl-Compatible Regular Expressions 2022. https:\/\/github.com\/PCRE2Project\/pcre2. Accessed on 2023-07-21.  PCRE2 - Perl-Compatible Regular Expressions 2022. https:\/\/github.com\/PCRE2Project\/pcre2. Accessed on 2023-07-21."},{"key":"e_1_2_1_37_1","unstructured":"PCREgrep - A grep program that uses the PCRE regular expression library 2014. https:\/\/github.com\/vmg\/pcre\/blob\/master\/pcregrep.c\/. Accessed on 2023-07-21.  PCREgrep - A grep program that uses the PCRE regular expression library 2014. https:\/\/github.com\/vmg\/pcre\/blob\/master\/pcregrep.c\/. Accessed on 2023-07-21."},{"key":"e_1_2_1_38_1","unstructured":"RE2 regular expression library 2022. https:\/\/github.com\/google\/re2. Accessed on 2023-07-21.  RE2 regular expression library 2022. https:\/\/github.com\/google\/re2. Accessed on 2023-07-21."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517035"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Luc Segoufin. 2013. Enumerating with constant delay the answers to a query. In ICDT. 10--20.  Luc Segoufin. 2013. Enumerating with constant delay the answers to a query. In ICDT. 10--20.","DOI":"10.1145\/2448496.2448498"},{"key":"e_1_2_1_41_1","volume-title":"Fast regular expression matching using FPGAs","author":"Sidhu Reetinder","unstructured":"Reetinder Sidhu and Viktor K Prasanna . 2001. Fast regular expression matching using FPGAs . In FCCM. IEEE , 227--238. Reetinder Sidhu and Viktor K Prasanna. 2001. Fast regular expression matching using FPGAs. In FCCM. IEEE, 227--238."},{"key":"e_1_2_1_42_1","volume-title":"Java 9 Regular Expressions","author":"Srivastava Anubhava","unstructured":"Anubhava Srivastava . 2017. Java 9 Regular Expressions . Packt Publishing . Anubhava Srivastava. 2017. Java 9 Regular Expressions. Packt Publishing."},{"key":"e_1_2_1_43_1","volume-title":"The Linked SPARQL Queries Dataset","author":"The LSQ","unstructured":"The LSQ team. 2015. The Linked SPARQL Queries Dataset . http:\/\/aksw.github.io\/LSQ\/. Accessed on 2023-07-21. The LSQ team. 2015. The Linked SPARQL Queries Dataset. http:\/\/aksw.github.io\/LSQ\/. Accessed on 2023-07-21."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_45_1","volume-title":"robust, and efficient POSIX compliant regexp matching library","author":"TRE","year":"2021","unstructured":"TRE - a lightweight , robust, and efficient POSIX compliant regexp matching library 2021 . https:\/\/github.com\/laurikari\/tre. Accessed on 2023-07-21. TRE - a lightweight, robust, and efficient POSIX compliant regexp matching library 2021. https:\/\/github.com\/laurikari\/tre. Accessed on 2023-07-21."},{"key":"e_1_2_1_46_1","first-page":"1582","article-title":"Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries","volume":"13","author":"Tziavelis Nikolaos","year":"2020","unstructured":"Nikolaos Tziavelis , Deepak Ajwani , Wolfgang Gatterbauer , Mirek Riedewald , and Xiaofeng Yang . 2020 . Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries . VLDB 13 , 9 (2020), 1582 -- 1597 . Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. 2020. Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries. VLDB 13, 9 (2020), 1582--1597.","journal-title":"VLDB"},{"key":"e_1_2_1_47_1","unstructured":"W3C Sparql 2013. SPARQL 1.1 Query Language. https:\/\/www.w3.org\/TR\/sparql11-query\/. Accessed on 2023-07-21.  W3C Sparql 2013. SPARQL 1.1 Query Language. https:\/\/www.w3.org\/TR\/sparql11-query\/. Accessed on 2023-07-21."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847525"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Xiaochun Yang Bin Wang Tao Qiu Yaoshu Wang and Chen Li. 2013. Improving regular-expression matching on strings using negative factors. In SIGMOD. 361--372.  Xiaochun Yang Bin Wang Tao Qiu Yaoshu Wang and Chen Li. 2013. Improving regular-expression matching on strings using negative factors. In SIGMOD. 361--372.","DOI":"10.1145\/2463676.2465289"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611488","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:19:00Z","timestamp":1695507540000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611488"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":49,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611488"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611488","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}