Преобразование Барроуза - Уилера

Введение

Преобразование Барроуза - Уилера применяется в алгоритмах сжатия качественных данных. Для эффективного использования преобразования необходимо, чтобы характеристики данных соответствовали модели источника с памятью.

Как и многие другие применяемые в алгоритмах сжатия преобразования, преобразование Барроуза - Уилера предназначено для того, чтобы сделать сжатие данных входного блока более эффективным. Посредством переста­новки элементов данное преобразование превращает входной блок данных со сложными зависимостями в блок, структуру которого моделировать го­раздо легче, причем отображение происходит без потерь информации.

Этот метод появился сравнительно недавно. Впервые он был опублико­ван 10 мая 1994 г. в [13]. Авторами метода являются Дэвид Уилер и Майк Барроуз. Причем первый из них придумал этот метод еще в 1983 г., когда работал в компании AT&T Bell Laboratories. Но, видимо, либо тогда не при­дал значения своему открытию, либо посчитал чрезмерными требования к вычислительным ресурсам.

По имени авторов, алгоритм был назван преобразованием Барроуза -Уилера (Burrows - Wheeler Transform, далее - BWT). Метод был объявлен компромиссным между быстрыми словарными алгоритмами, с одной сто­роны, и статистическими алгоритмами, дающими более сильное сжатие, но, малоприменимыми в то время на практике, с другой стороны.

Благодаря таким свойствам описываемое преобразование стало довольно популярным и среди разработчиков архиваторов, и среди научных работни­ков. Уже опубликовано более сотни статей на разных языках, посвященных этому методу, и написано столько же программ, его реализующих.