Автор: Mark R. Nelson

Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам.

Простая программа, приведенная ниже, работает с 12-битными кодами. Значения кодов 0 - 255 соответствуют отдельным байтам, а коды 256 - 4095 соответствуют подстрокам.

Сжатие

Алгоритм LZW-сжатия в простейшей форме приведен на рис.1. Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и , если так, выводит существующий код без генерации нового.

Процедура LZW-сжатия:

СТРОКА = очередной символ из входного потока
WHILE входной поток не пуст DO
  СИМВОЛ = очередной символ из входного потока
  IF СТРОКА+СИМВОЛ в таблице строк THEN
    СТРОКА = СТРОКА+СИМВОЛ
  ELSE
    вывести в выходной поток код для СТРОКА
    добавить в таблицу строк СТРОКА+СИМВОЛ
    СТРОКА = СИМВОЛ
  END of IF
END of WHILE
вывести в выходной поток код для СТРОКА 

Рис. 1 Алгоритм сжатия

Простая строка, использованная для демонстрации алгоритма, приведена на рис.2. Входная строка является кратким списком английских слов, разделенных символом "/". Как вы можете заметить, анализируя алгоритм, его работа начинается с того, что на первом шаге цикла он выполняет проверку на наличие строки "/W" в таблице. Когда он не находит эту строку, то генерирует код для "/" и добавляет в таблицу строку "/W". Т.к. 256 символов уже определены для кодов 0 - 255, то первой определенной строке может быть поставлен в соответствие код 256. После этого система читает следующую букву ("E"), добавляет вторую подстроку ("WE") в таблицу и выводит код для буквы "W".

Этот процесс повторяется до тех пор, пока вторая подстрока, состоящая из прочитанных символов "/" и "W", не сопоставится со строковым номером 256. В этом случае система выводит код 256 и добавляет трехсимвольную подстроку в таблицу. Этот процесс продолжается до тех пор, пока не исчерпается входной поток и все коды не будут выведены.

Входная строка : /WED/WE/WEE/WEB/WET

Вход(символы) Выход(коды) Новые коды и соответствующие строки

/W / 256 = /W 
E W 257 = WE 
D E 258 = ED 
/ D 259 = D/ 
WE 256 260 = /WE 
/ E 261 = E/ 
WEE 260 262 = /WEE 
/W 261 263 = E/W 
EB 257 264 = WEB 
/ B 265 = B/ 
WET 260 266 = /WET 
 T   

Рис. 2 Процесс сжатия

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

Распаковка

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

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

Процедура LZW-распаковки:

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
СТРОКА = перевести НОВЫЙ_КОД
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 3 Алгоритм распаковки

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

Входные коды : / W E D 256 E 260 261 257 B 260 T

Вход СТАРЫЙ КОД СТРОКА СИМВОЛ Новый вход таблицы

НОВЫЙ КОД

Выход

     
/ / /     
W / W W 256 = /W 
E W E E 257 = WE 
D E D D 258 = ED 
256 D /W / 259 = D/ 
E 256 E E 260 = /WE 
260 E /WE / 261 = E/ 
261 260 E/ E 262 = /WEE 
257 261 WE W 263 = E/W 
B 257 B B 264 = WEB 
260 B /WE / 265 = B/ 
T 260 T T 266 = /WET 

Рис. 4 Процесс распаковки

Выходной поток идентичен входному потоку алгоритма сжатия. Отметим, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.

Ловушка

К несчастью прекрасный , простой алгоритм распаковки, приведенный на рис. 4, является все таким слишком простым. В алгоритме сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.

Простой пример иллюстрирует это. Предположим, строка "JOEYN" определена в таблице с кодом 300. Когда последовательность "JOEYNJOEYNJOEY" появляется в таблице, выходной поток алгоритма сжатия выглядит подобно тому, как показано на рис. 5.

Входная строка : ...JOEYNJOEYNJOEY...

Вход(символы) Выход(коды) Новые коды и соотв. строки 
JOEYN 288 = JOEY 300 = JOEYN 
A N 301 = NA 
. . . 
. . . 
. . . 
JOEYNJ 300 = JOEYN 400 = JOEYNJ 
JOEYNJO 400 401 = JOEYNJO 

Рис. 5 Некоторые проблемы

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку "JOEYN" и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное "J", к строке. Результатом является правильный перевод кода 400 в строку "JOEYNJ".

Процедура LZW-распаковки:

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
СИМВОЛ = СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
IF NOT в таблице перевода НОВЫЙ_КОД THEN
СТРОКА = перевести СТАРЫЙ_КОД
СТРОКА = СТРОКА+СИМВОЛ
ELSE
СТРОКА = перевести НОВЫЙ_КОД
END of IF
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 6 Модифицированный алгоритм распаковки

Реализация

Концепции, использованные в алгоритме сжатия, настолько просты, что весь алгоритм может быть записан в несколько строк. Но так как управление построением таблицы требует некоторых специальных действий, реализация несколько более сложна. В демонстрационной программе, приведенной ниже, использовались коды длиной 12, 13 и 14 бит. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу. Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк.

Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк. Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода.

Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например в разобранном выше примере строка "/WEE" хранится как код 260 и символ "E". Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ "E". Наконец, код 256 хранится как "/" плюс "W".

Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается использованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэш-адреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки. В демонстрационной программе для этого используются элементы трех массивов : code_value[i], prefix_code[i] и append_character[i].

Когда необходимо добавить новый код в таблицу, используется хэшфункция в процедуре find_match для генерации корректного i. Процедура find_match генерирует адрес и затем проверяет, не использовался ли он уже. Если это так, то find_match выполняет вторую пробу и так до тех пор, пока не найдется свободное место.

Хэш-функция, использованная в этой программе - простая "xor"-типа хэш-функция. Префикс кода и добавочный символ комбинируются для формирования адреса массива. Если содержимое префикса кода и символ в массиве сопоставляются им, то возвращается корректный адрес. Если элемент массива по этому адресу уже использован, выполняется фиксированное смещение для поиска нового места. Это выполняется до тех пор, пока не будет найдено свободное место или не произойдет сопоставление. Среднее число поисков в такой таблице - меньше 3, если используется таблица на 25% большего размера, чем необходимо. Оно может быть улучшено путем увеличения размера таблицы. Необходимо отметить, что для того, чтобы порядок вторичных проб работал, размер таблицы должен быть простым числом. Это объясняется тем, что проба может быть любым целым между 1 и размером таблицы. Если проба и размер таблицы не являются взаимно простыми, поиск свободных мест может закончиться неудачей, даже если они есть.

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

К сожалению метод, использованный для хранения строковых величин, приводит к тому, что декодировка строк должна выполняться в инверсном порядке. Это значит, что все символы для данной строки при декодировании должны помещаться в стековый буфер, а затем выводиться в обратном порядке. В приведенной программе это выполняется функцией decode_string.

Проблема появляется, когда чтение входного потока прерывается при достижении конца потока. Для этого частного случая в программе зарезервирован последний определяемый код MAX_VALUE как признак конца данных. Это не является необходимым при чтении файла, но может помочь при чтении буфера сжатых данных из памяти. Затраты на потерю одного определяемого кода весьма малы сравнительно со всем процессом.

Результаты

Достаточно трудно охарактеризовать результативность какой-либо техники сжатия данных. Степень сжатия определяется различными факторами. LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры. По этой причине он работает весьма эффективно, когда встречает английский текст. Уровень сжатия может достигать 50% и выше. Соответственно, сжатие видеоформ и копий экранов показывает еще большие результаты.

Трудности при сжатии файлов данных несколько больше. В зависимости от данных, результат сжатия может быть как хорошим, так и не очень удовлетворительным. В некоторых случаях "сжатый" файл может превосходить по своим размерам исходный текст. Небольшой эксперимент даст Вам представление о том, хорошо или плохо упаковываются Ваши данные.

Ваша реализация

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

Одной из проблем является то, что приведенная программа не адаптируется к различной длине файлов. Использование 14- или 15-битных кодов дает лучшую степень сжатия на больших файлах (это объясняется тем, что для них строятся большие таблицы строк), но хуже работает с маленькими файлами. Такие программы, как "ARC", решают эту проблему использованием кодов переменной длины. Например, когда величина next_code находится между 256 и 511, "ARC" читает и выводит 9-битные коды. Когда величина next_code становится настолько большой, что необходимы 10-битные коды, процедуры сжатия и распаковки увеличивают размер кода. Это значит, что 12- и 15-битные варианты программы работают хорошо и на маленьких файлах.

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

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

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

И, наконец, можно брать вырабатываемые LZW-методом коды и пропускать их через адаптирующийся кодирующий фильтр Хаффмана. Это дает несколько большую степень сжатия, но стоимость такой работы более высока, также как и время обработки.

Коротко

Приведенная программа была написана и тестирована на MS-DOS машине и успешно скомпилирована и выполнена с использованием обычного компилятора "C". Она должна нормально работать на любой машине, поддерживающей 16-битный целые и 32-битные длинные целые языка "C".

Реализация компиляторов "C" для MS-DOS обычно создает сложности при использовании массивов больших, чем 64К байт, не позволяя использовать 15- или 16-битные коды в программе. На машинах с другими процессорами, таких как VAX, эти сложности преодолеваются и облегчается использование кодов большей длины.

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

--------------------------------------------------------------------------------

/************************************************************************
** Демонстрационная программа для LZW-алгоритма сжатия/распаковки данных.
** Mark R. Nelson
*************************************************************************/
#include 
#define BITS 12                  /* Установка длины кода равной 12, 13   */
#define HASHING_SHIFT BITS-8     /* или 14 битам.                        */
#define MAX_VALUE (1 << BITS) - 1/* Отметим, что на MS-DOS-машине при    */
#define MAX_CODE MAX_VALUE - 1   /* длине кода 14 бит необходимо компи-  */
                                 /* лировать, используя large-модель.    */
#if BITS == 14
  #define TABLE_SIZE 18041       /* Размер таблицы строк должен быть     */
#endif                           /* простым числом, несколько большим,   */
#if BITS == 13                   /* чем 2**BITS.                         */
  #define TABLE_SIZE 9029
#endif
#if BITS <= 12
  #define TABLE_SIZE 5021
#endif

void *malloc();
/* Это массив для значений кодов            */
int *code_value;                 
/* Этот массив содержит префиксы кодов      */
unsigned int *prefix_code;       
/* Этот массив содержит добавочные символы  */
unsigned char *append_character; 
/* Этот массив содержит декодируемые строки */
unsigned char decode_stack[4000];

/*******************************************************************
** Эта программа получает имя файла из командной строки. 
** Она упаковывает
** файл, посылая выходной поток в файл test.lzw. Затем распаковывает
** test.lzw в test.out. Test.out должен быть точной копией исходного
** файла.
********************************************************************/

main(int argc, char *argv[])
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];
/*
**  Эти три буфера необходимы на стадии упаковки.
*/
 code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
 prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
 append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
 if (code_value==NULL || prefix_code==NULL || append_character==NULL)
 {
     printf("Fatal error allocating table space!\n");
     exit();
 }

/*
** Получить имя файла, открыть его и открыть выходной lzw-файл.
*/
    if (argc>1)
        strcpy(input_file_name,argv[1]);
    else
    {
        printf("Input file name? ");
        scanf("%s",input_file_name);
    }
    input_file=fopen(input_file_name,"rb");
    lzw_file=fopen("test.lzw","wb");
    if (input_file==NULL || lzw_file==NULL)
    {
        printf("Fatal error opening files.\n");
        exit();
    };
/*
** Сжатие файла.
*/
    compress(input_file,lzw_file);
    fclose(input_file);
    fclose(lzw_file);
    free(code_value);
/*
** Сейчас открыть файлы для распаковки.
*/
    lzw_file=fopen("test.lzw","rb");
    output_file=fopen("test.out","wb");
    if (lzw_file==NULL || output_file==NULL)
    {
        printf("Fatal error opening files.\n");
        exit();
    };
/*
** Распаковка файла.
*/
    expand(lzw_file,output_file);
    fclose(lzw_file);
    fclose(output_file);
    free(prefix_code);
    free(append_character);
}

/*
** Процедура сжатия.
*/
compress(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;
    next_code=256;    /* Next_code - следующий доступный код строки */
    for (i=0;i=next_code)
        {
            *decode_stack=character;
            string=decode_string(decode_stack+1,old_code);
        }
/*
** Иначе декодируется новый код.
*/
        else
            string=decode_string(decode_stack,new_code);
/*
** Выводится декодируемая строка в обратном порядке.
*/
        character=*string;
        while (string >= decode_stack)
            putc(*string--,output);
/*
** Наконец, если возможно, добавляется новый код в таблицу строк.
*/
        if (next_code <= MAX_CODE)
        {
            prefix_code[next_code]=old_code;
            append_character[next_code]=character;
            next_code++;
        }
        old_code=new_code;
    }
    printf("\n");
}

/*
** Процедура простого декодирования строки из таблицы строк,
* сохраняющая
** результат в буфер.  Этот буфер потом может быть выведен
** в обратном порядке программой распаковки.
*/
char *decode_string(unsigned char *buffer,unsigned int code)
{
int i;

    i=0;
    while (code > 255)
    {
        *buffer++ = append_character[code];
        code=prefix_code[code];
        if (i++>=4094)
        {
            printf("Fatal error during code expansion.\n");
            exit();
        }
    }
    *buffer=code;
    return(buffer);
}
/*
** Следующие две процедуры управляют вводом/выводом кодов
** переменной длины.  Они для ясности написаны чрезвычайно 
** простыми и не очень эффективны.
*/
input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;
    while (input_bit_count <= 24)
    {
input_bit_buffer|=(unsigned long)getc(input)<<(24-input_bit_count);
input_bit_count += 8;
    }
    return_value=input_bit_buffer >> (32-BITS);
    input_bit_buffer <<= BITS;
    input_bit_count -= BITS;
    return(return_value);
}
output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;
output_bit_buffer|=(unsigned long)code<<(32-BITS-output_bit_count);
    output_bit_count += BITS;
    while (output_bit_count >= 8)
    {
        putc(output_bit_buffer >> 24,output);
        output_bit_buffer <<= 8;
        output_bit_count -= 8;
    }