Телекоммуникационные технологии. Том 1



         

Сжатие данных с использованием преобразования Барроуза-Вилера


Семёнов Ю.А. (ГНЦ ИТЭФ), book.itep.ru

Майкл Барроуз и Давид Вилер (Burrows-Wheeler) в 1994 году предложили свой алгоритм преобразования (BWT). Этот алгоритм работает с блоками данных и обеспечивает эффективное сжатие без потери информации. В результате преобразования блок данных имеет ту же длину, но другой порядок расположения символов. Алгоритм тем эффективнее, чем больший блок данных преобразуется (например, 256-512 Кбайт).

Последовательность S, содержащая N символов ({S(0),… S(N-1)}), подвергается N циклическим сдвигам (вращениям), лексикографической сортировке, а последний символ при каждом вращении извлекается. Из этих символов формируется строка L, где i-ый символ является последним символом i-го вращения. Кроме строки L создается индекс I исходной строки S в упорядоченном списке вращений. Существует эффективный алгоритм восстановления исходной последовательности символов S на основе строки L и индекса I. Процедура сортировки объединяет результаты вращений с идентичными начальными символами. Предполагается, что символы в S соответствуют алфавиту, содержащему K символов.

Для пояснения работы алгоритма возьмем последовательность S= “abraca” (N=6), алфавит X = {‘a','b','c','r'}.

1. Формируем матрицу из N*N элементов, чьи строки представляют собой результаты циклического сдвига (вращений) исходной последовательности S, отсортированных лексикографически. По крайней мере одна из строк M содержит исходную последовательность S. Пусть I является индексом строки S. В приведенном примере индекс I=1, а матрица M имеет вид:

Номер строки

0

aabrac

1

abraca

2

acaabr

3

bracaa

4

caabra

5

racaab

2. Пусть строка L представляет собой последнюю колонку матрицы M с символами L[0],…,L[N-1] (соответствуют M[0,N-1],…,M[N-1,N-1]). Формируем строку последних символов вращений. Окончательный результат характеризуется (L,I). В данном примере L='caraab', I =1.

Процедура декомпрессии использует L и I. Целью этой процедуры является получение исходной последовательности из N символов (S).




Содержание    Вперед