Усиление степени сжатия текста: различия между версиями

Парадигму усиления можно обобщить следующим образом. Пусть дан алгоритм компрессии A; необходимо найти перестановку P для символов строки s и стратегию разбиения, такие, чтобы примененный к ним подход к усилению минимизировал размер выходных данных. Выше были приведены убедительные свидетельства того, что преобразование Барроуза-Уилера является элегантной и эффективной перестановкой P. Как ни удивительно, другие классические задачи сжатия данных также вписываются в эту структуру: поиск кратчайшей общей надстроки (эта задача является MAX-SNP-сложной), кодирование с переменной длиной строки для множества строк (полиномиально разрешимая задача), LZ77 и нахождение минимального количества фраз (также MAX-SNP-сложная). Таким образом, подход к усилению является достаточно общим, чтобы заслуживать дальнейших теоретических и практических исследований [5].