{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T17:24:10Z","timestamp":1787592250108,"version":"build-2736575974"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:00:00Z","timestamp":1744156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2340479"],"award-info":[{"award-number":["2340479"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,4,9]]},"abstract":"<jats:p>Tokenization (also known as scanning or lexing) is a computational task that has applications in the lexical analysis of programs during compilation and in data extraction and analysis for unstructured or semistructured data (e.g., data represented using the JSON and CSV data formats). We propose two algorithms for the tokenization problem that have linear time complexity (in the length of the input text) without using large amounts of memory. We also show that an optimized version of one of these algorithms performs well compared to prior approaches on practical tokenization workloads.<\/jats:p>","DOI":"10.1145\/3720498","type":"journal-article","created":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T13:48:26Z","timestamp":1744206506000},"page":"1492-1518","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Algorithms for the Uniform Tokenization Problem"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4523-3401","authenticated-orcid":false,"given":"Angela W.","family":"Li","sequence":"first","affiliation":[{"name":"Rice University, Houston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1209-7738","authenticated-orcid":false,"given":"Konstantinos","family":"Mamouras","sequence":"additional","affiliation":[{"name":"Rice University, Houston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,9]]},"reference":[{"key":"e_1_3_1_2_1","volume-title":"Compilers Principles, Techniques & Tools","author":"Aho Alfred V.","year":"2007","unstructured":"Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2007. Compilers Principles, Techniques & Tools. Pearson Education."},{"key":"e_1_3_1_3_1","unstructured":"Amazon. 2024. Amazon Book Reviews Dataset. https:\/\/www.kaggle.com\/datasets\/mohamedbakhet\/amazon-books-reviews"},{"key":"e_1_3_1_4_1","doi-asserted-by":"crossref","unstructured":"M. Andrews. 1998. RFC2308: Negative Caching of DNS Queries (DNS NCACHE). https:\/\/datatracker.ietf.org\/doc\/html\/rfc2308","DOI":"10.17487\/rfc2308"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","unstructured":"arXiv.org. 2024. arXiv Dataset. https:\/\/doi.org\/10.34740\/KAGGLE\/DSV\/7548853 10.34740\/KAGGLE\/DSV\/7548853","DOI":"10.34740\/KAGGLE\/DSV\/7548853"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43144-4_5"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2015.09.002"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656431"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3703595.3705884"},{"key":"e_1_3_1_12_1","unstructured":"Colm Networks. 2021. Ragel State Machine Compiler. https:\/\/www.colm.net\/open-source\/ragel\/. [Online; accessed October 15 2024]."},{"key":"e_1_3_1_13_1","unstructured":"Russ Cox. 2010. Regular Expression Matching in the Wild. https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html. [Online; accessed October 15 2024]."},{"key":"e_1_3_1_14_1","unstructured":"data.gov. 2009. U.S. Government\u2019s Open Data. https:\/\/data.gov\/"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","unstructured":"Derek Egolf Sam Lasser and Kathleen Fisher. 2021. Verbatim: A Verified Lexer Generator. In 2021 IEEE Security and Privacy Workshops (SPW). IEEE USA 92\u2013100. https:\/\/doi.org\/10.1109\/SPW53761.2021.00022 10.1109\/SPW53761.2021.00022","DOI":"10.1109\/SPW53761.2021.00022"},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3497775.3503694"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:FORM.0000017718.28096.48"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_53"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837647"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10882-7_14"},{"key":"e_1_3_1_21_1","unstructured":"JSON. 2001. JSON. https:\/\/www.json.org\/json-en.html [Online; accessed October 15 2024]."},{"key":"e_1_3_1_22_1","unstructured":"JSON5. 2012. JSON5: JSON for humans. https:\/\/json5.org\/[Online; accessed October 15 2024]."},{"key":"e_1_3_1_23_1","unstructured":"Kaggle. 2010. Kaggle. https:\/\/www.kaggle.com"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.3396"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523456"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586044"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS49936.2021.00079"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.2983426"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632934"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656461"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.27.422"},{"key":"e_1_3_1_32_1","doi-asserted-by":"crossref","unstructured":"Paul Mockapetris. 1987. RFC 1035: Domain Names - Implementation and Specification. https:\/\/datatracker.ietf.org\/doc\/html\/rfc1035","DOI":"10.17487\/rfc1035"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData55660.2022.10020756"},{"key":"e_1_3_1_34_1","unstructured":"National Library of Medicine. 2021. FASTA Format for Nucleotide Sequences. (2021). https:\/\/www.ncbi.nlm.nih.gov\/genbank\/fastaformat\/"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.22152\/programming-journal.org\/2024\/8\/3"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEEESTD.2008.4694976"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/276393.276394"},{"key":"e_1_3_1_38_1","unstructured":"Robert van Engelen. 2016. RE\/flex: A high-performance C++ regex library and a lexical analyzer generator. https:\/\/www.genivia.com\/doc\/reflex\/html\/. [Online; accessed October 15 2024]."},{"key":"e_1_3_1_39_1","doi-asserted-by":"crossref","unstructured":"Yakov Shafranovich. 2005. RFC4180: Common Format and MIME Type for Comma-Separated Values (CSV) Files. https:\/\/www.ietf.org\/rfc\/rfc4180.txt","DOI":"10.17487\/rfc4180"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4302-0244-8_16"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07151-0_13"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITP.2023.27"},{"key":"e_1_3_1_43_1","unstructured":"The PCRE2 Developers. 2024. Perl-compatible Regular Expressions (revised API: PCRE2). https:\/\/pcre2project.github.io\/pcre2\/doc\/html\/index.html. [Online; accessed October 15 2024]."},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-023-09667-1"},{"key":"e_1_3_1_46_1","unstructured":"Vern Paxson. 1987. Flex: The Fast Lexical Analyzer. https:\/\/github.com\/westes\/flex. [Online; accessed October 15 2024]."},{"key":"e_1_3_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640412"},{"key":"e_1_3_1_48_1","unstructured":"XML. 1996. Extensible Markup Language (XML). https:\/\/www.w3.org\/TR\/xml\/ [Online; accessed October 15 2024]."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720498","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720498","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3720498","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T16:28:35Z","timestamp":1787588915000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3720498"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,9]]},"references-count":47,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2025,4,9]]}},"alternative-id":["10.1145\/3720498"],"URL":"https:\/\/doi.org\/10.1145\/3720498","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,9]]},"assertion":[{"value":"2024-10-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}