证明了固定字母表下的分词问题本质困难，解释了为何现有算法只能靠启发式方法。
Tokenisation over Bounded Alphabets is Hard
- 在有限字符集下研究分词，区分自底向上合并与直接选词典两种模式。
- 即使二进制字母表，两种模式均属NP难且无多项式时间近似方案。
- 结果揭示分词计算困难是根本性障碍，推动发展近似算法研究。
近期研究指出分词是NP完全问题，但假设输入具有无限大字母表，这不切实际。本文分析固定大小字母表下的分词问题，考虑两种自然变体：自底向上分词（需选择一系列合并操作）和直接分词（需选择使数据集压缩最优的词典）。我们证明，即使在二进制字母表下，两种变体均为NP完全且APX难，因此不存在多项式时间近似方案（除非P=NP）。此外，直接分词在单位字母表下仍为NP完全。这些结果表明分词的计算困难并非源于大字母表或复杂构造，而是根本性障碍。该结论解释了为何当前实用算法如BPE和UnigramLM依赖启发式方法，并指明近似算法将成为分词研究的重要方向。
原文摘要 · Abstract (English)
Recent works have shown that tokenisation is NP-complete. However, these works assume tokenisation is applied to inputs with unboundedly large alphabets -- an unrealistic assumption, given that in practice tokenisers operate over fixed-size alphabets, such as bytes or Unicode-characters. We close this gap by analysing tokenisation over bounded alphabets, considering two natural variants: bottomup tokenisation and direct tokenisation, where we must, respectively, select a sequence of merge operations or a vocabulary whose application optimally compresses a dataset. We prove that even with binary alphabets, both variants are not only NP-complete, but also APX-hard and thus admit no polynomial-time approximation scheme (unless P=NP). We further show that direct tokenisation remains NP-complete even when applied to unary alphabets. These results establish that the computational intractability of tokenisation is not an artifact of large alphabets or complex constructions, but a fundamental barrier. Overall, our results explain why current practical algorithms such as BPE and UnigramLM are heuristic, and point toward approximation algorithms being an important path going forward for tokenisation research.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。