11.02.2006

Архиватор LZH.

Введение.

В данном документе обсуждаются основные проблемы реализации алгоритма LZH на примере известного кода Haruhiko OKUMURA & Haruyasu YOSHIZAKI в виде класса Delphi (портирован Kenji RIKITAKE, Douglas Webb, Danny Heijl). Алгоритм относится к семейству LZ77 со словарем 4кб и адаптивным кодированием Хаффмана на выходе. Необходимо также отметить, что и алгоритм и архиватор на данный момент представляют ограниченную практическую ценность из-за наличия гораздо более быстрых и совершенных реализаций, однако может быть использован в учебных целях и приложениях с низкими требованиями к количеству оперативной памяти.

Реализация.

Интерфейс.

Интерфейс объекта-архиватора фактически сводится к 2м функциям архивирования и разархивирования соответственно. Обмен данными с входным и выходным потоками осуществляется при помощи Callback функций передаваемых в качестве аргументов. Также при разархивировании необходимо передавать размер реальных данных в архивном потоке, тк архиватор не поддерживает какого-либо заголовка архива (в архивированном потоке нет никакой служебной информации и нет символа-маркера для обозначения конца архивного потока). Также никаким образом не проверяется целостность архива.
...
PutBytesProc = procedure(var DTA; NBytes: WORD; var Bytes_Put: WORD) of object;
...
procedure TLZH.LZHPack(var Bytes_Written: LongInt; GetBytes: GetBytesProc; PutBytes: PutBytesProc);
procedure TLZH.LZHUnpack(TextSize: Longint; GetBytes: GetBytesProc; PutBytes: PutBytesProc);

Словарь LZ77.

Словарь выполнен в виде байтового массива text_buf объемом порядка 4кб+(максимальная длина строки) со скользящим указателем в нем. Указатель "зациклен" и по достижении конца словаря (4кб) он возвращяется в начало. Максимальная длина строки фиксирована и равна 60 - это значит, что при поиске совпадений словаре, максивальная длина этого совпадения ограничена этим значением. Минимальная длина совпадения - 3.
Примерный алгоритм следующий

• В текущей позиции словаря (если это не конец потока) есть всегда цепочка не менее 60 необработанных символов из входного потока, производится поиск наибольшего совпадения этой цепочке в словаре, который представляет собой окно до примерно 4кб обработанных символов входного потока, предшествующих данной цепочке. Приоритетны более длинные совпадения, близость к указателю словаря. Заперещенно сравнение первого необработанного символа с необработанным, однако следующие могут иметь такие сравнения (например, ... 0 0 0 0 0 0 ... - подчеркнутое обработано, жирный текущий - цепочка из одинаковых символов может быть закодирована в 2 этапа - первый символ и совпадение между цепочкой начиная с первого символа и цепочкой начиная со второго символа)
• Если находится совпадение в 3 и более символа, то на выход кодируется длина и расстояние от указателя словаря до совпадения, иначе на выход кодируется текущий символ.
• Указатель сдвигается на необходимое количество символов, производится обновление структур для поиска цепочек, вычитываются данные из входного потока, чтобы компенсировани закодированные символы
• Повтор всех пунктов до исчерпания входного потока и вычитанных в словарь данных.

Необходимость в словаре более 4кб обусловлена удобством сравнения строк, когда при сравнении в коце зацикленного массива, поидее надо переходить в начало, но этого можно и не делать, если хранить копию начала массива после его конца (но это требует и соответствующего заполнения словаря).
Procedure TLZH.LZHPack(VAR Bytes_Written:LongInt; GetBytes:GetBytesProc; PutBytes:PutBytesProc);
...
text_buf^[s] := ct;
IF (s < PRED(F)) THEN begin
    text_buf^[s + N] := ct; // мы делаем копию начала в область после конца
end;
...
Перед началом кодирования непосдедственно предшествует указателю цепочка из 60 пробелов (#32).

Поиск.

Поиск - важнейшая часть LZ алгоритмов. В данном случае для организации поиска используется механизм бинарных деревьев. Деревья организованы в виде массивов lson, dad, rson. Вот некоторые особенности организации.

• Во всех массивах элементом является номер символа в словаре text_buf.
  • lson[№ текущей цепочки] - цепочки меньшие текущей
  • dad[№ текущей цепочки] - предок текущей цепочки
  • rson[№ текущей цепочки] - цепочки большие или равные текущей (исходя из максивальной длины сравнения 60).
• Используется 256 деревьев для для ускорения поиска, за счет разделения цепочек по первому символу, т.е. в одном дереве все цепочки начинаются с одного и тогоже символа. Для определения в каком дереве искать в массиве rson присутствуют 256 дополнительных указателей на вершины деревьев.
• Деревья - структуры, требующие поддержания целостности, те при обработке каждого нового символа цепочка, с которой он начинается должна быть вставлена в дерево, а цепочка которая при этом начинает выходить за границу словаря (сдвиг окна) должна быть удалена. Массив dad нужен исключительно для удаления цепочек.
• В описываемой реализации деревья не сбалансированы, т.е. в "плохом" случае могут вырождаться в практически линейные структуры.
  

Кодирование.

Кодирование символов производится с использованием адаптивного алгоритма Хаффмана, кодирование расстояний от указателя - статическими кодами разной длины, заданными таблично (эти коды обеспечивают более компактное представление коротких дистанций). В набор символов, кодируемых адаптивно, входят не только 256 значений байта, но и 58 значений длин совпадений (длина кодируется спец. символом, длины 1, 2 не используются). Заметим, что подобный подход, в отличие от скажем блочно-адаптивного существенно зависит по скорости кодирования от избыточности данных, поскольку таблицы Хаффмана обновляются при кодировании каждого нового символа.

Основные проблемы.

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

1. Дерево очень дорого в смысле поддержания, из-за необходимости обновления его структуры при обработке каждого символа. Кроме того, дерево не позволяет осуществить оптимизацию кодирования в плане выбора совпадения на минимальной дистанции.
2. Адаптивное кодирование Хаффмана делает реализацию медленной на низкоизбыточных данных.
3. Чтение-запись из потоков осуществляются побайтно, что увеличивает количество обращений к потокам.
4. Словарь реально представляет окно из 4кб-60 символов, хотя декомпрессор и таблицы позволяют использовать ровно 4кб.

Возможные улучшения.

1. Дерево допустимо заменить на более простую структуру типа хэш. Такая структура обладает рядом достоинств
   • Обновление структуры очень быстро и сводится только к подсчету хэша для продолжения соответствующей хэш-цепочки (нет сравнений как в дереве).
   • Удаление отсутствует.
   • Потребление памяти меньше чем у дерева.
   • Проще и меньше код

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

2. Адаптивное кодирование Хаффмана используется как в кодере, так и в декодере, поэтому отказаться от него невозможно без потери совместимости. В тоже время, существенно улучшить кодер сложно.
3. Кэширование чтения/записи достаточно легко осуществить, выделив дополнительные объемы памяти (небольшие) под эти цели. При этом под сжатые данные логично выделить меньший объем, чем под оригинал. Интерфейс объекта подразумевает блочной обмен данными, хотя и не использует его, т.е. существенных изменений не потребуется.
4. Для использования словаря в 4 кб достаточно изменить способ хранения еще не обработанной цепочки - проще всего ее хранить вне окна словаря, также возможно изменение подхода к зацикленности словаря.

Реализация.

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

1. Произведена замена дерева на хэш. Выбран достаточно крупный хэш из 4096 элементов с функцией хэширования по 3 первым байтам цепочки H(D) = (D[2] xor (D[1] shl 4) xor (D[0] shl 8)) and $FFF. Такую функцию можно вычислять последовательно с меньшим числом операций, зная ее значение для предыдущего элемента. Введены массивы
   • Hash[H] - № цепочки, головной для значения хэш функции H.
   • Next[№ данной цепочки] - № цепочки следующей за данной в хэш цепочке (4кб элементов).

   Таким образом, потребовалось 2 массива вместо 3 (в случае дерева).
   В удалении цепочек нет необходимости, т.к. можно определить окончание хэш цепочки (выход за пределы окна).
   Поиск по цепочке хэша по умолчанию ораничен 50ю незначимыми сравнениями (не принесших улучшения для кодирования, может быть изменено в поле MaxChain).

2. В качестве словаря используется массив Dict. В отличие от оригинальной реализации словарь не зациклен и объединен с входным буфером размером 1кб (может быть изменен в тексте модуля). Массив Next используется циклическим образом для уменьшения объемов памяти. Упрощенно это работает так
   • Окно словаря (4кб) всегда находится в пределах массива Dict размером 5кб, после области окна всегда имеется необработанная цепочка в 60 байт. По мере обработки окно сдвигается. При поиске используются дистанции вплоть до 4 кб (в отличие от оригинальной реализации).
   • По достижении верхней границы словаря Dict, окно и необработанные данные перемещаются коммандой Move в начало словаря (поскольку объем данных ~4 кб - это быстрая операция). В верхнюю часть массива вычитываются данные из входного потока.
   • При таком перемещении окна значения в массивах Hash, Next становятся неверными (смещенными), их можно пересчитать, но это более медленная операция, поэтому мы просто учитываем появившееся смещение при обращении к этим массивам (альтернативно, можно предложить увеличить входной буфер до 4кб, чтобы смещение окна происходило реже и было бы проще обновлять зацикленный массив Next).
   • По достижении смещения в 16384 или более смещение уменьшается на 16384 и обновляются массивы Hash, Next (порог должен быть кратен 4 кб, иначе нарушится структура массива Next - см. следующий пункт). Увеличивать смещения более 16384 в текущем алгоритме нельзя из-за ограничений 16 битных указателей.
   • К массиву Next обращение идет всегда как Next[index and $FFF], таким образом осуществляется его зацикливание.
3. В качестве выходного буфера используется массив SBuf с размером по умолчанию 256 байт (можно изменить в тексте модуля).
4. Структуры дерева Хаффмана и код их использующий весьма близки к оригинальным, поскольку улучшить их затруднительно. Кодирование дистанций, набор символов также остались без изменений.

Ленивое сравнение (Lazy matching).

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

Для реализации ленивого сравнения мы осуществляем подобную проверку с условием, что текущее совпадение достаточно короткое (не превышает значения поля MaxLazy - им можно регулировать соотношение скорость\сжатие), кроме того в функцию поиска передается пороговое значение равное длине текущего совпадения - это усколяет поиск. В случае, если найденное таким образом совпадение длиннее, мы отказываемся от кодирования текущего совпадения, а кодируем текущий символ. На следующем шаге поиск нового совпадения уже не нужен, однако может быть произведеная проверка следующей цепочки в рамках Lazy matching, если совпадение все еще не превышает MaxLazy.

Заключение.

В результате изменений возрасла скорость кодирования, на низкоизбыточных данных улучшение составило 1,5 - 2 раза (за счет адаптивного Хаффмана), а на высокоизбыточных может достигать до 10 - 15 раз (имеется ввиду обработка по типу память - память). Ухудшение сжатия наблюдалось на некоторых типах файлов (например, на некоторых bmp и dbf файлах), однако был и обратный эффект, объясняющийся увеличением окна словаря и оптимальностью выбора цепочек по дистанции. В среднем, при обработке большего количества файлов различных типов результат очень близок к оригинальному алгоритму.

Количество динамической памяти, необходимой для архивации составляет ~26 кб, в оригинальной реализации ~34кб. Использование стека исчисляется сотнями байт (если верить комментариям к оригинальному исходнику ~400) - никаких существенных изменений в этом плане не произошло.

Исходные тексты