Яаков Зив – «отец» современных архиваторов

Беляев Е.А., Шалыто А.А.

Яаков Зив

Яаков Зив (Jacob Ziv) родился 27.11.1931 г. в городе Тверия (ныне Израиль). Его родители в 1927 г. эмигрировали из СССР. В прошлом году Яакову Зиву исполнилось 90 лет. В 1954 и 1957 гг. он получил степени бакалавра и магистра в Израильском технологическом институте («Технион»), который находится в городе Хайфа (Израиль) и является сильнейшим техническим вузом страны.

Начиная с 1955 г., он занимается исследованиями в области теории связи. До 1959 г. работал старшим научным сотрудником Министерства обороны Израиля. После этого был аспирантом в Массачусетском технологическом институте (MIT, США), где 1962 г. получил степень доктора философии (PhD). В том же году Зив вернулся в Израиль и не только снова начал работать в Министерстве обороны Израиля, где работал, до 1968 г., но и преподавать в «Технионе», где он трудится и по сей день в должности почётного профессора. Параллельно с преподаванием он несколько лет работал в Bell Laboratories (статья в Википедии), которая в то время была невероятно престижна.

Зив имеет выдающиеся результаты в области универсального сжатия данных без потерь (архивирования), полученные совместно с Абрахамом Лемпеломстатья ( в Википедии) (Abraham Lempel), которые оказали огромное влияние на теорию и практику сжатия данных.

К таким результатам прежде всего относится однопроходный алгоритм LZ77 (см. Википедию), который был опубликован в 1977 г. Этот алгоритм хранит в памяти некоторое число последних закодированных букв («скользящее окно»). Затем выполняется поиск максимально длинной последовательности из новых букв, совпадающей с последовательностью букв в окне, а после этого в выходной файл записывается ссылка на позицию в окне и число совпавших символов.

На основе алгоритма LZ77 разработан алгоритм LZSS, опубликованный Сторером (Storer) и Сжимански (Szymanski) в 1982 г. В отличие от LZ77, этот алгоритм не допускает случаев, когда число бит на ссылку в окне оказывается больше, чем число бит, необходимое на непосредственную передачу найденной последовательности. Поэтому, в ранних версиях архиваторов, таких как ARJ (см. статью в Википедии) и RAR (см. Википедию) алгоритм LZSS использовался в качестве основного алгоритма сжатия.

Алгоритм LZMA (Lempel-Ziv-Markov chain Algorithm), использующий словарное сжатие, в чем-то схожее с алгоритмом LZ77, создавался с 1996—1998 гг. и впервые был использован в архиваторе 7-Zip, разработанным Игорем Павловым. Этот алгоритм описан по следующим адресам: https://ru.wikipedia.org/wiki/LZMA и https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_LZMA.

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

Wiki-конспекты, описывающих эти алгоритмы,  приведены здесь:  (https://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_LZ77_и_LZ78).

Также широко известны результаты Зива, полученные им совместно с Аароном Винером в 1976 г. Они являются расширением теоремы распределённого кодирования информации, доказанной Девидом Слепианом и Джеком Вольфом в 1973 г.

Эти результаты достаточно долго не использовались на практике, но с появлением сенсорных сетей возникла необходимость в передаче зависимых данных от маломощных устройств, они стали востребованы. Другим примером использования указанных результатов является передача видеоинформации с нескольких камер, снимающих одну и ту же сцену со слегка различающихся ракурсов или сжатие видеоинформации, при которой каждый кадр сжимается отдельно друг от друга, а в процессе декодирования используется межкадровая схожесть. Наиболее известными примерами кодеков видеоинформации на основе результатов, полученных Зивом и Винером являются DISCOVER и openDVC. Они позволяют получить более высокое качество сжатия при покадровом кодировании по сравнению с кодеками стандарта H.264/AVC.

В 2021 г. «за фундаментальный вклад в теорию информации и технологию сжатия данных» профессор Зив  награжден престижнейшей наградой –  «Медалью Почета IEEE (см. статью в Википедии)» (The IEEE Medal of Honor) Института инженеров электротехники и электроники (Institute of Electrical and Electronics Engineers – IEEE), которая вручается ежегодно с 1919 г. только одному человеку в мире в год. Так как она присуждается «за выдающийся вклад в электронику и электротехнику», то Зив оказался в компании известнейших учёных и инженеров, среди которых, в частности, есть такие классики как Ли де Форест, Хартли, Зворыкин, Найквист, Шеннон, Таунс, Габор, Бардин, Форрестер, Нойс, Беллман, Шокли, Тьюки, Килби, Галлагер, Заде, Гроув и Холоньяк и др. Среди них есть лауреаты и других премий и, в частности, Нобелевской.

До этого Зив также получил ещё несколько очень престижных научных наград: премию Израиля (1993), медаль Ричарда Хэмминга (1995), премию Маркони (1995), премию Эдуарда Рейна (1996), премию Шеннона (1997), премию Канелликиса (1997), Ротшильдовскую премию (2002), испанскую премию BBVA Foundation Frontiers of Knowledge Awards (2008).

Об авторе: Анатолий Шалыто - докт. техн. наук, профессор, Университет ИТМО
Беляев Евгений Александрович, Университет ИТМО
Помещена в музей с разрешения авторов 8 августа 2022