Терри Уэлч¶

Терри Уэлч (англ. Terry Welch; 20 января 1939 — 22 ноября 1988) — американский учёный в области информатики и электротехники, наиболее известный как соавтор алгоритма сжатия данных LZW (Lempel — Ziv — Welch). Внёс значительный вклад в развитие методов сжатия без потерь, которые нашли широкое применение в компьютерных сетях, графических форматах и системах хранения данных.

¶Биография

Терри Уэлч родился 20 января 1939 года. Получил степень бакалавра в области электротехники в Массачусетском технологическом институте (MIT) в 1960 году, а затем степень магистра (1962) и доктора философии (1966) по той же специальности в Стэнфордском университете. Его диссертация была посвящена вопросам теории информации и кодирования.

После завершения обучения Уэлч работал в исследовательских лабораториях корпорации «Sperry Rand» (ныне часть Unisys), где занимался разработкой систем передачи данных и методов сжатия. В 1970-х годах он перешёл в компанию «Digital Equipment Corporation» (DEC), где продолжил исследования в области алгоритмов сжатия. В 1984 году Уэлч опубликовал свою знаменитую статью «A Technique for High-Performance Data Compression» в журнале «Computer», в которой описал модификацию алгоритма, предложенного израильскими учёными Абрахамом Лемпелем и Якобом Зивом.

Терри Уэлч скончался 22 ноября 1988 года в возрасте 49 лет.

¶Алгоритм LZW

¶Предпосылки создания

В 1977 и 1978 годах Абрахам Лемпель и Якоб Зив опубликовали два основополагающих алгоритма сжатия без потерь — LZ77 и LZ78. Эти алгоритмы использовали словарный подход, заменяя повторяющиеся последовательности символов ссылками на уже встречавшиеся фрагменты данных. Однако их практическая реализация на компьютерах того времени была ограничена из-за высокой вычислительной сложности и требований к памяти.

¶Модификация Уэлча

В 1984 году Терри Уэлч предложил упрощённую и более эффективную версию алгоритма LZ78, которая получила название LZW (Lempel — Ziv — Welch). Основные отличия LZW от предшественника:

• Инициализация словаря: словарь изначально заполняется всеми возможными одиночными символами (например, 256 байтами для 8-битных данных), что устраняет необходимость в специальном коде для «пустого» символа.
• Построение фраз: алгоритм ищет самую длинную последовательность, уже присутствующую в словаре, и добавляет новую фразу, состоящую из этой последовательности плюс следующий символ.
• Отсутствие кода конца: LZW не требует явного кода конца строки, так как словарь строится динамически.

¶Принцип работы

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

¶Преимущества и недостатки

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

¶Применение

¶Форматы графических файлов

Алгоритм LZW стал основой для нескольких популярных графических форматов:

• GIF (Graphics Interchange Format) — разработан компанией CompuServe в 1987 году. Формат использует LZW для сжатия изображений с палитрой до 256 цветов. Благодаря эффективности алгоритма, GIF стал стандартом для анимации и простых рисунков в интернете.
• TIFF (Tagged Image File Format) — поддерживает LZW как один из методов сжатия, наряду с другими (например, PackBits). Используется в профессиональной фотографии и полиграфии.
• PDF (Portable Document Format) — в некоторых версиях формата LZW применялся для сжатия текстовой и графической информации.

¶Другие области

LZW также применялся в программах архивации (например, в ранних версиях Unix-утилиты compress), в системах передачи данных (модемные протоколы) и в некоторых форматах аудиофайлов (например, в модулях MOD). Однако с развитием более совершенных алгоритмов (DEFLATE, LZMA) область использования LZW сузилась.

¶Патентные споры

Алгоритм LZW был запатентован корпорацией Unisys в 1985 году (патент США № 4,558,302). Это привело к длительным юридическим разбирательствам, особенно в связи с широким распространением формата GIF. Компания Unisys требовала лицензионных отчислений от разработчиков программного обеспечения, использующего LZW, что вызвало критику со стороны сообщества свободного программного обеспечения. В 1999 году Unisys объявила о прекращении взимания лицензионных сборов за использование LZW в формате GIF, а в 2003 году срок действия патента истёк. Тем не менее, споры вокруг алгоритма стимулировали разработку альтернативных методов сжатия, таких как PNG (Portable Network Graphics), который использует алгоритм DEFLATE.

¶Наследие

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