Tokenisierungsproblem als NP-vollständig bewiesen – Herausforderungen der Datenkompression verdoppelt
2024-12-22
Ein auf arXiv veröffentlichter Artikel beweist die NP-Vollständigkeit von zwei Varianten der Tokenisierung, definiert als das Problem, einen Datensatz auf höchstens δ Symbole zu komprimieren, entweder durch direktes Finden eines Vokabulars (direkte Tokenisierung) oder durch Auswahl einer Folge von Merge-Operationen (Bottom-up-Tokenisierung). Diese Erkenntnis hat erhebliche Auswirkungen auf die Datenkompression und die Verarbeitung natürlicher Sprache und unterstreicht die immense Herausforderung, das Tokenisierungsproblem für große Datensätze effizient zu lösen.