4551
правка
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 12:44, 13 января 2017
, 13 января 2017→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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) | |||