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



         

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


В нашем примере T равно: (4 0 5 1 2 3).

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

Индекс I указывает на строку М, где записана строка S. Таким образом, последний символ S равен L[I]. Мы используем вектор T для получения предшественников каждого символа: для каждого i = 0,…,N-1 S[N-1-i] = L[T i [I]], где T 0 [x] =x, а T i+1 [x] = T[T i [x]. Эта процедура позволяет восстановить первоначальную последовательность символов S (‘abraca').

Последовательность T i [I] для i =0,…,N-1 не обязательно является перестановкой чисел 0,…,N-1. Если исходная последовательность S является формой Z p для некоторой подстановки Z и для некоторого p>1, тогда последовательность T i [I] для i = 0,…,N-1 будет также формой Z 'p для некоторой субпоследовательности Z'. Таким образом, если S = ‘cancan', Z = ‘can' и p=2, последовательность T i [I] для i = 0,…,N-1 будет [2,4,0,2,4,0].

Описанный выше алгоритм упорядочивает вращения исходной последовательности символов S и формирует строку L, состоящую из последних символов вращений. Для того, чтобы понять, почему такое упорядочение приводит к более эффективному сжатию, рассмотрим воздействие на отдельную букву в обычном слове английского текста.

Возьмем в качестве примера букву “t” в слове ‘the' и предположим, что исходная последовательность содержит много таких слов. Когда список вращений упорядочен, все вращения, начинающиеся с ‘he', будут взаимно упорядочены. Один отрезок строки L будет содержать непропорционально большое число ‘t', перемешанных с другими символами, которые могут предшествовать ‘he', такими как пробел, ‘s', ‘T' и ‘S'.

Аналогичные аргументы могут быть использованы для всех символов всех слов, таким образом, любая область строки L будет содержать большое число некоторых символов.


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