Главная/

Программирование, базы данных. /

Сжатие данных

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 или без нее ), но может быть улучшено еще.

    Заметьте, что каждая буква, сжатая  арифметическим методом требует обраще-

ния к процедуре findrange, за которым следует вызов update. Т.о. путь от корня

к букве в дереве накапливаемых частот будет проделан дважды  во время сжатия и

дважды во время развертывания. Минимизация общего времени сжатия или развертывания сообщения требует минимизации общей длины всех путей, пройденных в дереве. Если частоты букв известны заранее, то статичное дерево Хаффмана будет минимизировать длину этого маршрута! Длина пути  для сообщения S будет ограничена значением 2(Hs(S) + C(S)), где C(S) - количество букв в строке, а множитель 2 отражает тот факт, что каждый маршрут проходится дважды.

    Нет смысла  в использовании  дерева накапливаемых частот, если все вероят-

ности известны заранее, что позволяет применять простую поисковую таблицу  для

нахождения вероятностей. Если они неизвестны, то оптимальный Л-алгоритм Уитте-

ра может быть легко модифицирован для управления деревом накапливаемых частот,

причем длина пути обхода дерева, имеющая место во время сжатия или развертыва-

ния не будет превышать значение 2( H (S) + C(S) ). Аналогично  можно использо-

вать алгоритм  расширяющегося префикса, дающего ограничение O(H (S)) для длины

пути, но при большем постоянном множителе. Ранее пpиведенные опытные результа-

ты показывают, что эти постоянные множители более чем компенсируются простотой

алгоритма расширяющегося префикса.

    В соответствии с этим алгоритмом операции расширения  не нужно затрагивать

информации  внутренних  узлов дерева. Когда расширение  выполняется  как часть

операции update, каждая  операция  полувpащения должна предохранять инвариацию

регулирования  весов узлов дерева. На рисунке 8 дерево полувpащается вокруг А,

имея результатом то, что вес  Х сокращается весом А  и наращивается весом С. В

то же время, поскольку это есть часть повторного пути от А к корню, вес А уве-

личивается. Итоговый код будет:

procedure update( c: codetype );

var

  c, d: upindex   { пара полувpащаемых узлов };

  a, b: downindex { наследники полувpащемых узлов };

begin

  a := c + succmax;

  repeat { вверх по дереву, чередуя и наращивая }

    c := up[a];

    if c # root then begin { оставшаяся пара }

      d := up[c];

      { обмен между наследниками пары }

      b := left[d];

      if c = b then begin b := right[d];

                          right[d] := a;

      end else left[d] := a;

      if a = left[c] then left[c] := b

      else                right[c] := b;

      up[a] := d;

      up[b] := c;

      freq[c] := ( freq[c] - freq[a] ) + freq[b];

      freq[a] := freq[a] + 1;

      a := d;

    end else begin { помещение непарного ( нечетного ) узла в конец пути }

      freq[a] := freq[a] + 1;

      a := up[a];

    end;

  until a = root;

  freq[root] := freq[root] + 1;

end { update };

    Программа игнорирует проблему переполнения счетчиков частот. Арифметичес-

кое  сжатие  данных постоянно  производит вычисление  по формуле a * b / c, и

предел  точности результата вычисления определяется размером памяти, выделяе-

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

ным. Многие 32-битные машины накладывают 32-битовое ограничение