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

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

FStart : PAnsiChar;{начало скользящего окна}

FStartOffset : longint;{смещение потока для FStart}

FStream : TStream;{базовый поток}

protected

procedure swAdvanceAfterAdd(aCount : integer);

procedure swReadFromStream;

procedure swSetCapacity(aValue : longint);

procedure swWriteToStream(aFinalBlock : boolean);

public

constructor Create(aStream : TStream;

aCompressing : boolean);

destructor Destroy; override;

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

procedure Clear;

{методы, используемые во время сжатия}

procedure Advance(aCount : integer);

function Compare(aOffset : longint;

var aDistance : integer): integer;

procedure GetNextSignature(var aMS : TtdLZSignature;

varaOffset : longint);

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

procedure AddChar(aCh : AnsiChar);

procedureAddCode(aDistance : integer;

aLength : integer);

property Name : TtdNameString read FName write FName;

end;

constructor TtdLZSlidingWindow.Create(aStream : TStream;

aCompressing : boolean);

begin

inherited Create;

{сохранить параметры}

FCompressing := aCompressing;

FStream := aStream;

{установить размер скользящего окна: согласно принятого определения размер скользящего окна равен 8192 байтам плюс 10 байтов для упреждающего просмотра}

swSetCapacity(tdcLZSlidingWindowSize + tdcLZLookAheadSize);

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

Clear;

if aCompressing then

swReadFromStream;

end;

destructor TtdLZSlidingWindow.Destroy;

begin

if Assigned(FBuffer) then begin

{завершить запись в выходной поток, если выполняется сжатие}

if not FCompressing then

swWriteToStream(true);

{освободить буфер}

FreeMem(FBuffer, FBufferEnd - FBuffer);

end;

inherited Destroy;

end;

procedure TtdLZSlidingWindow.AddChar(aCh : AnsiChar);

begin

{добавить символ в буфер}

FCurrent^ :=aCh;

{сместить скользящее окно на один символ}

swAdvanceAfterAdd(1);

end;

procedure TtdLZSlidingWindow.AddCode(aDistance : integer;

aLength : integer);

var

FromChar : PAnsiChar;

ToChar : PAnsiChar;

i : integer;

begin

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

FromChar := FCurrent - aDistance;

ToChar := FCurrent;

for i := 1 to aLength do

begin

ToChar^ := FromChar^;

inc(FromChar);

inc(ToChar);

end;

{сместить начало скользящего окна}

swAdvanceAfterAdd(aLength);

end;

procedure TtdLZSlidingWindow.swAdvanceAfterAdd(aCount : integer);

begin

{при необходимости сместить начало скользящего окна}

if ( (FCurrent - FStart) >= tdcLZSlidingWindowSize) then begin

inc(FStart, aCount);

inc(FStartOffset, aCount);

end;

{сместить текущий указатель}

inc(FCurrent, aCount);

{проверить смещение в зону переполнения}

if (FStart >= FMidPoint) then begin

{записать дополнительные данные в поток (от позиции FBuffer до позиции FStart)}

swWriteToStream(false);

{переместить текущие данные обратно в начало буфера}

Move(FStart^, FBuffer^, FCurrent - FStart );

{сбросить различные указатели}

dec(FCurrent, FStart - FBuffer);

FStart := FBuffer;

end;

end;

procedure TtdLZSlidingWindow.swSetCapacity(aValue : longint);

var

NewQueue : PAnsiChar;

begin

{округлить запрошенный объем до ближайшего значения, кратного 64 байтам}

aValue := (aValue + 63) and $7FFFFFC0;

{распределить новый буфер}

GetMem(NewQueue, aValue * 2);

{уничтожить старый буфер}

if ( FBuffer <> nil ) then

FreeMem(FBuffer, FBufferEnd - FBuffer);

{установить начальный/конечный и другие указатели}

FBuffer := NewQueue;

FStart := NewQueue;

FCurrent := NewQueue;

FLookAheadEnd := NewQueue;

FBufferEnd := NewQueue + (aValue * 2);

FMidPoint := NewQueue + aValue;

end;

procedure TtdLZSlidingWindow.swWriteToStream(aFinalBlock : boolean);

var

BytesToWrite : longint;

begin

{записать данные перед текущим скользящим окном}

if aFinalBlock then

BytesToWrite := FCurrent - Fbuffer else

BytesToWrite := FStart - FBuffer;

FStream.WriteBuffer(FBuffer^, BytesToWrite);

end;

Метод AddChar добавляет одиночный литеральный символ в скользящее окно и сдвигает это окно вперед на один байт. Внутренний метод swAdvanceAfterAdd выполняет реальный сдвиг и после сдвига окна проверяет, может ли еще один блок быть записан в выходной поток. Метод AddCode добавляет пару расстояние/длина в скользящее окно, по одному копируя символы из уже декодированной части скользящего окна в текущую позицию. Затем скользящее окно сдвигается вперед.

Теперь достаточно легко создать код восстановления. (Создавать код восстановления раньше кода сжатия кажется несколько неестественным, но в действительности формат сжатых данных настолько определен, что это можно сделать. Кроме того, это проще!) Мы реализуем основной цикл в виде машины состояний с тремя состояниями: считывание и обработка байта флага, считывание и обработка символа и, наконец, считывание и обработка кода расстояния/длины. Код показан в листинге 11.24. Обратите внимание, что определение момента завершения восстановления осуществляется по количеству байтов в несжатом потоке, записанному программой сжатия в начало сжатого потока.

После проверки того, что входной поток является закодированным с применением алгоритма LZ77, программа считывает количество несжатых данных. Затем осуществляется вход в простую машину состояний, состояния которой определяются байтом флага, считываемого из входного потока. Если текущее состояние -dsGetFlagByte, программа считывает из входного потока следующий байт флага. Если состояние - dsGetChar, программа считывает из входного потока литеральный символ и добавляет его в скользящее окно. В противном случае состоянием будет dsGetDistLen, и программа считывает из входного потока пару расстояние/ длина и добавляет ее в скользящее окно. Этот процесс продолжается до тех пор, пока не будут восстановлены все данные входного потока.

Листинг 11.24. Основной код программы сжатия, использующей алгоритм LZ77

procedure TDLZDecompress(aInStream, aOutStream : TStream);

type

TDecodeState = (dsGetFlagByte, dsGetChar, dsGetDistLen);

var

SlideWin : TtdLZSlidingWindow;

BytesUnpacked : longint;

TotalSize : longint;

LongValue : longint;

DecodeState : TDecodeState;

FlagByte : byte;

FlagMask : byte;

NextChar : AnsiChar;

NextDistLen : longint;

CodeCount : integer;

Len : integer;

begin

SlideWin := TtdLZSlidingWindow.Create(aOutStream, false);

try

SlideWin.Name := 'LZ77 Decompress sliding window';

{считать из потока заголовок: символы 'TDLZ', за которыми следует размер входного потока}

aInStream.ReadBuffer(LongValue, sizeof(LongValue));

if (LongValue <> TDLZHeader) then

RaiseError(tdeLZBadEncodedStream, 'TDLZDecompress');

aInStream.ReadBuffer(TotalSize, sizeof(TotalSize));

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

BytesUnpacked := 0;

NextDistLen := 0;

DecodeState := dsGetFlagByte;

CodeCount := 0;

FlagMask := 1;

{до тех nop, пока остаются байты для восстановления...}

while (BytesUnpacked < TotalSize) do

begin

{считывать следующий элемент в данном состоянии декодирования}

case DecodeState of

dsGetFlagByte : begin

aInStream.ReadBuffer(FlagByte, 1);

CodeCount := 0;

FlagMask := 1;

end;

dsGetChar : begin

aInStream.ReadBuffer(NextChar, 1);

SlideWin.AddChar(NextChar);

inc(BytesUnpacked);

end;

dsGetDistLen : begin

aInStream.ReadBuffer(NextDistLen, 2);

Len := (NextDistLen and tdcLZLengthMask) + 3;

SlideWin.AddCode( (NextDistLen shr tdcLZDistanceShift) + 1, Len);

inc(BytesUnpacked, Len);

end;

end;

{вычислить следующее состояние декодирования}

inc(CodeCount);

if (CodeCount > 8) then

DecodeState := dsGetFlagByte else begin

if ((FlagByte and FlagMask) = 0) then

DecodeState := dsGetChar

else

DecodeState := dsGetDistLen;

FlagMask := FlagMask shl 1;

end;

end;

finally

SlideWin.Free;

end;

{try.. finally}

end;

Сжатие LZ77

Теперь пора рассмотреть реализацию сжатия. При этом очень быстро мы сталкиваемся со следующей проблемой: поиском наиболее длинного соответствия между строкой в текущей позиции и предшествующими 8192 байтами. От одного возможного метода - поиска во всем буфере - придется полностью отказаться из-за его слишком низкой эффективности.

В своей первоначальной работе Зив и Лемпель не предложили почти никаких решений. Кое-кто использует дерево бинарного поиска, построенное поверх скользящего окна, для хранения максимальных встречавшихся совпадающих строк (примером может служить реализация, созданная Марком Нельсоном (Mark Nelson) [15]). Однако применение этого метода приводит к возникновению проблем, связанных с тем, что нужно беспокоиться о балансировке дерева и об избавлении от строк, которые должны быть удалены из скользящего окна. Поэтому мы воспользуемся советом, приведенным в онлайновом документе Deflate Compressed

Data Format Specification (Спецификация формата данных, сжатых методом Deflate) (RFC 1951) и применим хеш-таблицу.

Алгоритм выглядит следующим образом: мы просматриваем три символа в текущей позиции - будем называть их сигнатурой (signature). Сигнатура хешируется с применением одного из методов, а затем хеш-значение используется для доступа к элементу в хеш-таблице, использующему связывание. Цепочки или связные списки в каждом элементе хеш-таблицы будут состоять из последовательностей элементов, каждый из которых состоит из трехсимвольных сигнатур и значения смещения сигнатуры во входном потоке.

Итак, мы получаем сигнатуру текущей позиции и хешируем ее в связный список, представляющий собой - одну из цепочек в хеш-таблице. Затем мы просматриваем связный список и сравниваем хранящуюся в нем сигнатуру каждого элемента с имеющимися сигнатурами. При обнаружении совпадающей сигнатуры мы переходим в скользящее окно, используя значение смещения элемента, а затем сравниваем символы в скользящем окне с символами в текущей позиции. Мы повторяем этот процесс для каждого элемента в связном списке, совпадающего с данной сигнатурой, и запоминаем наиболее длинное найденное соответствие.