Интернет магазин китайских планшетных компьютеров

Компьютеры - Преобразование Барроуза Уилера - Производительность BWT и алгоритмов сжатия на его основе, потребление памяти

Важнейшей задачей, которая должна быть решена для получения быстрого алгоритма BWT, является задача сортировки строк. При этом следует учесть, что некоторые алгоритмы сортировки строк крайне зависимы от «удачности» входных данных, работают быстро в большинстве случаев, но крайне сильно деградируют в неудачных случаях.

Например, такова довольно удачная в общем случае комбинация «bucket sort+qsort Седжвика в каждой корзине» на входном тексте в виде длинной последовательности ABABABAB — bucket sort создаст 2 корзины для A и B, заполнив каждую почти полностью одинаковыми строками, после чего qsort на таком наборе затянется почти навсегда.

В таких случаях приходится прерывать исполнение «затянувшегося» алгоритма и переходить на другой алгоритм, который хуже в удачных случаях, но не подвержен обвальной деградации.

Потребление памяти BWT компрессором главным образом сводится к буферу под ныне сортируемую порцию входных данных, для хорошего качества компрессии это единицы мегабайт, что превосходит потребление памяти всеми остальными звеньями компрессора.

LZH компрессор немного хуже по качеству сжатия и примерно одинаков по скорости, но потребляет значительно меньше памяти.

BWT декомпрессор намного быстрее и не потребляет значительных объемов памяти, что отличает его от алгоритмов PPM.