Якоб Зив

Якоб Зив (род. 27 ноября 1931, Тверия, подмандатная Палестина) — израильский учёный в области компьютерных наук, один из создателей алгоритма сжатия данных LZW (Lempel-Ziv-Welch), а также соавтор алгоритмов LZ77 и LZ78, заложивших основы современных методов сжатия без потерь. Его работы оказали значительное влияние на развитие информационных технологий, включая архиваторы, форматы изображений (GIF, TIFF) и протоколы передачи данных.

Биография

Якоб Зив родился в городе Тверия, расположенном на берегу Тивериадского озера (в то время — подмандатная Палестина, ныне Израиль). Он учился в Израильском технологическом институте (Технион) в Хайфе, где в 1954 году получил степень бакалавра наук в области электротехники. В 1957 году он получил степень магистра наук, а в 1962 году — докторскую степень (Ph.D.) в области электротехники в Массачусетском технологическом институте (США).

После завершения обучения Зив вернулся в Израиль, где работал в научно-исследовательских лабораториях Министерства обороны Израиля, а затем в компании Rafael Advanced Defense Systems. В 1968 году он начал академическую карьеру в Технионе, где впоследствии стал профессором и деканом факультета компьютерных наук. В 1970-х годах он также работал в Bell Laboratories (США) в качестве приглашённого исследователя, что способствовало его сотрудничеству с Абрахамом Лемпелом.

Научная деятельность

Основные достижения Якоба Зива связаны с теорией сжатия данных. В 1977 году совместно с Абрахамом Лемпелом он опубликовал статью «A Universal Algorithm for Sequential Data Compression», в которой был описан алгоритм LZ77. В 1978 году последовала статья «Compression of Individual Sequences via Variable-Rate Coding», представившая алгоритм LZ78. Эти работы стали основой для целого семейства методов сжатия, известных как LZ-алгоритмы.

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

Алгоритмы LZ77 и LZ78 относятся к классу словарных методов сжатия. Они работают путём поиска повторяющихся последовательностей данных (строк) и замены их ссылками на предыдущие вхождения.

• LZ77 использует скользящее окно, в котором хранится недавно обработанный фрагмент данных. При кодировании ищется максимальное совпадение текущей последовательности с данными в окне, и вместо неё записывается пара (смещение, длина). Этот алгоритм лёг в основу форматов Deflate (используется в ZIP, gzip, PNG) и LZSS.
• LZ78 строит словарь фраз, который динамически расширяется по мере обработки данных. Каждая новая фраза добавляется в словарь, а на повторяющиеся фразы даются ссылки по их индексу. Этот алгоритм стал основой для LZW.

Алгоритм LZW

Алгоритм LZW (Lempel-Ziv-Welch) был разработан в 1984 году Терри Уэлчем (Terry Welch) на основе LZ78. Якоб Зив и Абрахам Лемпел не участвовали непосредственно в его создании, но их работа послужила фундаментом. LZW получил широкое распространение благодаря своей эффективности и простоте реализации. Он используется в форматах:

• GIF (Graphics Interchange Format) — формат растровых изображений, популярный в интернете.
• TIFF (Tagged Image File Format) — формат для хранения изображений с высоким качеством.
• Unix compress — утилита сжатия данных в операционных системах Unix.

LZW был запатентован компанией Unisys, что привело к юридическим спорам и ограничениям на его использование в свободном программном обеспечении. Впоследствии срок действия патента истёк, и алгоритм стал общедоступным.

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

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

• Премия Израиля (1993) — высшая государственная награда Израиля в области точных наук.
• Премия Маркони (1995) — за достижения в области телекоммуникаций.
• Премия Эдуарда Рейна (1997) — за вклад в компьютерные науки.
• Премия IEEE Ричарда Хэмминга (2007) — за выдающийся вклад в теорию информации.
• Член Израильской академии наук (с 1995 года).
• Член Национальной инженерной академии США (с 1998 года).

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

Влияние на современные технологии

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

• Архиваторах: ZIP, RAR, 7z, gzip, bzip2.
• Форматах изображений: PNG, GIF, TIFF.
• Форматах аудио и видео: FLAC, MPEG-4 (частично).
• Протоколах передачи данных: HTTP (сжатие gzip), SSH, VPN.
• Базах данных: сжатие столбцов в системах хранения.

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

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

Несмотря на широкое применение, алгоритмы LZ имеют ограничения. Они не обеспечивают оптимального сжатия для всех типов данных — например, для случайных или уже сжатых данных они могут увеличивать размер. Кроме того, LZW был подвержен критике из-за патентных ограничений, что стимулировало разработку альтернативных методов, таких как Deflate (используемый в PNG) и LZMA.

Личная жизнь

Якоб Зив женат, имеет троих детей. Он продолжает заниматься научной деятельностью, читает лекции и участвует в конференциях. В свободное время увлекается историей науки и философией.

Источники

• Ziv, J., Lempel, A. «A Universal Algorithm for Sequential Data Compression». IEEE Transactions on Information Theory, 1977.
• Ziv, J., Lempel, A. «Compression of Individual Sequences via Variable-Rate Coding». IEEE Transactions on Information Theory, 1978.
• Welch, T. A. «A Technique for High-Performance Data Compression». Computer, 1984.
• Биография Якоба Зива на сайте Техниона (Technion – Israel Institute of Technology).
• Статья «Lempel-Ziv-Welch» в энциклопедии «Encyclopedia of Computer Science».
• Материалы премии Маркони (Marconi Society).
• Официальные документы IEEE (Institute of Electrical and Electronics Engineers).