> bwt | transform | compress <
// Burrows-Wheeler Transform — обратимое текстовое преобразование, которое облегчает эффективное сжатие
>> возможности
Полностью обратимое
Без потерь и позволяет точно восстановить исходный текст.
Кластеризация символов
Собирает похожие символы в группы, что повышает эффективность последующих этапов сжатия.
Основа bzip2
Ключевой этап в алгоритмах сжатия семейства bzip2.
>> техническая информация
Как работает BWT
Преобразование Берроуза–Уилера строит все циклические сдвиги входной строки, сортирует их лексикографически и возвращает последний столбец отсортированной матрицы вместе с индексом исходной строки. В результате похожие символы группируются, и данные хорошо сжимаются при помощи RLE, Move-to-Front и других энтропийных кодеров.
Пример BWT
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
Зачем использовать BWT
- Повышает степень сжатия текстовых данных
- Полностью обратимо и без потерь
- Группирует похожие контексты
- Является основой алгоритма сжатия bzip2
- Эффективный этап предварительной обработки перед дальнейшим кодированием
>> часто задаваемые вопросы
Что такое преобразование Берроуза–Уилера?
Преобразование Берроуза–Уилера (BWT) — это обратимый алгоритм, который переставляет символы строки так, чтобы образовывались длинные участки одинаковых символов. Он был предложен Майклом Берроузом и Дэвидом Уилером в 1994 году и используется как этап предварительной обработки в компрессорах вроде bzip2 для улучшения коэффициента сжатия.
Почему BWT улучшает сжатие?
BWT группирует символы, которые встречаются в похожих контекстах, поэтому во выходной строке многие одинаковые символы оказываются рядом. Такие последовательности очень хорошо сжимаются с помощью кодирования длин серий, преобразования Move-to-Front и энтропийного кодирования, например Хаффмана.
Что такое маркер EOF?
Маркер EOF (конец файла), обычно символ '$' или другой уникальный знак, гарантирует, что все циклические сдвиги различимы и позволяет однозначно определить позицию исходной строки. Без него некоторые строки не имели бы единственного представления. При обратном преобразовании этот маркер удаляется.
Является ли BWT самостоятельным алгоритмом сжатия?
Нет. BWT сам по себе не выполняет сжатие, а лишь подготавливает данные, делая их более удобными для сжатия. На практике его комбинируют с Move-to-Front, RLE и кодированием Хаффмана в схемах наподобие bzip2.