arXiv cs.CL· Kundan Baliga, Aiden Xie, Aditya Byju·· 10 小时前AI 评分18
二元串上配对合并分词难以近似，一元数据集上强 NP 难
Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets
AI 导读
研究证明，除非 P = NP，否则不存在多项式时间算法能在 c·n/log n 因子内近似选择 k 次 BPE 式合并（对单个二元串即成立），核心思路是把顶点覆盖间隙转化为语法规模间隙。
正文 · AI 翻译
摘要：诸如字节对编码（BPE）之类的分词器通过反复将相邻的一对符号合并为一个新符号来缩短文本；更少的 token 意味着更少的计算。我们研究是否存在一种高效算法，能够选择 $k$ 次合并，使长度为 $n$ 的字符串几乎尽可能短；什么都不做已经处于因子 $n$ 之内。我们证明，除非 P = NP，否则不存在多项式时间算法能达到因子 $c\,n/\log n$ 以内，其中 $c>0$ 为某个常数，这已经对单个二进制字符串以及替换每次出现的 BPE 式合并成立。关键思想是：$k$ 次合并构成一个含 $k$ 条规则的文法：顶点覆盖的差距变成文法大小的差距，我们通过重新标记的副本来放大它，用二进制编码，并用显式合并来实现。对于可以跳过某些出现的合并，一个简单算法可达到 $O(n/\log\log n)$，并且除非 coNP $\subseteq$ NP/poly，否则任何 Karp 归约都无法证明超出 $n/\log n$ 阶的困难性。在单字母表上，Kastreva 等人留下的两个分词问题在含重复字符串的数据集上都是强 NP 完全的。
| 评论： | 34 页，11 幅图。代码与证书：此 https URL |
| 主题： | 数据结构与算法（cs.DS）；计算复杂性（cs.CC）；计算与语言（cs.CL） |
| MSC 分类： | 68Q17, 68Q25, 68W25, 68T50 |
| ACM 分类： | F.2.2; F.1.3; I.2.7 |
| 引用为： | arXiv:2611.13568 [cs.DS] |
| （或 arXiv:2611.13568v1 [cs.DS] 对应此版本） | |
| https://doi.org/10.48550/arXiv.2611.13568 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Aditya Byju [查看电子邮件]
[v1]
2026 年 11 月 10 日星期二 04:37:23 UTC（72 KB）
来源：arXiv cs.CL · arxiv.org