Le problème de la tokenisation prouvé NP-complet, doublant les défis de la compression de données
2024-12-22
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.