Авраам Лемпель

Авраам Лемпель — израильский учёный в области компьютерных наук, один из создателей алгоритмов сжатия данных LZ77 и LZ78, которые легли в основу многих современных форматов архивации (ZIP, GIF, PNG, TIFF и других). Профессор, почётный доктор ряда университетов, лауреат премии Израиля (2007) и премии IEEE Ричарда Хэмминга (2007).

Биография

Авраам Лемпель родился 10 февраля 1936 года во Львове (Польша, ныне Украина). В 1939 году, после начала Второй мировой войны, его семья была вынуждена бежать в СССР. В 1941 году, после нападения Германии на Советский Союз, Лемпель с семьёй оказался в эвакуации в Средней Азии. В 1947 году они репатриировались в Израиль.

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

После защиты диссертации Лемпель работал в Технионе, где прошёл путь от ассистента до полного профессора. В 1977–1978 годах он был приглашённым профессором в Корнеллском университете (США), а в 1979–1980 годах — в Стэнфордском университете. В 1980-х годах Лемпель занимал должность декана факультета электротехники Техниона. В 1990-х годах он также работал в компании IBM в Израиле, где участвовал в разработке алгоритмов сжатия для систем хранения данных.

С 2006 года — профессор-эмерит Техниона.

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

Алгоритм LZ77 (1977)

В 1977 году Авраам Лемпель совместно с Яаковом Зивом опубликовал статью «A Universal Algorithm for Sequential Data Compression» (IEEE Transactions on Information Theory). В этой работе был предложен алгоритм, получивший название LZ77 (Lempel–Ziv 1977). Основная идея алгоритма заключается в замене повторяющихся последовательностей символов ссылками на их предыдущие вхождения в скользящем окне. Алгоритм не требует предварительного знания статистики данных и является универсальным — он эффективно сжимает как текстовые, так и бинарные данные.

LZ77 стал основой для многих последующих алгоритмов, включая Deflate (используется в ZIP, gzip, PNG) и LZSS.

Алгоритм LZ78 (1978)

В 1978 году Лемпель и Зив опубликовали вторую статью — «Compression of Individual Sequences via Variable-Rate Coding» (IEEE Transactions on Information Theory), в которой представили алгоритм LZ78. В отличие от LZ77, LZ78 строит словарь фраз по мере обработки данных и кодирует повторяющиеся последовательности как индексы в этом словаре. Этот подход позволил избежать ограничения скользящего окна и лучше сжимать данные с большими повторяющимися блоками.

LZ78 лёг в основу форматов GIF (Graphics Interchange Format) и TIFF, а также алгоритма LZW (Lempel–Ziv–Welch), разработанного Терри Уэлчем в 1984 году. LZW, в свою очередь, стал стандартом для сжатия в UNIX (команда compress) и ранних версиях архиваторов.

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

Помимо алгоритмов сжатия, Лемпель внёс вклад в теорию информации, кодирование с исправлением ошибок и анализ сложности последовательностей. В 1976 году он совместно с Яаковом Зивом опубликовал работу «On the Complexity of Finite Sequences», в которой предложил меру сложности для конечных строк (сложность Лемпеля–Зива). Эта мера широко используется в анализе случайности последовательностей, в биоинформатике (сравнение геномов) и в криптографии.

Признание и награды

• Премия Израиля (2007) — за вклад в развитие компьютерных наук и теории информации.
• Премия IEEE Ричарда Хэмминга (2007) — за фундаментальные работы по сжатию данных.
• Член IEEE (с 1979 года).
• Почётный доктор Техниона (2008), Университета Бен-Гуриона (2010) и других вузов.
• Медаль «За выдающиеся заслуги» от Института инженеров по электротехнике и электронике (IEEE) (2015).

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

Алгоритмы Лемпеля и Зива стали основой для большинства современных систем сжатия без потерь. Они используются в:

• Архиваторах: ZIP, gzip, 7-Zip (частично), RAR (частично).
• Графических форматах: GIF (LZW), PNG (Deflate — вариант LZ77), TIFF (LZW).
• Коммуникационных протоколах: PPP (Compression Control Protocol), V.42bis (модемы).
• Файловых системах: NTFS (сжатие на уровне файловой системы), ZFS (сжатие LZJB — модификация LZSS).
• Базах данных и хранилищах: Oracle, SQL Server, Google Bigtable (используют алгоритмы на основе LZ).

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

Основные ограничения алгоритмов LZ77 и LZ78 связаны с их производительностью на малых объёмах данных и чувствительностью к типу данных. На очень коротких строках (менее нескольких десятков байт) сжатие может быть неэффективным или даже увеличивать размер. Кроме того, алгоритмы плохо сжимают данные с низкой избыточностью (например, уже сжатые данные или зашифрованные).

В 1990-х годах были разработаны более совершенные алгоритмы (например, BWT — преобразование Барроуза–Уилера, PPM — контекстное моделирование), которые в некоторых случаях обеспечивают лучшее сжатие, но требуют больше вычислительных ресурсов. Тем не менее, алгоритмы Лемпеля–Зива остаются наиболее распространёнными благодаря своей скорости и универсальности.

Источники

• Ziv, J., Lempel, A. (1977). «A Universal Algorithm for Sequential Data Compression». IEEE Transactions on Information Theory, 23(3), 337–343.
• Ziv, J., Lempel, A. (1978). «Compression of Individual Sequences via Variable-Rate Coding». IEEE Transactions on Information Theory, 24(5), 530–536.
• Welch, T. A. (1984). «A Technique for High-Performance Data Compression». Computer, 17(6), 8–19.
• Биография Авраама Лемпеля на сайте Техниона (Technion — Israel Institute of Technology).
• Пресс-релиз о присуждении Премии Израиля (2007).
• IEEE Richard W. Hamming Medal — 2007.