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

Особенности кодирования литеральных символов и пар расстояние/длина

Особенности кодирования литеральных символов и пар расстояние/длина

В предыдущих разделах ничего не было сказано о небольшом нюансе реализации алгоритма: как в процессе считывания сжатых данных отличить литеральный символ от кода расстояние/длина? В конце концов, не существует никакого принципиального различия между литеральным символом и первым байтом кода пары значений расстояние/длина. Одно возможное решение - вывод одиночного бита флага перед литеральным символом или кодом расстояние/длина. Если бит флага является нулевым, следующий считываемый код будет литеральным символом. Если флаг является единичным, следующий считываемый код будет парой расстояние/длина. Однако применение этого метода привело бы к необходимости вывода одиночных битов, сводя на нет преимущество использования одних только байтов.

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

Оглавление книги