Между прочим, определение буфера ранее встречавшихся символов как "скользящего окна" означает, что при попытке найти возможное соответствие рассматриваются только n байт. Обычно n равно 4 или 8 Кб (используемый в программе PKZIP алгоритм Deflate (понижения порядка) может использовать скользящее окно размером до 32 Кб). При перемещении текущей позиции вперед скользящее окно перемещается вперед по уже просмотренным данным. Возникает вопрос, зачем это делается? Почему бы не использовать весь ранее просмотренный текст? Ответ на этот вопрос обусловлен общей структурой текста. В общем случае считываемый и записываемый текст подчиняются так называемому правилу локальности ссылок (locality of reference). Это означает, что, как правило, в текстовом файле более вероятно совпадение близко расположенных символов, а не расположенных вдали друг от друга. Например, в романе описываемые действующие лица и места протекания событий обычно группируются в главы или разделы глав. В то же время часто используемые слова и фразы типа "и", "в" и "он сказал" могут встречаться в любом месте романа.
Для других текстов, таких как учебные пособия, подобные этому, также характерна локальность ссылок. Поэтому согласно правилу локальности ссылок имеет смысл ограничить объем ранее встречавшегося текста, просматриваемого с целью установки соответствия между строками. Еще одна веская причина ограничения размера скользящего окна связана с необходимостью замедлить сжатие с увеличением объема просматриваемого текста.
Теперь рассмотрим, как выполняется кодирование пары значений расстояние/ длина. До сих пор мы не обращали на это внимание, однако целесообразно сжимать их как можно больше. Если скользящее окно охватывает последние 4 Кб текста, значение расстояния можно закодировать 12 битами (2(^12^) как раз и составляет 4 Кб). Если максимальную длину проверяемых и сопоставляемых строк ограничить 15 символами, это значение можно закодировать 4 битами, а пару расстояние/длина - двумя полными байтами. Можно было бы использовать также окно с размером равным 8 Кб и максимум семь сопоставляемых символов, и при этом длина кода по-прежнему не превышала бы 2 байтов. Сжатый поток можно рассматривать как поток байтов, а не как явно более сложный поток битов, который мы использовали при генерировании кодов минимальной длины. Кроме того, если длину кодов значений расстояние/длина ограничить 2 байтами, можно сжимать строки, содержащие, по меньшей мере, три символа и совпадающие с какими-то уже встречавшимися строками, при этом не обращать внимания на совпадения одного или двух символов, поскольку сжиматься они не будут.
Мы кратко описали суть алгоритма Зива и Лемпеля (Лемпеля-Зива), на который в настоящее время ссылаются как на алгоритм LZ77.
В предыдущих разделах ничего не было сказано о небольшом нюансе реализации алгоритма: как в процессе считывания сжатых данных отличить литеральный символ от кода расстояние/длина? В конце концов, не существует никакого принципиального различия между литеральным символом и первым байтом кода пары значений расстояние/длина. Одно возможное решение - вывод одиночного бита флага перед литеральным символом или кодом расстояние/длина. Если бит флага является нулевым, следующий считываемый код будет литеральным символом. Если флаг является единичным, следующий считываемый код будет парой расстояние/длина. Однако применение этого метода привело бы к необходимости вывода одиночных битов, сводя на нет преимущество использования одних только байтов.
Общий способ избавления от этого недостатка состоит в применении флага, состоящего из восьми битов, указывающих, чем должны быть следующие восемь кодов. При этом первый бит определяет, чем тип первого кода, следующего за байтом флага, второй бит - второго кода, и так далее для 8 битов и кодов. Затем будет выводиться следующий байт флага. Используя эту схему, можно записывать (и считывать) сжатый поток в виде последовательности байтов.
Аналогичная схема использовалась в программе EXPAND.EXE компании Microsoft, которая применялась в составе M;
DOS и Windows 3.1 (в современных программных продуктах компании Microsoft вместо нее применяются CAB-файлы). Возможно, читатели помнят, что часто файлы на дискетах DOS имели имена наподобие FILENAME *ЕХ_, и программа EXPAND.EXE должна была их распаковывать и подставлять последний символ в расширении восстановленного файла. В версии алгоритма LZ77, применявшейся компанией Microsoft, коды пар значений расстояние/длина всегда имели размер, равный 2 байтам. При этом 12 бит использовались для указания значения расстояния (в действительности в этой версии использовалась циклическая очередь байтов, и значение расстояния представляло собой величину смещения от начала очереди), а остальные 4 бита служили для определения значения длины.
После того, как мы ознакомились с теорией, пора подумать о реализации и сформулировать ряд правил. Мы будем считать, что размер кода пары расстояние/длина будет всегда равен 2 байтам - длине одного слова - причем старшие 13 бит будут использоваться для указания значения расстояния, а 3 младших бита - для определения значения длины. Поскольку для указания значения расстояния используются 13 бит, теоретически можно закодировать расстояния от 0 до 8191 байта. Следовательно, размер скользящего окна составит 8 Кб. Обратите внимание, что при определении расстояния мы никогда не будем использовать значение, равное 0 (в противном случае соответствие устанавливалось бы с текущей позицией). Таким образом, эти 13 бит будут интерпретироваться как значения от 1 до 8192, а не от 0 до 8191, что будет достигаться за счет простого добавления единицы.
Теперь рассмотрим значение длины. Теоретически, тремя битами можно закодировать значения только от 0 до 7. Однако вспомним, что в пары значений расстояние/длина будут преобразовываться только совпадающие строки, состоящие из трех и более символов. Поэтому за счет простого добавления 3 целесообразно интерпретировать 3 бита как значения длины от 3 до 10 байтов.
Следовательно, чтобы преобразовать значение расстояния и длины в значение слова, нужно было бы записать определение, подобное следующему:
Code := ((Distance-1) shl 3) + (Length-3);
А для восстановления значений расстояния и длины потребовалось бы использовать следующий код:
Length := (Code and $7) +3;
Distance := (Code shr 3)+ 1;
Прежде чем приступить к рассмотрению сжатия данных, реализуем алгоритм восстановления, поскольку его концепция проще для визуализации. В процессе восстановления мы считываем байт флага, а затем используем его для определения способа считывания из потока следующих восьми кодов. Если текущий бит в байте флага является нулевым, мы считываем из потока 1 байт и интерпретируем его как литеральный символ, который должен быть записан непосредственно в выходной поток. И напротив, если текущий бит является единичным, мы считываем из входного потока 2 байта и разбиваем это значение на значения расстояния и длины. Затем эти значения используются с текущим скользящим окном ранее декодированных данных для определения того, какой символ должен быть записан в выходной поток.
При каждом декодировании отдельного символа или набора от трех до 10 символов, их нужно не только записать в выходной поток, но и добавить в конец буфера скользящего окна и сдвинуть начало скользящего окна на соответствующее расстояние, чтобы его размер не превышал 8192 байтов. Естественно, нежелательно, чтобы приходилось восстанавливать буфер при каждом декодировании символа или строки символов - это занимало бы слишком много времени. На практике используется циклическая очередь - очередь фиксированного размера, начало и конец которой определяются индексами. Поскольку на этапе сжатия будет использоваться аналогичное скользящее окно (как именно, мы вскоре рассмотрим), целесообразно создать реализацию класса, которая могла бы использоваться в обоих процессах.
Прежде чем приступить к описанию методов восстановления, которые потребуются для этого класса, я хочу описать небольшой прием, используемый методом Deflate программы FKZIP. Еще раз взгляните на пример предложения, сжатие которого было выполнено ранее. На одном из этапов описания алгоритма возникла следующая ситуация:
-------+
a cat is | a cat is a cat
-------+^
и мы вычислили пару значений расстояние/длина <9,9>. Однако можно применить небольшую хитрость. Почему мы должны прекращать сопоставление на 9 символах? В действительности можно сопоставить значительно больше символов, выйдя за пределы правой границы скользящего окна и продолжая сопоставление с текущим символом и с символами, расположенными справа от него. Фактически, можно было бы установить соответствие 14 символов, получив при этом код <9,14>, в котором значение длины превышает значение расстояния. Все это замечательно и достаточно разумно, но что при этом происходит во время декодирования? В момент декодирования кода <9,14> скользящее окно выглядит следующим образом:
--------+
a cat is I
--------+ ^
Мы возвращаемся в скользящем окне на 9 символов назад и начинаем по одному копировать символы, пока не будет достигнут 14-й символ. В результате мы копируем символы, которые нам удалось определить в одной и той же операции.
После копирования девяти символов мы получаем
--------+
a cat is I a cat is
--------+ ^________^
__________от______до
где показаны позиции, от которой и до которой выполняется копирование. Как видите, копирование остальных пяти символов может быть выполнено вообще без возникновения каких-либо проблем. Следовательно, значение длины вполне может превышать значение расстояния (хотя приходится признать, что для копирования данных нельзя было просто воспользоваться процедурой Move).
Во время восстановления мы передадим класс скользящего окна выходному потоку, в который должны записываться данные. В результате, когда объект определяет, что активные данные в буфере требуется передвинуть обратно к началу, вначале он копирует в поток данные, которые должны замещаться в буфере. Для выполнения восстановления требуются два основных метода: добавление одиночного символа и преобразование пары расстояние/длина. Обратите внимание, что эти действия выполняются классом скользящего окна, поскольку обновление скользящего окна и перемещение вперед по данным должны выполняться в обоих случаях. Кроме того, класс - лучший агент выполнения преобразования значений расстояния и длины. Код реализации интерфейса класса, служебных процедур и вывода соответствующего кода приведен в листинге 11.23.
Листинг 11.23. Код, связанный с выводом, класса скользящего окна
type
TtdLZSlidingWindow = class private
FBuffer : PAnsiChar;{циклический буфер}
FBufferEnd : PAnsiChar;{конечная точка буфера}
FCompressing : boolean;{true=сжатию данных}
FCurrent : PAnsiChar;{текущий символ}
FLookAheadEnd : PAnsiChar;{конец упреждающего просмотра}
FMidPoint : PAnsiChar;{средняя точка буфера}
FName : TtdNameString;{имя скользящего окна}
FStart : PAnsiChar;{начало скользящего окна}
FStartOffset : longint;{смещение потока для FStart}
FStream : TStream;{базовый поток}
protected
procedure swAdvanceAfterAdd(aCount : integer);
procedure swReadFromStream;