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

Помимо исследования эффективности алгоритмов сжатия на базе bwt, открытым остается весьма важный с практической точки зрения вопрос об эффективности использования памяти при выполнении bwt. Пусть дана строка s длины n над алфавитом <math>\Sigma \;</math>; s и <math>\hat{s} = bwt(s) \;</math> требуют <math>O(n log \; | \Sigma |)</math> бит. К сожалению, алгоритмы с линейным временем выполнения, представленные на рис. 2, используют дополнительные массивы (sa и psi), для хранения которых требуется <math>\Theta (n log \; n)</math> бит. Это налагает серьезные ограничения на размер самой большой матрицы bwt, которую можно вычислить в оперативной памяти. Алгоритмы обращения bwt, эфективно использующие память, были предложены в литературе, посвященной индексации сжатого текста [14], однако задача эффективного использования времени и памяти преобразованием bwt по-прежнему остается нерешенной, хотя для нее были получены обнадеживающие предварительные результаты [8, 10, 13].