{сбросить входной поток в исходное состояние}
aInStream.Position := 0;
{считать первый блок из входного потока}
BytesRead := aInStream.Read(Buffer^, SplayBufferSize);
while (BytesRead <> 0) do
begin
{записать строку битов для каждого символа в блоке}
for i := 0 to pred(BytesRead) do aTree.EncodeByte(aBitStream, Buffer^[i]);
{считать следующий блок из входного потока}
BytesRead := aInStream.Read(Buffer^, SplayBufferSize);
end;
finally
FreeMem(Buffer, SplayBufferSize);
end;
end;
Фактически эта подпрограмма представляется собой подпрограмму выполнения вложенного цикла. Во внешнем цикле выполняется поблочное считывание входного потока, а во внутреннем (через вызов метода EncodeByte скошенного дерева) -кодирование каждого байта текущего блока и запись результирующего кода в выходной поток битов.
Теперь пора рассмотреть внутренний класс TSplayTree, который выполняет основную часть работы по реализации алгоритма сжатия с использованием скошенного дерева. Код интерфейса этого класса показан в листинге 11.17.
Листинг 11.17. Класс сжатия с использованием скошенного дерева
type
PSplayNode = ^TSplayNode;
TSplayNode = packed record
hnParentInx: longint;
hnLeftInx : longint;
hnRightInx : longint;
hnIndex : longint;
end;
PSplayNodeArray = ^TSplayNodeArray;
TSplayNodeArray = array [0..510] of TSplayNode;
type
TSplayTree = class private
FTree : TSplayNodeArray;
FRoot : integer;
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 : TtdInputBitStream): byte;
end;
Хотя можно было бы воспользоваться ориентированным на узлы деревом, как это делалось в главе 8, поскольку нам известно количество символов в используемом алфавите (в общем случае используется алфавит, содержащий 256 символов), проще отдать предпочтение применению ориентированной на массивы системе, подобной структуре данных типа сортирующего дерева и дерева Хаффмана. Еще один аргумент в пользу перехода на использование других структур данных состоит в том, что в случае применения неадаптивных методов сжатия можно было строить таблицу кодов, так как они были статическими. При использовании сжатия с применением скошенного дерева битовый код символа зависит от состояния скошенного дерева и момента времени кодирования символа. В этом случае мы больше не можем использовать статическую таблицу. Следовательно, одно из выдвигаемых требований - возможность быстрого и эффективного поиска символа в дереве (предпочтительно при помощи алгоритма типа O(1) - мы не хотим его искать). Как только символ и его узел листа определены, можно легко выполнить обход вверх по дереву до корневого узла с целью вычисления кода символа (вообще говоря, мы получим битовый код с обратным порядком следования битов, но с помощью стека его легко можно изменить на противоположный).
Обработка начинается с известного состояния дерева. Можно было бы определить дерево, отражающее частоту употребления букв английского алфавита или какое либо иное распределение символов, но на практике значительно проще создать идеально сбалансированное дерево. В этом случае каждый узел имеет три 'указателя', которые в действительности являются всего лишь индексами других узлов в массиве, и мы определяем его таким же образом, как делали при работе с сортирующим деревом: дочерние узлы узла с индексом n располагаются в позициях 2n + 1 и 2n + 2, а его родительский узел - в позиции (n - 1)/2. Поскольку в действительности узлы не будут перемещаться в массив (мы собираемся манипулировать только индексами), позиции листьев всегда будут известны. Они всегда будут занимать одни и те же позиции в массиве: #0 всегда будет находиться в позиции с индексом 255, #1 - в позиции с индексом 256 и т.д. Код метода, выполняющего инициализацию дерева, показан в листинге 11.18. Этот метод вызывается из конструктора Create.
Листинг 11.18. Метод stInitialize
procedure TSplayTree.stInitialize;
var
i : integer;
begin
{создать полностью сбалансированное дерево; корневой узел будет соответствовать нулевому элементу; родительский узел узла n будет располагаться в позиции (n-1) /2, а его дочерние узлы - в позициях 2n+1 и 2n+2}
FillChar(FTree, sizeof(FTree), 0);
for i := 0 to 254 do
begin
FTree[i].hnLeftInx := (2 * i) + 1;
FTree[i].hnRightInx := (2 * i) + 2;
end;
for i := 1 to 510 do
FTree[i].hnParentInx := (i - 1) div 2;
end;
constructor TSplayTree.Create;
begin
inherited Create;
stInitialize;
