BriefGPT.xyz
Dec, 2024
标记化是NP-完全的
Tokenisation is NP-Complete
HTML
PDF
Philip Whittington, Gregor Bachmann, Tiago Pimentel
TL;DR
本研究解决了标记化过程中的NP-完全性问题，指出将数据集压缩至最多$\delta$个符号的两种变体都属于NP-完全问题。该论文的重要发现是，通过直接寻找词汇或选择合并操作进行的底向标记化均展示了其计算复杂性，对算法设计和数据压缩领域具有重要的影响。
Abstract
In this work, we prove the
NP-Completeness
of two variants of
Tokenisation
, defined as the problem of compressing a dataset to at most $\delta$ symbols by either finding a vocabulary directly (direct
→