arXiv cs.AI· Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran·· 1 天前AI 评分18
二元分词问题的计算难度与双标准近似算法
Tokenization: Hardness and Bicriteria Approximation Algorithms
AI 导读
研究证明二元分词（Binary Tokenization）问题不存在多项式时间的 n^{1-ε} 近似算法，除非 P=NP。为此提出多项式时间的 (γ,γ) 双标准近似算法，γ=√M·log n，输出词表规模不超过 γK、token 数不超过 γ·OPT_K；存储预算变体在 2≤B<n 时获得 (O(log n log B), O(log n log B)) 双标准近似。
正文 · 原文
Abstract:We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(\gamma,\gamma)$-bicriteria algorithm, with $\gamma = \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $\gamma K$ with number of tokens at most $\gamma {\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.
| Subjects: | Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC) |
| Cite as: | arXiv:2611.15074 [cs.DS] |
| (or arXiv:2611.15074v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2611.15074 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Vinodchandran Variyam [view email]
[v1]
Wed, 11 Nov 2026 05:49:07 UTC (26 KB)
来源：arXiv cs.AI · arxiv.org