Общий способ избавления от этого недостатка состоит в применении флага, состоящего из восьми битов, указывающих, чем должны быть следующие восемь кодов. При этом первый бит определяет, чем тип первого кода, следующего за байтом флага, второй бит - второго кода, и так далее для 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. Еще раз взгляните на пример предложения, сжатие которого было выполнено ранее. На одном из этапов описания алгоритма возникла следующая ситуация: