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

Барроуз и Уилер были заинтересованы главным образом в разработке алгоритма с высокой практической эффективностью. И в самом деле, их простая версия превосходила (по критерию коэффициента сжатия) инструмент gzip, бывший в то время стандартом сжатия бех потерь. Через несколько лет после публикации bwt в работах [9, 12] было показано, что коэффициент сжатия алгоритма Барроуза-Уилера может быть ограничен в терминах эмпирической энтропии k-го порядка входной строки для любого k > 0. К примеру, Каплан и др. [ ] показали, что для любой входной строки s и вещественного числа ji > 1 длина сжатой строки ограничена jinH^ (s) + n log(f (//.)) + jigi + O(logn) бит, где f (//.) – стандартная standard дзета-функция, а gk – функция, зависящая только от k и от размера S. Эта граница поточечно верна для любой строки s, одновременно для любых к > O и /x > 1; и это весьма примечательно, поскольку ни для одного другого алгоритма сжатия аналогичные границы не были доказаны. Теоретическое изучение эффективности алгоритмов сжатия на базе преобразования bwt в настоящее время является областью активных исследований. Дополнительную информацию см. в списке рекомендованной литературы.