4551
правка
Преобразование Барроуза-Уилера: различия между версиями
Перейти к навигации
Перейти к поиску
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 22:59, 23 января 2017
, 23 января 2017→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 130: | Строка 130: | ||
== Применение == | == Применение == | ||
Помимо исследования эффективности алгоритмов сжатия на базе bwt, открытым остается весьма важный с практической точки зрения вопрос об эффективности использования памяти при выполнении bwt. Пусть дана строка s длины n над алфавитом S; s и 5 = bwt(s) требуют O(nlog j £ j) бит. К сожалению, алгоритмы с линейным временем выполнения, представленные на рис. 2, используют дополнительные массивы (sa и psi), для хранения которых требуется 0(n log n) бит. Это налагает серьезные ограничения на размер самой большой матрицы bwt, которую можно вычислить в оперативной памяти. Алгоритмы обращения bwt, эфективно использующие память, были предложены в литературе, посвященной индексации сжатого текста [ ], однако задача эффективного использования времени и памяти преобразованием bwt по-прежнему остается нерешенной, хотя для нее были получены обнадеживающие предварительные результаты [8, 10, 13]. | |||
== Экспериментальные результаты == | |||
Экспериментальное исследование нескольких алгоритмов сжатия, основанных на преобразовании bwt, и сравнение их с другими современными способами сжатия приведено в работе [4]. | |||
== Наборы данных == | |||
Наборы данных, использовавшиеся в [ ], доступны по адресу http://www.mfn.unipmn.it/~manzini/boosting. Другие наборы данных для сжатия и индексации сжатого текста можно найти на сайте Pizza&Chili http://pizzachili.di.unipi.it/. | |||
== Ссылка на код == | |||
Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn. unipmn.it/~manzini/boosting) содержит исходный код алгоритмов, протестированных в [ ]. «Облегченный» код для вычисления преобразования bwt и его обращения (без сжатия) доступен по адресу http://www.mfn.unipmn.it/~manzini/lightweight. Код bzip2 доступен по адресу http://www.bzip.org. | |||
== См. также == | |||
* [[Арифметическое кодирование для сжатия данных]] | |||
* [[Усиление степени сжатия текста]] | |||
* [[Сжатый суффиксный массив]] | |||
* [[Индексация сжатого текста]] | |||
* [[Построение суффиксного массива]] | |||
* [[Сжатие таблиц]] | |||
* [[Сжатие и индексирование дерева]] | |||
== Литература == | |||
1. Bell, T.C., Cleary, J.G., Witten, I.H.: Text compression. Prentice Hall, NJ (1990) | |||
2. Bentley, J., Sleator, D., Tarjan, R., Wei, V.: A locally adaptive compression scheme. Commun. ACM 29, 320-330 (1986) | |||
3. Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Tech. Report 124, Digital Equipment Corporation (1994) | |||
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. Ferragina, P., Giancarlo, R., Manzini, G.: The myriad virtues of wavelet trees. In: Proc. 33th International Colloquium on Automata and Languages (ICALP), pp. 561-572. LNCS n. 4051. Springer, Berlin, Heidelberg (2006) | |||
6. Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression in optimal linear time. J. ACM 52, 688-713(2005) | |||
7. Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS), 184-193, Pittsburgh, PA (2005) | |||
8. Hon, W., Sadakane, K., Sung, W.: Breaking a time-and-space barrier in constructing full-text indices. In: Proc. of the 44th IEEE Symposium on Foundations of Computer Science (FOCS),251-260, Cambridge, MA (2003) | |||
9. Kaplan, H., Landau, S., Verbin, E.: A simpler analysis of Burrows-Wheeler-based compression. Theoretical Computer Science 387(3): 220-235 (2007) | |||
10. Karkkainen, J.: Fast BWT in small space by blockwise suffix sorting. Theoretical Computer Science 387(3): 249-257 (2007) | |||
11. Karkkainen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918-936 (2006) | |||
12. Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM 48, 407-430(2001) | |||
13. Na, J.: Linear-time construction of compressed suffix arrays using o(nlogn)-bit working space for large alphabets. In: Proc. 16th Symposium on Combinatorial Pattern Matching (CPM). LNCS, vol. 3537, pp. 57-67. Springer, Berlin (2005) | |||
14. Navarro, G., Makinen, V.: Compressed full text indexes. ACM Comput. Surv.39(1)(2007) | |||
15. Salomon, D.: Data Compression: the Complete Reference, 3rd edn. Springer, New York (2004) | |||
16. Vo, B.D., Vo, K.P.: Using column dependency to compress tables. In: Proc. of IEEE Data Compression Conference (DCC), pp. 92-101, IEEE Computer Society Press (2004) | |||