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

Перейти к навигации Перейти к поиску
Строка 109: Строка 109:


== Открытые вопросы ==
== Открытые вопросы ==
Парадигму усиления можно обобщить следующим образом. Пусть дан алгоритм компрессии A; необходимо найти перестановку P для символов строки s и стратегию разбиения, такие, чтобы примененный к ним подход к усилению минимизировал размер выходных данных. Выше были приведены убедительные свидетельства того, что преобразование Барроуза-Уилера является элегантной и эффективной перестановкой P. Как ни удивительно, другие классические задачи сжатия данных также вписываются в эту структуру: поиск кратчайшей общей надстроки (эта задача является MAX-SNP-сложной), кодирование с переменной длиной строки для множества строк (полиномиально разрешимая задача), LZ77 и нахождение минимального количества фраз (также MAX-SNP-сложная). Таким образом, подход к усилению является достаточно общим, чтобы заслуживать дальнейших теоретических и практических исследований [5].
== Экспериментальные результаты ==
Исследование нескольких алгоритмов сжатия, основанных на усилении, и сравнение их с другими современными способами сжатия приведено в работе [ ]. Эксперименты показывают, что техника усиления является более надежной по сравнению с другими подходами и хорошо работает даже с менее эффективными алгоритмами сжатия нулевого порядка. Однако положительные результаты достигаются за счет использования большего количества ресурсов (времени и памяти).
== Наборы данных ==
Наборы данных, использовавшиеся в [ ], доступны по адресу http://www.mfn.unipmn.it/~manzini/boosting. Другие наборы данных для сжатия и индексирования можно найти на сайте Pizza&Chili http://pizzachili.di.unipi.it/.
== Ссылка на код ==
Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn. unipmn.it/~manzini/boosting) содержит исходный код всех алгоритмов, протестированных в [ ]. Этот код организован в виде библиотеки с высокой степенью модульности, которая может использоваться любым алгоритмом сжатия и не требует знания алгоритма bwt или процедуры усиления.
== См. также ==
*' [[Арифметическое кодирование для сжатия данных]]
► Преобразование Барроуза-Уилера
► Индексация сжатого текста
► Сжатие таблиц
► Сжатие и индексирование дерева
== Литература ==
1. Bell, T.C., Cleary, J.G., Witten, I.H.: Text compression. Prentice Hall, NJ (1990)
2. Burrows, M. Wheeler, D.: A block sorting lossless data compression algorithm. Tech. Report 124, Digital Equipment Corporation (1994)
3. Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression inoptimal lineartime.J.ACM 52,688-713 (2005)
4. Ferragina, P., Giancarlo, R., Manzini, G.: The engineering of a compression boosting library: Theory vs practice in bwt compression. In: Proc. 14th European Symposium on Algorithms (ESA). LNCS, vol. 4168, pp. 756-767. Springer, Berlin (2006)
5. Giancarlo, R., Restivo, A., Sciortino, M.: From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization. Theor. Comput. Sci. 387(3):236-248 (2007)
6. Karp, R., Pippenger, N., Sipser, M.: A Time-Randomness trade-off. In: Proc. Conference on Probabilistic Computational Complexity, AMS, 1985, pp. 150-159
7. Manzini, G.: An analysis of the Burrows-Wheeler transform. J.ACM 48,407-430 (2001)
8. Navarro, G., Makinen, V.: Compressed full text indexes. ACM Comput. Surv.39(1) (2007)
9. Salomon, D.: Data Compression: the Complete Reference, 4th edn. Springer, London (2004)
10. Schapire, R.E.: The strength of weak learnability. Mach. Learn. 2,197-227 (1990)
Источник — http://pco.iis.nsk.su/wega/index.php/Усиление_степени_сжатия_текста