一句话：提出两种线性时间、低内存的 tokenization 算法，并验证优化版本在实际负载上优于先前方法。
论文研究 uniform tokenization 问题：tokenization（又称 scanning 或 lexing）既用于编译期程序的词法分析，也用于非结构化或半结构化数据（如 JSON、CSV）的抽取与分析。作者提出两种算法，均在线性时间内完成（以输入文本长度为度量），且不需要使用大量内存。为验证实用性，作者对其中一个算法进行优化，并在实际 tokenization 工作负载上与先前方法比较，表明该优化版本表现良好。该工作关注在保持线性时间的同时降低内存开销，为编译前端和数据抽取中的词法/扫描任务提供高效方案。
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.
@article{paperbot3163,
title = {Efficient Algorithms for the Uniform Tokenization Problem},
author = {Angela W. Li and Konstantinos Mamouras},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA1},
year = {2025},
doi = {10.1145/3720498}
}