邀请爱康集团做客直播间，介绍爱康携手鸿蒙生态共建全流程健康体系

研究人员发表了一篇论文，通过数学证明表明，要找到一种“最优”的分词方法（能够把一段文字压缩得尽可能短，同时保留所有信息），是一个“NP完备问题”。简单来说，这意味着分词的计算难度非常大，几乎不可能用计算机快速解决。

https://arxiv.org/abs/2412.15210

token 化（分词、tokenization）是自然语言处理（比如聊天机器人或翻译工具）中非常基础的一步，它把句子拆分成更小的单元（称为“子词”或“符号”）。token 化有两种变体，直接 token 化和自底向上的 token 化，直接分词通过优化词汇表来压缩数据，自底向上的分词则通过一系列合并操作实现压缩。

• 直接分词：先设计一个词汇表（比如定义哪些单词或符号可以直接使用），然后用这个词汇表去压缩文字。
• 自底向上的分词：从小单位（比如字母或字符）开始，逐步合并成更大的单元。

这篇论文通过对这两种 token 化的研究，表明 token 化问题是 NP 完备问题。这意味着，如果我们要做到最优分词，其实非常困难。

论文通过与“最大2-可满足性问题（max-2-SAT）”的归约，也就是说，找到最优分词器的问题至少和max-2-SAT问题一样难，而后者已知是NP完备的，从而证明了上述分词问题的NP完备性，表明无法找到高效的算法来解决这些问题。

分词与压缩算法之间存在紧密联系，但两者的目标和优化参数有所不同：分词优化的是生成的文本长度，而压缩还需要考虑存储的压缩信息大小。

研究指出，现有分词算法（如字节对编码 BPE 和 单元语言模型 UnigramLM）是近似算法，未来研究应聚焦于改进这些算法或设计新的近似算法。

NP 完备（NP-complete）是计算机科学中的一个术语，用来描述一种问题的计算难度。

---

基本概念：

P问题：

• 可以在多项式时间内（polynomial time，即时间复杂度是一个多项式函数）通过算法解决的问题。
• 例如：排序一个数组，找到某个数字是否在数组中。

NP问题：

• 可以在多项式时间内验证解是否正确的问题。
• 举例：猜一个谜题的答案，如果你已经知道一个答案，你可以快速验证它对不对，但找到这个答案可能很难。

NP 完备（NP-complete）：

• 这是NP问题中最难的一类。如果一个问题是NP完备的，它既是NP问题（解可以快速验证），又是NP难问题（比所有其他NP问题都难）。
• 这意味着：如果某一天有人找到一个NP完备问题的快速解决方法，所有NP问题都可以快速解决。

---

通俗理解：

生活中的例子：

• 想象你在拼图，目标是拼出一幅图画（问题的解）。如果别人告诉你答案，你很快能检查拼图对不对（验证解），但要从头自己拼好可能会很难，需要试很多种组合。
• NP 完备问题类似于这种拼图问题：难找到答案，但验证答案很快。

难点的核心：

• 找到解很难，可能需要试无数种可能性。
• 一旦有了解，验证它是否正确却很快。

---

NP 完备的意义：

1. 如果有一个高效算法解决NP完备问题，那么所有NP问题都能高效解决。这就是“P=NP？”这个著名未解问题的核心。
2. 如果问题是NP完备的，它就被认为是计算上“最难的”问题之一，通常我们会寻找近似解而不是精确解。

---

和分词问题的关系：

报告中提到，分词问题被证明是NP完备问题，这意味着：

• 找到最优分词的方法非常困难（需要试无数种组合）。
• 但如果有人给出一个分词方案，可以快速验证它是否达到了目标（比如是否压缩到某个长度）。