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

if (Signature <> TDHuffHeader) then

raise EtdHuffmanException.Create( FmtLoadStr(tdeHuffBadEncodedStrm,[UnitName, 'TDHuffmanDecompress']));

aInStream.ReadBuffer(Size, sizeof(longint));

{если данные для восстановления отсутствуют, осуществить выход из подпрограммы}

if (Size = 0) then

Exit;

{подготовиться к восстановлению}

HTree := nil;

BitStrm := nil;

try

{создать поток битов}

BitStrm := TtdInputBitStream.Create(aInStream);

BitStrm.Name := 'Huffman compressed stream';

{создать дерево Хаффмана}

HTree := THuffmanTree.Create;

{считать данные дерева из входного потока}

HTree.LoadFromBitStream(BitStrm);

{если корневой узел дерева Хаффмана является листом, исходный поток состоит только из повторений одного символа}

if HTree.RootIsLeaf then

WriteMultipleChars(aOutStream, AnsiChar(HTree.Root), Size) {в противном случае выполнить восстановление символов входного потока посредством использования дерева Хаффмана}

else

DoHuffmanDecompression(BitStrm, aOutStream, HTree, Size);

finally

BitStrm.Free;

HTree.Free;

end;

end;

Прежде всего, мы проверяем, начинается ли поток с корректной сигнатуры. Если нет, не имеет смысла продолжать процесс, поскольку поток явно содержит ошибки.

Затем выполняется считывание длины несжатых данных, и если она равна нулю, задача выполнена. В противном случае необходимо проделать определенную работу. В этом случае мы создаем входной поток битов, содержащий входной поток. Затем мы создаем объект дерева Хаффмана, который будет выполнять большую часть работы, и вынуждаем его выполнить собственное считывание из входного потока битов (вызывая для этого метод LoadFromBitStream). Если дерево Хаффмана представляет единственный символ, исходный поток восстанавливается в виде повторений этого символа. В противном случае мы вызываем подпрограмму DoHuffmanDecoonpression для выполнения восстановления данных. Код этой подпрограммы приведен в листинге 11.13.

Листинг 11.13. Подпрограмма DoHuffmanDecompression

procedure DoHuffmanDecompression( aBitStream : TtdInputBitStream;

aOutStream : TStream; aHTree : THuffmanTree; aSize : longint);

var

CharCount : longint;

Ch : byte;

Buffer : PByteArray;

BufEnd : integer;

begin

GetMem(Buffer, HuffmanBufferSize);

try

{предварительная установка переменных цикла}

BufEnd := 0;

CharCount := 0/

{повторять процесс до тех пор, пока не будут восстановлены все символы}

while (CharCount < aSize) do

begin

{считать следующий байт}

Ch := aHTree.DecodeNextByte (aBitStream);

Buffer^[BufEnd] :=Ch;

inc(BufEnd);

inc(CharCount);

{если буфер заполнен, необходимо выполнить его запись}

if (BufEnd = HuffmanBufferSize) then begin

aOutStream.WriteBuffer(Buffer^, HuffmanBufferSize);

BufEnd := 0;

end;

end;

{если в буфере остались какие-либо данные, необходимо выполнить его запись}

if (BufEnd <> 0) then

aOutStream.WriteBuffer(Buffer^, BufEnd);

finally

FreeMem(Buffer, HuffmanBufferSize);

end;

end;

По существу подпрограмма представляет собой цикл, внутри которого многократно выполняется декодирование байтов и заполнение буфера. Когда буфер заполняется, мы записываем его в выходной поток и начинаем заполнять его снова. Декодирование выполняется при помощи метода DecodeNextByte класса THuffmanTree.

Листинг 11.14. Метод DecodeNextByte

function THuffmanTree.DecodeNextByte(aBitStream : TtdInputBitStream): byte;

var

NodeInx : integer;

begin

NodeInx := FRoot;

while (NodeInx >= 256) do

begin

if not aBitStream.ReadBit then

NodeInx := FTree[NodeInx].hnLeftInx else

NodeInx := FTree[NodeInx].hnRightInx;

end;

Result := NodeInx;

end;

Этот метод крайне прост. Он просто начинает обработку с корневого узла дерева Хаффмана, а затем для каждого бита, считанного из входного потока битов, в зависимости от того, был ли он нулевым или единичным, выполняет переход по левой или правой связи. Как только подпрограмма достигает листа, она возвращает индекс достигнутого узла (его значение будет меньше или равно 255). Этот узел является декодированным байтом.

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

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

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

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

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

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