Английское название метода - Parallel Blocks Sorting (PBS).
Два блока А » В называются параллельными, если каждому элементу A[i] первого блока поставлен в соответствие один элемент B[i] второго блока и наоборот. Длины блоков LA и LB равны: La-Lb = L. Размеры элементов блоков RA и RB могут быть разными.
Основная идея метода 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...
В общем случае скорость Vc работы компрессора (реализующего прямое, "сжимающее" преобразование) равна скорости Vd декомпрессора (реализующего обратное, "разжимающее" преобразование) и зависит только от размера данных, но не от их содержания: Ус = VD = 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]-2R + 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=2R и два цикла от О до L. Какой из них займет больше времени? Чаще всего Д=8, и=256, a L - от нескольких килобайт до десятков мегабайт. И четвертый, главный цикл -самый долгий, второй выполняется быстрее, а третий и особенно первый -совсем быстро.
Но возможна и обратная ситуация: если, например, Л=16, л=216=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. Характерные особенности: необходимо наличие как минимум двух параллельных блоков данных.