Фрагментирование

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

Основная идея состоит в том, чтобы для каждой точки потока X (лежа­щей между парой соседних элементов) находить значение функции отличия FO(A^ предыдущей части потока от последующей. В базовом простейшем варианте используется "скользящее окно" фиксированной длины: Z эле­ментов до точки Хи Z элементов после нее.

Иллюстрация (Z=7):

...8536429349586436542 19865332 \Х\ 6564387 158676780674389...

Цифрами обозначены элементы потока, вертикальными чертами "|" гра­ницы левого и правого окон. Хне элемент потока, а точка между парой эле­ментов, в данном случае между "2" и "6".

При фиксированной длине окон Z и одинаковой значимости, или весе, всех элементов внутри окон (независимо от их удаленности от точки X) зна­чение функции отличия может быть легко вычислено на основании разно­сти частот элементов в левом и правом окнах. Это сумма по всем 2^я воз­можным значениям V_{ элементов. Суммируются абсолютные значения раз­ностей: число элементов с текущим значением V в левом окне длиной Z минус число элементов с данным значением V в правом окне длиной Z. Суммируя 2" модулей разности, получаем значение FO(A) в данной точке X:

2«-l

FO(X) = £ \CountLeft[V) - CountRight[V\,

где CountLeftff''] - число элементов со значением V в левом окне; Coun-tRightf И] - число элементов со значением К в правом окне.

Видно, что если в обоих окнах элементы одинаковые, то сумма будет стремиться к нулю, если же элементы совершенно разные - к 2Z. Для приведенного выше примера:

После того как все значения FO(A) найдены, остается отсортировать их по возрастанию и выбрать границы по заданному критерию (заданное число границ и/или пока FO(X)>F_min).

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

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

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

Обратного преобразования не требуется.

В общем случае скорость работы компрессора зависит только от размера данных, но не от их содержания: Скорость=0(Размер). Памяти требуется порядка 2^Я+1. Для левого окна - 0(2^Л), и столько же для правого. Операций умножения и деления нет.

С точки зрения сегментации данных метод отличается от RLE лишь тем, что выделяет из потока (или блока) не только цепочки одинаковых элемен­тов, но и вообще отделяет друг от друга фрагменты с разными распределе­ниями вероятностей значений элементов.

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

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

■ задаваемыми параметрами могут быть (максимальная) длина окна Z, F_min- минимальное значение FO(A0, минимальное расстояние между границами R_min (а в случае фрагментирования блока заданной длины -еще и число границ NG, минимальное и/или максимальное число границ:

'"min> "max/>

■ вычисление функции отличия при нескольких длинах окон - 2\ , Z₂ > ■■■ ..., Z„ - в общем случае улучшит качество фрагментирования;

■ уменьшение веса элементов окна с удалением от точки Л'также в общем случае улучшит качество фрагментирования.

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

Каков бы ни был размер окон Z, при проходе по входным данным ln[N] в каждой точке X при переходе к следующей точке (Х+1) достаточно следить за тремя элементами: вышедшим из левого окна (из-за сдвига точки ^впра­во), вошедшим в правое окно и перешедшим из правого окна в левое. Но сначала разберем самый понятный алгоритм: с проходом по всем элементам окон для каждой точки X.

#define Z 32

for( i=0; i<n; i++)

CountLeftfi]=CountRight[i;=0; //инициализация (l)

for ( x=0; x<Z; x++) { //цикл iro длине окон: (2)

i=In[x]; //возьмем очередной элемент левого окна 1п[х]
CountLeft[i]++; //в левом окне элементов на 1 больше

i=In[x+Z); //и аналогично с правым окном

CountRight[i]++; }

ЩЩ - входной фрагментируемый блок; N - количество байтов во входном блоке; л=2* - каждый байт может иметь 2^R значений; FO[N-2-Z\ - значения функции отличия; CountLeftfn] - частоты элементов в левом окне; CountRight[/i] - частоты элементов в правом окне.

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

for(x=Z; x<N-Z-l; x++) {

//точка X скользит с позиции Z до N-Z-1 (3)

f=0; //текущее значение функции отличия

for( i=0; i<n; i++) //вычислим по формуле как сумму

f+=abs(CountLeft[i]-CountRight[i]);/*т. е.если без abs()

if (CountLeft[i]>CountRight[i])
f+=CountLeft[i]-CountRight[i];
else f+=CountRight[i]-CountLeft[i];
*/
FO[x]=f; IЫ запишем в массив

for(i=0;i<n;i++) CountLeft[i]=Coun-Right[i]=0;//как в (1) for(j=x+l-Z;j<x+l;j++){ //цикл по длине окон: как в (2) CountLeft[In[j]]++;//подсчет частот элементов в левом окне CountRight[In[j+Z]]++; //и аналогично в правом )//но теперь левая граница левого окна - в позиции (x+1-Z) }

Наконец, последний цикл - это либо сортировка FO[7V] с целью нахож­дения заданного числа максимальных значений (заданного числа самых "четких" границ), либо просто нахождение таких FO[A;], значение которых больше заданного. Последнее можно делать в основном цикле.

Упражнение. Внесите необходимые изменения в (3), если задано минималь­ное значение отличия F_min.

Пути улучшения скорости

Если последние два цикла внутри (3) перенести и выполнять их до пер­вого, вычисляющего FO, то (1) и (2) не нужны. Но поскольку внутри цикла-прохода (3) по In достаточно следить за тремя элементами, в нем вообще не будет внутренних циклов. После выполнения (1) и (2) поступим так:

f=0; //исходное значение функции отличия

for( i=0; i<n; i++) //вычислим по формуле как сумму (2а)

f+■ abs(CountLeft[i]-CountRight[i]);
FO[0]=f; IЫ запишем в массив

А внутри основного цикла, проходящего по входному блоку In[N]:

for(x=Z; x<N-Z-l;x++) {

//точка X скользит с позиции Z до N-Z-1 (За)

i=In[x-Z]; //элемент, вышедший из левого скользящего окна

f-=abs(CountLeft[i]-CountRight[ i ]); //сумма без 1 слагаемого

CountLeft[i]—; //теперь в левом окне таких на 1 меньше

f+=abs(CountLeft[i]-CountRight[i]) ; //обратно к полной сумме

i=In[x+Z]; //элемент, вошедший в правое окно //совершенно аналогично обновлению для левого окна f-=abs(CountLeft[i]-CountRight[i]);

CountRight[i]++; //теперь в правом окне таких на 1 больше f+=abs(CountLeft[i]-CountRight[i]) ;

i»In[x];//элемент, перешедший из правого окна в левое

f-=abs(CountLeft[i]-CountRight[i]) ;

CountLeft[i]++; //теперь в левом окне таких на 1 больше

CountRight[i]—; //а в правом - на 1 меньше

f+-abs(CountLeft[i]-CountRight[i]) ;

FO[x]=f;//запишем значение функции отличия в массив )

Упражнение. Как изменится значение f, если все 3 элемента одинаковы, при­чем в левом окне таких было 7, а в правом 8?

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

f=0; // исходное значение функции отличия

stacksize=0; // и размера стека

for (х=0; x<2*Z; x++) (2z)

{

i=In[x]; // текущий элемент

s=0; // просмотрим все уже обработанные:

while(s<stacksize) if (Stack[s]==i) goto NEXT

// если элемент еще не вошел

f+= abs(CountLeft[i]-CountRight[i]) ;

Stack[stacksize++]=i; // то вносим сейчас NEXT: } FO[0]=f; // запишем в массив

Точно так же можно модифицировать первый цикл внутри (3), вычис­ляющий FO: вместо него будет (2z), т. е. цикл не до я, а до 2-Z.

Чтобы избавиться от второго цикла до п внутри (3), заведем два массива с флагами FlagLeft и FlagRight, параллельные CountLeft и CountRight. В них будем записывать, в какой позиции х делалась запись в соответствующую позицию массива Count. При чтении же из Count будем читать и из Flag. Ес­ли значение в Flag меньше текущего х, то в соответствующей ячейке масси­ва Count должен быть нуль.

Упражнение. Перепишите (3) так, чтобы не было циклов до л.

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

Общий случай

Самый выгодный путь - использование окна с убыванием веса эле­ментов при удалении от точки X. Линейное убывание, например: вес двух элементов, между которыми лежит точка X, равен Z, вес двух следующих, на расстоянии I от X, равен Z-1, и т. д., (Z-d) у элементов на расстоянии d, нуль у элемента, только что вышедшего из левого окна, и у элемента, кото­рый войдет в правое окно на следующем шаге.

Внутри основного цикла будет цикл либо до Z - по длине окна, либо до л - по всем возможным значениям элементов. В зависимости от значений Z и и, один из этих двух вариантов может оказаться существенно эффективнее другого.

В первом случае - Z существенно меньше п, выгоднее цикл до Z - вме­сто инкрементирования будем добавлять веса, т. е. расстояния от А'до даль­ней границы (самой левой в случае левого окна, самой правой в случае пра­вого):

for( x=0; x<Z; x++) { //цикл по длине окон: (2')

// CountLeft[In[x]]++; //так было в цикле (2)

// CountRight[In[x+Z]]++;//а теперь: прибавляем CountLeft[In[x]]+=х+1; // расстояние от левой границы до х, CountRight[In[x+Z]]+=Z-x;// от x+Z до правой границы:

// 2*Z-(x+Z) )

И аналогичные модификации в цикле (3).

Во втором случае - п существенно меньше Z, выгоднее цикл до я - реа­лизация гораздо сложнее: в дополнение к массиву со счетчиками появляется второй массив с весами. Зато сохраняется возможность действовать так, как в (За), не делая цикла по длине окна Z внутри основного цикла:

for(x=Z;x<N-Z-l;x++) {//точка X - с позиции Z до N-Z-1 3**) f=0; for (i=0;i<n; i++)

// как изменятся веса элементов со значением

{ // i при переходе к позиции х+1?

WeightLeft[i]-=CountLeft[i]; // всего их CountLeft[i],

// каждый изменится на -1 WeightRight[i]+=CountRight[i]); // а каждый правый - на +1 // считаем значение отличия f+=abs(WeightLeft[i]-WeightRight[i]) ; } // теперь сдвинем х на 1 вправо, внося и вынося элементы

i=In[x-Z];//элемент, вышедший из левого скользящего окна CountLeft[i]—; // теперь в левом окне таких на 1 меньше //вес его уже 0, поэтому WeightLeft[i] не изменен

i=In[x+Z]; //элемент, вошедший в правое окно f-=abs(WeightLeft[i]-WeightRight[i]) ; // сумма без 1 слагаемого

CountRight[i]++;//теперь в правом окне таких на 1 больше WeightRight[i]++;//и вес их на 1 больше // обратно к полной сумме

f+=abs(WeightLeft[i]-WeightRight[i]) ;

i=In[x]; // элемент, перешедший из правого окна в левое f-=abs(WeightLeft[i]-WeightRight[i]); // сумма без 1 слагаемого

CountLeft[i]++; // теперь в левом окне таких на 1 больше

WeightLeft[i]+=Z; // вес их на Z больше

CountRight[i]—; // а в правом - на 1 меньше

WeightRight[i]-=Z; // вес их на Z меньше // обратно к полной сумме

f+=abs(WeightLeft[i]-WeightRight[i]);

FO[x]=f; // запишем значение функции отличия в массив }

Упражнение. Как будут выглядеть циклы (1) и (2) ?

Второй путь улучшения качества фрагментирования - находить макси­мальное значение функции отличия при нескольких длинах окна: Z|, Z₂,... ..., Z_q . Тогда эти вычисляемые значения FOi придется делить на длину со­ответствующего окна Zj, при котором это FOj вычислено. И предварительно умножать на 2^К, чтобы получались величины не от 0 до 2, а от 0 до 2*^+l.

Третий путь - периодическое (через каждые Y точек) нахождение опти­мальной длины окна Z0.

Четвертый - анализ массива FO после того, как он полностью заполнен.

Пятый - использование и других критериев при вычислении FO(A), на­пример

не 2| CountLeft[V] - CountRight[V] |,

a Z(CountLeft[V] - CountRightfV])².

D-мерный случай

В двумерном случае появляется возможность следить за изменением характеристик элементов при перемещении через точку Л!" по К разным пря­мым. В простейшем варианте - по двум перпендикулярным: горизонталь­ной и вертикальной.

Алгоритм может выглядеть, например, так: сначала проходим по стро­кам и заполняем массив FO значениями функции отличия при горизонталь­ном проходе: FO[A!]=FOropW- Затем идем по столбцам, вычисляя отличия при вертикальном проходе FObepW ^и записывая в массив максимальное из этих двух значений - FO_ropW и FO_BepW- Дальше можно таким же образом добавить FO при двух диагональных проходах (рис. 6.2), причем не для ка­ждой точки, а в окрестностях точек с максимумами FO[A].

Рис. 6.2. Иллюстрация двумерного случая с К=4

Кроме того, если хватает ресурсов, можно рассматривать отличие не от­резков длиной Z, отмеченных на К прямых, а секторов круга радиуса Z, раз­битого на К секторов. Это могут быть, например, две половины круга или же 4 четвертинки круга.

Теперь можно варьировать не только Z, пытаясь найти оптимальное зна­чение, но также и К.

Таким образом, будут найдены "контуры" - границы, отделяющие об­ласти с разными характеристиками совокупности содержащихся в этих об­ластях элементов.

В трехмерном случае: либо используем К_п прямых, либо К_к секторов круга, либо АГ_С секторов сферы. Причем оптимальные (с точки зрения вы­числения) значения К_п не 2,4, 8..., как в двумерном, а 3,7, 13...

(5^. Упражнение. Нарисуйте эти варианты с тремя прямыми, семью и тринадца­тью. Как продолжить процесс дальше?

Совершенно аналогично и в D-мерном случае.

Характеристики метода фрагментирования:

Степень сжатия: увеличивается в 1.0-1.2 раза.

Типы данных: неоднородные данные, особенно с точными граница-I ми фрагментов.

Симметричность по скорости: более чем 10:1.

Характерные особенности: может применяться не только для сжатия ! данных, но и для анализа их структуры.