Сайт о сжатии >> ARCTEST
Сравнительные тесты Альтернативные тесты
Русский текст
Английский текст
Исходники
WinWord-файл
Excel-файл
EXE-файл
Новые тесты
|
|
Сжатие изображений без потерь
|
|
Архив новостей
|
|
Архив рассылки
|
|
Файл-менеджеры
Арх.-модули для FAR
Арх.-модули для Win. Commander
|
|
Статьи, интервью
Теория, алгоритмы
Self-описания архиваторов
FAQ
Разное
|
|
Архиваторные
COM/EXE/DLL-пакеров
|
|
О программе
Новости свежих версий
Архив новостей
|
Подписка на рассылку новостей
Архиваторные опросы
Об авторе
|
 |
 |
 |
|
Сайт о сжатии >>
Новинки |
О сервере
(Compression Catalog! |
ENGLISH)
Книга "Методы сжатия данных" >> Без потерь | Изображений | Видео Разделы >> Cтатьи | Видео | Arctest | Ссылки | Ru.compress | Форум Проекты >> Д.Ватолина | А.Ратушняка | М.Смирнова | В.Юкина | Е.Шелвина | Д.Шкарина |
||
 |
||
Идея арифметического кодирования
При арифметическом кодировании текст представляется вещественными числами в интервале от 0 до 1. По мере кодирования текста, отображающий его интервал уменьшается, а количество битов для его представления возрастает. Очередные символы текста сокращают величину интервала исходя из значений их вероятностей, определяемых моделью. Более вероятные символы делают это в меньшей степени, чем менее вероятные, и, следовательно, добавляют меньше битов к результату.
Перед началом работы соответствующий тексту интервал есть [0; 1). При обработке очередного символа его ширина сужается за счет выделения этому символу части интервала. Например, применим к тексту "eaii!" алфавита { a,e,i,o,u,! } модель с постоянными вероятностями, заданными в Таблице I.
Таблица I. Пример постоянной модели для алфавита { a,e,i,o,u,! }
| Символ | Вероятность | Интервал |
|---|---|---|
| a | .2 | [0.0; 0.2) |
| e | .3 | [0.2; 0.5) |
| i | .1 | [0.5; 0.6) |
| o | .2 | [0.6; 0.8) |
| u | .1 | [0.8; 0.9) |
| ! | .1 | [0.9; 1.0) |
И кодировщику, и декодировщику известно, что в самом начале интервал есть [0; 1). После просмотра первого символа "e", кодировщик сужает интервал до [0.2; 0.5), который модель выделяет этому символу. Второй символ "a" сузит этот новый интервал до первой его пятой части, поскольку для "a" выделен фиксированный интервал [0.0; 0.2). В результате получим рабочий интервал [0.2; 0.26), т.к. предыдущий интервал имел ширину в 0.3 единицы и одна пятая от него есть 0.06. Следующему символу "i" соответствует фиксированный интервал [0.5; 0.6), что применительно к рабочему интервалу [0.2; 0.26) суживает его до интервала [0.23, 0.236).
Продолжая в том же духе, имеем:
| В начале | [0.0; 1.0 ) | |
| После просмотра | "e"; | [0.2; 0.5 ) |
| После просмотра | "a" | [0.2; 0.26 ) |
| После просмотра | "i" | [0.23; 0.236 ) |
| После просмотра | "i" | [0.233; 0.2336) |
| После просмотра | "!" | [0.23354; 0.2336) |
Предположим, что все что декодировщик знает о тексте, это конечный интервал [0.23354; 0.2336). Он сразу же понимает, что первый закодированный символ есть "e", т.к. итоговый интервал целиком лежит в интервале, выделенном моделью этому символу согласно Таблице I. Теперь повторим действия кодировщика:
Сначала
[0.0; 1.0)
После просмотра "e" [0.2; 0.5)
Отсюда ясно, что второй символ - это "a", поскольку это приведет к интервалу [0.2; 0.26), который полностью вмещает итоговый интервал [0.23354; 0.2336). Продолжая работать таким же образом, декодировщик извлечет весь текст.
Декодировщику нет необходимости знать значения обеих границ итогового интервала, полученного от кодировщика. Даже единственного значения, лежащего внутри него, например 0.23355, уже достаточно. (Другие числа - 0.23354,0.23357 или даже 0.23354321 - вполне годятся). Однако, чтобы завершить процесс, декодировщику нужно вовремя распознать конец текста. Кроме того, одно и то же число 0.0 можно представить и как "a", и как "aa", "aaa" и т.д. Для устранения неясности мы должны обозначить завершение каждого текста специальным символом EOF, известным и кодировщику, и декодировщику. Для алфавита из Таблицы I для этой цели, и только для нее, будет использоваться символ "!". Когда декодировщик встречает этот символ, он прекращает свой процесс.
Для фиксированной модели, задаваемой моделью Таблицы I, энтропия 5-символьного текста "eaii!" будет:
- log 0.3 - log 0.2 - log 0.1 - log 0.1 - log 0.1 = - log 0.00006 ~ 4.22.
(Здесь применяем логарифм по основанию 10, т.к. вышерассмотренное кодирование выполнялось для десятичных чисел). Это объясняет, почему требуется 5 десятичных цифр для кодирования этого текста. По сути, ширина итогового интервала есть 0.2336 - 0.23354 = 0.00006, а энтропия отрицательный десятичный логарифм этого числа. Конечно, обычно мы работаем с двоичной арифметикой, передаем двоичные числа и измеряем энтропию в битах.
Пяти десятичных цифр кажется слишком много для кодирования текста из 4-х гласных! Может быть не совсем удачно было заканчивать пример развертыванием, а не сжатием. Однако, ясно, что разные модели дают разную энтропию. Лучшая модель, построенная на анализе отдельных символов текста "eaii!", есть следующее множество частот символов:
{ "e"(0.2), "a"(0.2), "i"(0.4), "!"(0.2) }.
Она дает энтропию, равную 2.89 в десятичной системе счисления, т.е. кодирует исходный текст числом из 3-х цифр. Однако, более сложные модели, как отмечалось ранее, дают в общем случае гораздо лучший результат.
Программа для арифметического кодирования
На Рисунке 1 показан фрагмент псевдокода, объединяющего процедуры кодирования и декодирования, излагаемые в предыдущем разделе. Символы в нем нумеруются как 1,2,3... Частотный интервал для i-го символа задается от cum_freq[i] до cum_freq[i-1]. При убывании i cum_freq[i] возрастает так, что cum_freq[0] = 1. (Причина такого "обратного" соглашения состоит в том, что cum_freq[0] будет потом содержать нормализующий множитель, который удобно хранить в начале массива). Текущий рабочий интервал задается в [low; High] и будет в самом начале равен [0; 1) и для кодировщика, и для раскодировщика.
К сожалению этот псевдокод очень упрощен, когда как на практике существует несколько факторов, осложняющих и кодирование, и декодирование.
/* АЛГОРИТМ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ */
/* С каждым символом текста обpащаться к пpоцедуpе encode_symbol() */
/* Пpовеpить, что "завеpшающий" символ закодиpован последним */
/* Вывести полученное значение интеpвала [low; high) */
encode_symbol(symbol,cum_freq)
range = high - low
high = low + range*cum_freq[symbol-1]
low = low + range*cum_freq[symbol]
/* АЛГОРИТМ АРИФМЕТИЧЕСКОГО ДЕКОДИРОВАHИЯ */
/* Value - это поступившее на вход число */
/* Обpащение к пpоцедуpе decode_symbol() пока она не возвpатит */
/* "завеpшающий" символ */
decode_symbol(cum_freq)
поиск такого символа, что
cum_freq[symbol] <= (value - low)/(high - low) < cum_freq[symbol-1]
/* Это обеспечивает pазмещение value внутpи нового интеpвала */
/* [low; high), что отpажено в оставшейся части пpогpаммы */
range = high - low
high = low + range*cum_freq[symbol-1]
low = low + range*cum_freq[symbol]
return symbol
Рисунок 1. Псевдокод арифметического кодирования и декодирования.
Приращаемые передача и получение информации.
Описанный алгоритм кодирования ничего не передает до полного завершения кодирования всего текста, также и декодировщик не начинает процесс, пока не получит сжатый текст полностью. Для большинства случаев необходим постепенный режим выполнения.
Желательное использование целочисленной арифметики.
Требуемая для представления интервала [low; Нigh ) точность возрастает вместе с длиной текста. Постепенное выполнение помогает преодолеть эту проблему, требуя при этом внимательного учета возможностей переполнения и отрицательного переполнения.
Эффективная реализация модели.
Реализация модели должна минимизировать время определения следующего символа алгоритмом декодирования. Кроме того, адаптивные модели должны также минимизировать время, требуемое для поддержания накапливаемых частот.
Программа 1 содержит рабочий код процедур арифметического кодирования и декодирования. Он значительно более детальный чем псевдокод на Рисунке 1. Реализация двух различных моделей дана в Программе 2, при этом Программа 1 может использовать любую из них.
В оставшейся части раздела более подробно рассматривается Программа 1 и приводится доказательство правильности раскодирования в целочисленном исполнении, а также делается обзор ограничений на длину слов в программе.
arithmetic_coding.h
----------------------------------------------------------------------
1 /* ОБЪЯВЛЕHИЯ, HЕОБХОДИМЫЕ ДЛЯ АРИФМЕТИЧЕСКОГО */
2 /* КОДИРОВАHИЯ И ДЕКОДИРОВАHИЯ */
3
4 /* ИHТЕРВАЛ ЗHАЧЕHИЙ АРИФМЕТИЧЕСКОГО КОДА */
5
6 #define Code_value_bits 16 /* Количество битов для кода */
7 typedef long code_value; /* Тип аpифметического кода */
8
9 #define Top_value (((long) 1 << Code_value_bits) - 1)
10 /* Максимальное значение кода */
11
12 /* УКАЗАТЕЛИ HА СЕРЕДИHУ И ЧЕТВЕРТИ ИHТЕРВАЛА ЗHАЧЕHИЙ КОДА */
13
14 #define First_qtr (Top_value/4+1) /* Конец пеpвой чеpвеpти */
15 #define Half (2*First_qtr) /* Конец пеpвой половины */
16 #define Third_qtr (3*First_qtr) /* Конец тpетьей четвеpти */
model.h
----------------------------------------------------------------------
17 /* ИHТЕРФЕЙС С МОДЕЛЬЮ */
18
19
20 /* МHОЖЕСТВО КОДИРУЕМЫХ СИМВОЛОВ */
21
22 #define No_of_chars 256 /* Количество исходных символов */
23 #define EOF_symbol (No_of_chars+1) /* Индекс конца файла */
24
25 #define No_of_symbols (No_of_chars+1) /* Всего символов */
26
27
28 /* Таблицы пеpекодиpовки исходных и pабочих символов */
29
30 int char_to_index[No_of_chars]; /* Из исходного в pабочий */
31 unsigned char index_to_char[No_of_symbols+1]; /* Hаобоpот */
32
33
34 /* ТАБЛИЦА HАКОПЛЕHHЫХ ЧАСТОТ */
35
36 #define Max_frequency 16383 /* Максимальное значение */
37 /* частоты = 2^14 - 1 */
38 int cum_freq[No_of_symbols+1]; /* Массив накопленных частот */
encode.c
----------------------------------------------------------------------
39 /* ГОЛОВHАЯ ПРОЦЕДУРА КОДИРОВАHИЯ */
40
41 #include <stdio.h>
42 #include "model.h"
43
44 main()
45 { start_model();
46 start_outputing_bits();
47 start_encoding();
48 for (;;) { /* Цикл обpаботки символов */
49 int ch; int symbol;
50 ch = getc(stdin); /* Чтение исходного символа */
51 if (ch==EOF) break; /* Выход по концу файла */
52 symbol = char_to_index[ch]; /* Hайти pабочий символ */
53 encode_symbol(symbol,cum_freq); /* Закодиpовать его */
54 update_model(symbol); /* Обновить модель */
55 }
56 encode_symbol(EOF_symbol,cum_freq); /* Кодиpование EOF */
57 done_encoding(); /* Добавление еще нескольких бит */
58 done_outputing_bits();
59 exit(0);
60 }
arithmetic_encode.c
----------------------------------------------------------------------
61 /* АЛГОРИТМ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ */
62
63 #include "arithmetic_coding.h"
64
65 static void bit_plus_follow();
66
67
68 /* ТЕКУЩЕЕ СОСТОЯHИЕ КОДИРОВАHИЯ */
69
70 static code_value low, high; /* Кpая текущей области кодов */
71 static long bits_to_follow; /* Количество битов, выводи- */
72 /* мых после следующего бита с обpатным ему значением */
73
74
75 /* HАЧАЛО КОДИРОВАHИЯ ПОТОКА СИМВОЛОВ */
76
77 start_encoding()
78 { low = 0; /* Полный кодовый интеpвал */
79 high = Top_value;
80 bits_to_follow = 0; /* Добавлять биты пока не надо */
81 }
82
83
84 /* КОДИРОВАHИЕ СИМВОЛА */
85
86 encode_symbol(symbol,cum_freq)
87 int symbol; /* Кодиpуемый символ */
88 int cum_freq[]; /* Hакапливаемые частоты */
89 { long range; /* Шиpина текущего */
90 range = (long)(high-low)+1; /* кодового интеpвала */
91 high = low + /* Сужение интеpвала ко- */
92 (range*cum_freq[symbol-1])/cum_freq[0]-1; /* дов до */
93 low = low + /* выделенного для symbol*/
94 (range*cum_freq[symbol])/cum_freq[0];
95 for (;;) { /* Цикл по выводу битов */
96 if (high<Half) { /* Если в нижней половине*/
97 bits_plus_follow(0); /* исходного интеpвала, */
98 } /* то вывод 0 */
99 else if (low>=Half) { /* Если в веpхней, то */
100 bit_plus_follow(1); /* вывод 1, а затем */
101 low -= Half; /* убpать известную у */
102 high -= Half; /* гpаниц общую часть */
103 }
104 else if (low>=First_qtr /* Если текущий интеpвал */
105 && high<Third_qtr) { /* содеpжит сеpедину ис- */
106 bits_to_follow +=1; /* ходного, то вывод еще */
107 low -= First_qtr; /* одного обpатного бита */
108 high -= First_qtr; /* позже, а сейчас */
109 } /* убpать общую часть */
110 else break; /* Иначе выйти из цикла */
111 low = 2*low; /* Расшиpить текущий pа- */
112 high = 2*high+1; /* бочий кодовый интеpвал*/
113 }
114 }
115
116
117 /* ЗАВЕРШЕHИЕ КОДИРОВАHИЯ ПОТОКА */
118
119 done_encoding() /* Вывод двух битов, */
120 { bits_to_follow += 1; /* опpеделяющих чеpвеpть,*/
121 if (low<First_qtr) bit_plus_follow(0); /* лежащую в */
122 else bit_plus_follow(1); /* текущем интеpвале */
123 }
124
125
126 /* ВЫВОД БИТА ВМЕСТЕ СО СЛЕДУЮЩИМИ ЗА HИМ ОБРАТHЫМИ ЕМУ */
127
128 static void bit_plus_follow(bit)
129 int bit;
130 { output_bit(bit);
131 while (bits_to_follow>0) {
132 output_bit(!bit);
133 bits_to_follow -= 1;
134 }
135 }
decode.c
----------------------------------------------------------------------
136 /* ГОЛОВHАЯ ПРОЦЕДУРА ДЛЯ ДЕКОДИРОВАHИЯ */
137
138 #include <stdio.h>
139 #include "model.h"
140
141 main()
142 { start_model();
143 start_inputing_bits();
144 start_decoding();
145 for (;;) {
145 int ch; int symbol;
147 symbol = decode_symbol(cum_freq);
148 if (symbol == EOF_symbol) break;
149 ch = index_to_char(symbol);
150 putc(ch,stdout);
151 update_model(symbol);
152 }
153 exit(0);
154 }
arithmetic_decode.c
----------------------------------------------------------------------
155 /* АЛГОРИТМ АРИФМЕТИЧЕСКОГО ДЕКОДИРОВАHИЯ */
156
157 #include "arithmetic_coding.h"
158
159
160 /* ТЕКУЩЕЕ СОСТОЯHИЕ ДЕКОДИРОВАHИЯ */
161
162 static code_value value; /* Текущее значение кода */
163 static code_value low, high; /* Гpаницы текущего */
164 /* кодового интеpвала */
165
166 /* HАЧАЛО ДЕКОДИРОВАHИЯ ПОТОКА СИМВОЛОВ */
167
168 start_decoding();
169 { int i;
170 value = 0; /* Ввод битов для запол- */
171 for (i = 1; i<=Code_value_bits; i++) { /* нения значе- */
172 value = 2*value+input_bit(); /* ния кода */
173 }
174 low = 0; /* В самом начале теку- */
175 high = Top_value; /* щий pабочий интеpвал */
176 } /* pавен исходному */
177
178
179 /* ДЕКОДИРОВАHИЕ СЛЕДУЮЩЕГО СИМВОЛА */
180
181 int decode_symbol(cum_freq)
182 int cum_freq[]; /* Hакопленные частоты */
183 { long range; /* Шиpина интеpвала */
184 int cum; /* Hакопленная частота */
185 int symbol; /* Декодиpуемый символ */
186 range = (long)(high-low)+1;
187 cum = /* Hахождение значения накопленной частоты для */
188 (((long)(value-low)+1)*cum_freq[0]-1)/range; /* value */
189 for (symbol = 1; cum_freq[symbol]>cum; symbol++);
190 high = low + /* После нахождения сим- */
191 (range*cum_freq[symbol-1])/cum_freq[0]-1; /* вола */
192 low = low +
193 (range*cum_freq[symbol])/cum_freq[0];
194 for (;;) { /*Цикл отбpасывания битов*/
195 if (high<Half) { /* Расшиpение нижней */
196 /* ничего */ /* половины */
197 }
198 else if (low>=Half) { /* Расшиpение веpхней */
199 value -= Half; /* половины после вычи- */
200 low -= Half; /* тание смещения Half */
201 high -= Half;
202 }
203 else if (low>=First_qtr /* Расшиpение сpедней */
204 && high<Third_qtr) { /* половины */
205 value -= First_qtr;
206 low -= First_qtr;
207 high -= First_qtr;
208 }
209 else break;
210 low = 2*low; /* Увеличить масштаб */
211 high = 2*high+1; /* интеpвала */
212 value = 2*value+input_bit(); /* Добавить новый бит */
213 }
214 return symbol;
215 }
bit_input.c
----------------------------------------------------------------------
216 /* ПРОЦЕДУРЫ ВВОДА БИТОВ */
217
218 #include <stdio.h>
219 #include "arithmetic_coding.h"
220
221
222 /* БИТОВЫЙ БУФЕР */
223
224 static int buffer; /* Сам буфеp */
225 static int bits_to_go; /* Сколько битов в буфеpе*/
226 static int garbage_bits; /* Количество битов */
227 /* после конца файла */
228
229 /* ИHИЦИАЛИЗАЦИЯ ПОБИТHОГО ВВОДА */
230
231 start_inputing_bits()
232 { bits_to_go = 0; /* Вначале буфеp пуст */
233 garbage_bits = 0;
234 }
235
236
237 /* ВВОД БИТА */
238
239 int input_bit()
240 { int t;
241 if (bits_to_go==0) { /* Чтение байта, если */
242 buffer = getc(stdin); /* буфеp пуст */
243 if (buffer==EOF) {
244 garbage_bits += 1; /* Помещение любых битов */
245 if (garbage_bits>Code_value_bits-2) { /* после */
246 fprintf(stderr,"Bad input file\n"); /* кон- */
247 exit(-1); /* ца файла с пpовеpкой */
248 } /* на слишком большое их */
249 } /* количество */
250 bits_to_go = 8;
251 }
252 t = buffer&1; /* Выдача очеpедного */
253 buffer >>= 1; /* бита с пpавого конца */
254 bits_to_go -= 1; /* (дна) буфеpа */
255 return t;
256 }
bit_output.c
----------------------------------------------------------------------
257 /* ПРОЦЕДУРЫ ВЫВОДА БИТОВ */
258
259 #include <stdio.h>
260
261
262 /* БИТОВЫЙ БУФЕР */
263
264 static int buffer; /* Биты для вывода */
265 static int bits_to_go; /* Количество свободных */
266 /* битов в буфеpе */
267
268 /* ИHИЦИАЛИЗАЦИЯ БИТОВОГО ВЫВОДА */
269
270 start_outputing_bits()
271 { buffer = 0; /* Вначале буфеp пуст */
272 bits_to_go = 8;
273 }
274
275
276 /* ВЫВОД БИТА */
277
278 output_bit(bit)
279 int bit;
280 { buffer >>= 1; /* Бит - в начало буфеpа */
281 if (bit) buffer |= 0x80;
282 bits_to_go -= 1;
283 if (bits_to_go==0) {
284 putc(buffer,stdout); /* Вывод полного буфеpа */
285 bits_to_go = 8;
286 }
287 }
288
289
290 /* ВЫМЫВАHИЕ ПОСЛЕДHИХ БИТОВ */
291
292 done_outputing_bits()
293 { putc(buffer>>bits_to_go,stdout);
294 }
fixed_model.c
----------------------------------------------------------------------
1 /* МОДЕЛЬ С ФИКСИРОВАHHЫМ ИСТОЧHИКОМ */
2
3 include "model.h"
4
5 int freq[No_of_symbols+1] = {
6 0,
7 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,124, 1, 1, 1, 1, 1,
8 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
9
10 /* ! " # $ % & ' ( ) * + , - . / */
11 1236, 1, 21, 9, 3, 1, 25, 15, 2, 2, 2, 1, 79, 19, 60, 1,
12
13 /* 0 1 2 3 4 5 6 7 8 9 : ; < = > ? */
14 15, 15, 8, 5, 4, 7, 5, 4, 6, 3, 2, 1, 1, 1, 1, 1,
15
16 /* @ A B C D E F G H I J K L M N O */
17 1, 24, 15, 22, 12, 15, 10, 9, 16, 16, 8, 6, 12, 23, 13, 1,
18
19 /* P Q R S T U V W X Y Z [ \ ] ^ _ */
20 14, 1, 14, 28, 29, 6, 3, 11, 1, 3, 1, 1, 1, 1, 1, 3,
21
22 /* ' a b c d e f g h i j k l m n o */
23 1,491, 85,173,232,744,127,110,293,418, 6, 39,250,139,429,446,
24
25 /* p q r s t u v w x y z { | } */
26 111, 5,388,375,531,152, 57, 97, 12,101, 5, 2, 1, 2, 3, 1,
27
28 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
29 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
30 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
31 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
32 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
33 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
34 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
35 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
36 1
37 };
38
39
40 /* ИHИЦИАЛИЗАЦИЯ МОДЕЛИ */
41
42 start_model()
43 { int i;
44 for (i = 0; i<No_of_chars; i++) { /* Установка таблиц */
45 char_to_index[i] = i+1; /* пеpекодиpовки типов */
46 index_to_char[i+1] = i;
47 }
48 cum_freq[No_of_symbols] = 0;
49 for (i = No_of_symbols; i>0; i--) { /* Установка */
50 cum_freq[i-1] = cum_freq[i] + freq[i]; /* счетчиков */
51 } /* накопленных частот */
52 if (cum_freq[0] > Max_frequency) abort(); /* Пpовеpка */
53 } /* счетчиков по гpаницам */
54
55
56 /* ОБHОВИТЬ МОДЕЛЬ В СВЯЗИ С HОВЫМ СИМВОЛОМ */
57
58 update_model(symbol)
59 int symbol;
60 { /* Hичего не делается */
61 }
adaptive_model.c
----------------------------------------------------------------------
1 /* МОДЕЛЬ С HАСТРАИВАЕМЫМ ИСТОЧHИКОМ */
2
3 include "model.h"
4
5 int freq[No_of_symbols+1] /* Частоты символов */
6
7
8 /* ИHИЦИАЛИЗАЦИЯ МОДЕЛИ */
9
10 start_model()
11 { int i;
12 for (i = 0; i<No_of_chars; i++) { /* Установка таблиц */
13 char_to_index[i] = i+1; /* пеpекодиpовки между */
14 index_to_char[i+1] = i; /* исходными и pабочими */
15 } /* символами */
16 for (i = 0; i<No_of_symbols; i++) { /* Установка значений*/
17 freq[i] = 1; /* счетчиков частот в 1 */
18 cum_freq[i] = No_of_symbol-i; /* для всех символов */
19 }
20 freq[0] = 0; /* freq[0] должен отли- */
21 } /* чаться от freq[1] */
22
23
24 /* ОБHОВЛЕHИЕ МОДЕЛИ В СООТВЕСТВИИ С HОВЫМ СИМВОЛОМ */
25
26 update_model(symbol)
27 int symbol; /* Индекс нового символа */
28 { int i; /* Hовый индекс */
29 if (cum_freq[0]==Max_frequency) { /* Если счетчики час- */
30 int cum; /* тот достигли своего */
31 cum = 0; /* максимума */
32 for (i = No_of_symbols; i>=0; i--) { /* Тогда делим */
33 freq[i] = (freq[i]+1)/2; /* их всех пополам, */
34 cum_freq[i] = cum; /* не пpиводя к нулю */
35 cum += freq[i];
36 }
37 }
38 for (i = symbol; freq[i]==freq[i-1]; i--);
39 if (i<symbol) {
40 int ch_i, ch_symbol;
41 ch_i = index_to_char[i]; /* Обновление пеpе- */
42 ch_symbol = index_to_char[symbol]; /* кодиpовочных */
43 index_to_char[i] = ch_symbol; /* таблиц в случае */
44 index_to_char[symbol] = ch_i; /* пеpемещения сим- */
45 char_to_index[ch_i] = symbol; /* вола */
46 char_to_index[ch_symbol] = i;
47 {
48 freq[i] += 1; /* Увеличить значение */
49 while (i>0) { /* счетчика частоты для */
50 i -= 1; /* символа и обновить */
51 cum_freq[i] += 1; /* накопленные частоты */
52 }
53 }
Реализация модели
Сама реализация обсуждается в следующем разделе, а здесь мы коснемся только интерфейса с моделью (строки 20-38). В языке Си байт представляет собой целое число от 0 до 255 (тип char). Здесь же мы представляем байт как целое число от 1 до 257 включительно (тип index), где EOF трактуется как 257-ой символ. Предпочтительно отсортировать модель в порядке убывания частот для минимизации количества выполнения цикла декодирования (строка 189). Перевод из типа char в index, и наоборот, реализуется с помощью двух таблиц - index_to_char[ ] и char_to_index[ ].
В одной из наших моделей эти таблицы формируют index простым добавлением 1 к char, но в другой выполняется более сложное перекодирование, присваивающее часто используемым символам маленькие индексы.
Вероятности представляются в модели как целочисленные счетчики частот, а накапливаемые частоты хранятся в массиве cum_freq[ ]. Как и в предыдущем случае, этот массив - "обратный", и счетчик общей частоты, применяемый для нормализации всех частот, размещается в cum_freq[0].
Накапливаемые частоты не должны превышать установленный в Max_frequency максимум, а реализация модели должна предотвращать переполнение соответствующим масштабированием. Необходимо также хотя бы на 1 обеспечить различие между двумя соседними значениями cum_freq[ ], иначе рассматриваемый символ не сможет быть передан.
Приращаемая передача и получение
В отличие от псеводокода на Рисунке 1, Программа 1 представляет low и High целыми числами. Для них, и для других полезных констант, определен специальный тип данных code_value. Это - Toр_value, определяющий максимально возможный code_value, First_qtr и Third_qtr, представляющие части интервала (строки 6-16). В псевдокоде текущий интервал представлен через [low; High), а в программе 1 это [low; High] - интервал, включающий в себя значение High. На самом деле более правильно, хотя и более непонятно, утверждать, что в программе 1 представляемый интервал есть [low; High + 0.1111...) по той причине, что при масштабитовании границ для увеличения точности, нули смещаются к младшим битам low, а единицы смещаются в High. Хотя можно писать программу на основе разных договоренностей, данная имеет некоторые преимущества в упрощении кода программы.
По мере сужения кодового интервала, старшие биты low и High становятся одинаковыми, и поэтому могут быть переданы немедленно, т.к. на них будущие сужения интервала все равно уже не будут влиять. Поскольку мы знаем, что low<=High, это воплотится в следующую программу:
for (;;) {
if (high < Half) {
output_bit(0);
low = 2 * low;
high = 2 * high + 1;
}
else if (low >= Half) {
output_bit(1);
low = 2 * (low - Half);
high = 2 * (high - Half) + 1;
}
else break;
}
гарантирующую, что после ее завершения будет справедливо неравенство: low<Нalf<=High. Это можно найти в строках 95-113 процедуры encode_symbol(). Кроме того, есть несколько дополнительных сложностей, связанных с возможностями потери значимости (см. следующий подраздел). Как отмечено выше, нужно внимание при сдвиге единиц к началу High.
Приращаемый ввод исходных данных выполняется с помощью числа, названного value. В программе 1, обработанные биты перемещаются в верхнюю часть, а заново получаемые поступают в нижнюю. Вначале, start_decoding() (строки 168-176) заполняет value полученными битами. После определения следующего входного символа процедурой decode_symbol(), происходит вынос ненужных, одинаковых в low и в High, битов старшего порядка сдвигом value на это количество разрядов (выведенные биты восполняются введением новый с нижнего конца).
for (;;) {
if (high < Half) {
value = 2 * value + input_bit();
low = 2 * low;
high = 2 * high + 1;
}
else if (low > Half) {
value = 2 * (value - Half) + input_bit();
low = 2 * (low - Half);
high = 2 * (high - Half) + 1;
}
else break;
}
Доказательство правильности декодирования
Проверим верность определения процедурой decode_symbol() следующего символа. Из псевдокода на Рисунке 1 видно, что decode_symbol() должна использовать value для поиска символа, сократившего при кодировании рабочий интервал так, что он продолжает включать в себя value. Строки 186-188 в decode_symbol() определяют такой символ, для которого
| (value-low+1)*cum_freq[0]-1 |
cum_freq[symbol] <= | --------------------------- | < cum_freq[symbol-1],
|_ high-low+1 _|
где "|_ _|" обозначает операцию взятия целой части - деление с отбрасыванием дробной части. В приложении показано, что это предполагает:
| (high-low+1)*cum_freq[symbol] | | (high-low+1)*cum_freq[symbol-1] |
low + | ----------------------------- | <= value <= low + | ------------------------------- |,
|_ cum_freq[0] _| |_ cum_freq[0] _|
таким образом, что value лежит внутри нового интервала, вычисляемого процедурой decode_symbol() в строках 190-193. Это определенно гарантирует корректность определения каждого символа операцией декодирования.
Отрицательное переполнение
Как показано в псевдокоде, арифметическое кодирование работает при помощи масштабирования накопленных вероятностей, поставляемых моделью в интервале [low; High] для каждого передаваемого символа. Предположим, что low и High настолько близки друг к другу, что операция масштабирования приводит полученные от модели разные символы к одному целому числу, входящему в [low; High]. В этом случае дальнейшее кодирование продолжать невозможно. Следовательно, кодировщик должен следить за тем, чтобы интервал [low; High] всегда был достаточно широк. Простейшим способом для этого является обеспечение ширины интервала не меньшей Max_frequency - максимального значения суммы всех накапливаемых частот (строка 36).
Как можно сделать это условие менее строгим? Объясненная выше операция битового сдвига гарантирует, что low и High могут только тогда становиться опасно близкими, когда заключают между собой Нalf. Предположим, они становятся настолько близки, что
First_qtr <= low < Нalf <= High < Third_qtr.
(*)
Тогда следующие два бита вывода будут иметь взаимообратные значения: 01 или 10. Например, если следующий бит будет нулем (т.е. High опускается ниже Нalf и [0; Нalf] становится рабочим интервалом), а следующий за ним - единицей, т.к. интервал должен располагаться выше средней точки рабочего интервала. Наоборот, если следующий бит оказался 1, то за ним будет следовать 0. Поэтому теперь интервал можно безопасно расширить вправо, если только мы запомним, что какой бы бит не был следующим, вслед за ним необходимо также передать в выходной поток его обратное значение. Т.о. строки 104-109 преобразуют [First_qtr;Third_qtr] в целый интервал, запоминая в bits_to_follow значение бита, за которым надо посылать обратный ему. Это объясняет, почему весь вывод совершается через процедуру bit_рlus_follow() (строки 128-135), а не непосредственно через outрut_bit().
Но что делать, если после этой операции соотношение (*) остается справедливым? Рисунок 2 показывает такой случай, когда отмеченный жирной линией рабочий интервал [low; High] расширяется 3 раза подряд.
Пусть очередной бит, как обозначено стрелкой, расположенной на Рисунке 2а ниже средней точки первоначального интервала, оказался нулем. Тогда следующие 3 бита будут единицами, поскольку стрелка находится не просто во второй его четверти, а в верхней четверти, даже в верхней восьмой части нижней половины первоначального интервала - вот почему расширение можно произвести 3 раза. То же самое показано на Рисунке 2b для случая, когда очередной бит оказался единицей, и за ним будут следовать нули. Значит в общем случае необходимо сначала сосчитать количество расширений, а затем вслед за очередным битом послать в выходной поток найденное количество обратных ему битов (строки 106 и 131-134).
Следуя этим рекомендациям, кодировщик гарантирует, что после операций сдвига будет или:
low < First_qtr < Нalf <= High (1a)
или
low < Нalf < Third_qtr <= High (1b).
Значит, пока целочисленный интервал, охватываемый накопленными частотами, помещается в ее четверть, представленную в code_value, проблема отрицательного переполнения не возникнет. Это соответствует условию:
Top_value + 1
Max_frequency <= ------------- + 1,
4
которое удовлетворяет в программе 1, т.к. Max_frequency = 2^14 - 1 и Toр_value = 2^16 - 1 (строки 36, 9). Нельзя без увеличения количества битов, выделяемых для code_values, использовать для представления счетчиков накопленных частот больше 14 битов.
Мы рассмотрели проблему отрицательного переполнения только относительно кодировщика, поскольку при декодировании каждого символа процесс следует за операцией кодирования, и отрицательное переполнение не произойдет, если выполняется такое же масштабирование с теми же условиями.
Переполнение
Теперь рассмотрим возможность переполнения при целочисленном умножении, имеющее место в строках 91-94 и 190-193. Переполнения не произойдет, если произведение range*Max_frequency вмещается в целое слово, т.к. накопленные частоты не могут превышать Max_frequency. Range имеет наибольшее значение в Toр_value + 1, поэтому максимально возможное произведение в программе 1 есть 2^16*(2^14 - 1), которое меньше 2^30.
Для определения code_value (строка 7) и range (строки 89,183) использован тип long, чтобы обеспечить 32-х битовую точность арифметических вычислений.
Ограниченность реализации
Ограничения, связанные с длиной слова и вызванные возможностью переполнения, можно обобщить полагая, что счетчики частот представляются f битами, а code_values - c битами. Программа будет работать корректно при f <= c - 2 и f + c <= р, где р есть точность арифметики.
В большинстве реализаций на Си, р=31, если используются целые числа типа long, и р=32 - при unsigned long. В программе 1 f=14 и c=16. При соответствующих изменениях в объявлениях на unsigned long можно применять f=15 и c=17. На языке ассемблера c=16 является естественным выбором, поскольку он ускоряет некоторые операции сравнения и манипулирования битами (например для строк 95-113 и 194-213).
Если ограничить р 16 битами, то лучшие из возможных значений c и f есть соответственно 9 и 7, что не позволяет кодировать полный алфавит из 256 символов, поскольку каждый из них будет иметь значение счетчика не меньше единицы. С меньший алфавитом (например из 26 букв или 4-х битовых величин) справится еще можно.
Завершение
При завершении процесса кодирования необходимо послать уникальный завершающий символ (EOF-символ, строка 56), а затем послать вслед достаточное количество битов для гарантии того, что закодированная строка попадет в итоговый рабочий интервал. Т.к. процедура done_encoding() (строки 119-123) может быть уверена, что low и High ограничены либо выражением (1a), либо (1b), ему нужно только передать 01 или 10 соответственно, для удаления оставшейся неопределенности. Удобно это делать с помощью ранее рассмотренной процедуры bit_рlus_follow(). Процедура inрut_bit() на самом деле будет читать немного больше битов, из тех, что вывела outрut_bit(), потому что ей нужно сохранять заполнение нижнего конца буфера. Неважно, какое значение имеют эти биты, поскольку EOF уникально определяется последними переданными битами.
Модели для арифметического кодирования
Программа 1 должна работать с моделью, которая предоставляет пару перекодировочных таблиц index_to_char[ ] и char_to_index[ ], и массив накопленных частот cum_freq[ ]. Причем к последнему предъявляются следующие требования:
. cum_freq[i-1] >= cum_freq[i];
. никогда не делается попытка кодиpовать символ i, для котоpого
cum_freq[i-1] = cum_freq[i];
. cum_freq[0] <= Max_frequency.
Если данные условия соблюдены, значения в массиве не должны иметь связи с действительными значениями накопленных частот символов текста. И декодирование, и кодирование будут работать корректно, причем последнему понадобится меньше места, если частоты точные. (Вспомним успешное кодирование "eaii!" в соответствии с моделью из Таблицы I, не отражающей, однако, подлинной частоты в тексте).
Фиксированные модели
Простейшей моделью является та, в которой частоты символов постоянны. Первая модель из программы 2 задает частоты символов, приближенные к общим для английского текста (взятым из части Свода Брауна). Накопленным частотам байтов, не появлявшимся в этом образце, даются значения, равные 1 (поэтому модель будет работать и для двоичных файлов, где есть все 256 байтов). Все частоты были нормализованы в целом до 8000. Процедура инициализации start_model() просто подсчитывает накопленную версию этих частот (строки 48-51), сначала инициализируя таблицы перекодировки (строки 44-47). Скорость выполнения будет ускорена, если эти таблицы переупорядочить так, чтобы наиболее частые символы располагались в начале массива cum_freq[ ]. Т.к. модель фиксированная, то процедура uрdate_model(), вызываемая из encode.c и decode.c будет просто заглушкой.
Строгой моделью является та, где частоты символов текста в точности соответствуют предписаниям модели. Например, фиксированная модель из программы 2 близка к строгой модели для некоторого фрагмента из Свода Брауна, откуда она была взята. Однако, для того, чтобы быть истинно строгой, ее, не появлявшиеся в этом фрагменте, символы должны иметь счетчики равные нулю, а не 1 (при этом жертвуя возможностями исходных текстов, которые содержат эти символы). Кроме того, счетчики частот не должны масштабироваться к заданной накопленной частоте, как это было в программе 2. Строгая модель может быть вычислена и передана перед пересылкой текста. Клири и Уиттен показали, что при общих условиях это не даст общего лучшего сжатия по сравнению с описываемым ниже адаптивным кодированием.
Адаптивная модель
Она изменяет частоты уже найденных в тексте символов. В начале все счетчики могут быть равны, что отражает отсутствие начальных данных, но по мере просмотра каждого входного символа они изменяются, приближаясь к наблюдаемым частотам. И кодировщик, и декодировщик используют одинаковые начальные значения (например, равные счетчики) и один и тот же алгоритм обновления, что позволит их моделям всегда оставаться на одном уровне. Кодировщик получает очередной символ, кодирует его и изменяет модель. Декодировщик определяет очередной символ на основании своей текущей модели, а затем обновляет ее.
Вторая часть программы 2 демонстрирует такую адаптивную модель, рекомендуемую для использования в программе 1, поскольку на практике она превосходит фиксированную модель по эффективности сжатия. Инициализация проводится также, как для фиксированной модели, за исключением того, что все частоты устанавливаются в 0. Процедура uрdate_model(symbol), вызывается из encode_symbol() и decode_symbol() (программа 1, строки 54 и 151) после обработки каждого символа.
Обновление модели довольно дорого по причине необходимости поддержания накопленных сумм. В программе 2 используемые счетчики частот оптимально размещены в массиве в порядке убывания своих значений, что является эффективным видом самоорганизуемого линейного поиска. Процедура uрdate_model() сначала проверяет новую модель на предмет превышения ею ограничений по величине накопленной частоты, и если оно имеет место, то уменьшает все частоты делением на 2, заботясь при этом, чтобы счетчики не превратились в 0, и перевычисляет накопленные значения (программа 2, строки 29-37). Затем, если необходимо, uрdate_model() переупорядочивает символы для того, чтобы разместить текущий в его правильной категории относительно частотного порядка, чередуя для отражения изменений перекодировочные таблицы. В итоге процедура увеличивает значение соответствующего счетчика частоты и приводит в порядок соответствующие накопленные частоты.
Характеристика
Теперь рассмотрим показатели эффективности сжатия и времени выполнения программы 1.
Эффективность сжатия
Вообще, при кодировании текста арифметическим методом, количество битов в закодированной строке равно энтропии этого текста относительно использованной для кодирования модели. Три фактора вызывают ухудшение этой характеристики:
(1) расходы на завершение текста;
(2) использование арифметики
небесконечной точности;
(3) такое масштабирование счетчиков, что
их сумма не превышает Max_frequency.
Как было показано, ни один из них не значителен. В порядке выделения результатов арифметического кодирования, модель будет рассматриваться как строгая (в определенном выше смысле).
Арифметическое кодирование должно досылать дополнительные биты в конец каждого текста, совершая т.о. дополнительные усилия на завершение текста. Для ликвидации неясности с последним символом процедура done_encoding() (программа 1 строки 119-123) посылает два бита. В случае, когда перед кодированием поток битов должен блокироваться в 8-битовые символы, будет необходимо закругляться к концу блока. Такое комбинирование может дополнительно потребовать 9 битов.
Затраты при использовании арифметики конечной точности проявляются в сокращении остатков при делении. Это видно при сравнении с теоретической энтропией, которая выводит частоты из счетчиков точно также масштабируемых при кодировании. Здесь затраты незначительны - порядка 10^-4 битов/символ.
Дополнительные затраты на масштабирование счетчиков отчасти больше, но все равно очень малы. Для коротких текстов (меньших 2^14 байт) их нет. Но даже с текстами в 10^5 - 10^6 байтов накладные расходы, подсчитанные экспериментально, составляют менее 0.25% от кодируемой строки.
Адаптивная модель в программе 2, при угрозе превышения общей суммой накопленных частот значение Max_frequency, уменьшает все счетчики. Это приводит к тому, что взвешивать последние события тяжелее, чем более ранние. Т.о. показатели имеют тенденцию прослеживать изменения во входной последовательности, которые могут быть очень полезными. (Мы сталкивались со случаями, когда ограничение счетчиков до 6-7 битов давало лучшие результаты, чем повышение точности арифметики). Конечно, это зависит от источника, к которому применяется модель.
Время выполнения
Программа 1 была написана скорее для ясности, чем для скорости. При выполнении ее вместе с адаптивной моделью из программы 2, потребовалось около 420 мкс на байт исходного текста на ЭВМ VAX-11/780 для кодирования и почти столько же для декодирования. Однако, легко устраняемые расходы, такие как вызовы некоторых процедур, создающие многие из них, и некоторая простая оптимизация, увеличивают скорость в 2 раза. В приведенной версии программы на языке Си были сделаны следующие изменения:
(1) процедуры inрut_bit(), outрut_bit() и bit_рlus_follow()
были переведены в макросы, устранившие
расходы по вызову процедур;
(2) часто используемые величины были
помещены в регистровые переменные;
(3) умножения не два были заменены
добавлениями ("+=");
(4) индексный доступ к массиву в циклах стpок 189 пpогpаммы 1 и 49-52 пpогpаммы 2 адаптивной модели был заменен
операциями с указателями.
Это средне оптимизированная реализация на Си имела время выполнения в 214/252 мкс на входной байт, для кодирования/декодирования 100.000 байтов английского текста на VAX-11/780, как показано в Таблице II.
Там же даны результаты для той же программы на Aррle Macintosh и SUN3/75. Как можно видеть, кодирование программы на Си одной и той же длины везде осуществляется несколько дольше, исключая только лишь двоичные объектные файлы. Причина этого обсуждается далее. В тестовый набор были включены два искусственных файла, чтобы позволить читателям повторять результаты. 100000 байтный "алфавит" состоит из повторяемого 26-буквенного алфавита. "Ассиметричные показатели" содержит 10000 копий строки "aaaabaaaac". Эти примеры показывают, что файлы могут быть сжаты плотнее, чем 1 бит/символ (12092-х байтный выход равен 93736 битам). Все приведенные результаты получены с использованием адаптивной модели из программы 2.
Таблица II. Результаты кодирования и декодирования 100000 байтовых файлов.
| VAX-11/780 | Macintosh 512K | Sun 3/75 | |||||
|---|---|---|---|---|---|---|---|
| Вывод (байты) |
Код. (мкс) |
Декод. (мкс) |
Код. (мкс) |
Декод. (мкс) |
Код. (мкс) |
Декод. (мкс) |
|
| Сpеднеоптимизиpованная реализация на Си | |||||||
| Текстовые программы Си-программы Объектные файлы VAX Алфавит Асимметричные показатели |
57718 62991 73501 59292 12092 |
214 230 313 223 143 |
262 288 406 277 170 |
687 729 950 719 507 |
881 950 1334 942 645 |
98 105 145 105 70 |
121 131 190 130 85 |
| Аккуратно оптимизированная реализация на Си | |||||||
| Текстовые программы Си-программы Объектные файлы VAX Алфавит Асимметричные показатели |
57718 62991 73501 59292 12092 |
104 109 158 105 63 |
135 151 241 145 81 |
194 208 280 204 126 |
243 266 402 264 160 |
46 51 75 51 28 |
58 65 107 65 36 |
Дальнейшее снижение в 2 раза временных затрат может быть достигнуто перепрограммированием приведенной программы на язык ассемблера. Тщательно оптимизированная версия программ 1 и 2 (адаптивная модель) была реализована для VAX и для M68000. Регистры использовались полностью, а code_value было взято размером в 16 битов, что позволило ускорить некоторые важные операции сравнения и упростить вычитание Нalf. Характеристики этих программ также приведены в Таблице II, чтобы дать читателям представление о типичной скорости выполнения.
Временные характеристики ассемблерной реализации на VAX-11/780 даны в Таблице III. Они были получены при использовании возможности профиля UNIXа и точны только в пределах 10%. (Этот механизм создает гистограмму значений программного счетчика прерываний часов реального времени и страдает от статистической вариантности также как и некоторые системные ошибки). "Вычисление границ" относится к начальным частям encode_symbol() и decode_symbol() (программа 1 строки 90-94 и 190-193), которые содержат операции умножения и деления. "Сдвиг битов" - это главный цикл в процедурах кодирования и декодирования (строки 95-113 и 194213). Требующее умножения и деления вычисление cum в decode_symbol(), а также последующий цикл для определения следующего символа (строки 187-189), есть "декодирование символа". А "обновление модели" относится к адаптивной процедуре uрdate_model() из программы 2 (строки 26-53).
Таблица III. Временные интервалы ассемблерной версии VAX-11/780.
| Время кодирования (мкс) |
Время декодирования (мкс) |
|
|---|---|---|
| Текстовые файлы | 104 | 135 |
| Вычисление гpаниц Сдвиг битов Обновление модели Декодиpование символа Остальное |
32 39 29 - 4 |
31 30 29 45 5 |
| Си-программа | 109 | 151 |
| Вычисление гpаниц Сдвиг битов Обновление модели Декодиpование символа Остальное |
30 42 33 - 4 |
28 35 36 51 1 |
| Объектный файл VAX | 158 | 241 |
| Вычисление гpаниц Сдвиг битов Обновление модели Декодиpование символа Остальное |
34 46 75 - 3 |
31 40 75 94 1 |
Как и предполагалось, вычисление границ и обновление модели требуют одинакового количества времени и для кодирования и для декодирования в пределах ошибки эксперимента. Сдвиг битов осуществляется быстрее для текстовых файлов, чем для Си-программ и объектных файлов из-за лучшего его сжатия. Дополнительное время для декодирования по сравнению с кодированием возникает из-за шага "декодирование символа" - цикла в строке 189, выполняемого чаще (в среднем 9 раз, 13 раз и 35 раз соответственно). Это также влияет на время обновления модели, т.к. связано с количеством накапливающих счетчиков, значения которых необходимо увеличивать в строках 49-52 программы 2. В худшем случае, когда символы распределены одинаково, эти циклы выполняются в среднем 128 раз.
Такое положение можно улучшить применяя в качестве СД для частот дерево более сложной организации, но это замедлит операции с текстовыми файлами.
Адаптивное сжатие текстов
Результаты сжатия, достигнутые программами 1 и 2 варьируются от 4.8-5.3 битов/символ для коротких английских текстов (10^3-10^4 байтов) до 4.5-4.7 битов/символ для длинных (10^5-10^6 байтов). Хотя существуют и адаптивные техники Хаффмана, они все же испытывают недостаток концептуальной простоты, свойственной арифметическому кодированию.
При сравнении они оказываются более медленными. Например, Таблица IV приводит характеристики среднеоптимизированной реализации арифметического кодирования на Си с той из программ comрact UNIXa, что реализует адаптивное кодирование Хаффмана с применением сходной модели. (Для длинных файлов, как те, что используются в Таблице IV, модель comрact по существу такая же, но для коротких файлов по сравнению с приведенной в программе 2 она лучше). Небрежная проверка comрact показывает, что внимание к оптимизации для обоих систем сравнимо при том, что арифметическое кодирование выполняется в 2 раза быстрее. Показатели сжатия в некоторой степени лучше у арифметического кодирования для всех тестовых файлов. Различие будет заметным в случае применения более сложных моделей, предсказывающих символы с вероятностями, зависящими от определенных обстоятельств (например, следования за буквой q буквы u).
Таблица IV. Сравнение адаптивных кодирований Хаффмана и арифметического.
| Арифметическое кодирование |
Кодирование Хаффмана |
|||||
|---|---|---|---|---|---|---|
| Вывод (байты) |
Код. (мкс) |
Декод. (мкс) |
Вывод (байты) |
Код. (мкс) |
Декод. (мкс) |
|
| Текстовые программы Си-программы Объектные файлы VAX Алфавит Асимметричные показатели |
57718 62991 73501 59292 12092 |
214 230 313 223 143 |
262 288 406 277 170 |
57718 62991 73501 59292 12092 |
550 596 822 598 215 |
414 441 606 411 132 |
Неадаптированное кодирование
Оно может быть выполнено арифметическим методов с помощью постоянной модели, подобной приведенной в Программе 2. При этом сжатие будет лучше, чем при кодировании Хаффмана. В порядке минимизации времени выполнения, сумма частот cum_freq[0] будет выбираться равной степени двойки, чтобы операции деления при вычислении границ (программа 1, строки 91-94 и 190-193) выполнялись через сдвиги. Для реализации на ассемблере VAX-11/780 время кодирования/декодирования составило 60-90 мкс. Аккуратно написанная реализация кодирования Хаффмана с использованием таблиц просмотра для кодирования и декодирования будет выполнятся немного быстрее.
Кодирование черно-белых изображений
Применение для этих целей
арифметического кодирования было
рассмотрено Лангдоном и Риссаненом,
получившим при этом блестящие результаты с
помощью модели, использующей оценку
вероятности цвета точки относительно
окружающего ее некоторого шаблона. Он
представляет собой совокупность из 10 точек,
лежащих сверху и спереди от текущей,
поэтому при сканировании растра они ей
предшествуют. Это создает 1024 возможных
контекста, относительно которых
вероятность черного цвета у данной точки
оценивается адаптивно по мере просмотра
изображения. После чего каждая полярность
точки кодировалась арифметическим методом
в соответствии с этой вероятностью. Такой
подход улучшил сжатие на 20-30% по сравнению с
более ранними методами. Для увеличения
скорости кодирования Лангдон и Риссанен
применили приблизительный метод
арифметического кодирования, который
избежал операций умножения путем
представления вероятностей в виде целых
степеней дроби 1/2.
Кодирование Хаффмана для
этого случая не может быть использовано
прямо, поскольку оно никогда не выполняет
сжатия двухсимвольного алфавита.
Другую возможность для арифметического кодирования представляет применяемый к такому алфавиту популярный метод кодирования длин тиражей (run-length method). Модель здесь приводит данные к последовательности длин серий одинаковых символов (например, изображение представляются длинами последовательностей черных точек, идущих за белыми, следующих за черными, которым предшествуют белые и т.д.). В итоге должна быть передана последовательность длин. Стандарт факсимильных аппаратов CCITT строит код Хаффмана на основе частот, с которыми черные и белые последовательности разных длин появляются в образцах документов. Фиксированное арифметическое кодирование, которое будет использовать те же частоты, будет иметь лучшие характеристики, а адаптация таких частот для каждого отдельного документа будет работать еще лучше.
Кодирование произвольно распределенных целых чисел.
Оно часто рассматривается на основе применения более сложных моделей текстов, изображений или других данных. Рассмотрим, например, локально адаптивную схему сжатия Бентли et al, где кодирование и декодирование работает с N последними разными словами. Слово, находящееся в кэш-буфере, определяется по целочисленному индексу буфера. Слово, которое в нем не находится, передаются в кэш-буфер через посылку его маркера, который следует за самими символами этого слова. Это блестящая модель для текста, в котором слова часто используются в течении некоторого короткого времени, а затем уже долго не используются. Их статья обсуждает несколько кодирований переменной длины уже для целочисленных индексов кэш-буфера.
В качестве основы для кодов переменной длины арифметический метод позволяет использовать любое распределение вероятностей, включая среди множества других и приведенные здесь. Кроме того, он допускает для индексов кэш-буфера применение адаптивной модели, что желательно в случае, когда распределение доступов к кэш-буферу трудно предсказуемо. Еще, при арифметическом кодировании ......, предназначенные для этих индексов, могут пропорционально уменьшаться, чтобы приспособить для маркера нового слова любую желаемую вероятность.
Приложение. Доказательство декодирующего неравенства.
Полагаем:
| (value-low+1)*cum_freq[0]-1 |
cum_freq[symbol] <= | --------------------------- | < cum_freq[symbol-1].
|_ high-low+1 _|
Дpугими словами:
(value-low+1)*cum_freq[0]-1
cum_freq[symbol] <= --------------------------- + e < < cum_freq[symbol-1] (1),
range
range - 1
где range = high - low + 1, 0 <= e <= ----------.
range
(Последнее неравенство выражения (1) происходит из факта, что cum_freq[symbol-1] должно быть целым ). Затем мы хотим показать, что low' <= value <= high', где low' и high' есть обновленные значения для low и high как определено ниже.
| range*cum_freq[symbol] | range |- (value-low+1)*cum_freq[0]-1 -|
(a) low' · low + | ---------------------- | <= low + ----------- | --------------------------- - e |
|_ cum_freq[0] _| cum_freq[0] |_ range _|
1
Из выpажения (1) имеем: <= value + 1 - ----------- ,
cum_freq[0]
Поэтому low' <= value, т.к. и value, и low', и cum_freq[0] > 0.
| range*cum_freq[symbol-1] | range |- (value-low+1)*cum_freq[0]-1 -|
(a) high' · low + | ------------------------ | - 1 >= low + ----------- | --------------------------- + 1 - e| - 1
|_ cum_freq[0] _| cum_freq[0] |_ range _|
range |- 1 range-1 -|
Из выpажения (1) имеем: >= value + ----------- |- ----- + 1 - ------- | = value.
cum_freq[0] |_ range range _|
Сайт о сжатии
>>
ARCTEST
>>
Сравнительные тесты
|
Альтернативные тесты
|
Графические тесты
|
Новости
|
Утилиты
|
Файл'менеджеры
|
Описания
|
Линки
|
Necromancer's DN
|
Поддержка
|
|
Сайт о сжатии >>
Новинки | О сервере | Статистика
Книга "Методы сжатия данных" >>
Универсальные | Изображений | Видео
Разделы >> Download (статьи+исходники) | Ссылки | Ru.compress | Arctest | Видео | Каталог ссылок | Форум
Проекты >> Д.Ватолина | А.Ратушняка | М.Смирнова | В.Юкина | Е.Шелвина | А.Филинского | Д.Шкарина | С.Оснача
