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

Кодирование с минимальной избыточностью - это метод кодирования байтов (или, более строго, символов), при котором чаще встречающиеся байты кодируются меньшим количеством битов, чем те, которые встречаются реже. Например, в тексте на английском языке буквы Е, m и А встречаются чаще, нежели буквы Q, X и Z. Поэтому, если бы удалось закодировать буквы Е, m и А меньшим количеством битов, чем 8 (как должно быть в соответствии со стандартом ASCII), а буквы Q, X и Z - большим, текст на английском языке удалось бы сохранить с использованием меньшего количества битов, чем при соблюдении стандарта ASCII.

При использовании сжатия с применением словаря данные разбиваются на большие фрагменты (называемые лексемами), чем символы. Затем применяется алгоритм кодирования лексем определенным минимальным количеством битов. Например, слова "the", "and" и "to" будут встречаться чаще, чем такие слова, как "electric", "ambiguous" и "irresistible", поэтому их нужно закодировать меньшим количеством битов, чем требовалось бы при кодировании в соответствии со стандартом ASCII.

Потоки битов

Прежде чем приступить к исследованию реальных алгоритмов сжатия, необходимо кратко рассмотреть задачу манипулирования битами. При использовании большинства алгоритмов сжатия, которые будут рассмотрены, сжатие данных выполняется с использованием переменного количества битов, независимо от того, рассматриваются ли данные в качестве последовательности символов или лексем. Нельзя считать, что байты всегда будут состоять из групп по 8 битов.

Нам потребуется выполнять две базовых операции: считывание отельного бита и запись отдельного бита. На основе этих операций можно было бы построить операции, выполняющие считывание и запись сразу нескольких битов. Поэтому мы разработаем и создадим поток битов (bit stream) - структуру данных, содержащую в себе набор битов. Понятно, что поток битов будет использовать еще одну структуру данных, в которой данные битов хранятся в виде последовательности байтов. Эта структура будет извлекать биты в соответствии с байтами в данных, на основе которых она построена. Поскольку мы используем Delphi, в качестве базовой структуры данных потока битов мы выберем объект TStream (или производный от него). В результате, например, мы смогли бы рассматривать поток памяти или поток файла как поток битов. Фактически, поскольку потоки битов будут использоваться только в качестве последовательных групп битов, мы создадим два различных типа: входной поток битов и выходной поток битов. Кроме того, можно избавиться от обычно используемого метода Seek, поскольку поиск в потоке битов мы выполнять не будем.

Код интерфейса классов TtdInputBitStream и TtdOutputBitStream приведен в листинге 11.1.

Листинг 11.1. Интерфейс классов потоков битов

type

TtdInputBitStream = class private

FAccum : byte;

FBufEnd : integer;

FBuffer : PAnsiChar;

FBufPos : integer;

FMask : byte;

FName : TtdNameString;

FStream : TStream;

protected

procedure ibsError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure ibsReadBuffer;

public

constructor Create(aStream : TStream);

destructor Destroy; override;

function ReadBit : boolean;

procedure ReadBits(var aBitString : TtdBitString; aBitCount : integer);

function ReadByte : byte;

property Name : TtdNameString read FName write FName;

end;

TtdOutputBitStream = class private

FAccum : byte;

FBuffer : PAnsiChar;

FBufPos : integer;

FMask : byte;

FName : TtdNameString;

FStream : TStream;

FStrmBroken : boolean;

protected

procedure obsError(aErrorCode : integer;

const aMethodName : TtdNameString);

procedure obsWriteBuffer;

public

constructor Create(aStream : TStream);

destructor Destroy; override;

procedure WriteBit(aBit : boolean);

procedure WriteBits(const aBitString : TtdBitString);

procedure WriteByte(aByte : byte);

property Name : TtdNameString read FName write FName;

end;

Оба конструктора Create требуют передачи им в качестве параметра уже созданного производного объекта TStream. Из этого потока байтов класс потока битов будет извлекать или сохранять отдельные байты. Код конструкторов Create и деструкторов Destroy этих классов приведен в листинге 11.2.

Листинг 11.2. Создание и уничтожение объектов потока битов

constructor TtdInputBitStream.Create(aStream : TStream);

begin

inherited Create;

FStream := aStream;

GetMem(FBuffer, StreamBufferSize);

end;

destructor TtdInputBitStream.Destroy;

begin

if (FBuffer <> nil) then

FreeMem(FBuffer, StreamBufferSize);

inherited Destroy;

end;

constructor TtdOutputBitStream.Create(aStream : TStream);

begin

inherited Create;

FStream := aStream;

GetMem(FBuffer, StreamBufferSize);

FMask := 1;

{подготовиться к записи первого бита}

end;

destructor TtdOutputBitStream.Destroy;

begin

if (FBuffer <> nil) then begin

{если значение Mask не равно 1, это означает присутствие в аккумуляторной переменной каких-то бит, которые требуется записать в буфер. Следует убедиться, что буфер записывается в базовый поток}

if not FStrmBroken then begin

if (FMasko 1) then begin

byte(FBuffer[FBufPos]) := FAccum;

inc(FBufPos);

end;

if ( FBuf Pos > 0 ) then

obsWriteBuffer;

end;