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

Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n) ) бит рабочего пространства при помощи, например, алгоритма из [ ]. Суффиксный массив представляет собой строку целых чисел sa[1, n], такую, что для i = 1, ... , n значением s[sa[i], n - 1] является i-й суффикс s в лексикографическом порядке. Поскольку префиксом каждой строки матрицы <math>\mathcal{M} \;</math> является уникальный суффикс s, за которым идет специальный символ $, суффиксный массив обеспечивает упорядочение строк в <math>\mathcal{M} \;</math>. Следовательно, bwt(s) можно вычислить из sa за линейное время при помощи процедуры sa2bwt на рис. 2. □

'''Теорема 7. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. При наличии bwt(s) строка s может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.'''

Доказательство. Алгоритм вычисления s практически дословно воспроизводит процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения <math>\Psi \;</math> вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует счетчик массива, представляющий собой «компактное» представление F. В момент начала работы процедуры для любого символа <math>c \in \Sigma \;</math> счетчик count[c] выдает индекс первой строки матрицы <math>\mathcal{M} \;</math>, префиксом которой является c. Например, на рис. 1 count[i] = 1, count[m] = 5 и т.д. В основной части процедуры bwt2psi с циклом сканируется счетчик массива bwt, и значение count[c] увеличивается каждый раз при обнаружении вхождения символа c (строка 6). Строка 6 также присваивает переменной h индекс <math>\ell</math>-го вхождения элемента c в F. Согласно лемме 3, строка 7 корректно сохраняет в psi[h] значение <math>i = \Psi(h) \;</math>. После вычисления массива psi строка s восстанавливается при помощи процедуры psi2text на рис. 2, корректность которой непосредственно следует из теоремы 5.

Для того чтобы использовать это свойство, Барроуз и Уилер предложили обрабатывать строку <math>\hat{s} \;</math> с использованием кодирования по модели «движение к началу» (move-to-front) [ ] (процедура mtf). mtf кодирует каждый символ количеством различных символов, встретившихся после предыдущего вхождения этого же символа. Для этого mtf ведет список символов, упорядоченный по давности вхождения; когда встречается следующий символ, алгоритм выводит его текущий ранг и перемещает его в начало списка. Заметим, что mtf вычисляет строку, имеющую ту же длину, что и <math>\hat{s} \;</math> и в случае, если <math>\hat{s} \;</math> является локально гомогенной, строка <math>mtf(\hat{s}) \;</math> будет в основном состоять из целых числе малой величины. ''[Если s – текст на английском языке, <math>mtf(\hat{s}) \;</math> обычно содержит более 50% нулей.]''  

Барроуз и Уилер были заинтересованы главным образом в разработке алгоритма с высокой практической эффективностью. И в самом деле, их простая версия превосходила (по критерию коэффициента сжатия) инструмент gzip, бывший в то время стандартом сжатия бех потерь. Через несколько лет после публикации bwt в работах [9, 12] было показано, что коэффициент сжатия алгоритма Барроуза-Уилера может быть ограничен в терминах эмпирической энтропии k-го порядка входной строки для любого <math>k \ge 0 \;</math>. К примеру, Каплан и др. [9] показали, что для любой входной строки s и вещественного числа <math>\mu > 1 \;</math> длина сжатой строки ограничена <math>\mu \; n \; H_k (s) + n \; log(\zeta (\mu)) + \mu \; g_k + O(log \; n)</math> бит, где <math>\zeta (\mu) \;</math> – стандартная дзета-функция, а <math>g_k \;</math> – функция, зависящая только от k и от размера <math>\Sigma \;</math>. Эта граница ''поточечно'' верна для любой строки s, ''одновременно'' для любых <math>k \ge O \;</math> и <math>\mu > 1 \;</math>; и это весьма примечательно, поскольку ни для одного другого алгоритма сжатия аналогичные границы не были доказаны. Теоретическое изучение эффективности алгоритмов сжатия на базе преобразования bwt в настоящее время является областью активных исследований. Дополнительную информацию см. в списке рекомендованной литературы.

После выхода основополагающей работы Барроуза и Уилера многие исследователи предложили собственные алгоритмы сжатия на базе bwt (см. [4, 5] и ссылки в этих статьях). Особенно интересны в практическом плане результаты работы [6], демонстрирующие, что преобразование bwt может быть использовано для разработки «[[Усиление_степени_сжатия_текста|усилителей сжатия]]» (или механизмов повышения степени сжатия), которые служат инструментов повышения эффективности других алгоритмов сжатия вполне определенным и измеримым образом.

Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn. unipmn.it/~manzini/boosting) содержит исходный код алгоритмов, протестированных в [ ]. «Облегченный» код для вычисления преобразования bwt и его обращения (без сжатия) доступен по адресу http://www.mfn.unipmn.it/~manzini/lightweight. Код bzip2 доступен по адресу http://www.bzip.org.