|
Майкл Барроуз и Давид Вилер (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, а последняя - L. Колонка F (EEMNOSV) содержит все символы исходной строки S, записанные в упорядоченной последовательности. Строка L представляет собой последовательность префиксных символов для строки S.
Результатом работы алгоритма BWT является строка L и первичный индекс, который представляет собой номер элемента строки L, где хранится первый символ исходной строки S. В приведенном примере индекс равен 1.
Смотри
http://web2.airmail/markn/articles/bwt/bwt.htm
|
