Tokenisation over Bounded Alphabets is Hard
本文证明了在包括二进制和一元在内的有限字母表上的分词问题在本质上是 NP 完全且 APX 硬的，从而确立了其计算不可解性是一个内在障碍而非大输入字母表的产物，并解释了当前实际算法中启发式方法的必要性。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下，你正试图给一位朋友发送一条秘密信息，但你唯一的发送方式就是将你的词语拆解成微小的、预先批准的块。如果你发送“superduper”，你可能必须将其拆分为“super”和“duper”，而不是整个单词，因为你朋友的字典里只有这两个部分。这就是分词（tokenization）的核心，它是教计算机理解人类语言的第一步。在计算机阅读一个句子之前，它必须将其切分成这些易于处理的“标记”（就像乐高积木一样）。目标是以使用最少积木的方式来拆解文本，从而使信息更短、传输更快。这被称为压缩（compression）。如果你能将一本书压缩成更少的积木，计算机就能更快地阅读并更高效地学习。多年来，科学家们一直在构建聪明的、贪婪的算法——就像一个孩子尽可能抓取能找到的最大乐高积木一样——来自动完成这种拆解工作。但一个大问题一直萦绕不去：是否存在一种完美的、在数学上最优的方法来拆解任何文本，还是说我们只能停留在“足够好”的猜测上？
这篇题为《有界字母表上的分词是困难的》（Tokenisation Over Bounded Alphabets Is Hard）的论文，深入探讨了这个问题的核心。作者们是一支来自苏黎世联邦理工学院（ETH Zürich）和索非亚大学的研究团队，他们试图证明，即使规则很简单，寻找那种完美拆解方法对计算机来说实际上也是一场噩梦。他们专注于两种主要的拆解方式：直接分词（Direct Tokenisation），即你一次性选出最好的积木集（词汇表）；以及自底向上分词（Bottom-Up Tokenisation），即你从单个字母开始，不断将配对的部分粘合在一起，直到用完所有的胶水（合并）。他们故事中的大转折在于，他们测试这些方法时，并非针对人类所有可能发音的无限且混乱的字母表，而是针对计算机实际使用的微小、固定的集合：二进制（只有0和1，就像一个开关）和一元（unary）（只有一个单一符号，就像一串完全相同的珠子）。
该论文的主要发现是一个响亮的“不，你无法轻易找到完美的解决方案”。作者证明，即使是在最简单的字母表下——比如一个仅由零和一组成的世界——寻找压缩文本的最优方式也是 NP-完全（NP-complete） 且 APX-难（APX-hard） 的。用通俗的话说，这意味着无论你投入多少计算能力，都不存在一种快速、高效的算法能够保证得到最好的结果。这不仅仅是问题本身很难；而是它在本质上就是困难的。论文明确排除了这样一种观点，即难度源于人类语言的复杂性或巨大的字母表。相反，他们证明了即使在最简单、受限最严苛的情景下，这种障碍依然存在。此外，他们还证明了除非解决一个重大的数学谜题（P = NP），否则你无法在合理的时间内获得“足够接近”完美答案的解；不存在可以在合理时间内获得任意接近最优解的多项式时间近似方案（PTAS）。
研究人员还探讨了**一元（unary）的情况，即字母表只有一个符号（想象一条完全由字母“a”组成的短消息）。你可能会想：“如果我只有一个字母，这能有多难呢？”令人惊讶的是，他们证明了即使在这种情况下，寻找最优拆解方式也是强NP完全（strongly NP-complete）**的。这是一个沉重的数学结论，表明这种难度不仅仅是大型数据集带来的特质；它已经植根于尝试优化压缩文本的逻辑之中。
那么，这对未来意味着什么？这篇论文并没有提供一种新的、神奇的算法来解决这个问题。相反，它解释了为什么我们今天使用的工具，如 BPE（字节对编码）和 UnigramLM，被迫成为**启发式（heuristic）**的——这意味着它们使用聪明的捷径和猜测，而不是计算出完美的答案。作者认为，由于寻找完美答案在计算上是不可能的，研究人员应该停止追逐分词器的“圣杯”，转而专注于构建更好的、可证明有效的近似方法。通往完美的门已经锁上了，钥匙并不存在；我们能做的最好的事情，就是学会挑选我们现有的最好的开锁工具。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。