Реферат: Сжатие данных
пропорционально размеру выходного файла, и в обоих случаях, выход в наихудшем
варианте имеет длину O(H ), т.о. оба должны выполняться в худшем случае за время
O(H ). Постоянные коэффициенты отличаются, поскольку алгоритм расширяемого
префикса производит меньше работы на бит вывода, но в худшем случае производя на
выходе больше битов. Для 13 файлов, представленных в таблице I, Лалгоритм
выводит в среднем 2К битов в секунду, когда как алгоритм расширяемого префикса -
более 4К битов в секунду, т.о. второй алгоритм всегда намного быстрее. Эти
показатели были получены на рабочей станции М68000, серии 200 9836CU Хьюлет
Паккард, имеющей OC HP-UX. Оба алгоритма были реализованы на Паскале, сходным по
описанию с представленным здесь языком.
АРИФМЕТИЧЕСКИЕ КОДЫ.
Tекст, полученный при сжатии арифметических данных, рассматривается в качестве
дроби, где каждая буква в алфавите связывается с некоторым подинтервалом
открытого справа интервала [0,1). Текст источника можно рассматривать как
буквальное представление дроби, использующей систему исчисления, где каждая
буква в алфавите используется в качестве числа, а интервал значений, связанных с
ней зависит от частоты встречаемости этой буквы. Первая буква сжатого текста
(самая "значащая" цифра) может быть декодирована нахождением буквы, полуинтеpвал
которой включает значение пpедставляющей текст дроби. После определения
очередной буквы исходного текста, дробь пересчитывается для нахождения
следующей. Это осуществляется вычитанием из дроби основы связанной с найденной
буквой подобласти, и делением результата на ширину ее полуинтервала. После
завершения этой операции можно декодировать следующую букву.
В качестве примера арифметического кодирования рассмотрим алфавит из 4-х букв
(A, B, C, D) с вероятностями ( 0.125, 0.125, 0.25, 0.5 ). Интервал [ 0,1) может
быть разделен следующим образом:
A = [ 0, 0.125 ), B = [ 0.125, 0.25 ), C = [ 0.25, 0.5 ), D = [ 0.5, 1 ).
Деление интервала легко осуществляется посредством накопления вероятностей
каждой буквы алфавита и ее предшественников. Дан сжатый текст 0.6 (
представленный в виде десятичной дроби ), тогда первой его буквой должна быть D,
потому что это число лежит в интервале [ 0.5, 1 ). Пересчет дает результат:
( 0.6 - 0.5 ) / 0.5 = 0.2
Второй буквой будет B, т.к. новая дробь лежит в интервале [ 0.125, 0.25 ).
Пересчет дает:
( 0.2 - 0.125 ) / 0.125 = 0.6.
Это значит, что 3-я буква есть D, и исходный текст при отсутствии информации о
его длине, будет повторяющейся строкой DBDBDB ...
Первоочередной проблемой здесь является высокая точность арифметики для
понимания и опеpиpования со сплошным битовым потоком, каковым выглядит сжатый
текст, рассматриваемый в качестве числа. Эта проблема была решена в 1979 году.
Эффективность сжатия методом статичного арифметического кодирования будет равна
H , только при использовании арифметики неограниченной точности. Но и
ограниченной точности большинства машин достаточно, чтобы позволять осуществлять
очень хорошее сжатие. Целых переменных длиной 16 битов, 32-битовых произведений
и делимых достаточно, чтобы результат адаптивного арифметического сжатия лежал в
нескольких процентах от предела и был едва ли не всегда немного лучше, чем у
оптимального адаптированного кода Хаффмана, предложенного Уитером.
Как и в случае кодов Хаффмана, статичные арифметические коды требуют двух
проходов или первоначального знания частот букв. Адаптированные арифметические
коды требуют эффективного алгоритма для поддержания и изменения информации о
бегущей и накапливаемой частотах по мере обработки букв. Простейший путь для
этого - завести счетчик для каждой буквы, увеличивающий свое значение на единицу
всякий раз, когда встречена сама эта буква или любая из следующих после нее в
алфавите. В соответствии с этим подходом, частота буквы есть разница между
числом ее появлений и числом появлений ее предшественников. Этот простой подход
может потребовать O(n) операций над буквой n-арного алфавита. В реализованном на
Си Уиттеном, Нейлом и Клири алгоритме сжатия арифметических данных, среднее
значение было улучшено посредством использования дисциплины move-to-front, что
сократило количество счетчиков, значения которых измененяются каждый раз, когда
обрабатывается буква.
Дальнейшее улучшение организации распределения накопленной частоты требует
коренного отхода от простых СД. Требования, которым должна отвечать эта СД лучше
изучить, если выразить ее через абстрактный тип данных со следующими пятью
операциями: initialize, update, findletter, findrange и maxrange. Операция
инициализации устанавливает частоту всех букв в 1, и любое не равное нулю
значение будет действовать до тех пор, пока алгоритм кодирования и
раскодирования используют одинаковые начальные частоты. Начальное значение
частоты, равное нулю, будет присваиваться символу в качестве пустого интервала,
т.о. предупреждая его от передачи или получения.
Операция update(c) увеличивает частоту буквы с. Функции findletter и findrange
обратны друг другу, и update может выполнять любое изменение порядка алфавита,
пока сохраняется эта обратная связь. В любой момент времени findletter ( f, c,
min, max ) будет возвращать букву c и связанный с нею накапливаемый частотный
интервал [ min, max ), где f [ min, max ). Обратная функция findrange( c, min,
max ) будет возвращать значения min и max для данной буквы c.
Функция maxrange возвращает сумму всех частот всех букв алфавита, она нужна
для перечисления накопленных частот в интервале [ 0, 1 ).
Применение расширения к арифметическим кодам.
Ключом к реализации СД, накапливающей значение частот и в худшем случае
требующей для каждой буквы менее, чем O(n) операций для n-буквенного алфавита,
является представление букв алфавита в качестве листьев дерева. Каждый лист
дерева имеет вес, равный частоте встречаемой буквы, вес каждого узла
представляет собой сумму весов его наследников. Рисунок 7 демонстрирует такое
дерево для 4-х-буквенного алфавита ( A, B, C, D ) с вероятностями ( 0.125,
0.125, 0.25, 0.5 ) и частотами ( 1, 1, 2, 4 ). Функция maxrange на таком дереве
вычисляется элементарно - она просто возвращает вес корня. Функции update и
findrange могут быть вычислены методом обхода дерева от листа к корню, а функция
findletter - от корня к листу.
СД для представления дерева накапливаемых частот по существу такие же, как
и рассмотренные ранее для представления дерева кодов префиксов, с добавлением
массива, хранящего частоты каждого узла.
const
maxchar = ... { maximum source character code };
succmax = maxchar + 1;
twicemax = 2 * maxchar + 1;
root = 1;
type
codetype = 0..maxchar { source character code range };
bit = 0..1;
upindex = 1..maxchar;
downindex = 1..twicemax;
var
up: array[downindex] of upindex;
freq: array[downindex] of integer;
left,right: array[upindex] of downindex;
Инициализация этой структуры включает в себя не только построение древовидной
СД, но и инициализацию частот каждого листа и узла следующим образом:
procedure initialize;
var
u: upindex;
d: downindex;
begin
for d := succmax to twicemax do freq[d] := 1;
for u := maxchar downto 1 do begin
left[u] := 2 * u;
right[u] := ( 2 * u ) + 1;
freq[u] := freq[left[u]] + freq[right[u]];
up[left[u]] := u;
up[right[u]] := u;
end;
end { initialize };
Для того, чтобы отыскать букву и соответствующий ей интервал накопленной
частоты, когда известна отдельная накопленная частота, необходимо обойти дерево
начиная с корня по направлению к букве, производя беглое вычисление интервала
частот, соответствующего текущей ветке дерева. Интервал, соответствующий корню,
есть [0, freq[root]], он должен содержать f. Если отдельный узел деpева i связан
с интервалом [a, b), где a - b = freq[i], то интервалами, связанными с двумя
поддеревьями будут интервалы [a, a+freq[left[i]] ) и [a+freq[left[i]], b). Они
не пересекаются, поэтому путь вниз по дереву будет таким, что f содержится в
подинтервале, связанном с каждым узлом на этом пути. Это показано в
следующей процедуре:
procedure findsymbol( f: integer; var c: codetype; var a, b: integer );
var
i: downindex;
t: integer;
begin
a := 0;
i := root;
b := freq[root];
repeat
t := a + freq[left[i]];
if f < t then begin { повоpот налево }
i := left[i];
b := t;
end else begin { повоpот напpаво }
i := right[i];
a := t;
end;
until i > maxchar;
c := i - succmax;
end { findsymbol };
Чтобы найти связанный с буквой частотный интервал, процесс, описанный в
findsymbol должен происходить в обратном направлении. Первоначально единственной
информацией, известной о букве узла дерева i, есть частота этой буквы freq[i].
Это означает, что интервал [0, freq[i]) будет соответствовать какойлибо букве,
если весь алфавит состоит из нее одной. Дано: интервал [a, b) связан с некоторым
листом поддерева с корнем в узле i, тогда может быть вычислен интервал,
