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)) 双标准近似。
正文 · AI 翻译
摘要：我们研究二元分词（Binary Tokenization）：给定一个由 $\{0,1\}$ 上的二进制串组成的语料库以及一个词汇表预算 $K$，选择至多 $K$ 个子串（称为词汇表），以最小化表示该语料库所需的总 token 数。基本符号 $0$ 和 $1$ 始终可用，且每个文档必须单独分词。设 $n$ 表示语料库总长度，$M$ 表示最大文档长度，我们证明：对于任意固定的 $\varepsilon\in(0,1)$，除非 $\mathsf{P}=\mathsf{NP}$，否则二元分词问题不存在多项式时间的 $n^{1-\varepsilon}$-近似算法。为补充该困难性结果，我们给出一个多项式时间的 $(\gamma,\gamma)$-双准则算法，其中 $\gamma = \sqrt{M}\log n$：该算法输出的词汇表大小至多为 $\gamma K$，token 数至多为 $\gamma {\rm OPT}_K$，其中 ${\rm OPT}_K$ 是在原始预算 $K$ 下的最优 token 数。我们还研究了一种存储预算变体，其中所选子串的长度之和以 $B$ 为界。对于 $2\le B<n$，我们得到一个 $(O(\log n\log B),O(\log n\log B))$-双准则近似算法。
| 学科： | 数据结构与算法（cs.DS）；人工智能（cs.AI）；计算复杂性（cs.CC） |
| 引用为： | arXiv:2611.15074 [cs.DS] |
| （或 arXiv:2611.15074v1 [cs.DS] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.15074 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Vinodchandran Variyam [查看电子邮件]
[v1]
2026年11月11日星期三 05:49:07 UTC（26 KB）
来源：arXiv cs.AI · arxiv.org