Lune

OOPSLA2025Top-tier venue

Efficient Algorithms for the Uniform Tokenization Problem

Angela W. Li, Konstantinos Mamouras

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Linear Matching of JavaScript Regular Expressions cites Regular Expression Matching using Bit Vector Automata
  • Linear Matching of JavaScript Regular Expressions cites Efficient Matching of Regular Expressions with Lookaround Assertions
  • Static Analysis for Efficient Streaming Tokenization cites BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions
  • Static Analysis for Efficient Streaming Tokenization cites Software-hardware codesign for efficient in-memory regular pattern matching
  • Static Analysis for Efficient Streaming Tokenization cites Streaming Validation of JSON Documents Against Schemas
  • Static Analysis for Efficient Streaming Tokenization cites Regular Expression Matching using Bit Vector Automata
  • Static Analysis for Efficient Streaming Tokenization cites Efficient Matching of Regular Expressions with Lookaround Assertions
  • BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions cites Software-hardware codesign for efficient in-memory regular pattern matching
  • BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions cites Regular Expression Matching using Bit Vector Automata
  • BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions cites Efficient Matching of Regular Expressions with Lookaround Assertions
  • Streaming Validation of JSON Documents Against Schemas cites Software-hardware codesign for efficient in-memory regular pattern matching
  • Streaming Validation of JSON Documents Against Schemas cites Regular Expression Matching using Bit Vector Automata
  • Streaming Validation of JSON Documents Against Schemas cites Efficient Matching of Regular Expressions with Lookaround Assertions
  • Regular Expression Matching using Bit Vector Automata cites Software-hardware codesign for efficient in-memory regular pattern matching
  • Efficient Matching of Regular Expressions with Lookaround Assertions cites Software-hardware codesign for efficient in-memory regular pattern matching
  • Efficient Matching of Regular Expressions with Lookaround Assertions cites Regular Expression Matching using Bit Vector Automata
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Streaming Validation of JSON Documents Against SchemasAlexis Le Glaunec, Angela W. Li, Konstantinos MamourasVLDB 2026 · 2 citations
  2. Static Analysis for Efficient Streaming TokenizationAngela W. Li, Yudi Yang, Konstantinos MamourasASPLOS 2026 · 1 citation
  3. Formally Verified Linear-Time Invertible LexingSamuel Chassot, Viktor KuncakCAV 2026

Builds on6

  1. Software-hardware codesign for efficient in-memory regular pattern matchingLingkun Kong, Qixuan Yu, Agnishom Chattopadhyay, Alexis Le Glaunec et al.PLDI 2022 · 23 citations
  2. Regular Expression Matching using Bit Vector AutomataAlexis Le Glaunec, Lingkun Kong, Konstantinos MamourasOOPSLA 2023 · 22 citations
  3. Efficient Matching of Regular Expressions with Lookaround AssertionsKonstantinos Mamouras, Agnishom ChattopadhyayPOPL 2024 · 19 citations
  4. Linear Matching of JavaScript Regular ExpressionsAurèle Barrière, Clément Pit-ClaudelPLDI 2024 · 11 citations
  5. BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded RepetitionsZiyuan Wen, Lingkun Kong, Alexis Le Glaunec, Konstantinos Mamouras et al.ASPLOS 2024 · 11 citations

Related papers

  1. A Partition Cover Approach to TokenizationJia Peng Lim, Shawn Tan, Davin Choo, Hady W. LauwNeurIPS 2025 · 6 citations
  2. Tokenisation is NP-CompletePhilip Whittington, Gregor Bachmann, Tiago PimentelACL 2025 · 6 citations
  3. LoPT: Lossless Parallel Tokenization Acceleration for Long Context Inference of Large Language ModelWei Shao, Lingchao Zheng, Pengyu Wang, Peizhen Zheng et al.ACL 2026 · 1 citation
  4. Tokenisation over Bounded Alphabets is HardVioleta Kastreva, Philip Whittington, Dennis Komm, Tiago PimentelICLR 2026 · 6 citations
  5. An Efficient Algorithm for Streaming BPE TokenizationKonstantinos Mamouras, Angela W. Li, Yudi YangPLDI 2026
Dusk over the sea between two cliffs drawn in fine vertical lines