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



         

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


1. Сначала вычисляем первую колонку матрицы M (F). Это делается путем сортировки символов строки L. Каждая колонка исходной матрицы M представляет собой перестановки исходной последовательности S. Таким образом, первая колонка F и L являются перестановками S. Так как строки в M упорядочены, размещение символов в F также упорядочено. F='aaabcr'.

2. Рассматриваем ряды матрицы M, которые начинаются с заданного символа ch. Строки матрицы М упорядочены лексикографически, поэтому строки, начинающиеся с ch упорядочены аналогичным образом. Определим матрицу M', которая получается из строк матрицы M путем циклического сдвига на один символ вправо. Для каждого i=0,…, N-1 и каждого j=0,…,N-1,

M'[i,j] = m[i,(j-1) mod N]

В рассмотренном примере M и M' имеют вид:

Строка

M

M'

0

aabrac

caabra

1

abraca

aabraс

2

acaabr

racaab

3

bracaa

abraca

4

caabra

acaabr

5

racaab

bracaa

Подобно M каждая строка M' является вращением S, и для каждой строки M существует соответствующая строка M'. M' получена из M так, что строки M' упорядочены лексикографически, начиная со второго символа. Таким образом, если мы рассмотрим только те строки M', которые начинаются с заданного символа ch, они должны следовать упорядоченным образом с учетом второго символа. Следовательно, для любого заданного символа ch, строки M, которые начинаются с ch, появляются в том же порядке что и в M', начинающиеся с ch. В нашем примере это видно на примере строк, начинающихся с ‘a'. Строки ‘aabrac', ‘abraca' и ‘acaabr' имеют номера 0, 1 и 2 в M и 1, 3, 4 в M'.

Используя F и L, первые колонки M и M' мы вычислим вектор Т, который указывает на соответствие между строками двух матриц, с учетом того, что для каждого j = 0,…,N-1 строки j M' соответствуют строкам T[j] M.

Если L[j] является к-ым появлением ch в L, тогда T[j]=1, где F[i] является к-ым появлением ch в F. Заметьте, что Т представляет соответствие один в один между элементами F и элементами L, а F[T[j]] = L[j].


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