arXiv cs.CL· Kundan Baliga, Aiden Xie, Aditya Byju·· 10 小时前AI 评分20
贪心 Byte-Pair Encoding 的压缩率下界提升至最优的 0.361
Greedy Byte-Pair Encoding Achieves at Least 0.361 of the Optimal Compression
AI 导读
研究证明贪心 BPE 对任意字符串、任意合并预算和任意平局规则，都能达到最优字符串长度缩减量的至少 0.361，首次改进了此前三分之一的下界。作者指出三分之一是瓶颈，因为其背后的 pair-packing 松弛是紧的，更好界必须利用最优解更多结构；论文还精确求出两次合并的最坏情况比值，并对三次合并给出界，同时将问题归结为单一不等式。
正文 · AI 翻译
摘要：字节对编码（BPE）通过反复合并最频繁的相邻符号对来构建分词器；其效用是 $k$ 次合并所实现的字符串总长度缩减量。已知该贪心规则至少能达到最优缩减量的三分之一。我们证明，对于任意字符串、任意预算和任意平局打破规则，它总能达到字符串长度最优缩减量的至少 0.361；这是对三分之一这一界限的首次改进。我们还解释了为何三分之一曾是一道屏障：其背后的配对打包松弛是紧的，因此更好的界限必须更多地利用最优解的结构。当贪心一次性破坏最优解的三个合并点时，其中通常有一个可以移到相邻位置，因为最优解中某条规则的所有副本看起来都一样；其余情况则留待后续补偿。在此过程中，我们精确确定了两次合并的最坏情况比值，对三次合并给出了界限，并分离出一个可以解决该问题的单一不等式。
| 评论： | 27 页，5 幅图。代码与证书：此 https URL |
| 主题： | 数据结构与算法（cs.DS）；计算与语言（cs.CL） |
| MSC 分类号： | 68W25, 68P30, 68W32 |
| ACM 分类号： | F.2.2; E.4; I.2.7 |
| 引用为： | arXiv:2611.08671 [cs.DS] |
| （或 arXiv:2611.08671v1 [cs.DS] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.08671 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Kundan Baliga [查看电子邮件]
[v1]
2026 年 11 月 5 日星期四 20:27:56 UTC（42 KB）
来源：arXiv cs.CL · arxiv.org