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

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

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

Значащие цифры начинаются со старшей ненулевой цифры: например, в числе 000001101₂ = 1-2°+0-2¹+1-2²+1-2³+0-2⁴+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^х и границами, выровненными по 2^L (К, 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 = [log₂(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<2^s, первые т кодов начинаются с 0, вторая группа из т кодов начинается с 10, третья - 110 и т. д. Диапазоны длиной т не выровнены по границам, равным 2^L, как в у-кодах Элиаса. Экспоненты вычисляются как е = (л-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

И те и другие состоят из последовательности групп длиной L_it L₂, Z-з,..., L_m, начинающихся с бита 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), и хотя бы один из двух соседних со сбойным битов экспоненты единичный. В остальных же случаях "сломает­ся" только один код (в некоторых случаях может "сломаться" пара ссседних кодов). Но весь поток, как может быть в случае у- и Голомб-кодов, никогда¹.

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

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

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

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

Заметим, что в общем случае "флагом" в потоке может быть не только условие на значение одного элемента вида "S[i']=F?" или "fiS[i\)=^sFlⁿ, но и условие на значение функции от нескольких последних элементов: 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-2¹⁶, то вместо

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, а 2⁸=25б.

натяжные потолки контакты, Производство натяжных потолков

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