二进制分词的难解性与双标准近似算法
Tokenization: Hardness and Bicriteria Approximation Algorithms
AI 导读
一篇 arXiv 论文研究二进制分词问题：给定二进制语料和词表预算 K，选出至多 K 个子串以最小化表示语料所需 token 总数。论文证明对任意固定 ε∈(0,1)，该问题在 P≠NP 假设下不存在多项式时间 n^{1-ε} 近似算法，并给出 (γ,γ) 双标准近似算法，γ=√M·log n，输出词表不超过 γK、token 数不超过 γOPT_K。
正文 · 原文
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