Метод LZW-сжатия данных _____________________________ Mark R. Nelson Перевод : Запольский С.А. Каждый пpограммист имеет хотя бы некоторое представление о сжатии (упаковке) данных. Такие программы, как "ARC" (System Enhancement Associates, Wayne, N.J.) и "PKZIP" (PKWARE, Glendale, Wisc.) везде- сущи в мире MS-DOS. "ARC", к тому же, используется в ряде других операционных систем, таких как Unix, CP/M и т.д. Пользователи CP/M долгое время использовали также "SQ" и "USQ" для сжатия и распаковки программ. Пользователи Unix имеют утилиты "COMPRESS" и "COMPACK". Однако техника сжатия данных используется этими программами только двумя способами : пересылка файлов по линиям связи и архивация. Сжатие данных имеет незаслуженную репутацию трудного для освоения, тяжелого в реализации и тем не менее существующего явления. Факти- чески техника, использованная в выше упомянутых программах, относи- тельно проста и может быть реализована в виде стандартных утилит, содержащих довольно мало строк кода. В этой статье обсуждается Lempel-Ziv-Welch (LZW) сжатие, хорошая, повсеместно используемая техника. LZW, к примеру, сжимая экранные формы, может легко "снять" 50K байт с программы, основную часть которой состовляют хэлповые эк- раны. При использовании LZW-сжатия 500K байт программного обес- печения могут быть поставлены конечному пользователю на 360Kб дискете. Чрезмерно разбухшие файлы базы данных могут быть сжаты до десяти процентов их исходного размера. Основы LZW ______________ Собственно исходный 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 ¦ ¦ вывести в выходной поток код для СТРОКА ¦ ¦ ¦ L--------------------------------------------------- Рис. 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 ¦ ¦ ¦ L------------------------------------------------------------ Рис. 2 Процесс сжатия Выходной поток для заданной строки показан на рис. 2, также как и полученная в результате таблица строк. Как вы можете заметить, эта таблица быстро заполняется, т.к. новая строка добавляется в таблицу каждый раз, когда генерируется код. В этом явно вырожденном примере было выведено пять закодированных подстрок и семь символов. Если ис- пользовать 9-битные коды для вывода, то 19-символьная входная строка будет преобразована в 13.5-символьная выходную строку. Конечно, этот пример был выбран только для демонстрации. В действительности сжатие обычно не начинается до тех пор, пока не будет построена достаточно большая таблица, обычно после прочтения порядка 100 входных байт. Распаковка _____________ Алгоритму сжатия соответствует свой алгоритм распаковки. Он полу- чает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эфективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это воз- можно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены неоходимостью тянуть за собой большую таблицу перевода. Алгоритм распаковки представлен на рис. 3. В соответствии с алго- ритмом сжатия, он добавляет новую строку в таблицу строк каждый раз, когда читает из входного потока новый код. Все, что ему необходимо сделать в добавок - это перевести каждый входной код в строку и пе- реслать ее в выходной поток. ---------------------------------------------------¬ ¦ Процедура LZW-распаковки ¦ ¦ ¦ ¦ читать СТАРЫЙ_КОД ¦ ¦ вывести СТАРЫЙ_КОД ¦ ¦ WHILE входной поток не пуст DO ¦ ¦ читать НОВЫЙ_КОД ¦ ¦ СТРОКА = перевести НОВЫЙ_КОД ¦ ¦ вывести СТРОКУ ¦ ¦ СИМВОЛ = первый символ СТРОКИ ¦ ¦ добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ ¦ ¦ СТАРЫЙ_КОД = НОВЫЙ_КОД ¦ ¦ END of WHILE ¦ ¦ ¦ L--------------------------------------------------- Рис. 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 ¦ ¦ ¦ L--------------------------------------------------------------- Рис. 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 ¦ L------------------------------------------------------------ Рис. 5 Некоторые проблемы Когда распаковщик просматривает входной поток, он сначала деко- дирует код 300, затем выводит строку "JOEYN" и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем чи- тает следующий входной код, 400, и обнаруживает, что его нет в таб- лице. Это уже проблема. К счатью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная колли- зия, то можно без труда усовершенствовать алгоритм. Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется зна- чение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное "J", к строке. Результатом является правильный пере- вод кода 400 в строку "JOEYNJ". ---------------------------------------------------¬ ¦ Процедура LZW-распаковки ¦ ¦ ¦ ¦ читать СТАРЫЙ_КОД ¦ ¦ вывести СТАРЫЙ_КОД ¦ ¦ СИМВОЛ = СТАРЫЙ_КОД ¦ ¦ WHILE входной поток не пуст DO ¦ ¦ читать НОВЫЙ_КОД ¦ ¦ IF NOT в таблице перевода НОВЫЙ_КОД THEN ¦ ¦ СТРОКА = перевести СТАРЫЙ_КОД ¦ ¦ СТРОКА = СТРОКА+СИМВОЛ ¦ ¦ ELSE ¦ ¦ СТРОКА = перевести НОВЫЙ_КОД ¦ ¦ END of IF ¦ ¦ вывести СТРОКУ ¦ ¦ СИМВОЛ = первый символ СТРОКИ ¦ ¦ добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ ¦ ¦ СТАРЫЙ_КОД = НОВЫЙ_КОД ¦ ¦ END of WHILE ¦ ¦ ¦ L--------------------------------------------------- Рис. 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-битную математику, не встретит затруднений и позволит улучшить некоторые характеристики. Библиография ________________ Terry Welch, "Technique for High-Performance Data Compression, "Computer, June 1984. J. Ziv and A. Lempel, "A Universal Algorithm for Sequentia Data Compression, "IEEE Transactions on Information Theory, May 1977 Rudy Rucker, "Mind Tools, Houghton Miffilin Company, Boston, Mass.: 1987 /**************************************************************************** ** Демонстрационная программа для 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; } }