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

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

Теперь рассмотрим, как выполняется кодирование пары значений расстояние/ длина. До сих пор мы не обращали на это внимание, однако целесообразно сжимать их как можно больше. Если скользящее окно охватывает последние 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, что будет достигаться за счет простого добавления единицы.