previous up down next index index
Previous: 2.6.2 Локально адаптивный алгоритм сжатия    UP: 2.6 Методы сжатия информации
Down: 3 Каналы передачи данных
    Next: 2.6.4 Метод Шеннона-Фано

2.6.3 Сжатие данных с использованием преобразования Барроуза-Вилера
Семенов Ю.А. (ГНЦ ИТЭФ)

Майкл Барроуз и Давид Вилер (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

Previous: 2.6.2 Локально адаптивный алгоритм сжатия    UP: 2.6 Методы сжатия информации
Down: 3 Каналы передачи данных    Next: 2.6.4 Метод Шеннона-Фано