Историческая справка

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

• В 1977 году Абрахам Лемпел и Джекоб Зив опубликовали статью об универсальном алгоритме сжатия данных, который получил название "алгоритм сжатия LZ77".

• В 1978 году Лемпел и Зив предложили усовершенствованную, базирующуюся на словаре, схему сжатия под названием LZ78.

• В 1981 году, работая в Sperry Corporation, Лемпел и Зив вместе с Кохеном и Истменом подали заявку на патент на алгоритм сжатия LZ78. Патент за номером 4464650 был выдан

им в 1984 году.

• В том же 1984 году работавший в Sperry Corporation Терри Велч модифицировал алгоритм LZ78, повысив его эффективность с целью реализации в высокопроизводительных дисковых контроллерах. Результатом стал алгоритм LZW, который Велч после своего увольнения из Sperry описал в статье, опубликованной в журнале IEEE Computer (см. раздел "Дополнительная информация об алгоритме LZW").

• В 1985 году фирма Sperry Corporation получила патент (номер 4558302) на изобретение Велча и реализацию алгоритма сжатия данных LZW. С того времени этот патент предоставляется для свободного изучения в Бюро патентов США и многих публичных библиотеках. Описание этого патента имеется и в Internet.

• В 1986 году путем слияния Sperry Corporation и Burroughs была образована фирма Unisys, к которой и перешло право собственности на этот патент.

• В 1987 году фирма CompuServe разработала формат файлов GIF для хранения и интерактивной выборки растровых графических данных. Спецификация GIF оговаривала необходимость использования алгоритма LZW для сжатия данных в GIF-файлах. Весьма возможно, что CompuServe не проверила патентную чистоту своих решений (т.е. ее сотрудники не порылись в архивах патентов на предмет нарушения форматом GIF оговоренных в них прав), а это нужно было обязательно сделать с учетом будущего широкого распространения данного формата. В ходе такой проверки обнаружился бы патент на алгоритм LZW Велча, который затем перешел в собственность Unisys. В то время фирма Unisys, очевидно, также не знала, что именно метод LZW использован в столь популярном формате, как GIF.

• В 1988 году фирма Aldus Corporation выпустила версию Revision 5.0 своего формата TIFF. Там была добавлена новая возможность, позволяющая записывать растровые RGB-данные либо в необработанном формате, либо в сжатом, построенном на базе алгоритма LZW. (Хотя алгоритм LZW, используемый в TIFF, считается "сломанным", на него все равно распространяется действие патента Unisys.) Соглашение, заключенное между Aldus и Unisys, требует, чтобы с 1991 года фирма Aldus давала в своей документации ссылку на патент Unisys и его применимость к TIFF. В версии Revision 6.0 спецификации TIFF (1992 год) эта ссылка уже есть.

• В 1990 году Unisys выдала фирме Adobe лицензию на использование алгоритма LZW в языке PostScript.

• В 1991 году Unisys выдала фирме Aldus лицензию на использование LZW в спецификации TIFF.

• В 1993 году Unisys стало известно, что алгоритм LZW использован в формате GIF фирмы CompuServe. Начались переговоры о заключении соответствующего лицензионного соглашения.

• В 1994 году Unisys и CompuServe достигли взаимопонимания в вопросе о выдаче разрешения на использование алгоритма LZW в формате GIF для применения в программных средствах, используемых в основном для доступа к информационной службе CompuServe.

• В 1995 году лицензионные соглашения с фирмой Unisys об использовании LZW заключили также службы America Online и Prodigy. Начиная с 1990 года лицензионные соглашения с Unisys заключили сотни фирм.

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

Многие форматы, которые используются для поддержки факсимильной связи и представления документов, поддерживают способ сжатия данных без потерь, часто описываемый как кодирование CCITT. Международный Консультативный комитет по телеграфии и телефонии (CCITT) разработал серию коммуникационных протоколов для факсимильной передачи черно-белых изображений по телефонным каналам и сетям передачи данных. Эти протоколы официально известны как стандарты Т.4 и Т.6 CCITT, но более распространенное их название — сжатие CCITT Group 3 и Group 4 соответственно.

Иногда кодирование CCITT называют кодированием по алгоритму Хаффмена. Это простой алгоритм сжатия, предложенный Давидом Хаффменом в 1952 году. Одномерное кодирование CCITT, описанное ниже, является специфическим типом кодирования по алгоритму Хаффмена.

Стандарты Group 3 и Group 4 — это алгоритмы сжатия, специально разработанные для кодирования однобитовых данных изображения. Многие форматы для поддержки факсимильной связи и представления документов поддерживают сжатие Group 3, а некоторые, включая TIFF, — и Group 4.

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

Group 4 является более эффективной формой двухуровневого сжатия и полностью может заменить Group 3 в большинстве систем хранения документальных изображений (за исключением систем хранения факсимильных документов, где оригинальные изображения, закодированные Group 3, должны сохраняться в неизменном виде).

Объем данных, закодированных Group 4, приблизительно вдвое меньше, чем у обработанных с помощью одномерного Group 3. Хотя Group 4 довольно трудно реализовать эффективно, данная схема не медленнее, чем Group 3, а в некоторых реализациях декодирование происходит даже быстрее. Кроме того, Group 4 разрабатывали специально для применения в сетях передачи данных, поэтому коды синхронизации, используемые в Group 3 для обнаружения ошибок, здесь отсутствуют.

Group 4 иногда путают с методом сжатия IBM MMR. Фактически Group 4 и MMR — это почти один и тот же алгоритм, который к тому же дает и идентичные результаты. Фирма IBM реализовала MMR в 1979 году, представив продукт Scanmaster, т.е. до того как был стандартизован Group 4. MMR стал для IBM собственным стандартом сжатия документов и до сих пор применяется во многих ее системах.

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

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

В случае стандартного документа формата А4 (204 х 196 точек на дюйм), закодированного по схеме Group 3, достигается степень сжатия от 5:1 до 8:1, а в результате кодирования того же документа с помощью Group 4 — свыше 15:1. Утверждения, что алгоритмы CCITT способны намного эффективнее сжимать стандартные деловые документы, преувеличены в основном производителями оборудования.

Поскольку алгоритмы CCITT были оптимизированы для печатных и рукописных документов, есть мнение, что с их помощью изображения не могут хорошо сжиматься. И это правда — двухуровневые растры, содержащие большое количество различных коротких групп, плохо сжимаются с помощью алгоритмов CCITT. Степень сжатия таких изображений обычно не превышает 3:1, а многие из них после сжатия имеют больший размер, чем у оригинала.

Фактически определены три алгоритма кодирования CCITT для данных двухуровневых изображений:

• одномерное Group 3 (G3 ID),

• двухмерное Group 3 (G32D),

• двухмерное Group 4 (G42D).

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

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

• В качестве эталонных использовались тестовые изображения, не обработанные CCITT.

• Были задействованы собственные модификации алгоритма.

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

• Вы получили дезинформацию.