Английское название метода - Parallel Blocks Sorting (PBS).

Два блока А » В называются параллельными, если каждому элементу A[i] первого блока поставлен в соответствие один элемент B[i] второго бло­ка и наоборот. Длины блоков L_A и L_B равны: L_a-Lb ⁼ L. Размеры элементов блоков R_A и R_B могут быть разными.

Основная идея метода PBS состоит в сортировке элементов In[i] входно­го блока In и их раскладывании в несколько выходных блоков Out, на осно­вании атрибутов А[/] этих элементов. Атрибут A[i] есть значение функции А, определяемой значениями предшествующих элементов 1п[/] и/или эле­ментов ?[к] из параллельного блока Р:

A[i]=A(i, In[j], P[k]), i=0...L-l; j=0,...,i-1; k=0,...,L-l

При декодировании осуществляется обратное преобразование: элементы из нескольких блоков Out, собираются в один результирующий, соответст­вующий несжатому блоку In (рис. 6.1).

Чем лучше значения 1п[/] предсказуемы по значениям А[/], тем эффек­тивнее последующее сжатие блоков Out,- с помощью простых универсаль­ных методов.

Методы этой группы преобразующие и блочные, т. е. могут приме­няться только в том случае, когда известна длина блока с данными.

Размер данных в результате применения PBS, как и при ST/BWT, не из­меняется. Для сжатия результата работы метода может быть применена лю­бая комбинация методов - RLE, LPC, MTF, DC, HUFF, ARIC, ENUC, SEM...

В общем случае скорость V_c работы компрессора (реализующего пря­мое, "сжимающее" преобразование) равна скорости Vd декомпрессора (реа­лизующего обратное, "разжимающее" преобразование) и зависит только от размера данных, но не от их содержания: У_с = V_D = 0(L). Памяти требуется 2L+C. Константа С определяется особенностями реализации и может быть довольно большой. Операций умножения и деления нет.

Рис. 6.1. Иллюстрация PBS: атрибут А[\] определяется значением элемента Р[\]; значение А[\] показано штриховкой

Из краткого описания общей идеи видно, что

■ для распаковки нужно иметь не только содержимое сортированных бло­ков Outj, но и их размеры;

■ параллельных блоков может быть и два, и больше;

■ если функция А не использует те ?[k], которые находятся после текущей позиции /', т. е. Л=/+1,..., L , то можно создавать параллельный блок Р од­новременно с текущим сортируемым In;

■ если А задана так, что принимает мало значений: от 2 до, допустим, 16, метод вполне может быть применим и к потокам данных;

■ если параллельного блока Р нет, получаем ST/BWT как частный случай PBS.

ОСНОВНОЙ АЛГОРИТМ ПРЕОБРАЗОВАНИЯ

В простейшем случае сортирующего преобразования ST(1) значение атри­бута вычисляется так: А[/]=1п[/-1]; при ST(2): A[/]=In[/-l]-2^R + In[*'-2] и т. д.

В простейшем случае PBS А[/]=Р[/], т. е. значение атрибута равно значению элемента из параллельного блока. Выходных блоков столько, сколько значений принимают Р[/]. Делая проход по Р, считаем частоты значений атрибута и в результате получаем размеры сортированных блоков (далее - контейнеров), в ко­торые будем раскладывать элементы из входного блока In:

for( а=0; a<n; a++) Attr[а]=0; //инициализация (1)

for( i=0; i<L; i++) Attr[P[i]]++; //подсчет частот (2)

In - входной сортируемый блок длины L;

Р - параллельный блок длины L;

L - количество элементов во входном блоке;

л=2^л - число всех возможных значений атрибута;

Attrfrt] - частоты значений атрибута.

Например, в Р содержатся старшие 8 бит массива 16-битовых чисел, а в In - младшие 8. Заметим, что этот процесс "дробления" можно продолжать и дальше, создавая вплоть до 16 параллельных блоков: содержащий первые биты, вторые, и т. д. Кроме того, при сжатии мультимедийных данных часто уже имеются параллельные блоки, например левый и правый каналы сте­реозвука, красная, зеленая и синяя компоненты изображения и т. п.

Если функция А задана иначе, то и при подсчете частот формула будет иной:

// A[i]=P[i]s252 :

for( i=0; i<L; i++) Attr[ P[i]&252 ]++;// (2a)

// A[i]=255-P[i] :

for( i=0; i<L; i++) Attr[ 255-РЦ] ]++;// (2b)

// A[i]-(P[i]+P[i-l])/2 :

Attr[ P[0] ]++; // (2c)

for( i-1; i<L; i++) Attr[ (P[i]+P[i-1])/2 ]++;

Итак, после двух циклов - инициализации и подсчета частот - мы полу­чили в массиве Attr длины контейнеров (сортированных блоков). Теперь можно вычислить, где какой контейнер будет начинаться, если их последо­вательно сцепить в один блок в порядке возрастания значения атрибута:

for( a=0, pos=0; a<n; а++) { // (3)

tmp=Attr[a]; // длина текущего а-го контейнера Attr[a]=pos; // теперь там адрес-указатель на его начало

// (указатель на начало свободного места в нем) pos+=tmp; // начало следующего - дальше на длину текущего }

В том же массиве Attr[n] теперь адреса-указатели на начала контейнеров. Остается только пройти по входному блоку, раскладывая элементы из него по контейнерам:

for(i=0; i<L; i++) Out[Attr[P[i]]++]-In[i]; //(4c)

Out - выходной отсортированный блок (sorted, transformed), содержащий все контейнеры. Подробнее:

for( i=0; i<L; i++) { // На каждом шаге: s=In[i];// берем следующий элемент s из входного блока In,

a=P[i];// берем его атрибут а из параллельного блока Р, // и адрес свободного места в контейнере, задаваемом этим а;

pos=Attr[а]; // кладем элемент s в выходной блок Out по этому адресу,

Out[pos]=s;

pos++; //теперь в этом контейнере на один элемент больше,

Attr[a]=pos;//a свободное место - на один элемент дальше. }

Функция А - та же, что и во втором цикле. То есть, для выше рассмот­ренных примеров:

(2а) a=P[i]&252; (2b) a=255-P[i]; (2с) a=(P[i]+P[i-l])/2;

//причем i=l...L-l, а когда i=0, a=P[0].

Обратное преобразование

Совершенно идентичны первые 3 цикла: инициализируем, в результате прохода по параллельному блоку находим длины контейнеров, затем опре­деляем адреса начал контейнеров во входном отсортированном блоке In. Именно эти адреса - цель выполнения первых трех циклов. И только в чет­вертом цикле, наоборот, берем из отсортированного блока с контейнерами In, кладем в единый выходной блок Out:

for(i=0;i<L; i++) Out[i]=In[Attr[P[i] ]++]; //(4d) In - входной отсортированный блок со всеми контейнерами; Out - создаваемый выходной блок.

Подробнее:

for( i=0; i<L; i++) {

a=P[i];

pos=Attr[a]; //так было при прямом (сжимающем) преобразовании:

//Out[pos]=In[i];

//(в текущих обозначениях это записывается так: //In[pos]=Out[i];) //а так делаем сейчас, при разжимающем преобразовании: Out[i]=In[pos]; pos++; Attr[a]=pos;

)

Пути увеличения скорости сжатия

Итак, в обоих случаях выполняем два цикла от 0 до n=2^R и два цикла от О до L. Какой из них займет больше времени? Чаще всего Д=8, и=256, a L - от нескольких килобайт до десятков мегабайт. И четвертый, главный цикл -самый долгий, второй выполняется быстрее, а третий и особенно первый -совсем быстро.

Но возможна и обратная ситуация: если, например, Л=16, л=2¹⁶=65536, а 1=512, т. е. требуется сжать поток блоков из 512 16-битовых элементов (по­ток "фреймов"). Тогда, наоборот, самым долгим будет третий цикл, затем первый, четвертый и второй.

Два цикла при больших R

Если памяти хватает, поступим так: будем наполнять контейнеры не од­новременно, проходя по In, P и записывая элементы In[i] в вычисляемые ад­реса блока Out, а последовательно: проходя по Out и вычисляя адреса в In, Р, из которых нужно брать значения атрибута и элементы, помещаемые за­тем в Out. Останутся два цикла от 0 до I, а циклы от 0 до л=2^я исчезнут.

При первом проходе заполняем вспомогательный массив Anext, содер­жащий цепочки указателей на позиции с одинаковыми атрибутами (А-цепочки). То есть в Anext[(j записываем указатель на следующую позицию (i+k) с таким же значением атрибута A[i], если таковая (i+k) в оставшейся части блока есть. В противоположном случае, если в оставшейся части бло­ка атрибут не принимает значение A[i], в Anext[i] записываем /.

// при инициализации: вспомогательные массивы

int Anext[L];

int Beg[n]; // начала,

int End[n]; // концы и

int Flg[n]; // флаги наличия А-цепочек в текущем фрейме

//в цикле для каждого фрейма:

FrameNumber++; // следующий L-элементный фрейм

for( i=0; i<L; i++) {

a=P[i]; //вычислим значение атрибута а

if(Flg[a]==FrameNumber) //если цепочка, определяемая этим а,
{ //в текущем фрейме уже есть,

e=End[a]; // то конец ее - в массиве концов цепочек Anext[e]=i;// теперь прошлый конец указывает на новый

>

else

( // иначе

Flg|a]=FrameNumber;// запишем, что такая цепочка есть

Beg[a]=i; //и сохраним адрес ее начала

}
Anext[i]=i; // текущий элемент А-цепочки - ее конец
End[a]=i; // укажем конец в массиве концов цепочек

}

Массив Fig нужен только затем, чтобы инициализировать не Beg и End перед каждым фреймом, а только Fig перед всеми фреймами. Если создать еще два массива Fprev и Fnext, соединяющие все элементы Fig с одним зна­чением в одну F-цепочку (причем Fnext указывает на следующий элемент F-цепочки, Fprev - на предыдущий), то не придется при втором проходе ли­нейно искать в Fig появлявшиеся в текущем фрейме А-цепочки. И цикла от О до л удастся избежать. Соответствующие изменения читатель легко внесет в алгоритм сам.

При втором проходе выполняем сортировку:

pos=f=0;
while (Fnext[f]!=f)	{	//
f=Fnext[f];		// 1
i=Beg[f];		II :
do {		II i
Out[pos]=In[i];		// i
pos++;		// i
i=Anext[i];		//и
) while(i!=Anext[:	U>	ll№

(линейный поиск следующей А-цепочки в Fig, если без Fnext) первый элемент текущей А-цепочки, и далее для всех ее элементов: берем из In, кладем в Out последовательно, т. д., проходя всю А-цепочку э конца }

На этот раз во втором цикле уже нет обращений к Р, поэтому можно со­вместить А и Р. Памяти же требуется не 21 + /rsizeof(*char), a 2-L + 5-/isizeof(*char),

так как Beg, End, Fig, Fprv, Fnxt занимают по nsizeof(*char) байт.

Два цикла при малых R

Если памяти доступно больше, чем необходимо для хранения 2-L+n-C элементов, и С достаточно велико - 256 или, например, 512, можно сразу "расформатировать" память под начала контейнеров:

#define К 256;

for( i=0; i<n; i++) Attr[i]=i*K; // (Ism)

// под каждый из п контейнеров отведено К элементов

// (1 "сектор")

И затем при проходе по In, P, если свободное место в каком-то контей­нере кончается, будем записывать в конце "сектора" указатель на следую­щий сектор, выделяемый под продолжение этого контейнера:

FreeSector=n;

for( i=0; i<L; i++) { // (2sm)

a=P[i]; // берем атрибут а из параллельного блока Р, pos=Attr[a];// и адрес свободного места в контейнере,

// задаваемом этим а; Out[pos]=In[i]; pos++; if(pos%K+sizeof(*char)==K)//если свободное место кончилось, {

Out[pos]=FreeSector;//пишем указатель на следующий сектор // если FreeSector типа int32, a Out[i] типа int8, то: // Out[pos] =FreeSector%256; // Out[pos+l] = (FreeSector»8)%256; // 0ut[pos+2] = (FreeSector»16) %256; // Out[pos+3] = (FreeSector»24) %25б; pos=FreeSector*K;//свободное место= начало нового сектора FreeSector++; // свободный сектор на один сектор дальше } Attr[a]=pos; }

QL Упражнение. Сравните этот цикл с (4с) и оцените, насколько он будет медленнее.

Это очень выгодно, если л<256, и, кроме того, после PBS выполняется еще один проход по всем элементам блока Out. Как правило, это так. Таким образом, весь алгоритм сводится к одному тривиальному циклу (Ism) и од­ному проходу по данным (2sm).

Увеличение скорости разжатия

Ускорение разжатия возможно, если длины контейнеров сжимать и пе­редавать отдельно. Если L существенно больше и, описание длин занимает незначительную часть сжатого блока, так что потери в степени сжатия бу­дут невелики. Тогда в массив Апт[и] при разжатии можно сразу записывать не длины, а начала контейнеров. Заметим, что и в случае ST/BWT это даст заметное увеличение скорости: подсчет частот элементов требует при раз­жатии дополнительного прохода по данным.

Пути улучшения сжатия

Общий случай

Если содержимое каждого контейнера (или некоторых из них) подверга­ется преобразованию, зависящему от его атрибута, то длины контейнеров надо обязательно передавать декомпрессору, иначе он неправильно постро­ит таблицу частот по содержимому контейнеров.

Если параллельный блок уже существует и не изменяется при прямом и обратном преобразовании, функцию А можно строить без всяких ограниче­ний, используя любую комбинацию арифметических, логических и других операций. Например,

A[i]=(int)P[i]/2; // деление целочисленное

Если сравнивать со случаем A[i] = P[j], то можно сказать, что каждая пара контейнеров объединяется в один "двойной" контейнер.

A[i]=P[i]^А(п-1); // или, что то же самое, A[i]=n-1-P[i].

То есть контейнеры будут лежать в Out в обратном порядке по сравнению с A[i]=P[i]. Это полезно для второго отсортированного блока Out2, записы­ваемого за первым Outl, особенно если данные мультимедийные, поскольку в этом случае значения In[i] и 1п[/+1], как правило, близки.

Еще два варианта вычисления атрибута:

A[i]-(P[i] S 16 == 0)? P[i] : (Р[1]^л15);

Младшие 4 бита изменяются только на +1 или -1: abs(P[i]&15-P[i-l]&15)=l.

A[i]=(P[i]<0)? (-P[i]*2+l ) : P[i]*2; Расстояние до нуля, а знак - в младшем бите.

Упражнение. Напишите к последним двум формулам формулы обратного пре­образования.

Функция А может быть и адаптивной, т.е. производится периодическая корректировка каких-то ее коэффициентов, чтобы выходной блок больше соот­ветствовал заданному критерию. Например, известно, что последние 20-30 контейнеров из 256 полезно объединять в четверки, а остальные - в пары:

// последние 256-232=24 контейнера объединяем в четверки

К=232;

A[i]=(P[i]>K)? P[i]/4 : P[i]/2; // деление - целочисленное

При этом критерий используется такой: сумма первой производной вы­ходного блока Out должна стремиться к нулю:

/.-I Sum = £ (Out[i] - Out[i -1]) = 0,

/'=1

где Out[/]-Out[M] - первая производная блока.

Тогда можно вычислять

SumCurrent+=Out [i] -Out [i.-l], при текущем значении К, SumMinus+=0utm[i]-0utra[i-l] при К=К-4, SumPlus+=Outp[i]-Outp[i-l] при К=К+4,

и через каждые StepK шагов выбирать новое значение К по результату срав­нения SumCurrent, SumMinus и SumPlus:

if (SumMinus<SumCurrent && SumMinus<SumPlus) K=K-4; else if (SumPlus<SumCurrent) K=K+4;

Может оказаться полезным сохранять блок А вместо Р, особенно если параллельный блок строится одновременно с сортируемым, например, Р[/] вычисляется по Р[«-1] и In[i-1]. Тогда Р должен быть восстановим по А и функция А должна быть биективной: по значению A[iJ=A(P[/]) однозначно находится P[i]. Реально такая функция А сводится к перестановке: имеем контейнеры с атрибутами А[г']=Р[/], затем перетасовываем их, меняя места­ми внутри единого выходного блока Out, но не изменяя их содержимого. Но формально А может выглядеть очень по-разному, содержать прибавление константы: A[i]=P[i]+123; // результат берется по модулю п

логический XOR:

A[i]=P[i]^A157;

сравнения и перестановки битов, в том числе циклическим вращением:

A[i]=(P[i]&(n/2))? ( (P[i]-(n/2))*2+l ) : P[i]*2;

Упражнение. Как будет выглядеть А, собирающая вместе элементы ln[/J, соот­ветствующие тем Р[/], остаток которых от деления на заданное К одинаков? Начните со случаев К=4 и К=8.

Если функция А неадаптивна или зависит только от элементов парал­лельного блока, сами контейнеры, поскольку их длины известны, можно сортировать внутри единого выходного блока по их длинам. Это может улучшить сжатие даже при ST/BWT, особенно в случае качественных дан­ных, а не количественных. Часто оказывается выгодным группировать ко­роткие контейнеры в одном конце выходного блока, а длинные - в другом. И при сжатии, и при разжатии процедура сортировки контейнеров по дли­нам добавится между циклами (2) и (3).

Рассмотрим последний вариант: весь блок А сохраняется и передается (компрессором декомпрессору), поэтому и строится он именно с учетом такой особенности. Если есть параллельный блок Р, можно строить А так, чтобы и Р преобразовывать на основе А, и чтобы суммарно блоки А, Р, In сжимались лучше, чем Р и In. Если нет Р, то получается, что In распадается на две компоненты: "идеальную" - моделируемые, предсказываемые А[/], и "реальную" - отклонения In[i] от предсказанных значений А[/].

Двумерный случай

Параллельным блоком может быть предыдущая, уже обработанная стро­ка таблицы. Либо предсказываемая (текущая), формируемая на основе од­ной или нескольких предыдущих строк. В обоих случаях целесообразно вы­числять атрибут как среднее арифметическое соседних элементов, особенно для мультимедийных данных:

//если известны те, что выше и левее, то соседних - четыре: // P[i-2] P[i-1] P[i] P[i+1] // Inti-2] In[i-1] ln[i] A[i]=(P[i-l]+ P[i]+P[i+l])/3;

A[i]=(P[i-l]+2*P[i]+P[i+l])/4; A[i]-(P[i-l]+ P[i]+In[i-l])/3; A[i]-(P[i-l]+2*P[i]+In[i-l])/4; A[i]=(P[i-l]+ P[i]+2*In[i-l])/4; A[i]=(P[i-l]+ P[i]+P[i+l]+In[i-l])/4;

Тогда опять же длины контейнеров (частоты значений атрибутов) надо обязательно передавать декомпрессору. Перед делением полезно делать ок­ругление до ближайшего числа, кратного делителю. Еще сложнее будут формулы, если использовать более одной предыдущей строки.

Заметим важное полезное свойство метода: увеличение сложности вы­числений не влечет увеличения объема необходимой памяти.

Если рассматривать множество строк как единый блок, то в простейшем случае A[i]=P[i]=In[*-№] (W- число элементов в строке), т. е. в качестве атри­бута используется значение "верхнего" элемента. Тогда таблицу длин сохранять не нужно, но первые ^элементов в неизменном виде - обязательно.

Упражнение. Опишите подробно алгоритм сортировки в случае A[i]=ln[i-W]. Начните с W=1 и W=2.

Характеристики методов семейства PBS: Степень сжатия: увеличивается в 1.0-2.0 раза. Типы данных: многомерные или многоуровневые данные. Симметричность по скорости: в общем случае 1:1. Характерные особенности: необходимо наличие как минимум двух параллельных блоков данных.