arXiv cs.CL· Kundan Baliga, Aiden Xie, Aditya Byju·· 11 小时前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 松弛是紧的，更好界必须利用最优解更多结构；论文还精确求出两次合并的最坏情况比值，并对三次合并给出界，同时将问题归结为单一不等式。
正文 · 原文
Abstract:Byte-Pair Encoding (BPE) builds a tokeniser by repeatedly merging a most frequent adjacent pair of symbols; its utility is the total reduction in string length achieved by $k$ merges. It was known that this greedy rule achieves at least a third of the optimal reduction. We prove that it always achieves at least 0.361 of the optimal reduction in string length, for every string, every budget and every tie-breaking rule; this is the first improvement of the bound one third. We also explain why one third was a barrier: the pair-packing relaxation behind it is tight, so a better bound must use more of the optimum's structure. When greedy destroys three of the optimum's merge points at once, one of them can usually be moved next door, because all copies of a rule of the optimum look alike; the remaining cases are paid for later. Along the way we determine the worst-case ratio for two merges exactly, bound it for three, and isolate a single inequality that would settle the problem.
| Comments: | 27 pages, 5 figures. Code and certificates: this https URL |
| Subjects: | Data Structures and Algorithms (cs.DS); Computation and Language (cs.CL) |
| MSC classes: | 68W25, 68P30, 68W32 |
| ACM classes: | F.2.2; E.4; I.2.7 |
| Cite as: | arXiv:2611.08671 [cs.DS] |
| (or arXiv:2611.08671v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2611.08671 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Kundan Baliga [view email]
[v1]
Thu, 5 Nov 2026 20:27:56 UTC (42 KB)
来源：arXiv cs.CL · arxiv.org