Алгоритм сжатия ZIP и его патентование

Алгоритм сжатия, лежащий в основе многих форматов (включая LZW, который часто ассоциируют с историей сжатия данных), действительно был запатентован в США в середине 1980-х годов. Ключевой патент, US Patent 4,558,302, был подан Терри А. Уэлчем 20 июня 1983 года и выдан 10 декабря 1985 года [1]. Этот факт объясняет юридическую защиту технологии на протяжении двух десятилетий и связан с конкретным механизмом динамического словаря, лежащим в основе алгоритма.

Механизм динамического словаря как ядро патентной новизны

Алгоритм LZW реализует сжатие данных за счёт непрерывного построения и обновления словаря строк входных символов. Словарь изначально содержит все возможные одиночные байты (символы). При чтении входного потока алгоритм пытается найти максимально длинную последовательность символов из текущего словаря. Если следующая последовательность отсутствует в словаре, кодируется индекс уже известной максимально длинной последовательности (префикса), затем новая последовательность (префикс + следующий символ) добавляется в словарь с новым уникальным кодом.

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

Почему именно этот механизм получил патент?

Патенты защищают конкретные технические решения. В случае US 4,558,302 ключевым объектом охраны стала именно идея использования динамически расширяемого словаря для кодирования повторяющихся фрагментов данных через индексы. Это отличается от предыдущих методов сжатия тем, что не требует предварительного знания статистики входных данных или фиксированной таблицы кодов.

Подача патента была сделана 20 июня 1983 года, что отражает дату формального юридического признания новизны этого подхода. Дополнительный патент, US Patent 4,814,746, поданный 1 июня 1983 года Виктором Миллером и Марком Вегманом для варианта LZW, также подкрепляет эту технологию с точки зрения интеллектуальной собственности [2].

Последствия патентования для практической реализации

В течение срока действия патента (20 лет от даты подачи) использование алгоритма LZW требовало лицензирования технологии у правообладателя. Это повлияло на развитие программных продуктов и форматов файлов. Например:

- Формат GIF использовал LZW как основной метод сжатия графических данных. Наличие патента вызвало необходимость уплаты роялти или ограничения распространения некоторых реализаций.
- В UNIX-системах утилита compress применяла LZW; однако лицензионные сложности побудили разработчиков искать альтернативы.
- В итоге многие современные форматы и инструменты перешли на другие методы сжатия без патентных ограничений, например, DEFLATE в gzip и PNG.

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

Технические ограничения и особенности алгоритма LZW

Динамический словарь не бесконечен: он ограничен размером кода (обычно 12 бит), что задаёт максимальное количество элементов в таблице (до 4096). При переполнении словаря обычно происходит сброс или прекращение добавления новых записей. Эти особенности влияют на эффективность сжатия при различных типах данных.

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

Окончание срока действия патента и переход к свободному использованию

Патент US 4,558,302 истёк 20 июня 2003 года [5], что открыло свободное использование метода без лицензионных барьеров. Международные аналоги патентов (например, EP0129439, JP7249996) были поданы в 1984 году и истекли примерно через двадцать лет после подачи [6].

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

Техническая формализация процесса работы алгоритма

Процесс кодирования можно описать так:

Для входного потока \( S = s_1, s_2,... s_n \) создаётся пустая строка \( w = '' \). Для каждого символа \( k \):

- Если \( w + k \) содержится в словаре \( D \), то обновляем \( w = w + k \).
- Иначе выводим код для \( w \), добавляем \( w + k \) в \( D \) с новым кодом и устанавливаем \( w = k \).

После обработки всего потока выводится код для оставшегося \( w \).

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

Резюме технического феномена: почему именно в 1983 году?

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

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