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

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

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

0.3 0,4 0.5 0.6 0.7

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

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

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

На графике выше приводится сравнение оптимального кодирования и кодирования по методу Хаффмана. Хорошо видно, что в ситуации, когда относительные частоты не являются степенями двойки, сжатие становится менее эффективным (мы тратим больше битов, чем это необходимо). На­пример, если у нас два символа а и Ь с вероятностями 253/256 и 3/256, то в идеале мы должны потратить на цепочку из 256 байт -log₂(253/256)-253-bg₂(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. Графический процесс кодирования первых трех символов

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

I₀=0; h₀=l; 1=0;

while (not DataFile.EOFO ) {

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

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

h_L = 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; h₀=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 {{l_t <= value) && (value < hi) ) break; }; DataFile.WriteSymbol(c^) ;

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

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

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

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

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

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

J	Символ (q)	Накопленная частота	ЬИ
0	-	-	0
I	О	3	3
2	К	2	5
3	в	2	7
4	р	1	8
5	А	1	9
6	к и	1	10

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

i₀=0; h₀=65535; i=0; delitel- b[c_u,_t]; II delitel=10

First_qtr - (h₀+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]*{h_i.₁ - li-x + l)/delitel;
hi = li.! + b[j )*(h_i.₁ - 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 символа цепочки.

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

2₀=0; h₀=65535; delitel= b[c_last] ;
First_qtr = (h₀+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-2_i.₁+l)*delitel-l)/(h_i._I - 1_±._х + 1) ;

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

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

hi = Im + b[j ]*{h_i.₁ - 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+=2_i; hi+= hi+1;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы наиболее эффективно сжать данные, мы должны закодировать каждый символ s посредством -log₂(Ј) бит, где f, - частота символа s. Ко­нечно, на практике такая точность недостижима, но мы можем для каждого символа s отвести в интервале диапазон значений [N(F_s)^f(F,+fi)), где F_s -накопленная частота символов, предшествующих символу s в алфавите, N(f) - значение, соответствующее частоте / в интервале из N возможных значений. И чем больше будет N(f_s), тем точнее будет представлен символ 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

Как уже было отмечено, чаще всего при нормализации не происходит переноса. Исходя из этого, Дмитрий Субботин¹ предложил отказаться от переноса вовсе. Оказалось, что потери в сжатии совсем незначительны, по­рядка нескольких байтов. Впрочем, выигрыш по скорости тоже оказался не очень заметен. Главное достоинство такого подхода - в простоте и ком­пактности кода. Вот как выглядит функция нормализации для 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; > }

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