Применение расширяющихся деревьев для сжатия данных

АРИФМЕТИЧЕСКИЕ КОДЫ. 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 году [6]. Эффективность сжатия методом статичного арифметического кодирования будет равна H , только при использовании арифметики неограниченной точности. Но и ограниченной точности большинства машин достаточно, чтобы позволять осуществ- лять очень хорошее сжатие. Целых переменных длиной 16 битов, 32-битовых произ- ведений и делимых достаточно, чтобы результат адаптивного арифметического сжа- тия лежал в нескольких процентах от предела и был едва ли не всегда немного лучше, чем у оптимального адаптированного кода Хаффмана, предложенного Уитером. Как и в случае кодов Хаффмана, статичные арифметические коды требуют двух проходов или первоначального знания частот букв. Адаптированные арифметические коды требуют эффективного алгоритма для поддержания и изменения информации о бегущей и накапливаемой частотах по мере обработки букв. Простейший путь для этого - завести счетчик для каждой буквы, увеличивающий свое значение на еди- ницу всякий раз, когда встречена сама эта буква или любая из следующих после нее в алфавите. В соответствии с этим подходом, частота буквы есть разница ме- жду числом ее появлений и числом появлений ее предшественников. Этот простой подход может потребовать O(n) операций над буквой n-арного алфавита. В реали- зованном на Си Уиттеном, Нейлом и Клири алгоритме сжатия арифметических данных [12], среднее значение было улучшено посредством использования дисциплины move -to-front, что сократило количество счетчиков, значения которых измененяются каждый раз, когда обрабатывается буква. Дальнейшее улучшение организации распределения накопленной частоты требует коренного отхода от простых СД, используемых в [12]. Требования которым должна отвечать эта СД лучше изучить, если выразить ее через абстрактный тип данных со следующими пятью операциями: initialize, update, findletter, findrange и maxrange. Операция инициализации устанавливает частоту всех букв в 1, и любое не равное нулю значение будет действовать до тех пор, пока алгоритм кодирова- ния и раскодирования используют одинаковые начальные частоты. Начальное значе- ние частоты, равное нулю, будет присваиваться символу в качестве пустого ин- тервала, т.о. предупреждая его от передачи или получения. Операция update(c) увеличивает частоту буквы с. Функции findletter и find- range обратны друг другу, и update может выполнять любое изменение порядка ал- фавита, пока сохраняется эта обратная связь. В любой момент времени findletter ( f, c, min, max ) будет возвращать букву c и связанный с нею накапливаемый частотный интервал [ min, max ), где f [ min, max ). Обратная функция find- range( 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 - от корня к листу. A/1 ------- o ------ o ------ o 2| 4| 8| | | | B/1 C/2 D/4 Рисунок 7. Дерево накапливаемых частот. СД для представления дерева накапливаемых частот по существу такие же, как и рассмотренные ранее для представления дерева кодов префиксов, с добавлением массива, хранящего частоты каждого узла.

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, тогда может быть вычислен интервал, связанный с этим листом в поддереве up[i]. Если i - левый наследник, то это просто интервал [ a, b ), если правый, то - [ a + d, b + d ), где d = freq[up[i]] - freq[i], или, что одно и то же: d = freq[left[up[i]]].

procedure findrange(c: codetype; var a, b: integer);

var

 i: downindex;

 d: integer;

begin

 a := 0;

 i := c + succmax;

 b := freq[i];

 repeat

  if right[up[i]] = i then

  begin { i is right child }

  d := freq[left[up[i]]];

  a := a + d;

  b := b + d;

  end;

  i := up[i];

 until i = root;

end { findrange };

Если проблема сохранения сбалансированности в дереве накапливаемых частот не стоит, то функция update будет тривиальной, состоящей из обхода дерева от изменяемого листа до корня, сопровождающегося увеличением значения каждого встреченного узла на единицу. В противном случае время, затраченное на опера- ции findletter, findrange и update при первоначально сбалансированном дереве будет в сpеднем O(log n) на одну букву для n-буквенного алфавита. Это лучше, чем худший вариант O(n), достигаемый посредством применения линейной СД (с ор- ганизацией move-to-front или без нее ), но может быть улучшено еще.

Отправить комментарий

Проверка
Антиспам проверка
Image CAPTCHA
...