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

Барроуз и Уилер были заинтересованы главным образом в разработке алгоритма с высокой практической эффективностью. И в самом деле, их простая версия превосходила (по критерию коэффициента сжатия) инструмент 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 в настоящее время является областью активных исследований. Дополнительную информацию см. в списке рекомендованной литературы.