Бакнелл Джулиан М.
Шрифт:
procedure htSaveNode(aBitStream : TtdOutputBitStream;
aNode : integer);
public
constructor Create;
procedure CalcCharDistribution(aStream : TStream);
procedure CalcCodes(var aCodes : THuffmanCodes);
function DecodeNextByte(aBit St ream : TtdInputBitStream): byte;
procedure LoadFromBitStream(aBitStream : TtdInputBitStream);
function RootIsLeaf : boolean;
procedure SaveToBitStream(aBitStream : TtdOutputBitStream);
property Root : integer read FRoot;
end;
Предположим, что дерево содержит только два типа узлов: внутренние, имеющие ровно по два дочерних узла, и листья, не имеющие узлов (иначе говоря, не существует узлов, имеющих только один дочерний узел, - именно такой вид имеет префиксное дерево). Сколько внутренних узлов имеет это дерево, если оно содержит n листьев? Лемма утверждает, что такое дерево содержит ровно n - 1 внутренних узлов. Это утверждение можно доказать методом индукции. Когда n = 1, лемма явно выполняется, поскольку дерево содержит только корневой узел.
Теперь предположим, что лемма справедлива для всех i < n, где n < 1, и рассмотрим случай, когда i = n. В этом случае дерево должно содержать, по меньшей мере, один внутренний узел - корневой. Этот корневой узел имеет два дочерних дерева: левое и правое. Если левое дочернее дерево имеет x листьев, то, согласно сделанному нами допущению, оно должно содержать x - 1 внутренних узлов, поскольку x < n. Аналогично, согласно сделанному допущению, если правое дочернее дерево имеет y листьев, оно должно содержать y - 1 внутренних узлов. Все дерево содержит n листьев, причем это число должно быть равно X + Y (вспомните, что корневой узел является внутренним). Следовательно, количество внутренних узлов равно (x-1) + (y-1) + 1, что составляет в точности n-1.
Чем же эта лемма может нам помочь? В префиксном дереве все символы должны храниться в листьях. В противном случае было бы невозможно получить однозначные коды. Следовательно, независимо от его внешнего вида, префиксное дерево, подобное дереву Хаффмана, будет содержать не более 511 узлов: не более 256 листьев и не более 255 внутренних узлов. Следовательно, мы должны быть в состоянии реализовать дерево Хаффмана (по крайней мере, обеспечивающее кодирование значений байтов) в виде 511-элементного массива.
Структура узла включает в себя поле счетчика (содержащее значение общего количества появлений символов для самого узла и всех его дочерних узлов), индексы левого и правого дочерних узлов и, наконец, поле, содержащее индекс самого этого узла (эта информация облегчит построение дерева Хаффмана).
Причина выбора типов кода Хаффмана (THuffmanCodeStr и THuffmanCodes) станет понятной после рассмотрения генерации кодов для каждого из символов.
Конструктор Create класса дерева Хаффмана всего лишь выполняет инициализацию внутреннего массива дерева.
Листинг 11.8. Конструирование объекта дерева Хаффмана
constructor THuffmanTree.Create;
var
i : integer;
begin
inherited Create;
FillChar(FTree, sizeof(FTree), 0);
for i := 0 to 510 do
FTree[i].hnIndex := i;
end;
Поскольку конструктор не распределяет никакой памяти, и никакое распределение памяти не выполняется ни в каком другом объекте класса, явному деструктору нечего делать. Поэтому по умолчанию класс использует метод TObject.Destroy.
Первым методом, вызываемым для дерева Хаффмана в подпрограмме сжатия, был метод CalcCharDistribution. Это метод считывает входной поток, вычисляет количество появлений каждого символа, а затем строит дерево.
Листинг 11.9. Вычисление количеств появлений символов
procedure THuffmanTree.CalcCharDistribution(aStream : TStream);
var
i : integer;
Buffer : PByteArray;
BytesRead : integer;
begin
{считывать все байты с поддержанием счетчиков появлений для каждого значения байта, начиная с начала потока}
aStream.Position := 0;
GetMem(Buffer, HuffmanBufferSize);
try
BytesRead := aStream.Read(Buffer^, HuffmanBufferSize);
while (BytesRead <> 0) do
begin
for i := pred(BytesRead) downto 0 do
inc(FTree[Buffer^[i]].hnCount);
BytesRead := aStream.Read(Buffer^, HuffmanBufferSize);
end;
finally
FreeMem(Buffer, HuffmanBufferSize);
end;
{построить дерево}
htBuild;
end;
Как видно из листинга 11.9, большая часть кода метода вычисляет количества появлений символов и сохраняет эти значения в первых 256 узлах массива. Для повышения эффективности метод обеспечивает поблочное считывание входного потока (прежде чем выполнить цикл вычисления, он распределяет в куче большой блок памяти, а после вычисления освобождает его). И в завершение, в конце подпрограммы вызывается внутренний метод htBuild, выполняющий построение дерева.