Сжатие
данных с использованием преобразования Барроуза-Вилера
Майкл Барроуз и
Давид Вилер (Burrows-Wheeler) в 1994 году предложили свой алгоритм преобразования
(BWT). Этот алгоритм работает с блоками данных и обеспечивает эффективное
сжатие без потери информации. В результате преобразования блок данных имеет ту
же длину, но другой порядок расположения символов. Алгоритм тем эффективнее,
чем больший блок данных преобразуется (например, 256-512 Кбайт). Пояснение
работы алгоритма будет выполнено на ограниченном объеме исходных данных (строка
S длиной N, например, SEMENOV). Строка S рассматривается как
последовательность, состоящая из N строк.
Сначала
осуществляется циклический сдвиг строки S и формируется N-1 новая строка. На
практике строки не размножаются, а создается массив указателей на циклический
буфер, где лежит исходная строка S.
|
Строка |
S E M E N O V |
S0 |
E M E N O V S |
S1 |
M E N O V S E |
S2 |
E N O V S E M |
S3 |
N O V S E M E |
S4 |
O V S E M E N |
S5 |
V S E M E N O |
S6 |
Далее
выполняется лексикографическое упорядочение (сортировка) этих строк
(указателей). Для упорядочения можно использовать С-функции типа strcmp() или
memcmp() (учитывая особенности структуры буфера, это должны быть их
функциональные аналоги).
F |
|
|
|
|
|
L |
Строка |
E |
M |
E |
N |
O |
V |
S |
S1 |
E |
N |
O |
V |
S |
E |
M |
S3 |
M |
E |
N |
O |
V |
S |
E |
S2 |
N |
O |
V |
S |
E |
M |
E |
S4 |
O |
V |
S |
E |
M |
E |
N |
S5 |
S |
E |
M |
E |
N |
O |
V |
S0 |
V |
S |
E |
M |
E |
N |
O |
S6 |
Первая колонка
помечена буквой F, а последняя Колонка F (EEMNOSV) содержит все символы
исходной строки S, записанные в упорядоченной последовательности. Строка L
представляет собой последовательность префиксных символов для строки S.
Результатом
работы алгоритма BWT является строка L и первичный индекс, который представляет
собой номер элемента строки L, где хранится первый символ исходной строки S. В
приведенном примере индекс равен 1.