Преобразование Барроуза-Уилера: различия между версиями

Перейти к навигации Перейти к поиску
Строка 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)
Источник — http://pco.iis.nsk.su/wega/index.php/Преобразование_Барроуза-Уилера