本文证明了两种标记化变体的NP完全性。
标记化被定义为将数据集压缩到最多δ个符号的问题,可以通过两种方式实现:
1. 直接查找词汇表(直接标记化)。
2. 选择一系列合并操作(自底向上标记化)。
该研究结果表明,标记化问题在计算上是复杂的,对于理解和解决标记化问题在不同场景下的复杂性具有重要意义。