Опрос

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

Новички

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

Арифметическое сжатие

Классический вариант алгоритма

Сжатие по методу Хаффмана постепенно вытесняется арифметическим сжатием. Свою роль в этом сыграло то, что закончились сроки действия па­тентов, ограничивающих использование арифметического сжатия. Кроме того, алгоритм Хаффмана приближает относительные частоты появления символов в потоке частотами, кратными степени двойки (например, для символов а, Ъ, с, d с вероятностями 1/2, 1/4, 1/8, 1/8 будут использованы ко­ды О, 10, 110, 111), а арифметическое сжатие дает лучшую степень прибли­жения частоты. По теореме Шеннона наилучшее сжатие в двоичной ариф­метике мы получим, если будем кодировать символ с относительной часто­той f с помощью -log2(f) бит.

0.3 0,4 0.5 0.6 0.7

Относительная частота символа

"^~" Оптимальное сжатие
---- Метод Хаффмана

Рис. 1.1. График сравнения оптимального кодирования и кодирования по методу Хаффмана

На графике выше приводится сравнение оптимального кодирования и кодирования по методу Хаффмана. Хорошо видно, что в ситуации, когда относительные частоты не являются степенями двойки, сжатие становится менее эффективным (мы тратим больше битов, чем это необходимо). На­пример, если у нас два символа а и Ь с вероятностями 253/256 и 3/256, то в идеале мы должны потратить на цепочку из 256 байт -log2(253/256)-253-bg2(3/256)-3 = 23.546, т. е. 24 бита. При кодировании по Хаффману мы за­кодируем а и Ъ как 0 и 1 и нам придется потратить 1 -253+1 -3=256 бит, т. е. в 10 раз больше. Рассмотрим алгоритм, дающий результат, близкий к опти­мальному.

Арифметическое сжатие - достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дро­би, при этом строим дробь таким образом, чтобы наш текст был представ­лен как можно компактнее. Для примера рассмотрим построение такой дро­би на интервале [0, 1) (0 - включается, 1 - нет). Интервал [0, 1) выбран по­тому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В даль­нейшем будем называть их диапазонами соответствующих символов.

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

Символ

Частота

Вероятность

Диапазон

О

3

0.3

Г0.0; 0.3)

К

2

0.2

Г0.3; 0.5)

В

2

0.2

[0.5; 0.7)

Р

1

0.1

Г0.7; 0.8)

А

1

0.1

Г0.8; 0.9)

и и

1

0.1

Г0.9; 1.0)


Будем считать, что эта таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствии с заданными частотами символов (см. таблицу диапазонов). В качестве следующего рабочего интервала берется диапазон, соответствующий текущему кодируемому символу. Его длина пропор­циональна вероятности появления этого символа в потоке. Далее считываем следующий символ. В качестве исходного берем рабочий интервал, полу­ченный на предыдущем шаге, и опять разбиваем его в соответствии с таб­лицей диапазонов. Длина рабочего интервала уменьшается пропорциональ­но вероятности текущего символа, а точка начала сдвигается вправо про­порционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего и т. д.

Используя исходную таблицу диапазонов, кодируем текст "КОВ.КОРОВА":

Исходный рабочий интервал Символ "К" [0.3; 0.5) получаем [0.0; 0.3) получаем [0.5; 0.7) получаем [0.9; 1.0) получаем

[0, 1).

Символ "О" Символ "В" Символ"."

Графический процесс представить так, как на рис

[0.3000; 0.5000). [0.3000; 0.3600). [0.3300; 0.3420). [0,3408; 0.3420).

кодирования первых трех символов можно 1.2.

Рис. 1.2. Графический процесс кодирования первых трех символов

Таким образом, окончательная длина интервала равна произведению ве­роятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Если обозначить диапазон символа с как [а[с]; Ь[с]), а интервал для /-го кодируемого символа потока как [/,, А/), то алгоритм сжатия может быть записан как

I0=0; h0=l; 1=0;

while (not DataFile.EOFO ) {

с = DataFile.ReadSymbol (); i++;

lt = li.j + a[c)- {hi-! - li.j);

hL = li.i + b[c) • {h^! - Ii_i); };

Большой вертикальной чертой на рисунке выше обозначено произволь­ное число, лежащее в полученном при работе интервале [/,-, Л/). Для после­довательности "КОВ.", состоящей из четырех символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки.

Рассмотрим работу алгоритма восстановления цепочки. Каждый сле­дующий интервал вложен в предыдущий. Это означает, что если есть число 0.341, то первым символом в цепочке может быть только "К", поскольку только его диапазон включает это число. В качестве интервала берется диа­пазон "К" - [0.3; 0.5) и в нем находится диапазон [а[с]; Ь[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал [0.3; 0.36), соответствующий диапазону для "О", включает число 0.341. Этот интервал выбирается в качестве следующе­го рабочего и т. д. Алгоритм декомпрессии можно записать так:

2о=0; h0=l; value=»File.Code () ; for(i=l; i<=File.DataLength(); i++){ for(для всех С)){

li = Ij.j + a[Cj]-(fti-j - li-i); hi = li.! + b[c}] ■ {hi.! - li.i); if {{lt <= value) && (value < hi) ) break; }; DataFile.WriteSymbol(c^) ;

где value - прочитанное из потока число (дробь), а с - записываемые в вы­ходной поток распаковываемые символы. При использовании алфавита из 256 символов Cj внутренний цикл выполняется достаточно долго, однако его можно ускорить. Заметим, что поскольку Ь[с^ {\=a[cj\ (см. приведенную выше таблицу диапазонов), то /,■ для Cy+i равно А, для с,, а последователь­ность ht для Cj строго возрастает с ростом у. То есть количество операций во внутреннем цикле можно сократить вдвое, поскольку достаточно проверять только одну границу интервала. Также если у нас мало символов, то, отсор­тировав их в порядке уменьшения вероятностей, мы сокращаем число ите­раций цикла и таким образом ускоряем работу декомпрессора. Первыми бу­дут проверяться символы с наибольшей вероятностью, например в нашем примере мы с вероятностью 1/2 будем выходить из цикла уже на втором символе из шести. Если число символов велико, существуют другие эффек­тивные методы ускорения поиска символов (например, бинарный поиск).

Хотя приведенный выше алгоритм вполне работоспособен, он будет ра­ботать медленно по сравнению с алгоритмом, оперирующим двоичными дробями. Двоичная дробь задается как O-a^a^jij = ail/2 + a2l/4 + + а3-1/8+... а,-1/2'. Таким образом, при сжатии нам необходимо дописывать в дробь дополнительные знаки до тех пор, пока получившееся число не по­падет в интервал, соответствующий закодированной цепочке. Получившее­ся число полностью задает закодированную цепочку при аналогичном алго­ритме декодирования (рис. 1.3).

Упражнение. Восстановить исходный текст из закодированной цепочки в 2 би­та, равных "11" (число 0.1'\ю=0.75уо)), используя приведенную выше таблицу диапазонов, если известно, что длина текста 10 символов.

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

файла при этом следует передавать декомпрессору явным образом перед сжатыми данными, как это делалось в приведенных выше примерах.

Приведенный выше алгоритм может сжимать только достаточно корот­кие цепочки из-за ограничений разрядности всех переменных. Чтобы избе­жать этих ограничений, реальный алгоритм работает с целыми числами и оперирует с дробями, числитель и знаменатель которых являются целыми числами (например, знаменатель равен lOOOOh = 65536). При этом с потерей точности можно бороться, отслеживая сближение // и ht и умножая числи­тель и знаменатель представляющей их дроби на какое-то число (удобно на 2). С переполнением сверху можно бороться, записывая старшие биты в 1, и ht в файл тогда, когда они перестают меняться (т. е. реально уже не участ­вуют в дальнейшем уточнении интервала). Перепишем таблицу диапазонов с учетом сказанного выше:

J

Символ (q)

Накопленная частота

ЬИ

0

-

-

0

I

О

3

3

2

К

2

5

3

в

2

7

4

р

1

8

5

А

1

9

6

к и

1

10

Теперь запишем алгоритм сжатия, используя целочисленные операции. Минимизация потерь по точности достигается благодаря тому, что длина целочисленного интервала всегда не менее половины всего интервала. Ко­гда /,• или ht одновременно находятся в верхней или нижней половине (Half) интервала, то мы просто записываем их одинаковые верхние биты в выходной поток, вдвое увеличивая интервал. Если /,• и й, приближаются к середине интервала, оставаясь по разные стороны от его середины, то мы также вдвое увеличиваем интервал, записывая биты "условно". "Условно" означает, что реально эти биты выводятся в выходной файл позднее, когда становится известно их значение. Процедура изменения значений /,■ и А на­зывается нормализацией, а вывод соответствующих битов - переносом. Знаменатель дроби в приведенном ниже алгоритме будет равен lOOOOh = = 65536, т. е. максимальное значение Л0=65535.

i0=0; h0=65535; i=0; delitel- b[cu,t]; II delitel=10

First_qtr - (h0+l)/4; // - 16384

Half = First_qtr*2; // - 32768

Third_qtr - First_qtr*3;// •= 49152

bits_to_follow =0; // Сколько битов сбрасывать

while (not DataFile.EOFO ) {

с = DataFile.ReadSymbol(); // Читаем символ
j = IndexForSymbol(с); i++; // Находим его индекс
li = li.j + b[j-l]*{hi.1 - li-x + l)/delitel;
hi = li.! + b[j )*(hi.1 - li.! + l)/delitel - 1;
for(;;) { // Обрабатываем варианты

if (hi < Half) // переполнения

BitsPlusFollow(O); else if {li >= Half) { BitsPlusFollow(l); li-= Half; hi-= Half;

}

else if((li >= First_gtr)&&(hi < Third_qtr)){ bits_to_follow++; li-= First_qtr; hi-= First_gtr; } else break; li+=li,- hi+= hi+1; } }

// Процедура переноса найденных битов в файл void BitsPlusFollow(int bit) {

CompressedFile.WriteBit(bit); for(; bits_to_follow > 0; bits_to_follow--) CompressedFile.WriteBit(!bit); }

Упражнение. Покажите, что BitsPlusFollow работает правильно и записы­вает в выходной файл значения, попадающие внутрь рабочего интервала.

/

Символ

(С/)

1,

hi

Нормалиэова нный /,

Нормали­зованный hi

Результат

0

0

65535

1

К

19660

32767

13104

65535

01

2

0

13104

28832

26208

57665

010

3

В

41937

48227

7816

58143

010101

4

53111

58143

15836

35967

01010111

5

К

21875

25901

21964

38071

0101011101

6

О

21964

26795

22320

41647

010101110101

Упражнение. Выведите самостоятельно, какими битами нужно закончить сжа­тый файл, чтобы при декомпрессии были корректно получены последние 2- 3 символа цепочки.

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

20=0; h0=65535; delitel= b[clast] ;
First_qtr = (h0+l)/4; // = 16384

Half = First_qtr*2; // = 32768

Third_qtr = First_qtr*3; // = 49152

value=CompressedFile.Readl6Bit();

for(i=l; i< CompressedFile.DataLengthO; i++){

freq=((value-2i.1+l)*delitel-l)/(hi.I - 1±.х + 1) ;

for(j=l; b[jf]<=freq; j++); // Поиск символа

li = 1ы + blj-l]*{bi.! - li-u + l)/delitel;

hi = Im + b[j ]*{hi.1 - li.! + l)/delitel - 1;

for(;;) { // Обрабатываем варианты

if (hi < Half) // переполнения

; // Ничего else ifdi >= Half) {

2i-= Half; hi-= Half; value-= Half; }

else if (di >= First_qtr)&& (hi < Third_qtr)) { 2i-= First_qtr; hi-= First_qtr; value-= First_qtr,-} else break; 2i+=2i; hi+= hi+1;

value+=value+CompressedFile.ReadBit(); } DataFile.WriteSymbol(c); );

Упражнение. Предложите примеры последовательностей, сжимаемых алго­ритмом с максимальным и минимальным коэффициентом.

Как видно, с неточностями арифметики мы боремся, выполняя отдель­ные операции над /, и А, синхронно в компрессоре и декомпрессоре.

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

Для того чтобы оценить степень сжатия арифметическим алгоритмом конкретной строки, нужно найти минимальное число N, такое, чтобы длина рабочего интервала при сжатии последнего символа цепочки была бы меньше 1/2^.. Этот критерий означает, что внутри нашего интервала заведо­мо найдется хотя бы одно число, в двоичном представлении которого после N-ro знака будут только 0. Длину же интервала, дорчитать просто, поскольку она равна произведению вероятностей всех символов.

Рассмотрим приводившийся ранее пример строки из двух символов л и Ъ с вероятностями 253/256 и 3/256. Длина последнего рабочего интервала для цепочки из 256 символов а и Ь с указанными вероятностями равн. Легко подсчитать, что искомое N=24 (1/224= 5.96-10"8), поскольку 23 дает слишком большой интервал (в 2 раза шире), а 25 не является минимальным числом, удовлетворяющим критерию. Выше было показано, что алгоритм Хаффмана кодирует данную цепочку в 256 бит. То есть для рассмотренного примера арифметический алгоритм дает десятикратное преимущество, пе­ред алгоритмом Хаффмана и требует менее 0.1 бита на символ.

Упражнение. Подсчитайте оценку степени сжатия для строки "КОВ.КОРОБА".

Следует сказать пару слов об адаптивном алгоритме арифметического сжатия. Его идея заключается в том, чтобы перестраивать таблицу вероят­ностей b[f] по ходу упаковки и распаковки непосредственно при получении очередного символа. Такой алгоритм не требует сохранения значений веро­ятностей символов в выходной файл и, как правило, дает большую степень сжатия. Так, например, файл вида а1000£1000с1000б/1000 (где степень означает число повторов данного символа) адаптивный алгоритм сможет сжать, эф­фективнее, чем потратив 2 бита на символ. Приведенный выше алгоритм достаточно просто превращается в адаптивный. Ранее мы сохраняли табли­цу диапазонов в файл, а теперь мы считаем прямо по ходу работы компрес­сора и декомпрессора, пересчитываем относительные частоты, корректируя в соответствии с ними таблицу диапазонов. Важно, чтобы изменения в таб­лице происходили в компрессоре и декомпрессоре синхронно, т. е., напри­мер, после кодирования цепочки длины 100 таблица диапазонов должна быть точно такой же, как и после декодирования цепочки длины 100. Это условие легко выполнить, если изменять таблицу после кодирования и де­кодирования очередного символа. Подробнее об адаптивных алгоритмах смотрите в гл. 4.

Характеристики арифметического алгоритма:

Лучшая и худшая степень сжатия: лучшая > 8 (возможно кодирование менее бита на символ), худшая - 1.

Плюсы алгоритма: обеспечивает лучшую степень сжатия, чем алго-I ритм Хаффмана (на типичных данных на 1-10%).

Характерные особенности: так же как кодирование по Хаффману, не увеличивает размера исходных данных в худшем случае.

Интервальное кодирование

В отличие от классического алгоритма, интервальное кодирование пред­полагает, что мы имеем дело с целыми дискретными величинами, которые могут принимать ограниченное число значений. Как уже было отмечено, начальный интервал в целочисленной арифметике записывается в виде [ОД) или [0,//-1], где N- число возможных значений переменной, используемой для хранения границ интервала.

Чтобы наиболее эффективно сжать данные, мы должны закодировать каждый символ s посредством -log2(Ј) бит, где f, - частота символа s. Ко­нечно, на практике такая точность недостижима, но мы можем для каждого символа s отвести в интервале диапазон значений [N(Fs)^f(F,+fi)), где Fs -накопленная частота символов, предшествующих символу s в алфавите, N(f) - значение, соответствующее частоте / в интервале из N возможных значений. И чем больше будет N(fs), тем точнее будет представлен символ s в интервале. Следует отметить, что для всех символов алфавита должно со­блюдаться неравенство Х>0.

Задачу увеличения размера интервала выполняет процедура, называемая нормализацией. Практика показывает, что можно отложить выполнение нормализации на некоторое время, пока размер интервала обеспечивает приемлемую точность. Микаэль Шиндлер (Michael Schindler) предложил в работе [3] рассматривать выходной поток как последовательность байтов, а не битов, что избавило от битовых операций и позволило производить нормализацию заметно реже. И чаще всего нормализация обходится без вы­полнения переноса, возникающего при сложении значений нижней границы интервала и размера интервала. В результате скорость кодирования возрос­ла в полтора раза при крайне незначительной потере в степени сжатия (раз­мер сжатого файла обычно увеличивается лишь на сотые доли процента).

Выходные данные арифметического кодера можно представить в виде четырех составляющих:

1. Составляющая, записанная в выходной файл, которая уже не может из­мениться.

2. Один элемент (бит или байт), который может быть изменен переносом, если последний возникнет при сложении значений нижней границы ин­тервала и размера интервала.

3. Блок элементов, имеющих максимальное значение, через которые по це­почке может пройти перенос.

4. Текущее состояние кодера, представленное нижней границей интервала.

Например:

Составляющая, за­писанная в файл

Элемент, который может быть изме­нен переносом

Блок элементов, имеющих макси­мальное значение

Нижняя грани­ца интервала

D7 03 56 Е4

ЗА

FFFF

35 38В1

+

Размер интервала

ЕА 12 1А

=

Перенос

ЗВ

00 00

1F4ACB

При выполнении нормализации возможны следующие действия:

1. Если интервал имеет приемлемый для обеспечения заданной точности размер, нормализация не нужна.

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

3. В случае возникновения переноса он выполняется в составляющих 2 и 3, после чего они также записываются в выходной файл.

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

Ниже приведен исходный текст алгоритма, реализующего нормализа­цию для интервального кодирования[3].

// Максимальное значение, которое может принимать // переменная. Для 32-разрядной арифметики // C0DEBITS = 31. Один бит отводится для // определения факта переноса. #define TOP (l«CODEBITS)

// Минимальное значение, которое может принимать // размер интервала. Если значение меньше, // требуется нормализация #define BOTTOM (TOP»8)

//На сколько битов надо сдвинуть значение нижней // границы интервала, чтобы остался 1 байт #define SHIFTBITS (C0DEBITS-8)

// Если для хранения значений используется 31 бит,

// каждый символ сдвинут на 1 байт вправо

// в выходном потоке и при декодировании приходится

// его считывать в 2 этапа.

Idefine EXTRABITS ((C0DEBITS-1)%8+1)

// Используемые глобальные переменные:

// next_char - символ, который может быть изменен

// переносом (составляющая 2).

// carry_counter - число символов, через которые

// может пройти перенос до символа next_char

// (составляющая 3).

// low - значение нижней границы интервала,

// начальное значение равно нулю.

// range - размер интервала,

// начальное значение равно ТОР.

void encode_normalize( void ) { while ( range <= BOTTOM ) {

// перенос невозможен, поэтому возможна

// запись в выходной файл (ситуация 2) if ( low < OxFF « SHIFTBITS ) {

output_byte( next_char );

for (;carry_counter;carry_counter—) output_byte(OxFF);

next_char = low » SHIFTBITS;

// возник перенос (ситуация 3) } else if( low >= TOP ) {

output_byte( next_char+l );

for (;carry_counter;carry_counter—) output_byte(OxO);

next_char = low » SHIFTBITS;

// элемент, который может повлиять на перенос // (ситуация 4) } else {

carry_counter++;

}

range «= 8;

low = (low « 8) & (TOP-1);
void decode_normalize( void ) { while( range <= BOTTOM ) { range «= 1 ; low = low«8 I

((next_char«EXTRABITS) & OxFF) ; next_char = input_byte(); low |= next_char » (8-EXTRABITS); range «= 8; } }

Для сравнения приведем текст функции, оперирующей с битами, из ра­боты [2]:

#define HALF (1« (CODEBITS-1)) #define QUARTER (HALF»1)

void bitplusfollow( int bit ) {

outputjbit( bit );

for(;carry_counter;carry_counter—) output_bit(!bit); }

void encode_normalize( void ) { while ( range <= QUARTER ) { if( low >= HALF ) { bit_plus_follow(1) ; low -= HALF; ) else if( low + range <= HALF ) {

bit_plus_follow(0); } else {

carry_counter++; low -= QUARTER; }

low «= 1; range «= 1; ) }

void decode_normalize( void ) { while( range <= QUARTER ) { range «= 1 ;

low = 1ow<<1 |input_bit(); } )

Процедура интервального кодирования очередного символа выглядит следующим образом:

void encode(

int symbol_freq, // частота кодируемого символа
int prev_freq, // накопленная частота символов,
// предшествующих кодируемому
//в алфавите
int total_freq // частота всех символов
) { •" '

int r «= range / total_freq; low +■ r*prev_freq; range •= r*symbol_freq; encode^normalize(); }

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

Рассмотрим пример интервального кодирования строки "КОВ.КОРО-ВА". Частоты символов задаются следующим образом:

Индекс

Символ

Symbol_freq

Prev_freq

0

О

3

0

1

К

2

3

2

В

2

5

3

Р

1

7

4

А

1

8

5

и tt

1

9

total freq

10

Для кодирования строки будем использовать функцию compress:

void compress (

DATAFILE *DataFile // файл исходных данных

) {

low - 0;

range ■= TOP;

next_char ■ 0;

carry_counter - 0;

while( IDataFile.EOF ()) {

с = DataFile.ReadSymbol() // очередной символ encode( Symbol_freq[c], Prev_freq[c], 10 ) ;

}

Символ

Symbol _freq

Prev _freq

Low

Range

Результат

0

0x7FFFFFFF

К

2

3

0x26666664

0x19999998

0

3

0

0x26666664

0x051EB850

В

2

5

0x28F5C28A

0x010624DC

1

9

0x29ElB07C

0x001A36E2

Нормализация

0x61B07C00

0xlA36E200

0x53

К

2

3

0x698DC232

0x053E2ECC

0x53

0

3

0

0x698DC232

0x0192A7A3

0x53

Р

1

7

0x6AA79DEC

0x002843F6

0x53

Нормализация

0x279DEC00

0x2843F600

0x53D5

0

3

0

0x279DEC00

0x0C146364

0x53D5

В

2

5

0x2DA81DAF

0x026A7A46

0x53D5

А

1

8

0x2F96E5E7

0x003DD907

0x53D5

Нормализация

0xl6E5E700

0x3DD90700

0x53D55F

Как уже было отмечено, чаще всего при нормализации не происходит переноса. Исходя из этого, Дмитрий Субботин1 предложил отказаться от переноса вовсе. Оказалось, что потери в сжатии совсем незначительны, по­рядка нескольких байтов. Впрочем, выигрыш по скорости тоже оказался не очень заметен. Главное достоинство такого подхода - в простоте и ком­пактности кода. Вот как выглядит функция нормализации для 32-разрядной арифметики:

♦define CODEBITS 24

♦define TOP (l«CODEBITS)

♦define BOTTOM (TOP»8)

♦define BIGBYTE (0xFF«(CODEBITS-8))

void encode_normalize( void ) { while( range < BOTTOM ) {

if( low & BIGBYTE == BIGBYTE &&

range + (low & BOTTOM-1) >= BOTTOM ) range = BOTTOM - (low & BOTTOM-1); output_byte (low»24) ; range<<=8; low«=8; } )

Можно заметить, что избежать переноса нам позволяет своевременное принудительное уменьшение значения размера интервала. Оно происходит

тогда, когда второй по старшинству байт low принимает значение OxFF, а при добавлении к low значения размера интервала range возникает пере­нос. Так выглядит оптимизированная процедура нормализации:

void encode_normalize( void ) { while((low " low+range)<TOP || range < BOTTOM && ((range = -low & BOTTOM-1),1)) { output_byte (low»24) ; range«=8; low«=8; } }

void decode_normalize( void ) { while((low л low+range)<TOP || range<BOTTOM && ((range= -low & BOTTOM-1),1)) { low = low«8 | input_byte () ; range«=8; > }

Упражнение. Применить интервальное кодирование без переноса для строки "ков.корова".