Яаков Зив разработал то, что мы привыкли называть термином lossless data compression — сжатие данных без потерь. Его работы стали основой для технологий, которыми мы пользуемся и по сей день, от GIF и PDF до ZIP и MP3.
Должно быть, Зив сказочно богат? Увы, нет.
В 1927 году родители Зива, представители интеллигенции, эмигрировали из СССР. Будущий математик и изобретатель родился уже в Израиле, в Тверии. Когда Яакову исполнилось 3 года, семья переехала в Раанану (пригород Тель-Авива) — отцу предложили должность директора первой школы в городке. Мать Зива получила литературное образование в Москве. Перебравшись в Израиль, она заняла пост в Совете женщин-трудящихся при федерации профсоюзов страны. Старший брат Зива, родившийся еще в СССР, поступил в армию и впоследствии участвовал в создании местного образовательного департамента.
С ранних лет Зив проявлял технические способности. Когда ему было восемь, путем нехитрых манипуляций он превратил свой пюпитр (мальчика учили играть на скрипке) в торшер. Свое изобретение он подарил родителям: «Им понравилось… они называли этот торшер Янкеле» — со смехом вспоминает Зив.
Несколькими годами позже, когда ему исполнилось 11, Зив обнаружил в семейной библиотеке русскоязычную книгу, в которой, помимо прочего, содержалось иллюстрированное описание радиопередатчика. Русским языком он владел очень слабо, так что пришлось долго и упорно, при помощи словаря, переводить и осваивать текст. В итоге ему удалось самостоятельно построить это устройство из металлической катушки от пластыря и круглых дверных ручек. Предполагалось, что искра будет «прыгать» между этими самыми ручками. При первой же возможности, когда родители отлучились из дома, он воткнул свое изобретение в розетку. Разумеется, с плачевным итогом: вспышка, короткое замыкание и вылетевшие пробки.
Все регалии Зива перечислены на странице Википедии.
О хитрых пилотах
Зив окончил гимназию «Герцлия» и в 16 лет с началом войны за независимость был призван в Армию обороны Израиля. Первое время он служил в охране: несмотря на юный возраст он получал полный солдатский паек, включавший, помимо прочего, канадские сигареты. По словам Зива, иногда удавалось обменять их с кем-то из заключенных на шоколадку.
Скучная, монотонная служба не устраивала Зива: спустя некоторое время он услышал, что в Тель-Авиве открылись курсы инженеров обслуживания радаров. Эта позиция показалась ему куда более интересной, нежели текущая служба и перспектива обучаться метеорологии (буквально в то же самое время для него пришло соответствующее назначение). После некоторой путаницы — Зив самовольно посещал курсы инженеров — ему позволили продолжить обучение. Зива назначили командиром мобильной радиолокационной системы американского производства. Непосредственно радар состоял из трех ящиков метр на метр каждый. Сверху на них были установлены вращающиеся антенны. Зив отвечал за сборку и эксплуатацию устройства.
Если верить бумагам, карьера Зива на этом посту была более чем успешной. Так, он был поощрен командованием, когда заметил, что израильские пилоты зачастую «срезают» путь, самовольно пролетая над территорией Сектора Газа. Правда, позднее выяснилось, что важное наблюдение — следствие банальной ошибки: «Работать с картой из-за отсутствия компаса мне приходилось на глаз. Конечно, я более-менее представлял себе границы Израиля, но в итоге чересчур сдвинул их направо» — смеется Зив.
Из Хайфы в Тель-Авив
Зив встретил Авраама Лемпеля, своего будущего партнера по разработке революционного алгоритма сжатия, практически на боевом посту. Оказалось, оба инженера уже работали в Технионе, но именно долгие поездки из Хайфы на базу в Тель-Авиве помогли им сдружиться.
Коллега Зива вспоминает: «[Зив] скромный и тихий. Он мог пройти мимо вас в Технионе, и если бы вы не знали, кто он такой, приняли бы его за кого-то из обслуги, например, за смотрителя. И только во время работы с ним, во время обсуждения становилось ясно: перед вами умнейший человек. Возможно, самый умный из тех, кто находится в комнате.»
В 1975 году Зив и Лемпель вместе работали над доказательством одного математического утверждения в области сжатия данных. Безусловно, технологии сжатия уже активно применялись, однако быстрого и эффективного метода сжатия без потерь все еще не существовало. Алгоритм Лемпеля-Зива появился на свет в 1977 году. Его новизна заключалась в том, что он был способен обрабатывать данные на лету:
«Может показаться, что мы заперлись в комнате и несколько недель пыхтели над математической задачей. Что ж, всё было не так просто», — говорит Зив. «Нам потребовалось почти два года споров и дискуссий, чтобы выйти на результат».
Зив и Лемпель не могли запатентовать свой алгоритм, поскольку в то время патентов на ПО не существовало, только на само оборудование. Алгоритм быстро набрал популярность и послужил основой для множества важных разработок. А спустя несколько лет, когда патентование программного обеспечения стало возможным в США, небольшая контора из Лос-Анджелеса практически присвоила алгоритм Лемпеля-Зива, чтобы «стричь» роялти с Microsoft — компания как раз включила продукт, основанный на этом алгоритме, в свою ОС.
Обе компании попросили израильских ученых проконсультировать их и выступить в качестве свидетелей-экспертов в суде. «Маленькая компания, не помню, как она называлась, пригласила нас к себе» — вспоминает Зив. «И у них было две аудитории для лекций — одна называлась «Лемпель», а другая — «Зив». Это было очень забавно».
В конечном итоге коллеги заняли сторону Microsoft. Кстати, консалтинговое соглашение предусматривало почасовую оплату их работы, включая время перелета. По пути в США самолет пошел на вынужденную посадку из-за снежной бури. Тысячи пассажиров застряли в аэропорту почти на сутки. Но только двоим повезло получить солидное вознаграждение за вынужденный простой.
Билл Гейтс сам явился в суд. Он пришел в футболке с надписью «Пришел, увидел, купил». Судья выгнал его и велел переодеться. В конце концов Гейтс действительно приобрел компанию-конкурента и получил исключительные права на патент и всю причитающуюся прибыль.
Позднее Зив разработал еще один алгоритм сжатия данных, на сей раз совместно с Аароном Вайнером из Bell Laboratories. Алгоритм позволял на лету сжимать кадры с камер, (например, на футбольном матче), и одновременно транслировать их.
Между армией и наукой
Технион сыграл важную роль в жизни Зива. По окончании учебы Зив поступил в магистратуру, которую совмещал со стажировкой в научном департаменте Министерства обороны (позднее — Rafael, производитель вооружения, входит в четвёрку крупнейших израильских фирм-экспортёров вооружений). Его руководителем был знаменитый профессор Давид Бергман.
По словам Зива, в те годы в Rafael приходили работать талантливые молодые люди, которые «знали, что ничего не знают».
«Все понимали, что для разработки порученных нам систем необходимо повышать квалификацию. И мы учились как дети в ультраортодоксальной школе: поглощали книгу за книгой, работали сообща. Другого выхода у нас не было».
По возвращении все мы поступили на работу в Технион. Это произвело революцию: за границей мы изучали дисциплины, которых в институте попросту не существовало» — вспоминает Зив.
По словам ученого, текущая политика государства в отношении молодых и перспективных ученых вызывает у него беспокойство.
Случайная роль Говарда Хьюза
Несмотря на огромное количество научной работы, Зиву удалось ощутить дух предпринимательства и даже насладиться некоторыми плодами коммерческой работы. Ему помог собственный сотрудник Йосси Варди, нанятый им в Rafael и известный ныне как «крестный отец израильской технологической промышленности». А сын Варди основал компанию Mirabilis, разработавшую знаменитую ICQ.
В 1969 году Варди пригласил Зива к участию в стартапе под названием Tekem (на иврите — слово-синоним передовых технологий). Де-факто, это была одна из первых израильских компаний, специализировавшихся на разработке программного обеспечения. Стартап «взлетел» и обзавелся более чем 300 сотрудниками (позднее он послужил основой для компании Ness Digital Engineering).
Но в начале пути молодая компания пережила несколько потрясений. Во время Войны Судного дня (1973) большая часть сотрудников была призвана в армию. Денег не хватало, и Зив был вынужден заложить собственную квартиру, чтобы получить ссуду в банке. Спас Tekem пионер-летчик, миллиардер и кинопродюсер Говард Хьюз: вышло так, что медийному воротиле необходимо было вложиться в израильскую компанию, чтобы доказать, что он ведет бизнес и в этой стране. К счастью, он выбрал Текем.
Вот, что говорит о своем друге и коллеге сам Варди: «Яаков, как и все его поколение, чувствовал на себе ответственность, будто он своими руками строит свою страну 24 часа в сутки, семь дней в неделю. Логика его работы всегда заключалась в том, какое решение принесет наибольшую экономическую и оборонную выгоду Израилю. Он воспринимал себя строителем не только технологической инфраструктуры, но и «человеческой». Днем он работал над своими проектами, а по вечерам обучал новое поколение инженеров в Технионе.
Зив женат, у него четверо детей. В последние годы он очень плохо видит — виной тому наследственное заболевание.
«У меня есть устройство OrCam», — объясняет Зив. Оно фиксируется на очках и помогает людям с ослабленным зрением. «Мне оно очень нравится, однако это не панацея. OrCam помогает только тем, кто еще способен видеть предметы, но не может прочесть текст. Сам я пользуюсь этим прибором нечасто — в основном, чтобы проверить налоговую отчетность. Однако по-настоящему мне интересны технические материалы, чертежи, схемы. К сожалению, даже OrCam мне здесь не помощник» — сетует Зив.
Каждый день Зив звонит своему старшему сыну Ноаму, который живет в Калифорнии. Он читает отцу электронные письма и отвечает на них под диктовку. Ноам работает в сфере ИТ и является консультантом по биотехнологиям.
Зив по-прежнему старается быть в курсе дел в своей области. Много времени он проводит за прослушиванием MP3-книг. Да-да, пользуется отголосками той самой технологии, которую помог разработать еще в 1970-х. В разговоре он по-прежнему остроумен и красноречив, всегда рад говорить о литературе. «В настоящее время я читаю книгу Тары Вестовер «Образованная», - говорит Зив. «А недавно закончил читать биографию Генриетты Сольд «Лидерство без границ» на иврите. Иногда я почитываю даже триллеры. Но, видите ли, больше десяти трупов в неделю осилить сложно» — говорит Зив. И смеется удачной шутке.
KYuri
Каким боком mp3 затесался в ряды «lossless data compression»?
mapron
Пометили бы статью «перевод», написали бы комментарий от переводчика что автор перепутал lossless и lossy, была бы зачетная статья для Хабра
www.haaretz.com/israel-news/tech-news/.premium-the-man-who-actually-made-the-world-a-better-place-with-data-compression-1.9497904
(есть вообще какие-то санкции для тех кто не оформляет посты-переводы как перевод? хотя это корп блог. им всё можно.)
optemist
Лично мне не мешает, что статья — перевод. Главное, чтобы читалось хорошо.
KvanTTT
Проблема не в самом переводе, а оформлении — как минимум некрасиво выдавать переводы за свои статьи.
mapron
Я ошибся.
en.wikipedia.org/wiki/LZ77_and_LZ78
Это действительно lossless алгоритмы.
Soffort
У меня есть подозрение, что в сжатии с потерями используют в том числе алгоритмы сжатия без потерь на каких-то этапах.
x86128
Да, коэф-ты после FFT (что в MP3 что в JPEG) квантуются и ужимаются методом Хаффмана, но не LZW.
be52
так в мп3 потери не от сжатия, там просто отбрасывается то что человеческое ухо не слышит а остальное сжимается уже без потерь
vladkorotnev
А в жпеге потери тоже не от сжатия, там просто дискретным косинусоидальным преобразованием отбрасывается всё то, что человеческий глаз не слышит, а остальное сжимается уже без потерь? :-)
x86128
Да, остальное сжимается без потерь.
Полученные коэффициенты после ДКП квантуются (вот тут как раз потери возникают) и потом сжимаются методом Хаффмана (который lossless) и укладываются в файл.
vladkorotnev
Тут вопрос терминологии, в таком случае надо делать ремарку отделять понятия "кодек" и "компрессор", тогда да — можно сказать, что в кодеке мп3 из-за именно компрессии потерь не возникает. Иначе исходный коммент звучит слегка нелепо.
Понятно, что в основе многих систем сжатия с потерями будет лежать сжатие без потерь на каком-то этапе — просто потому что раз уж жмём, почему бы и не дожать, раз уж можем.
x86128
Кодек — это сокращение от кодер/декодер, компрессор это и есть кодер.
Сжатие достигается путем отбрасывания младших бит у коэффициентов ДКП высокочастотных составляющих + дополнительное уменьшение числа бит на коф-т за счет кодирования методом Хаффмана (арифметическое сжатие).
RomanArzumanyan
Сначала режут высокочастотные компоненты преобразования ДКП, а потом квантуют низкочастотные. Грубо говоря, из 64 коэффициентов ДКП преобразования 8х8 оставляют 5-6, остальные обнуляют. Потом оставшиеся 5-6 квантуют. После квантования бинаризация строк, затем уже сжатие бинарных строк без потерь различными методами: это может быть и алгоритм Хаффмана, а может быть и простое Run-Length кодирование.
Арифметическое сжатие — это уже другой, более сложный алгоритм. Применяется начиная с H.264.
Для преобразования двумерной матрицы коэффициентов в одномерную используют порядок обхода зигзагом (см. логотип ffmpeg).
nochkin
Очень просто: при переводе предложение было ужато и там потерялась немного информации.