Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Разделение мантисс и экспонент

Английское название метода - Separate Exponents and Mantissas (SEM).

Цель - сжатие потока Л-битовых элементов. В общем случае никаких предположений о свойствах значений элементов не делается, поэтому эту группу методов называют также представлением целых чисел (Representa­tion of Integers).

Основная идея состоит в том, чтобы отдельно описывать порядок значе­ния элемента Xt ("экспоненту" Е,) и отдельно - значащие цифры значения ("мантиссу" М,).

Значащие цифры начинаются со старшей ненулевой цифры: например, в числе 0000011012 = 1-2°+0-21+1-22+1-23+0-24+0-... = 13 это последние 4 цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем. В этом пункте экспонентой называем старшие биты, мантиссой - младшие.

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

Поскольку никаких величин вероятностей не вычисляется, никаких таб­лиц вероятностей не формируется, методы более эффективны в случае про­стой зависимости вероятности Р появления элемента со значением Z от са­мого значения Z: P=P(Z), и функция P(Z) относительно проста.

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

1) формируется один либо два выходных потока (в зависимости от ва­рианта метода) с кодами меньшего размера;

2) каждый из них может быть либо фиксированного размера (под запись числа отводится С бит, C<R), либо переменной (размер битовой за­писи зависит от ее содержания);

3) к каждому из них можно итеративно применять метод этого же се­мейства SEM (чаще всего это полезно применять к потоку с экспо­нентами).

Прямое преобразование

В самом простом случае под запись экспонент и мантисс отводится фик­сированное число битов: ЕиМ. Причем Е £ 1, М £ 1, E+M=R, где R - число битов в записи исходного числа.

Этот первый из четырех вариантов метода условно обозначим

■ Fixed+Fixed (Фиксированная длина экспоненты - Фиксированная длина мантиссы), а остальные три:

■ Fixed+Variable (Фиксированная длина экспоненты - Переменная длина мантиссы),

■ Variable+Variable (Переменная длина экспоненты - Переменная длина мантиссы) и

■ Variable+Fixed (Переменная длина экспоненты - Фиксированная длина мантиссы).

Базовый алгоритм первого варианта:

♦define R 15 //исходные элементы - 15-битовые

♦define E 7 //задано число битов под экспоненты

♦define M (R-E) //и мантиссы

for( i=0; i<N; i++) {//с каждым элементом исходного блока:
M[i] = ( (unsigned) S [i]) S ((1«M)-1); //мантиссы в массив М
E[i] = ((unsigned)S [i]) » M; //экспоненты в массив Е

}

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

S[N] - входной блок;

Е[Л/] - блок с экспонентами;

M[N] - блок с мантиссами.

Побитовый логический сдвиг влево на единицу эквивалентен умноже­нию на 2, поэтому (1«М) = 2м.

Если имеем распределение вероятностей, близкое к "плоскому": P{Z) ~ ~ const, то только первый рассмотренный вариант - Fixed+Fixed - может оказаться полезным: при правильном выборе числа Е результат сжатия блоков E[N], M[N] будет лучше, чем если сжимать исходный блок S[N]. Но ес­ли вероятности в целом убывают с ростом значений элементов и их распре­деление близко к такому:

P(Z) ;> P(Z+1), при любом Z, (1.3)

то полезны два варианта с переменным числом битов под мантиссы, т. е. схемы Fixed+Variable и Variable+Variable.

Если справедливо (1.3), кодирование таких чисел называется универ­сальным (Universal Coding of Integers).

Алгоритм второго варианта (Fixed+Variable):

idefine R 15 // исходные элементы - 15-битовые

tdefine E 4 //4 бита под экспоненты, так как 23 й R < 24

// S[i] - беззнаковые числа for(i=0; i<N; i++) { // с каждым элементом исходного блока:

j=0;

while (S[i]>=l«j) j++; // найдем такое j, что S[i]<(l«j)

E[i]=j; // запишем j, т. е- порядок

// числа S[i],B массив Е

if (j>l) // если j>l,

WriteBits(Output, S[i], j-1);// запишем (j-1) младших бит

//числа S[i] в битовый блок с мантиссами }

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

Упражнение. Составьте таблицу из 16 строк и двух столбцов: в левом - число битов, необходимых для записи чисел из диапазона D, справа - соответст­вующий диапазон D.

Третий вариант (Variable+Variable) будет отличаться лишь тем, что вместо

E[i]=j; //запишем j, т. е. порядок числа S[il", в массив Е

будет

WriteBits(Output,l,j+1);

В выходной битовый блок Output записываем подряд несколько нулевых битов, количество которых равно значению экспоненты, и в качестве при­знака окончания экспоненты записываем единичный бит:

for (k=j; k>0; k~)

WriteBit(Output,0); //j бит "О" WriteBit(Output,1); //и один бит "1"

| 0 1 О I О I О I ... I О I 1~1

•----- г------------ ■ Т

j нулевых младший

битов бит

Такая запись числа N, последовательность из N нулевых бит и одного единичного, называется унарным кодом.

Если исходные элементы - 32-битовые и почти все равны нулю, степень сжатия может доходить до 32:1.

Упражнение. Какой будет степень сжатия блока 16-битовых элементов в случае применения варианта Variable+Variable: 3,8,0,15,257,11,57867,2,65,18?

Последний, четвертый вариант (Variable+Fixed), отводящий переменное число битов под экспоненты и фиксированное - под мантиссы, будет рас­смотрен чуть ниже в подразд. про коды Раиса.

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

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

Обратное преобразование не сложнее прямого. В первом варианте внут­ри цикла будет:

for( i=0; i<N; i++) {//с каждым элементом исходного блока: S[i] = (E[i]«M)+M[i]; //старшие биты в массиве Е, младшие - в М }

Во втором варианте:

for( i=0; i<N; i++) {// с каждым элементом исходного блока:
j=E[i]; // возьмем j, т. е. порядок

// числа S[i],H3 массива Е
S[i]=l« (j-1); // запишем первую единицу в позиции,

// определяемой порядком числа
if (j>l) // если j>l,

S[i]+=GetBits (Input,j-1); // возьмем (j-1) младших бит //S[i] из битового блока с мантиссами }

В третьем вместо j=E[i]; //возьмем j, т. е. порядок числа 3[л.],из массива Е будет

j=0; // j - счетчик числа нулевых

while (GetBit(Input)==0) j++;// битов в битовом блоке Input

а дальше выполняются те же действия, что и во втором варианте:

S[i]=l«(j-1); // запишем первую единицу в позицию,

// определяемую порядком числа if (j>l) // если j>l, .,

S,(X]+-GetBits (Input, j-1);//возьмем (j-1) младших бит S[i]

//из битового блока с мантиссами

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

В каждом из рассмотренных выше четырех вариантов (Fixed+Fixed, Variable+Variable, Fixed+Variable, Variable+Fixed) можно пробовать улуч­шать сжатие за счет:

■ отказа от "классической" схемы с диапазонами длиной 2х и границами, выровненными по 2L (К, L - константы схемы);

■ использования априорного знания диапазона допустимых значений ис­ходных элементов;

■ применения хорошо исследованных схем кодирования (Элиаса, Раиса, Голомба, Фибоначчи).

При сжатии с потерями можно просто ограничивать число битов ман­тиссы М: сохранять только не более чем Л/, бит мантиссы (а остальные (М[/]-Л/|) бит - удалять, если M[i]>M{).

КОДЫ ПЕРЕМЕННОЙ ДЛИНЫ ( VARIABLE+VARIABLE ) Гамма- и дельта-коды Элиаса Эти коды генерируются так:

Диапазон

Гамма-коды

Длина кода, бит

Дельта-коды

Длина кода, бит

1

1

1

1

1

2...3

01х

3

ОЮх

4

4...7

001 хх

5

ОПхх

5

8...15

0001ххх

7

ООЮОххх

8

16...31

00001хххх

9

00101хххх

9

32...63

00000lxxxxx

И

ООПОххххх

10

64...127

000000lxxxxxx

13

ООП lxxxxxx

И

128...255

0000000lxxxxxxx

15

ОООЮООххххххх

14

и т. д., символами "х" здесь обозначены биты мантиссы без старшей единицы. Для диапазона [2*, 2*+|-1] коды формируются следующим образом: у-код: 00...(ЛГраз)...001х..(ЛТраз)..х; длина: 2К+1 бит; 5-код: n...(2L+l раз)...пх..(£раз)..х ; длина: 2-L+K+1 бит, где L = [log2(K+l)] - целая часть значения логарифма числа (К+\) по осно­ванию 2; п - биты, относящиеся к записи экспоненты 5-кода; их число 2-1+1.

Единственное отличие между у- и 5-кодами состоит в том, что в у-кодах экспоненты записываются в унарном виде, а в 8-кодах к ним еще раз при­меняется у-кодирование.

Видно, что у-коды первых 15 чисел короче 8-кодов, а у-коды первых 31 не длиннее 8-кодов. То есть чем неравномернее распределение вероятно­стей, чем круче возрастает вероятность чисел при приближении их значения к нулю, тем выгоднее у-коды по сравнению с 8-кодами.

Как соотносятся у-коды и наш базовый алгоритм третьего варианта (Variable+Variable)? Если к у-коду слева добавить столбец, состоящий из одной единицы и последовательности нулей, то получим такое соответствие кодов числам:

Диапазон

Гамма-коды

Диапазон

Дельта-коды

0

-

0

1

1

1

1

01

2-3

01х

2-3

001х

4-7

001 хх

4-7

0 001хх

8-15

0001ххх

8-15

0 0001 ххх

16-31

00001хххх

16-31

0 00001хххх

32-63

00000lxxxxx (до добавления)

32-63

0 00000 lxxxxx (после добавления)

Оно как раз и соответствует базовому алгоритму третьего варианта. Если еще раз прибавить такой столбец и к значениям чисел прибавить 2, то соответствие примет такой вид:

Диапазон

Гамма-коды

1

1

2

01

3

001

4-5

OOOlx

6-9

0 0 001хх

10-17

0 0 0001 ххх

18-33

0 0 00001хххх

34-65

0 0 00000 lxxxxx

Y(3)

Таким образом, единственный параметр обобщенных у(Л>кодов - число кодов без битов мантиссы. Традиционный у-код - это у(1). У обобщенных 8-кодов два параметра.

Упражнение. Напишите функцию, создающую у(3)-код задаваемого числа, а затем функцию для 6(3,3)-кода.

Коды Раиса и Голомба

Коды Раиса и Голомба изначально задаются с одним параметром и вы­глядят так:

я ю

si

о U

т=1

т=2

/и=3

т=4

т=5

т=6

т=1

т=8

Код Раи­са:

А=0

А=1

*=2

к=Ъ

п=1

0

00

00

000

000

000

000

0000

2

10

01

010

001

001

001

0010

0001

3

ПО

100

011

010

010

0100

ООП

0010

4

1110

101

100

011

ОНО

0101

0100

ООП

5

НПО

1100

1010

1000

0111

оно

0101

0100

6

111110

1101

1011

1001

1000

0111

оно

0101

7

1111110

11100

1100

1010

1001

1000

0111

оно

8

11101

11010

1011

1010

1001

1000

0111

9

111100

поп

11000

10110

10100

10010

10000

Алгоритм построения кодов можно понять с помощью следующих двух таблиц:

7Л=2

т=Ъ

m=4

m=8

Ох

00

Oxx

Oxxx

10х

01х

Юхх

Юххх

ИОх

100

HOxx

HOxxx

1П0х

101х

lllOxx

11 Юххх

ППОх

1100

llllOxx

llllOxxx

П01х

11100

lllOlx

Видно, что коды Голомба при m=2 - это коды Раиса с к = S, экспоненты записываются в унарном виде, а под мантиссы отведено S бит. Далее:

т—5

т=6

т=1

ООх

ООх

000

010

01хх

001х

ОПх

ЮОх

Olxx

ЮОх

101хх

1000

1010

ПООх

lOOlx

1011х

HOlxx

lOlxx

ПООх

11 ЮОх

11000

lllOlxx

HOOlx

11 ПООх

HOlxx

111000

Если m<2s, первые т кодов начинаются с 0, вторая группа из т кодов начинается с 10, третья - 110 и т. д. Диапазоны длиной т не выровнены по границам, равным 2L, как в у-кодах Элиаса. Экспоненты вычисляются как е = (л-1)/от (деление целочисленное) и записываются в унарной системе счис­ления: е бит 1 и в конце бит 0. Под мантиссы г ~ п-ет-1 отводится либо (S4), либо S бит.

Очевидно, что к экспонентам, как и в случае с у-кодами Элиаса, можно применять либо у(Х)-, либо Оо1отЬ(т)-кодирование. Аналогично и к экспо­нентам у-кода - не только у(Х), но и Golomb(m).

Упражнение. Напишите функцию, создающую y(3)-Golomb(2)-KOfl задаваемого числа. То есть у(3), к экспонентам которого применен Golomb(2)-KOfl.

Омега-коды Элиаса и коды Ивэн-Родэ

Английские названия кодов: omega (oo) Elias codes и Even-Rodeh codes соответственно.

Эти коды определены так:

Диапазон

ш-код

Би­тов

Ивэн-Родэ-код

Би­тов

1

0

1

00

2

2...3

1x0

3

Olx

3

Л...1

10 1хх0

6

lxxO

4

8...15

11 lxxxO

7

100 lxxx 0

8

16...31

10 100 1хххх0

11

101 lxxxxO

9

32...63

10 101 lxxxxxO

12

HOlxxxxxO

10

64...127

10 110 lxxxxxxO

13

111 lxxxxxxO

11

128...255

10 111 lxxxxxxxO

14

100 1000 lxxxxxxxO

16

И те и другие состоят из последовательности групп длиной Lit L2, Z-з,..., Lm, начинающихся с бита 1. Конец последовательности задается битом 0. Длина каждой следующей (и+1)-й группы задается значением битов преды­дущей n-й группы. Значение битов последней группы является итоговым значением всего кода, т. е. всей последовательности групп. Иначе говоря, все первые т-\ групп служат лишь для указания длины последней группы.

В со-кодах Элиаса длина первой группы - 2 бита и далее длина следую­щей группы равна значению предыдущей плюс один. Первое значение зада­но отдельно.

В Ивэн-Родэ-кодах длина первой группы - 3 бита и далее длина каждой следующей группы равна значению предыдущей. Первые 3 значения заданы особым образом.

При кодировании формируется сначала последняя группа, затем предпо­следняя и т. д., пока процесс не будет завершен.

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

Упражнение. Как будут выглядеть коды ш Элиаса и Ивэн-Родэ для чисел из диапазонов 256...511 и 512...1023 ?

Старт-шаг-стоп (start-step-stop) коды

Старт-шаг-стоп-коды задаются тремя параметрами: (i j,k). Экспонента может занимать l,2,3,...,m-l,m бит, а мантисса - /, /+/', /+2/, i+3j,...,k.

Если (ijjc)=(3,2,l 1), то коды выглядят так:

Диапазон

(3,2,11)-код

Длина кода, бит

1...8

Оххх

4

9...40

Юххххх

7

41...168

ПОххххххх

10

169...680

ШОххххххххх

13

681...2728

llllxxxxxxxxxxx

15

Таким образом, это соответствие можно использовать для чисел из диа­пазона [1,2728]. Экспонента записывается в унарной системе счисления: ко­нец поля экспоненты указывается с помощью нуля. Для пятой группы, имеющей максимальную длину мантиссы - 11 бит, разделяющий нуль не нужен, так как вне зависимости от его наличия декодирование однозначно.

Если максимальное значение кодируемых чисел не задано, то и третий параметр не задается. Такие коды называются Старт-Шаг-кодами (Start-Step-codes).

Коды Фибоначчи

Самые интересные, нетривиальные коды. Исходное число ./V раскладыва­ется в сумму чисел Фибоначчи/ (f\=\, fi=2, frfi-\+fi-i)- Известно, что любое число однозначно представимо в виде суммы чисел Фибоначчи. Поэтому можно построить код числа как последовательность битов, каждый из кото­рых указывает на факт наличия в N определенного числа Фибоначчи.

Заметим также, что если в N есть/-, то в нем не может быть/|+1. Поэтому если единичное значение бита указывает на использование какого-то числа //, то мы можем обозначать конец записи текущего кода и начало следующе­го последовательностью из двух единиц:

fr.

1

2

3

5

8

13

21

34

55

и=1

1

2

0

1

(1)

3

0

0

1

d)

4

1

0

1

(1)

5

0

0

0

1

(1)

б

1

0

0

1

(1)

7

0

1

0

1

(1)

8

0

0

0

0

1

(1)

12

1

0

1

0

1

(1)

13

0

0

0

0

0

1

(1)

...

20

0

1

0

1

0

1

(1)

21

0

0

0

0

0

0

1

(1)

...

27

1

0

0

1

0

0

1

(1)

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

Рассмотрим утверждение подробнее.

Если в потоке у-кодов или кодов Раиса будет искажен 1 бит, длина и со­держимое остального потока не изменится, если этот бит мантисса (и "испорчен" окажется только один код). Но если "сломанный" бит экспо­нента, то будет неправильно декодирована значительная часть потока.

Если в потоке унарных кодов изменить один бит, кодов станет либо на один больше, если этот бит экспонента:

...00000001000000001... -было

... 00100001000000001... - стало

либо на один код меньше, если этот бит мантисса: ...00000000000000001...

С другой стороны, для потока кодов Фибоначчи кодов станет на один меньше, если "сломавшийся" бит экспонента, т. е. один из двух единичных битов, обозначающих конец кода, либо на один больше, если и "сбойный" бит стал таким, как бит экспоненты (1), и хотя бы один из двух соседних со сбойным битов экспоненты единичный. В остальных же случаях "сломает­ся" только один код (в некоторых случаях может "сломаться" пара ссседних кодов). Но весь поток, как может быть в случае у- и Голомб-кодов, никогда1.

Упражнение. Приведите пример, показывающий, как из-за сбоя в одном бите "сломается* 3 кода Фибоначчи.

Замечание по унарным кодам. Если, например, мы сжимаем поток элемен­тов со значениями:

1,3,4,7,9,10,13,15,16,20,25,26,28,30,33... так называемым методом флагов:

101100101100101100010000110101001... то реально здесь имеем два метода: линейно-предсказывающее кодирование (LPC) плюс унарные коды (см. подразд. "Линейно-предсказывающее кодирова­ние'').

Коды фиксированной длины (fixed+fixed)

Несмотря на недостатки с точки зрения сравнительно низкой степени сжатия, коды фиксированной длины широко используются на практике. Положительными особенностями данного варианта SEM являются:

■ высокая скорость кодирования;

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

Fixed+Fixed - это самый простой, самый подходящий вариант для по­следующей сортировки параллельных блоков (PBS).

Предварительная обработка данных с помощью варианта SEM Fixed+Fixed может также улучшить степень сжатия RLE, SC или LPC. Весьма вероятно,

что во входных данных разность между экспонентами соседних кодов явля­ется в основном D-битовой (т. е. ее можно записать с помощью D бит) и эти D-битовые элементы далее несжимаемы. А после SEM Fixed+Fixed с M-D-1 разность между соседними экспонентами в основном равна нулю. Н таким образом, от каждого элемента остается в среднем примерно D-1 бит, а не D. Пример: поток элементов, у которых младшие 8 бит меняются хаотично, а старшие 8 - константа. Если делать LPC без SEM, в выходном потоке бу­дет оставаться в среднем по 9 бит от каждого элемента, а после SEM+LPC -по 8 бит.

Улучшит сжатие выбор оптимальных размеров экспонент и мантисс. Правильное разделение мантисс и экспонент во многом аналогично выделе­нию шума из аналогового сигнала.

Коды смешанные (fixed+variable)

Поможет улучшить сжатие знание диапазона, особенно если его длина не равна степени двойки: L<2s+\ L=2S+C. Тогда при максимальном значении экспоненты под запись мантиссы потребуется на 1 бит меньше в (2S-Q слу­чаях при С^2*"', на 2 бита меньше в (2*"'-С) случаях при г^^ОЗ5-1 и т. д.

Например, если диапазон 1=215, то при Е[/]=15 под запись мантиссы нужно 15 бит, а если 1=214+213-7, то при Е[/]=15 достаточно 14 бит, а в семи случаях -13 бит.

PBS в данном случае уже не столь прост и тривиален, как в предыдущем случае Fixed+Fixed, но все-таки применим, a LPC, RLE или SC для экспо­нент ничуть не сложнее.

Применимы также методы типа DAKX (по имени первоисследователя: D. A. Kopf), отводящие на каждом шаге фиксированное число битов под экспоненту, но помещающие в единый выходной поток "флаги" с информацией об изменении числа битов экспоненты.

Заметим, что в общем случае "флагом" в потоке может быть не только условие на значение одного элемента вида "S[i']=F?" или "fiS[i\)=sFln, но и условие на значение функции от нескольких последних элементов: 7(S[/],S[/-1],S[/-2],...)=F?". И битов, относящихся исключительно к записи "флага", в потоке может и не быть.

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

Если памяти достаточно, имеет смысл при инициализации алгоритма строить таблицу. Для алгоритма сжатия - содержащую соответствующие Е[/] и М[г] по адресу, задаваемому значением S[i]. Для разжатия, наобо­рот, - содержащую S[/] по адресам, задаваемым значениями E[i] и M[i].

В результате внутренний цикл (если он есть) вида

j-0;

while (S[i] >= l«j) j++; //найдем такое j, что S[i]< (l«j)

(см. алгоритм сжатия, второй вариант)

преобразуется в вид

j=T[S[i]]; //возьмем такое j, что S[i]< (l«j)

Упражнение. Напишите функцию, строящую таблицу Т для этого варианта (Fixed+ +Variable).

Очевидно, что размер таблицы Т будет равен размеру диапазона 2Л воз­можных значений элементов входного потока S. Поэтому компромисс меж­ду объемом памяти и скоростью работы может находиться где-то посереди­не: например если L-216, то вместо

j=T[S[i]]; //возьмем такое j, что S[i]< (l«j)

можно реализовать вычисление^' так:

j=T[S[i]»8]+8; // j>8, если S[i]>=256

if (j==8) j-T[S[i]]; // j-8, если S[i]<256

На несколько операций дольше по сравнению с первым рассмотренным ва­риантом использования таблицы, но и размер Т уже не 2|6=65536, а 28=25б.

Характеристики методов семейства SEM: Степень сжатия: до R: 1, где R - размер исходных элементов. Типы данных: любые данные, лучше количественные. Симметричность по скорости: в общем случае 1:1. Характерные особенности: традиционно используется для эффектив-\ ного кодирования источников без памяти.