Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
Обработка начинается с известного состояния дерева. Можно было бы определить дерево, отражающее частоту употребления букв английского алфавита или какое либо иное распределение символов, но на практике значительно проще создать идеально сбалансированное дерево. В этом случае каждый узел имеет три "указателя", которые в действительности являются всего лишь индексами других узлов в массиве, и мы определяем его таким же образом, как делали при работе с сортирующим деревом: дочерние узлы узла с индексом 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;
end;
При сжатии символа мы находим его узел в дереве. Затем мы выполняем переходы вверх по дереву, сохраняя соответствующие биты в стеке (левой связи соответствует нулевой бит, а правой - единичный). По достижении корневого узла можно вытолкнуть биты из стека. Они определят код символа (в коде, приведенном в листинге 11.19, в качестве стека используется короткая строка).
Затем выполняется скос родительского узла по направлению к корневому узлу. Мы не выполняем скос к корню самого узла символа ввиду того, что требуется сохранить размещение символов в узлах листьев. В противном случае было бы совершенно исключено, чтобы код одного символа становился началом кода следующего. Скос родительского узла повлечет "перетаскивание" вместе с ним и дочернего узла. В результате чаще используемые символы окажутся ближе к верхушке дерева.
Листинг 11.19. Методы EncodeByte и stSplay
procedure TSplayTree.EncodeByte(aBitStream : TtdOutputBitStream;
aValue : byte)/
var
NodeInx : integer;
ParentInx : integer;
RevCodeStr : ShortString;
BitString : TtdBitString;
begin
{начиная с узла aValue, сохранить на каждом шаге (0) бит при перемещении вверх по дереву по левой связи и (1) бит при перемещении по правой связи}
RevCodeStr := 1 ';
NodeInx := aValue + 255;
while (NodeInx <> 0) do
begin
ParentInx := FTree[NodeInx].hnParentInx;
inc(RevCodeStr[0]);
if (FTree[ParentInx].hnLeftInx = NodeInx) then
RevCodeStr[length(RevCodeStr)] := f0' else
RevCodeStr[length(RevCodeStr)] := ' 11;
NodeInx := ParentInx;
end;
{преобразовать строковый код в строку битов}
stConvertCodeStr(RevCodeStr, BitString);
{записать строку битов в поток битов}
aBitStream.WriteBits(BitString);
{выполнить скос узла}
stSplay(aValue + 255);
end;
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(aNodeInx : integer);
var
Dad : integer;
GrandDad : integer;
Uncle : integer;
begin
{выполнить скос узла}
repeat
{извлечь родительский узел данного узла}
Dad := FTree[aNodeInx].hnParentInx;
{если родительский узел является корневым, задача выполнена}
if (Dad= 0) then
aNodeInx := 0
{в противном случае необходимо выполнить поворот узла на 90 градусов с целью его перемещения вверх по дереву}
else begin
{извлечь родительский узел родительского узла}
GrandDad := FTree[Dad].hnParentInx;
{выполнить поворот на 90 градусов (т.е. поменять мечтами узел и его узел-дядю)}
if (FTree[GrandDad].hnLeftInx = Dad) then begin
Uncle := FTree[GrandDad].hnRightInx;
FTree[GrandDad].hnRightInx := aNodeInx;
end
else begin
Uncle := FTree[GrandDad].hnLeftInx;
FTree[GrandDad].hnLeftInx := aNodeInx;
end;
if (FTree[Dad].hnLeftInx = aNodeInx) then
FTree[Dad].hnLeftInx := Uncle
else
FTree[Dad].hnRightInx := Uncle;
FTree[Uncle].hnParentInx := Dad;
FTree[aNodeInx].hnParentInx :=GrandDad;
{возобновить цикл с узла-деда}
aNodeInx :=GrandDad;
end;
until (aNodeInx = 0);
end;
При восстановлении мы устанавливаем дерево в исходную конфигурацию, как это делалось на этапе сжатия. Затем мы по одному выбираем биты из потока битов и выполняем обычное перемещение вниз по дереву. По достижении листа, содержащего символ (который мы выводим в качестве восстановленных данных), мы будем выполнять скос родительского узла данного узла к корню дерева. При условии, что обновление дерева выполняется одинаково и во время сжатия, и во время восстановления, алгоритм декодирования может поддерживать дерево в том же состоянии, что и на соответствующем этапе выполнения алгоритма кодирования.
Листинг 11.20. Базовый алгоритм восстановления скошенного дерева
procedure TDSplayDecompress(aInStream, aOutStream : TStream);
var
Signature : longint;
Size : longint;
STree : TSplayTree;
BitStrm : TtdInputBitStream;
begin
{выполнить проверку того, что входной поток является корректно закодированным с использованием скошенного дерева}
aInStream.Seek(0, soFromBeginning);
aInStream.ReadBuffer(Signature, sizeof(Signature));
if (Signature <> TDSplayHeader) then
raise EtdSplayException.Create(FmtLoadStr(tdeSplyBadEncodedStrm,
[UnitName, 'TDSplayDecompress']));
aInStream.ReadBuffer(Size, sizeof(longint));
{при отсутствии данных для восстановления выйти из подпрограммы}
if (Size = 0) then
Exit;
{подготовиться к восстановлению}
STree := nil;
BitStrm := nil;
try
{создать поток битов}
BitStrm := TtdInputBitStream.Create(aInStream);
BitStrm.Name := 'Splay compressed stream';
{создать скошенное дерево}
STree := TSplayTree.Create;
{восстановить символы входного потока с использованием скошенного дерева}
DoSplayDecompression(BitStrm, aOutStream, STree, Size);
finally
BitStrm.Free;
STree.Free;
end;
end;
В процессе восстановления потока вначале за счет проверки сигнатуры выполняется проверка того, что поток является сжатым с использованием скошенного дерева. Затем мы считываем размер несжатых данных и осуществляем выход из подпрограммы, если он равен нулю.
При наличии данных для восстановления мы создаем входной поток битов, который будет содержать входной поток и скошенное дерево. Затем для выполнения реального декодирования вызывается метод DoSplayDecompression (см. листинг 11.21).
Листинг 11.21. Цикл восстановления скошенного дерева
procedure DoSplayDecompression(aBitStream : TtdInputBitStream;
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(Buffer^,SplayBufferSize);
BufEnd := 0;
end;
end;
{записать любые оставшиеся в буфере данные}
if (BufEnd <> 0) then
aOutStream.WriteBuffer(Buffer^, BufEnd);
finally
FreeMem(Buffer, SplayBufferSize);
end;
end;
Как и в цикле декодирования дерева Хаффмана, буфер заполняется декодированными байтами с последующей их записью в выходной поток. Реальное декодирование и запись выполняется методом DecodeByte класса скошенного дерева.
Листинг 11.22. Метод TSplayTree.DecodeByte
function TSplayTree.DecodeByte(aBitStream : TtdInputBitStream): byte;
var
NodeInx : integer;
begin
{переместиться вниз по дереву в соответствии с битами потока битов, начиная с корневого узла}
NodeInx := 0;
while NodeInx < 255 do
begin
if not aBitStream.ReadBit then
NodeInx := FTree[NodeInx].hnLeftInx else
NodeInx := FTree[NodeInx].hnRightInx;
end;
{вычислить байт, исходя из значения индекса конечного узла}
Result := NodeInx - 255;
{выполнить скос узла}
stSplay(NodeInx);
end;
Этот метод всего лишь выполняет перемещение вниз по дереву, считывая биты из входного потока битов и осуществляя перемещение по левой или правой связи, в зависимости от того, является ли текущий бит нулевым или единичным. И, наконец, достигнутый узел листа скашивается по направлению к корневому узлу с целью повторения того, что произошло во время сжатия. Одинаковое выполнение скоса во время сжатия и восстановления гарантирует правильность декодирования данных.
Полный код реализации алгоритма сжатия с использованием скошенного дерева можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSplyCm.pas.
