Сайт о сжатии >> Новинки | О сервере (Compression Catalog! | ENGLISH) Книга "Методы сжатия данных" >> Без потерь | Изображений | Видео Разделы >> Cтатьи | Видео | Arctest | Ссылки | Ru.compress | Форум Проекты >> Д.Ватолина | А.Ратушняка | М.Смирнова | В.Юкина | Е.Шелвина | Д.Шкарина

Сжатие данных без потерь

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

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

Две схемы сжатия, кодирование Хаффмена (Huffman) и LZW-кодирование (по начальным буквам фамилий Лемпел (Lempel) и Зив (Ziv) - его создатели и Уэлч (Welch), который существенно его модифицировал), формируют основу для многих систем сжатия, которые мы используем из дня в день.

Эти схемы представляют еще и две различные школы алгоритмов сжатия. Понимание того, как работает каждый алгоритм, дает великолепную основу для понимания сжатия вообще. И кодирование Хаффмена, и LZW-кодирование являются алгоритмами сжатия без потерь. Они подходят для сжатия любого типа данных, потому что развернутое представление идентично исходным входным данным системы сжатия. Алгоритмы сжатия данных изображений, такие как Joint Photographics Experts Group (JPEG), Motion Picture Experts Group (MPEG) (см. "Putting th Squeeze on Graphics," в журнале "Байт", декабрь 1990 г.), и другие, достигают фантастических отношений сжатия за счет точности воспроизведения данных.

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

Кодирование Хаффмена

Кодирование Хаффмена, вероятно, самый известный метод сжатия данных. Простота и элегантность способа сделали его на долгое время академическим фаворитом. Но коды Хаффмена имеют и практическое применение; например, статические коды Хаффмена используются на последнем этапе сжатия JPEG. Стандарт сжатия данных для модемов MNP-5 (см. "4800 Bits, No Errors", BYTE, Июнь 1989) использует динамическое сжатие Хаффмена в качестве части его процесса. Наконец, кодирование Шеннона-Фано (Shannon-Fano), довольно близкое к кодированию Хаффмена, используется как один из этапов в мощном "imploding"-алгоритме программы PkZip.

Кодирование Хаффмена работает на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Наиболее общее представление - алфавит ASCII - использует 8 бит для каждого символа. В английском языке буква e явно будет чаще встречаться, чем буква q, хотя мы используем для их представления одинаковое количество бит. Если мы используем только 4 бита для e и 12 бит для q, мы могли бы выиграть несколько бит, сохраняя английский текст.

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

С помощью этой информации о вероятностях компрессор и декомпрессор могут сконструировать кодирующее дерево. Кодирующее дерево является двоичным деревом с одним листом для каждого символа. Чтобы построить дерево, компрессор начинает с двух символов наименьшей вероятности. Затем он объединяет их как два листа двумя ветвями в узел; этому узлу, в свою очередь, назначается сумма двух вероятностей. Компрессор затем рассматривает этот узел вместе с оставшимися символами в списке вероятностей, и снова выбирает два наименее вероятных элемента. Он продолжает строить и объединять узлы, пока не построит единое дерево с вероятностью корня, равной 1.

Полученное дерево имеет листья с различным расстоянием от корня. Листья, которые представляют символы с наивысшей вероятностью, самые близкие к корню, тогда как символы с наименьшей вероятностью вынесены подальше.

Для кодировки символа компрессор находит путь от корня дерева к листу символа. Предположим, что компрессор хочет закодировать букву s. Он начинает с листа, соответствующего букве s, и переходит в родительский узел, отмечая при этом, по какой ветви он про шел (по 0 или по 1). Он продолжает идти вверх по дереву, пока не достигнет корня. Список ветвей в обратном порядке описывает путь от корня до s: это и есть код Хаффмена для этого символа.

Символы с большой вероятностью находятся ближе к корню, так что их коды короткие. Символы с малой вероятностью дальше от корня, и их коды длиннее.

Чтобы декодировать, декомпрессор берет код и обрабатывает его в обратном порядке. Это значит, что он начинает с корня дерева. Если первый бит кода равен 1, то декомпрессор идет от корня в узел по ветви 1. Он продолжает чтение битов и проход по ветвям, пока не достигнет листа; символ в листе и есть декодированный символ.

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

Динамическое кодирование Хаффмена

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

К счастью, динамическая версия сжатия Хаффмена может строить дерево Хаффмена "на лету" во время чтения и активного сжатия. Дерево постоянно обновляется, чтобы отражать изменения вероятностей входных данных.
  Листинг 1 содержит версию программы динамических сжатия/распаковки Хаффмена, написанную на псевдокоде. Реальный код, доступный из обычных источников, написан на языке ассемблера 8088. Эти программы основаны на алгоритме, описанном в [1], который ссылается на несколько оригинальных источников. [2] представляет более эффективный, хотя и более сложный, алгоритм динамического сжатия Хаффмена.

Ключом к началу неинициализированного дерева является введение пустого листа. Пустой лист - это просто лист без присоединенного к нему символа; этот лист имеет нулевую вероятность. Начальное дерево как в компрессоре, так и в декомпрессоре, имеет только корень и единственный пустой лист.

Компрессор начинает "катать мячи" с чтения символа. Он присоединяет этот символ к ветви 1 корня, оставляя пустой лист на ветви 0. Затем он посылает этот символ в декомпрессор как буквальный код ASCII, и декомпрессор выполняет точно такое же действие над своим деревом.

Для каждого символа, прочитанного после этого, компрессор выполняет следующие шаги. Вначале он проверяет, находится ли код в кодовом дереве. Если код есть, компрессор выдает его так же, как и в случае статического сжатия. Если же нет, он посылает код для пустого листа. Затем он посылает новый символ как буквальный код ASCII. Наконец, компрессор добавляет два кода, один для нового пустого листа на ветви 0, и один - для нового кода ветви 1. Когда дерево заполнится, т.е. когда в нем будут все символы, компрессор просто изменяет последний пустой лист на последний символ.

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

Однако пустой лист и неинициализированное дерево не решают проблему отслеживания изменения вероятностей. Чтобы делать это, вам необходимо добавить веса к каждому узлу дерева и изменять эти веса во время обработки данных. Вы должны также поддерживать список обозначений узлов (и весов), сортированный по весу.

Каждый символ начинается с веса 1 (пустой лист начинается с 0). Всякий раз, когда компрессор передает символ, который находится в таблице, он инкрементирует вес узла, соответствующего этому символу. Если это изменение делает узел "тяжелее", чем узлы, которые выше него в списке, компрессор обменивает узел символа с самым тяжелым узлом, который, однако, легче, чем узел символа. При обмене в дело идут только определения родительских узлов и ветвей; это не касается потомков обмениваемых узлов, так что не существует опасности, что лист станет внутренним узлом, а внутренний узел - листом.

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

Рисунок показывает ранние этапы динамического построения дерева Хаффмена для очень простого входного примера. Вы можете продолжить добавление новых листьев через механизм пустого листа, а также обмена.

Проблемы

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

Способ обхода этой дилеммы - сделать в компрессоре два прохода - один для передачи и другой для обновления. Декомпрессор также делает два прохода - один для приема (проход вниз по дереву) и один для обновления (обратно вверх).

Вторая проблема появляется из-за пустого листа. Поскольку вес пустого листа равен нулю, возможно для "брата" пустого листа стать тяжелее своего родителя в самом начале процесса обновления. Однако обмен между ребенком и родителем смешает дерево, оставив родителя собственным ребенком. К счастью, простое отбрасывание любого обмена между ребенком и родителем решает проблему.

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

LZW сжатие

Алгоритм LZW, который впервые был представлен Уэлчем в 1984 году [3], в последние несколько лет стал широко используемым методом. Формат GIF файлов CompuServe использует сжатие LZW; это делают и ARC, compress из Unix, Stuffit и PkZip. Сам алгоритм запатентован фирмой Sperry.

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

LZW работает путем расширения алфавита - он использует дополнительные символы для представления строк обычных символов. Чтобы использовать LZW-сжатие на 8-битовые коды ASCII, вы расширяете алфавит, используя девяти- и больше битовые  коды. Дополнительные 256 символов, которые предоставляет вам 9-битовый код, используются для хранения строк 8-битовых кодов, которые определяются из строк во входном потоке.

Компрессор поддерживает таблицу строк, состоящую из строк и соответствующих им кодов. Таблица строк соответствует расширенному алфавиту. Компрессор начинает с таблицы строк, определенной только 256 кодами букв. Если вы используете 9-битовые коды, таблица строк имеет 256 дополнительных пустых элементов; если вы используете 10-битовые коды, она имеет 768 пустых элемента и т.д.

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

Таблица 1 показывает пример LZW-сжатия, использующий тот же самый пример. Компрессор читает начальное T и добавляет его к нулевой строке. Строка T является символом, так что она уже находится в таблице. Далее компрессор читает h и ищет строку Th в таблице строк, где ее не находит. Он добавляет Th к таблице в следующую доступную позицию и выводит последнюю известную строку, T. Он продолжает читать символы и добавлять строки, пока ввод не будет исчерпан.

Этот короткий и простой входной пример показывает только один случай сжатия, когда код 258 посылается вместо строки is. Если бы я использовал 9-битовые коды, я выдал бы восемь 9-битовых кодов, чтобы представить 9-байтовую строку This is a в любом случае.  Конечно, реальный, более длинный ввод позволит вам построить более длинную и эффективную таблицу строк. Чем больше будет появляться повторяющихся строк, тем сильнее вы сможете сжать данные.

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

Однако существует простой способ избежать этого. Как вы могли заметить, каждая новая строка в действительности старая строка плюс новый символ. Вместо того, чтобы хранить строку явно, вы можете хранить ее как комбинацию кода с добавленным символо. Таблица 1 показывает этот метод хранения. Код 261, например, сохраняется как 258+(пробел), а не как строка "is(пробел)", которую он представляет.

LZW-распаковка

Подобно динамическому алгоритму Хаффмена, LZW-кодирование не требует от вас передавать таблицу декодировки в декомпрессор вместе со сжатыми данными. Распаковщик LZW может построить свою собственную таблицу только из кодов в сжатых данных.

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

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

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

Уэлч описал специальный случай, который немного усложняет алгоритм распаковки. Строки некоторого типа заставляют компрессор выводить код, прежде чем распаковщик имеет его в своей таблице. Эта ситуация встречается, когда встречается строка вида XandXandX и строка Xand уже находится в таблице. В этом случае компрессор посылает код для Xand (потому что он уже знает его) и затем добавляет XandX к таблице. Потом он начинает со среднего X, находит, что следующая группа символов, которую он знает, является XandX, и посылает код для XandX, хотя распаковщик еще не знает, что это значит.

Вы можете обрабатывать этот специальный случай, добавив пару строк кода в программу распаковщика. Если распаковщик принял код, который он не может опознать, он знает, что произошел именно этот особый случай. В вышеупомянутом примере распаковщик принимает   код для Xand, а следом неизвестный код. Он опять выводит последний переданный код (Xand), а потом первый символ из этого кода (X). После этого он добавляет комбинацию этих символов (XandX) в таблицу, чем синхронизирует ее с компрессором.

Улучшенный LZW

Два улучшения основного алгоритма LZW - коды переменной длины и очистка таблицы - делают более гибкий и надежный компрессор.

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

Пример программы (см. листинг 2) использует коды переменной длины для обхода этой проблемы. Вначале он использует 9-битовые коды. Когда компрессор использовал все 9-битовые коды, он переключается на 10-битовые, и так далее до 13 бит. Для остального вывода он использует 13-битовые коды.

Листинг 2 показывает, что компрессор увеличивает битовую длину, когда следующий код, добавляемый к таблице, требует больше битов, чем допускается текущей битовой длиной. Это не следующий код для вывода; следующий выводимый код будет кодом, который соотве тствует следующей порции ввода. Однако, поскольку распаковщик и компрессор используют один и тот же метод для определения, какой код использовать следующим, они делают переключение битового размера одновременно.

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

Вы могли бы также очищать таблицу, когда она заполняется, и начинать строить новую для новых данных. Хотя этот способ и делает компрессор более гибким, чем подход "ничего-не-делать", он также приводит к уменьшению коэффициента сжатия, когда таблица почти пуста.
  Листинг 2 использует подход частичной очистки для очистки таблицы строк, когда она заполняется. Программа чистит только некоторые старые строки в таблице, когда это становится необходимым.
Из-за того, что строковые данные хранятся как комбинация "базовый код/символ", вы не можете просто отслеживать наименее часто или давно используемые строки в таблице и позже избавляться от них, когда заполнится таблица. Вы можете избавляться только от узлов-листьев, которые не используются другими кодами в качестве базовых.

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

Чтобы определить, какой узел является листом, а какой не является, процедура очистки таблицы применяет довольно прямолинейный подход. Сначала она помечает все узлы как листья. Затем она проходит по таблице, проверяя базовые коды. Каждый базовый код - код узла, который не является листом, так что процедура отменяет метку листа соответствующего базовому коду листа.

К сожалению, имеется еще одна сложность в поиске листьев, подлежащих удалению. Компрессор сохраняет свою таблицу строк в хэшируемом массиве, поскольку он должен пытаться искать коды в таблице, зная только их базовые коды и добавленные символы. Для процедуры очистки, чтобы найти коды, заданные самим кодом, вы должны использовать таблицу перекрестных указателей, которая отображает отсортированные коды на места в таблице. Хотя это отнимает добрый кусок памяти (16 Кбайт для 16-битовых указателей и 13-битовой таблицы), таблица обеспечивает быстрый доступ к таблице строк как по кодам, так и по содержанию.

Примеры кода

Чтобы попробовать эти два алгоритма сжатия, я написал две ассемблерные процедуры для использования их из программ, написанных на C. (Полный текст этих процедур доступен в электронном формате. Подробно см.стр.5 журнала.) Обе они принимают входной и выходной хэндлы, сжимают данные из входного файла и записывают его в выходной.

Даже если вы не собираетесь писать свой собственный компрессор, небольшие знания основ сжатия данных будут весьма полезны. Хотя сжатие данных может оказаться сложным и сопряженным с опасностью, это действительно стоящая вещь, как вы можете видеть сами.

Ссылки:

• Storer, James A. Data Compression: Methods and Theory. Computes Science Press, 1988.
• Vitter, J.S. "Design and Analysis of Dynamic Huffman Codes." Journal of the Association for Computing Machinery, October 1987.
• Welch, Terry A. "A Technique for High Performance Data Compression." Computer, June 1984.

Листинг 1. Псевдокод динамического сжатия/распаковки Хаффмена. Все обращения к структурам упрощены в целях читабельности. Если это не указано явно, структуры являются элементами массива Tree. Например, char.parent должно читаться как Tree[char].parent.

PROCEDURE huffman compress
tree <- ROOT                     // initialize the tree
add_node (empty leaf, ROOT, 0) // add the empty leaf to the tree
char <- (next character from buffer) // read in the first character
add_node (char, ROOT, 1)        // add this char to the tree
write char to output buffer     // send the first character
                                // as a literal character
WHILE (input buffer not empty)
                                // read in a character
   char <- (next character from buffer)
   IF (char is not known)
      transmit(empty leaf code)
      write char to output buffer   // send the literal character
      update_tree (empty leaf code) // adjust the tree
      IF (all nodes not full)
                                // add to the tree
         add_node(char, empty leaf, 1)
                                // move empty leaf
         add_node(empty leaf, empty leaf, 0)
      ELSE                       // last node to add
                                // assign empty leaf info to char
         char.parent <- empty leaf.parent
   ELSE                          // this character is known
      transmit_code (char code)
      update_tree (char code)   // adjust the tree
CONTINUE

PROCEDURE huffmann expand
tree <- ROOT                     // initialize the tree
add_node (empty leaf, ROOT, 0)  // add the empty leaf to the tree
char <- (next char from buffer) // read in literal first character
add_node (char, ROOT, 1)        // add this char to the tree
write char to output buffer     // write the first character
WHILE (input buffer not empty)
   char <- incode (buffer)      // read in a code
   update_tree (char code)      // adjust the tree
   IF (char=empty leaf)
      char <- next char from buffer // read in literal character
      IF (all nodes not full)
                                // add to the tree
         add_node(char, empty leaf, 1)
                                // move empty leaf
         add_node(empty leaf, empty leaf, 0)
      ELSE                       // last node to add
                                // assign empty leaf info to char
         char.parent <- (empty leaf.parent)
   write char to putput buffer
CONTINUE

// Huffman compression support routines
// assume expander has same tree structure as compressor for
// readability. In reality, each expansion tree node has daughter
// pointers as well as a parent pointer.

                                // add a node to the tree
PROCEDURE add_node (code, parent, branch)
code.parent <- parent           // assign parent pointer
code.bit <- branch               // assign bit for this code
code.weight_ptr <- (next available spot in weight list)
IF (code is a character)
   Weightlist[code.weight_ptr] <- 1
ELSE                             // code is the empty leaf
   Weightlist[code.weight_ptr] <- 0
ENDIF

PROCEDURE update_tree(code)
WHILE (code != ROOT)
   Weightlist[code.weight_ptr] ++       // increment weight
   IF (Weightlist[code.weight_ptr] = MAXWEIGHT)
      scale(weightlist)
   IF (Weightlist[code.weight_ptr] > Weightlist[code.weight_ptr-1]
                                // if weight is greater than
                                // that of node listed above
                                // it in the weightlist
      swap_node <- (heaviest node, which is lighter than code)
      IF (swap_node != code.parent) // don't swap if parent-child
         swap(swap_node, code)
   code <- code.parent
CONTINUE

PROCEDURE transmit (code)       // transmit a Huffman code
DO
   push code.bit                 // push this code's bit on a stack
   code <- code.parent           // move to parent mode
WHILE (code != ROOT)
pop bitstack                     // send the bits to output

PROCEDURE incode (buffer)       // read a Huffman code
code <- ROOT                     // start at the root
DO
   bit <- (next bit from buffer)        // read in a bit
   IF (bit=0)
      code <- code.zero_daughter         // jump to zero child
   ELSE
      code <- code.one_daughter          // or one child
WHILE (code.daughter != NULL)   // until you find a leaf
RETURN code                      // leaf location is its value

Листинг 2. Псевдокод сжатия/распаковки LZW. Все обращения к структурам упрощены в целях читабельности. Если это не указано явно, структуры являются элементами массива Table. Например, tableoffset.char должно читаться как Table[tableoffset].char.

PROCEDURE LZW compress
next_code <- MAXCHAR+1
numbits <- MINBITS               // bits to represent a char + 1
basecode <- (next char from buffer) // read in a character
WHILE (input buffer not empty)
   char <- (next char from buffer) // read in another character
   IF (lookup(char, basecode, location)=FOUND)
                                // this combination in the table
      basecode <- location.code // update the base code
      CONTINUE                   // get another character
// found a code that is not in the table
   outcode (basecode, numbits)  // send the last complete code
   add_code(char, basecode, next_code, location)
                                // add basecode+char to table
   IF (table full)
      clear(codelist)            // clear some entries and put
                                // their codes in the list of
                                // available codes
   IF (table has been filled)
                                // get another code from list
      next_code <- next code from list
   ELSE
      next_code ++               // or just use the next code
      IF (log2 (next code) > numbits) // increase the bit size?
         numbits ++
   basecode <- char              // start of next string
CONTINUE
outcode (basecode, numbits)

PROCEDURE LZW expand
next_code <- MAXCHAR + 1
numbits <- MINBITS               // bits to represent a char + 1
code <- incode (buffer, numbits) // read a variable-length code
write code to output            // write out this character
lastcode <- code                 // start with this character
WHILE (input buffer not empty)
   code <- incode (buffer, numbits) // read another character
   IF (code not in table)       // is this the special case?
// this is the special case handler for codes not in table
      outstring(lastcode)       // send out the last string again
      write lastchar to output  // and a duplicate first char
   ELSE                          // the normal case
      outstring(code)            // send the string for this code
                                // get the new last char
   lastchar <- (first char from output string)
                                // add a new table entry
   add_code(lastchar, lastcode, next_code)
   lastcode <- code
   IF (table full)
      clear (codelist)           // clear some entries and put
                                // their codes in the list of
                                // available codes
   IF (table has been filled)
                                // get another code from the list
      next_code <- (next code from codelist)
   ELSE
      next_code++                // or just use the next code
      IF (log2(next_code) > numbits) // increase the bit size?
         numbits++
CONTINUE

// LZW compression support routines

// Note: expansion string table is indexed, while compression
// table is hashed by char and basecode. Therefore, add_code and
// clear shown here are appropriate for the compressor.
// Actual add_code and clear used by expander are not as complex.

PROCEDURE lookup (char, basecode, tableoffset)
                                // find the table entry (table
                                // offset is passed by reference)
tableoffset <- hashfunction (char, basecode)
DO FOREVER
   IF (tableoffset is a filled table entry)
      IF (tableoffset.char = char AND
          tableoffset.basecode = basecode)
         RETURN FOUND
      ELSE
         tableoffset <- rehash (char, basecode)
   ELSE
      RETURN NOT_FOUND
CONTINUE

PROCEDURE add_code (char, basecode, code, tableoffset)
tableoffset.code <- code        // update the field at
tableoffset.char <- char        // location in the table
tableoffset.basecode <- basecode
x_index[code] <- tableoffset // update the cross-reference table

PROCEDURE clear (codelist)      // clear part of the table
STATIC bits_in_oldest <- MINBITS // keep track of oldest leaves
FOR (entry <- 0) TO (entry = TABLESIZE)
   mark x_index[entry] as a leaf // mark every cross-index entry
FOR (entry <- 0) TO (entry = TABLESIZE)
   notleaf <- x_index[entry].basecode
   unmark x_index[notleaf]      // unmark those used as other
                                // node's basecode
FOR (each entry represented by bits_in_oldest bits)
   IF x_index[entry] is marked as a leaf
                                // erase the oldest leaves and
      add entry to available code list
      mark table entry as empty // recycle their codes
bits_in_oldest ++                // update oldest leaves
IF bits_in_oldest > MAXBITS
   bits_in_oldest <- MINBITS    // wraparound

PROCEDURE outstring(code)
IF (code is a literal character)
   write code to output buffer
   RETURN
WHILE (code is not a literal character)
   push code.char       // push the character for this node
   code<-code.basecode  // jump to previous location
push code                // save the last code (the literal)
pop string to output buffer     // pop the string we've built

Стив Эпики
(Byte, March 1991)

Последнее обновление: 12-May-2022