Le problème de la tokenisation prouvé NP-complet, doublant les défis de la compression de données

Un article publié sur arXiv prouve la complétude NP de deux variantes de la tokenisation, définie comme le problème de compression d'un ensemble de données à au plus δ symboles, soit en trouvant un vocabulaire directement (tokenisation directe), soit en sélectionnant une séquence d'opérations de fusion (tokenisation ascendante). Cette découverte a des implications significatives pour la compression de données et le traitement du langage naturel, soulignant l'immense défi de résoudre efficacement le problème de la tokenisation pour les ensembles de données à grande échelle.