BPE 的理论分析：字节对编码的压缩效用优化问题被证明为 APX-complete

查看 PDF HTML（实验性）

摘要：字节对编码（Byte-Pair Encoding，BPE）是一种广泛使用的子词分词方法，其起源可追溯到基于文法的文本压缩。它被用于机器翻译或大语言模型（LLM）预训练等多种语言处理任务中，以构建指定规模的词元词典。迄今为止，对 BPE 的大多数评估都是经验性的，其良好实际表现的原因尚未被充分理解。
在本文中，我们聚焦于 BPE 背后的优化问题：寻找一种能够实现最优压缩效用的对编码。我们证明该问题是 APX 完全的，这表明它不太可能具有多项式时间近似方案。这以更强的形式回答了 Zouhar 等人最近提出的一个问题。
在积极的一面，我们证明 BPE 对最优对编码压缩效用的近似比在最坏情况下介于 $1/3$ 与 $(1-e^{-2})/2 \approx 0.4324$ 之间。我们的结果旨在解释 BPE 持续取得的成功，并且据我们所知，这是关于其压缩效用的首批对所有输入均成立的严格保证。

评论：	ESA 2026 论文的扩展版本。v2 中的变更：(1) BPE 近似比的上界约为 0.4324，改进了此前的 0.625；(2) 对 Claim 5 的证明进行了修改，修正了 v1 中的一处不准确之处
主题：	数据结构与算法（cs.DS）；计算与语言（cs.CL）
引用为：	arXiv:2411.08671 [cs.DS]
	（或本版本使用 arXiv:2411.08671v2 [cs.DS]）
	https://doi.org/10.48550/arXiv.2411.08671 由 DataCite 颁发的 arXiv DOI

提交历史

来自：László Kozma [查看电子邮件]
[v1] 2024年11月13日星期三 15:04:02 UTC（24 KB）
[v2] 2026年10月30日星期五 18:26:29 UTC（258 KB）