Как было показано, и кодирование Шеннона-Фано, и кодирование Хаффмана связано со значительной проблемой - необходимостью поставлять дерево вместе со сжатыми данными. Это является недостатком, поскольку трудно добиться существенного сжатия дерева, что ведет к снижению коэффициента сжатия данных. Еще один недостаток применения этих методов состоит в том, что входные данные приходится считывать дважды: первый раз для вычисления частоты появления символов в данных, а второй - сразу после построения дерева при выполнении действительного кодирования данных.

Не существует ли какой-либо способ исключения необходимости поставки дерева или двукратного считывания входных данных (желательно было бы избавиться от обоих этих недостатков)? Существует вариант сжатия Хаффмана, называемый адаптивным кодированием Хаффмана, который позволяет это сделать. Однако в этой главе мы рассмотрим малоизвестную адаптивную технологию, использующую скошенные деревья, с которыми мы впервые встретились в главе 8.

Дуглас В. Джонс (Douglas W. Jones) разработал сжатие с использованием скошенного дерева в 1988 году [8]. Если помните, в главе 8 говорилось, что скошенные деревья - это метод балансировки дерева бинарного поиска посредством скоса достигнутого узла к корневому узлу. Таким образом, после отыскания узла он перемещается к корневому узлу с помощью ряда поворотов, называемых операциями двустороннего и одностороннего поворота. В результате скоса узлы, обращение к которым осуществляется наиболее часто, оказываются, как правило, в верхней части дерева, а узлы, обращение к которым происходит реже - ближе к листьям. Если применить эту стратегию к префиксному дереву и закодировать символы, как это делалось при использовании алгоритмов Хаффмана и Шеннона-Фано (левая связь кодируется нулевым битом, а правая единичным), окажется, что со временем кодирование данного символа будет меняться. Дерево будет приспосабливаться к частоте появления закодированных символов. Более того, наиболее часто используемые символы будут располагаться вблизи вершины дерева и, следовательно, как правило, их коды будут короче кодов реже используемых символов.

Следует признать, что скошенные деревья были разработаны для оптимизации деревьев бинарного поиска, т.е. упорядоченных деревьев. Частично их полезность обусловлена тем, что операции скоса поддерживают упорядоченность во время различных поворотов и трансформаций. Префиксные деревья не упорядочены, поэтому можно избежать большей части сложного манипулирования указателями, связного с поворотами. Кроме того, потребуется обеспечить, чтобы листья оставались листьями. В противном случае дерево перестало бы быть префиксным. Поэтому мы будем использовать скос, в результате которого родительский узел листа перемещается ближе к корневому узлу.

Код реализации базового алгоритма выполнения сжатия выглядит подобно приведенному в листинге 11.15.

Листинг 11.15. Базовый алгоритм сжатия с использованием скошенного дерева

procedure TDSplayCompress(aInStream, aOutStream : TStream) ; var
STree : TSplayTree;
BitStrm : TtdOutputBitStream;
Signature : longint;
Size : longint;
begin
{вывести информацию заголовка fсигнатуру и размер несжатых данных} Signature := TDSplayHeader;
aOutStream.WriteBuffer(Signature, sizeof(longint));
Size := alnStream.Size;
aOutStream.WriteBuffer(Size, sizeof(longint));

{в случае отсутствия данных для сжатия выйти из подпрограммы} if (Size = 0) then Exit; {подготовка} STree := nil; BitStrm := nil; try

{создать сжатый поток битов}
BitStrm : = TtdOutputBitStream.Create(aOutStream);
BitStrm.Name := 1 Splay compressed stream1 ; {создать скошенное дерево) STree : = TSplayTree.Create;

{сжатье символы входного потока и поместить их в поток битов} DoSplayCompression(aInStream, BitStrm, STree); finally

BitStrm.Free;
STгее.Free;
end;
end;

Для пометки выходного потока как сжатого с использованием скошенного дерева в выходной поток мы записываем сигнатуру типа длинного целого, а затем записываем размер несжатого потока. Если входной поток пуст, выполняется выход из подпрограммы, - в этом случае задача выполнена. В противном случае мы создаем выходной поток битов, который будет содержать выходной поток и скошенное дерево. Затем для выполнения реального сжатия мы вызываем метод DoSplayConapression. Код этой подпрограммы приведен в листинге 11.16.

Листинг 11.16. Цикл выполнения сжатия с использованием скошенного дерева

procedure DoSplayCompression(aInStream : TStream;
aBitStream : TtdOutputBitStream;
aTree : TSplayTree);
var
i : integer;
Buffer : PByteArray;
BytesRead : longint;
BitString : TtdBitString;
begin
GetMem(Buffer, SplayBufferSize); try
{сбросить входной поток в исходное состояние)
alnStream.Position := 0;
{считать первый блок из входного потока}
BytesRead := alnStream.Read(BufferA, SplayBufferSize);
while (BytesRead <> 0) do begin
{записать строку битов для каждого символа в блоке}
for i := 0 to pred(BytesRead) do aTree.EncodeByte(aBitStream, Buf ferA[i]);

{считать следующий блок из входного потока) BytesRead := alnStream.Read(BufferA, SplayBufferSize); end; finally

FreeMem(Buffer, SplayBufferSize);
end;
end;

Фактически эта подпрограмма представляется собой подпрограмму выполнения вложенного цикла. Во внешнем цикле выполняется поблочное считывание входного потока, а во внутреннем (через вызов метода EncodeByte скошенного дерева) -кодирование каждого байта текущего блока и запись результирующего кода в выходной поток битов.

Теперь пора рассмотреть внутренний класс TSplayTree, который выполняет основную часть работы по реализации алгоритма сжатия с использованием скошенного дерева. Код интерфейса этого класса показан в листинге 11.17.

Листинг 11.17. Класс сжатия с использованием скошенного дерева

type PSplayNode = ATSplayNode;
TSplayNode = packed record
hnParentlnx: longint;
hnLeftlnx : longint;
hnRightlnx : longint;
hnlndex : longint;
end;
PSplayNodeArray = ATSplayNodeArray;
TSplayNodeArray = array [0..510] of TSplayNode;
type TSplayTree = class private FTree : TSplayNodeArray;
FRoot : integers-protected
procedure stConvertCodeStr (const aRevCodeStr : ShortString;
var aBitString : TtdBitString);
procedure stInitialize;
procedure stSplay(aNode!nx : integer);
public constructor Create;
procedure EncodeByte(aBitStream : TtdOutputBitStream;
aValue : byte);
function DecodeByte(aBitStream : TtdlnputBitStream) : byte;
end;

Хотя можно было бы воспользоваться ориентированным на узлы деревом, как это делалось в главе 8, поскольку нам известно количество символов в используемом алфавите (в общем случае используется алфавит, содержащий 256 символов), проще отдать предпочтение применению ориентированной на массивы системе, подобной структуре данных типа сортирующего дерева и дерева Хаффмана. Еще один аргумент в пользу перехода на использование других структур данных состоит в том, что в случае применения неадаптивных методов сжатия можно было строить таблицу кодов, так как они были статическими. При использовании сжатия с применением скошенного дерева битовый код символа зависит от состояния скошенного дерева и момента времени кодирования символа. В этом случае мы больше не можем использовать статическую таблицу. Следовательно, одно из выдвигаемых требований - возможность быстрого и эффективного поиска символа в дереве (предпочтительно при помощи алгоритма типа O(l) - мы не хотим его искать). Как только символ и его узел листа определены, можно легко выполнить обход вверх по дереву до корневого узла с целью вычисления кода символа (вообще говоря, мы получим битовый код с обратным порядком следования битов, но с помощью стека его легко можно изменить на противоположный).

Обработка начинается с известного состояния дерева. Можно было бы определить дерево, отражающее частоту употребления букв английского алфавита или какое либо иное распределение символов, но на практике значительно проще создать идеально сбалансированное дерево. В этом случае каждый узел имеет три "указателя", которые в действительности являются всего лишь индексами других узлов в массиве, и мы определяем его таким же образом, как делали при работе с сортирующим деревом: дочерние узлы узла с индексом п располагаются в позициях 2п + 1 и 2п + 2, а его родительский узел - в позиции (п - 1)/2. Поскольку в действительности узлы не будут перемещаться в массив (мы собираемся манипулировать только индексами), позиции листьев всегда будут известны. Они всегда будут занимать одни и те же позиции в массиве: #0 всегда будет находиться в позиции с индексом 255, #1 - в позиции с индексом 256 и т.д. Код метода, выполняющего инициализацию дерева, показан в листинге 11.18. Этот метод вызывается из конструктора Create.

Листинг 11.18. Метод stlnitialize

procedure TSplayTree. stlnitialize; var i : integer; begin {создать полностью сбалансированное дерево; корневой узел будет соответствовать нулевому элементу; родительский узел узла п будет располагаться в позиции (п-1) /2, а его дочерние узлы -

в позициях 2п+1 и 2п+2} FillChar(FTree, sizeof(FTree), 0);
for i : = 0 to 254 do begin
FTree[i] .hnLeftlnx := (2 * i) + 1;
FTree[i] .hnRightlnx := (2 * i) + 2;
end;
for i := 1 to 510 do
FTree[i].hnParentlnx := (i - 1) div 2;
end;
constructor TSplayTree.Create;
begin
inherited Create;
stlnitialize;
end;

При сжатии символа мы находим его узел в дереве. Затем мы выполняем переходы вверх по дереву, сохраняя соответствующие биты в стеке (левой связи соответствует нулевой бит, а правой - единичный). По достижении корневого узла можно вытолкнуть биты из стека. Они определят код символа (в коде, приведенном в листинге 11.19, в качестве стека используется короткая строка).

Затем выполняется скос родительского узла по направлению к корневому узлу. Мы не выполняем скос к корню самого узла символа ввиду того, что требуется сохранить размещение символов в узлах листьев. В противном случае было бы совершенно исключено, чтобы код одного символа становился началом кода следующего. Скос родительского узла повлечет "перетаскивание" вместе с ним и дочернего узла. В результате чаще используемые символы окажутся ближе к верхушке дерева.

Листинг 11.19. Методы EncodeByte и stSplay

procedure TSplayTree.EncodeByte(aBitStream : TtdOutputBitStream;
aValue : byte)/
var
Nodelnx : integer;
ParentInx : integer;
RevCodeStr : ShortString;
BitString : TtdBitString;
begin
{начиная с узла aValue, сохранить на каждом шаге (0) бит при перемещении вверх по дереву по левой связи и (1) бит при перемещении по правой связи) RevCodeStr := 1 ' ; Nodelnx := aValue + 255; while (Nodelnx <> 0) do begin
Parentlnx := FTree[Nodelnx].hnParentlnx;
inc(RevCodeStr[0]) ;
if (FTree[Parentlnx] .hnLeftlnx = Nodelnx) then
RevCodeStr[length(RevCodeStr)] := f0' else
RevCodeStr[length(RevCodeStr)] : = ' 11; Nodelnx := Parentlnx;
end;
{преобразовать строковый код в строку битов)
stConvertCodeStг(RevCodeStr, BitString);
{записать строку битов в поток битов}
aBitStream.WriteBits(BitString);
{выполнить скос узла)
stSplay(aValue + 255);
ends-procedure TSplayTree. stConvertCodeStr (const aRevCodeStr : ShortString;
var aBitString : TtdBitString);
var
ByteNum : integer;
i : integer;
Mask : byte;
Accum : byte;
begin
{подготовиться к выполнению цикла преобразования) ByteNum := 0; Mask := 1; Accum := 0;
{преобразовать порядок следования битов на противоположный) for i := length (aRevCodeStr) downto 1 do begin if (aRevCodeStr[i] = '1') then
Accum := Accum or Mask;
Mask := Mask shl 1; if (Mask = 0) then begin aBitString.bsBits[ByteNum] : = Accum;
inc(ByteNum) ; Mask := 1; Accum :- 0;
end;
end;
{сохранить биты, расположенные слева от текущего) if (Mask о 1) then
aBitString .bsBits [ByteNum] : = Accum; {сохранить двоичный код в массиве кодов) aBitString.bsCount : = length(aRevCodeStr);
end;

procedure TSplayTree.stSplay(aNodelnx : integer); var Dad : integer; GrandDad : integer; Uncle : integers-begin {выполнить скос узла) repeat

{извлечь родительский узел данного узла) Dad := FTree[aNodelnx].hnParentlnx;

{если родительский узел является корневым, задача выполнена) if (Dad= 0) then aNodelnx := 0

{в противном случае необходимо выполнить поворот узла на 90 градусов с целью его перемещения вверх по дереву) else begin
{извлечь родительский узел родительского узла) GrandDad := FTree[Dad].hnParentlnx;
{выполнить поворот на 90 градусов (т.е. поменять мечтами узел и его узел-дядю)}
if (FTree[GrandDad] .hnLeftlnx = Dad) then begin
Uncle := FTree[GrandDad].hnRightlnx;
FTree[GrandDad].hnRightlnx := aNodelnx;
end
else begin
Uncle := FTree[GrandDad].hnLeftlnx;
FTree[GrandDad].hnLeftlnx := aNodelnx;
end;
if (FTree[Dad] .hnLeftlnx = aNodelnx) then FTree[Dad].hnLeftlnx : = Uncle
else
FTree[Dad].hnRightlnx := Uncle;
FTree[Uncle].hnParentlnx := Dad;
FTree[aNodelnx].hnParentlnx :=GrandDad; {возобновить цикл с узла-деда} aNodelnx :=GrandDad;
end;
until (aNodelnx = 0);
end;

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

Листинг 11.20. Базовый алгоритм восстановления скошенного дерева

procedure TDSplayDecompress(aInStream, aOutStream : TStream); var
Signature : longint;
Size : longint;
STree : TSplayTree;
BitStrm : TtdlnputBitStream;
begin
{выполнить проверку того, что входной поток является корректно закодированным с использованием скошенного дерева} alnStream.Seek(0, soFromBeginning);
alnStream.ReadBuffer(Signature, sizeof(Signature));
if (Signature <>
TDSplayHeader) then
raise EtdSplayException.Create(FmtLoadStr(tdeSplyBadEncodedStrm, [UnitName, 1TDSplayDecompress1])) ; alnStream.ReadBuffer(Size, sizeof(longint)); {при отсутствии данных для восстановления выйти из подпрограммы} if (Size = 0) then
Exit;

{подготовиться к восстановлению} STree := nil; BitStrm := nils-try

{создать поток битов}
BitStrm := TtdlnputBitStream.Create(alnStream);
BitStrm.Name := 'Splay compressed stream1;
{создать скошенное дерево] STree : = TSplayTree.Create;
{восстановить символы входного потока с использованием скошенного дерева] DoSplayDecompression(BitStrm, aOutStream, STree, Size);
finally BitStrm.Free;
STree.Free;
end;
end;

В процессе восстановления потока вначале за счет проверки сигнатуры выполняется проверка того, что поток является сжатым с использованием скошенного дерева. Затем мы считываем размер несжатых данных и осуществляем выход из подпрограммы, если он равен нулю.

При наличии данных для восстановления мы создаем входной поток битов, который будет содержать входной поток и скошенное дерево. Затем для выполнения реального декодирования вызывается метод DoSplayDecompression (см. листинг 11.21).

Листинг 11.21. Цикл восстановления скошенного дерева

procedure DoSplayDecompression (aBitStream : TtdlnputBitStream;
aOutStream : TStream;
aTree : TSplayTree;
aSize : longint);
var
CharCount : longint;
Ch : byte;
Buffer : PByteArray;
BufEnd : integer;
begin
GetMem(Buffer, SplayBufferSize); try
{предварительная установка значений переменных цикла] BufEnd := 0; CharCount := 0;

{повторять цикл до тех пор, пока не будут восстановлены все символы] while (CharCount < aSize) do begin {считать следующий байт]

BufferА[BufEnd] := aTree.DecodeByte(aBitStream);
inc(BufEnd) ; inc(CharCount) ;
{записать буфер в случае его заполнения] if (BufEnd = SplayBufferSize) then begin
aOutStream.WriteBuffer(BufferA, SplayBufferSize);
BufEnd := 0;
end;
end;

{записать любые оставшиеся в буфере данные} if (BufEndo 0) then aOutStream.WriteBuffer(BuffегЛ, BufEnd); finally

FreeMem(Buffer, SplayBufferSize);
ends-end;

Как и в цикле декодирования дерева Хаффмана, буфер заполняется декодированными байтами с последующей их записью в выходной поток. Реальное декодирование и запись выполняется методом DecodeByte класса скошенного дерева.

Листинг 11.22. Метод TSplayTree. DecodeByte

function TSplayTree.DecodeByte(aBitStream : TtdlnputBitStream) : byte;
var
Nodelnx : integers-begin
{переместиться вниз по дереву в соответствии с битами потока битов, начиная с корневого узла} Nodelnx := 0;
while Nodelnx < 255 do begin if not aBitStream.ReadBit then
Nodelnx := FTree[Nodelnx].hnLeftlnx else
Nodelnx := FTree[Nodelnx].hnRightlnx;
end;
{вычислить байт, исходя из значения индекса конечного узла) Result := Nodelnx - 255; {выполнить скос узла} stSplay(Nodelnx) ;
end;

Этот метод всего лишь выполняет перемещение вниз по дереву, считывая биты из входного потока битов и осуществляя перемещение по левой или правой связи, в зависимости от того, является ли текущий бит нулевым или единичным. И, наконец, достигнутый узел листа скашивается по направлению к корневому узлу с целью повторения того, что произошло во время сжатия. Одинаковое выполнение скоса во время сжатия и восстановления гарантирует правильность декодирования данных.

Полный код реализации алгоритма сжатия с использованием скошенного дерева можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSplyQn.pas.

Кодирование Хаффмана || Оглавление || Сжатие с использованием словаря


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Август
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс