Абрахам Лемпель

Абрахам Лемпель — израильский учёный в области теории информации и компьютерных наук, один из создателей алгоритмов сжатия данных без потерь, известных как семейство LZ (Lempel-Ziv). Совместно с Якобом Зивом разработал фундаментальные методы, которые легли в основу большинства современных архиваторов (ZIP, gzip, 7z) и форматов изображений (PNG, GIF). Лауреат премии Израиля (2007) и премии IEEE Ричарда Хэмминга (2007).

Биография

Абрахам Лемпель родился 10 февраля 1936 года во Львове (Польша, ныне Украина). В 1952 году, после окончания средней школы, репатриировался в Израиль. В 1959 году получил степень бакалавра в Технионе — Израильском технологическом институте (Хайфа). В 1963 году там же защитил магистерскую диссертацию, а в 1967 году — докторскую (PhD) по электротехнике.

С 1967 года работал в Технионе, где прошёл путь от преподавателя до профессора. В 1970—1971 годах находился в творческом отпуске в Исследовательском центре IBM имени Томаса Уотсона (США), где и началось его сотрудничество с Якобом Зивом. В 1977—1978 годах — приглашённый профессор в Стэнфордском университете. С 1981 года — профессор кафедры компьютерных наук Техниона. В 1982—1984 годах — декан факультета компьютерных наук. В 1995—1996 годах — вице-президент по академическим вопросам Техниона. Вышел на пенсию в 2004 году.

Научный вклад

Алгоритмы LZ77 и LZ78

Основной вклад Лемпеля в науку — разработка совместно с Якобом Зивом двух алгоритмов словарного сжатия, опубликованных в 1977 и 1978 годах.

• LZ77 (1977, статья «A Universal Algorithm for Sequential Data Compression»): алгоритм использует скользящее окно — в процессе сжатия ищет повторяющиеся подстроки в уже обработанном фрагменте данных. На выходе выдаёт пары (смещение, длина) или литералы. Этот метод лёг в основу форматов ZIP, gzip, DEFLATE (используется в PNG и HTTP).
• LZ78 (1978, статья «Compression of Individual Sequences via Variable-Rate Coding»): алгоритм строит словарь фраз по мере обработки данных, не ограничиваясь скользящим окном. Каждая новая фраза добавляется в словарь, а на выходе выдаётся пара (индекс словаря, следующий символ). Этот метод лёг в основу формата GIF (LZW — вариант LZ78, доработанный Терри Уэлчем).

Оба алгоритма доказали свою универсальность: они не требуют знания статистики источника (отсюда «универсальные» в названии) и работают с любыми типами данных — текстом, изображениями, аудио.

Теория сложности Лемпеля — Зива

В 1976 году Лемпель и Зив предложили меру сложности для конечных последовательностей, известную как сложность Лемпеля — Зива (LZ-сложность). Она оценивает, сколько новых фраз нужно выделить в последовательности, чтобы её можно было восстановить. Эта мера используется в анализе временных рядов, биомедицинской обработке сигналов (например, ЭЭГ) и криптографии.

Другие работы

Лемпель также внёс вклад в теорию кодирования, обработку сигналов и компьютерную архитектуру. В 1970-х годах он занимался проблемами сжатия изображений и цифровой связи. В 1990-х годах его исследования касались теории сложности вычислений и параллельных алгоритмов.

Награды и признание

• 2007 — Премия Израиля в области инженерных наук и технологий.
• 2007 — Премия IEEE Ричарда Хэмминга за фундаментальный вклад в теорию сжатия данных.
• 2010 — Избран членом Национальной инженерной академии США (NAE).
• 2014 — Премия Эдуарда Рейна (Германия) за достижения в области компьютерных наук.
• 2015 — Золотая медаль Общества теории информации IEEE.

Влияние на технологии

Алгоритмы LZ77 и LZ78 стали основой для целого семейства методов сжатия, которые используются повсеместно:

• ZIP (PKZIP, WinZip) — на основе LZ77 + алгоритм Хаффмана (DEFLATE).
• gzip — вариант LZ77, используемый в Unix/Linux.
• PNG — использует DEFLATE (LZ77 + Хаффман).
• GIF — использует LZW (вариант LZ78).
• ARJ, RAR, 7z — также используют LZ-подобные алгоритмы.
• Сжатие в протоколах HTTP (gzip, deflate) — на основе LZ77.

Без работ Лемпеля и Зива современная цифровая коммуникация, хранение данных и интернет были бы невозможны в их нынешнем виде — объём передаваемой информации был бы на порядки выше.

Критика и ограничения

Алгоритмы LZ, как и любые методы сжатия, имеют ограничения:

• Неэффективность на малых объёмах данных: для коротких строк (менее 100 байт) словарные методы часто дают отрицательное сжатие (выходной поток больше входного).
• Чувствительность к шуму: при наличии ошибок в сжатом потоке (например, при передаче по каналу с помехами) восстановление данных может быть невозможно без дополнительных механизмов коррекции.
• Патентные ограничения: алгоритм LZW (основа GIF) был запатентован компанией Unisys в 1985 году, что привело к юридическим спорам и ограничению использования формата GIF в свободном программном обеспечении до истечения срока патента в 2003 году.

Интересные факты

• Несмотря на то, что алгоритмы названы в честь Лемпеля и Зива, сам Лемпель неоднократно подчёркивал, что решающую роль в разработке LZ77 сыграл Зив, а LZ78 — Лемпель.
• В 2007 году, получая премию Израиля, Лемпель сказал: «Сжатие данных — это не просто технология, это способ думать о мире: как избавиться от избыточности и оставить только суть».
• Сложность Лемпеля — Зива используется в медицине для анализа электроэнцефалограмм (ЭЭГ) — например, для диагностики эпилепсии или оценки глубины наркоза.

Источники

• Lempel A., Ziv J. A Universal Algorithm for Sequential Data Compression // IEEE Transactions on Information Theory. — 1977. — Vol. 23, No. 3. — P. 337–343.
• Lempel A., Ziv J. Compression of Individual Sequences via Variable-Rate Coding // IEEE Transactions on Information Theory. — 1978. — Vol. 24, No. 5. — P. 530–536.
• Lempel A., Ziv J. On the Complexity of Finite Sequences // IEEE Transactions on Information Theory. — 1976. — Vol. 22, No. 1. — P. 75–81.
• Биография Абрахама Лемпеля на сайте Техниона (архивная версия).
• Премия Израиля 2007 года — описание вклада лауреатов (официальный сайт премии).
• IEEE Richard W. Hamming Medal — список лауреатов и обоснование награды.