company_banner

Профессор Яаков Зив: автор метода сжатия данных без потерь

    Яаков Зив разработал то, что мы привыкли называть термином lossless data compression — сжатие данных без потерь. Его работы стали основой для технологий, которыми мы пользуемся и по сей день, от GIF и PDF до ZIP и MP3. 

    Должно быть, Зив сказочно богат? Увы, нет.

    В 1927 году родители Зива, представители интеллигенции, эмигрировали из СССР. Будущий математик и изобретатель родился уже в Израиле, в Тверии. Когда Яакову исполнилось 3 года, семья переехала в Раанану (пригород Тель-Авива) — отцу предложили должность директора первой школы в городке. Мать Зива получила литературное образование в Москве. Перебравшись в Израиль, она заняла пост в Совете женщин-трудящихся при федерации профсоюзов страны. Старший брат Зива, родившийся еще в СССР, поступил в армию и впоследствии участвовал в создании местного образовательного департамента.

    С ранних лет Зив проявлял технические способности. Когда ему было восемь, путем нехитрых манипуляций он превратил свой пюпитр (мальчика учили играть на скрипке) в торшер. Свое изобретение он подарил родителям: «Им понравилось… они называли этот торшер Янкеле» — со смехом вспоминает Зив.

    Несколькими годами позже, когда ему исполнилось 11, Зив обнаружил в семейной библиотеке русскоязычную книгу, в которой, помимо прочего, содержалось иллюстрированное описание радиопередатчика. Русским языком он владел очень слабо, так что пришлось долго и упорно, при помощи словаря, переводить и осваивать текст. В итоге ему удалось самостоятельно построить это устройство из металлической катушки от пластыря и круглых дверных ручек. Предполагалось, что искра будет «прыгать» между этими самыми ручками. При первой же возможности, когда родители отлучились из дома, он воткнул свое изобретение в розетку. Разумеется, с плачевным итогом: вспышка, короткое замыкание и вылетевшие пробки.

    Приблизительно такое устройство Зив увидел на фотографии в своей книге
    Приблизительно такое устройство Зив увидел на фотографии в своей книге

    Все регалии Зива перечислены на странице Википедии.

    О хитрых пилотах

    Зив окончил гимназию «Герцлия» и в 16 лет с началом войны за независимость был призван в Армию обороны Израиля. Первое время он служил в охране: несмотря на юный возраст он получал полный солдатский паек, включавший, помимо прочего, канадские сигареты. По словам Зива, иногда удавалось обменять их с кем-то из заключенных на шоколадку.

    Скучная, монотонная служба не устраивала Зива: спустя некоторое время он услышал, что в Тель-Авиве открылись курсы инженеров обслуживания радаров. Эта позиция показалась ему куда более интересной, нежели текущая служба и перспектива обучаться метеорологии (буквально в то же самое время для него пришло соответствующее назначение). После некоторой путаницы — Зив самовольно посещал курсы инженеров — ему позволили продолжить обучение. Зива назначили командиром мобильной радиолокационной системы американского производства. Непосредственно радар состоял из трех ящиков метр на метр каждый. Сверху на них были установлены вращающиеся антенны. Зив отвечал за сборку и эксплуатацию устройства. 

    Если верить бумагам, карьера Зива на этом посту была более чем успешной. Так, он был поощрен командованием, когда заметил, что израильские пилоты зачастую «срезают» путь, самовольно пролетая над территорией Сектора Газа. Правда, позднее выяснилось, что важное наблюдение — следствие банальной ошибки: «Работать с картой из-за отсутствия компаса мне приходилось на глаз. Конечно, я более-менее представлял себе границы Израиля, но в итоге чересчур сдвинул их направо» — смеется Зив.

    Из Хайфы в Тель-Авив

    Зив встретил Авраама Лемпеля, своего будущего партнера по разработке революционного алгоритма сжатия, практически на боевом посту. Оказалось, оба инженера уже работали в Технионе, но именно долгие поездки из Хайфы на базу в Тель-Авиве помогли им сдружиться. 

    Слева направо: Яаков Зив, основатель Qualcomm Эндрю Витерби и Абрахам Лемпель
    Слева направо: Яаков Зив, основатель Qualcomm Эндрю Витерби и Абрахам Лемпель

    Коллега Зива вспоминает: «[Зив] скромный и тихий. Он мог пройти мимо вас в Технионе, и если бы вы не знали, кто он такой, приняли бы его за кого-то из обслуги, например, за смотрителя. И только во время работы с ним, во время обсуждения становилось ясно: перед вами умнейший человек. Возможно, самый умный из тех, кто находится в комнате.»

    В 1975 году Зив и Лемпель вместе работали над доказательством одного математического утверждения в области сжатия данных. Безусловно, технологии сжатия уже активно применялись, однако быстрого и эффективного метода сжатия без потерь все еще не существовало. Алгоритм Лемпеля-Зива появился на свет в 1977 году. Его новизна заключалась в том, что он был способен обрабатывать данные на лету:

    «Может показаться, что мы заперлись в комнате и несколько недель пыхтели над математической задачей. Что ж, всё было не так просто», — говорит Зив. «Нам потребовалось почти два года споров и дискуссий, чтобы выйти на результат».

    Зив и Лемпель не могли запатентовать свой алгоритм, поскольку в то время патентов на ПО не существовало, только на само оборудование. Алгоритм быстро набрал популярность и послужил основой для множества важных разработок. А спустя несколько лет, когда патентование программного обеспечения стало возможным в США, небольшая контора из Лос-Анджелеса практически присвоила алгоритм Лемпеля-Зива, чтобы «стричь» роялти с Microsoft — компания как раз включила продукт, основанный на этом алгоритме, в свою ОС.

    Профессор Зив в 1971 году
    Профессор Зив в 1971 году

    Обе компании попросили израильских ученых проконсультировать их и выступить в качестве свидетелей-экспертов в суде. «Маленькая компания, не помню, как она называлась, пригласила нас к себе» — вспоминает Зив. «И у них было две аудитории для лекций — одна называлась «Лемпель», а другая — «Зив». Это было очень забавно».

    В конечном итоге коллеги заняли сторону Microsoft. Кстати, консалтинговое соглашение предусматривало почасовую оплату их работы, включая время перелета. По пути в США самолет пошел на вынужденную посадку из-за снежной бури. Тысячи пассажиров застряли в аэропорту почти на сутки. Но только двоим повезло получить солидное вознаграждение за вынужденный простой.

    Билл Гейтс сам явился в суд. Он пришел в футболке с надписью «Пришел, увидел, купил». Судья выгнал его и велел переодеться. В конце концов Гейтс действительно приобрел компанию-конкурента и получил исключительные права на патент и всю причитающуюся прибыль.

    Позднее Зив разработал еще один алгоритм сжатия данных, на сей раз совместно с Аароном Вайнером из Bell Laboratories. Алгоритм позволял на лету сжимать кадры с камер, (например, на футбольном матче), и одновременно транслировать их.

    Между армией и наукой

    Технион сыграл важную роль в жизни Зива. По окончании учебы Зив поступил в магистратуру, которую совмещал со стажировкой в научном департаменте Министерства обороны (позднее — Rafael, производитель вооружения, входит в четвёрку крупнейших израильских фирм-экспортёров вооружений). Его руководителем был знаменитый профессор Давид Бергман.

    По словам Зива, в те годы в Rafael приходили работать талантливые молодые люди, которые «знали, что ничего не знают». 

    «Все понимали, что для разработки порученных нам систем необходимо повышать квалификацию. И мы учились как дети в ультраортодоксальной школе: поглощали книгу за книгой, работали сообща. Другого выхода у нас не было».

    Зив и проф. Моше Закаи, 1973
    Зив и проф. Моше Закаи, 1973

    По возвращении все мы поступили на работу в Технион. Это произвело революцию: за границей мы изучали дисциплины, которых в институте попросту не существовало» — вспоминает Зив.

    По словам ученого, текущая политика государства в отношении молодых и перспективных ученых вызывает у него беспокойство.

    Случайная роль Говарда Хьюза

    Несмотря на огромное количество научной работы, Зиву удалось ощутить дух предпринимательства и даже насладиться некоторыми плодами коммерческой работы. Ему помог собственный сотрудник Йосси Варди, нанятый им в Rafael и известный ныне как «крестный отец израильской технологической промышленности». А сын Варди основал компанию Mirabilis, разработавшую знаменитую ICQ.

    Йосси Варди, 2015
    Йосси Варди, 2015

    В 1969 году Варди пригласил Зива к участию в стартапе под названием Tekem (на иврите — слово-синоним передовых технологий). Де-факто, это была одна из первых израильских компаний, специализировавшихся на разработке программного обеспечения. Стартап «взлетел» и обзавелся более чем 300 сотрудниками (позднее он послужил основой для компании Ness Digital Engineering).

    Но в начале пути молодая компания пережила несколько потрясений. Во время Войны Судного дня (1973) большая часть сотрудников была призвана в армию. Денег не хватало, и Зив был вынужден заложить собственную квартиру, чтобы получить ссуду в банке. Спас Tekem пионер-летчик, миллиардер и кинопродюсер Говард Хьюз: вышло так, что медийному воротиле необходимо было вложиться в израильскую компанию, чтобы доказать, что он ведет бизнес и в этой стране. К счастью, он выбрал Текем.

    Вот, что говорит о своем друге и коллеге сам Варди: «Яаков, как и все его поколение, чувствовал на себе ответственность, будто он своими руками строит свою страну 24 часа в сутки, семь дней в неделю. Логика его работы всегда заключалась в том, какое решение принесет наибольшую экономическую и оборонную выгоду Израилю. Он воспринимал себя строителем не только технологической инфраструктуры, но и «человеческой». Днем он работал над своими проектами, а по вечерам обучал новое поколение инженеров в Технионе.

    Зив женат, у него четверо детей. В последние годы он очень плохо видит — виной тому наследственное заболевание.

    «У меня есть устройство OrCam», — объясняет Зив. Оно фиксируется на очках и помогает людям с ослабленным зрением. «Мне оно очень нравится, однако это не панацея. OrCam помогает только тем, кто еще способен видеть предметы, но не может прочесть текст. Сам я пользуюсь этим прибором нечасто — в основном, чтобы проверить налоговую отчетность. Однако по-настоящему мне интересны технические материалы, чертежи, схемы. К сожалению, даже OrCam мне здесь не помощник» — сетует Зив.

    Каждый день Зив звонит своему старшему сыну Ноаму, который живет в Калифорнии. Он читает отцу электронные письма и отвечает на них под диктовку. Ноам работает в сфере ИТ и является консультантом по биотехнологиям. 

    Зив по-прежнему старается быть в курсе дел в своей области. Много времени он проводит за прослушиванием MP3-книг. Да-да, пользуется отголосками той самой технологии, которую помог разработать еще в 1970-х. В разговоре он по-прежнему остроумен и красноречив, всегда рад говорить о литературе. «В настоящее время я читаю книгу Тары Вестовер «Образованная», - говорит Зив. «А недавно закончил читать биографию Генриетты Сольд «Лидерство без границ» на иврите. Иногда я почитываю даже триллеры. Но, видите ли, больше десяти трупов в неделю осилить сложно» — говорит Зив. И смеется удачной шутке.

    Источник

    CloudMTS
    Виртуальная инфраструктура IaaS

    Комментарии 24

      +12
      Каким боком mp3 затесался в ряды «lossless data compression»?
        +12
        Пометили бы статью «перевод», написали бы комментарий от переводчика что автор перепутал 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

        You’ve probably never heard of him, but you have certainly used technology based on his mathematical inventions — most famously lossless compression of data which enables us to use files like PDF, GIF, MP3 and countless others.


        (есть вообще какие-то санкции для тех кто не оформляет посты-переводы как перевод? хотя это корп блог. им всё можно.)
          0

          Лично мне не мешает, что статья — перевод. Главное, чтобы читалось хорошо.

            +1

            Проблема не в самом переводе, а оформлении — как минимум некрасиво выдавать переводы за свои статьи.

            +3
            Я ошибся.
            en.wikipedia.org/wiki/LZ77_and_LZ78
            Это действительно lossless алгоритмы.
            +5

            У меня есть подозрение, что в сжатии с потерями используют в том числе алгоритмы сжатия без потерь на каких-то этапах.

              +3
              Да, коэф-ты после FFT (что в MP3 что в JPEG) квантуются и ужимаются методом Хаффмана, но не LZW.
              +2
              так в мп3 потери не от сжатия, там просто отбрасывается то что человеческое ухо не слышит а остальное сжимается уже без потерь
                0

                А в жпеге потери тоже не от сжатия, там просто дискретным косинусоидальным преобразованием отбрасывается всё то, что человеческий глаз не слышит, а остальное сжимается уже без потерь? :-)

                  +1
                  Да, остальное сжимается без потерь.
                  Полученные коэффициенты после ДКП квантуются (вот тут как раз потери возникают) и потом сжимаются методом Хаффмана (который lossless) и укладываются в файл.
                    0

                    Тут вопрос терминологии, в таком случае надо делать ремарку отделять понятия "кодек" и "компрессор", тогда да — можно сказать, что в кодеке мп3 из-за именно компрессии потерь не возникает. Иначе исходный коммент звучит слегка нелепо.


                    Понятно, что в основе многих систем сжатия с потерями будет лежать сжатие без потерь на каком-то этапе — просто потому что раз уж жмём, почему бы и не дожать, раз уж можем.

                      0
                      Кодек — это сокращение от кодер/декодер, компрессор это и есть кодер.
                      Сжатие достигается путем отбрасывания младших бит у коэффициентов ДКП высокочастотных составляющих + дополнительное уменьшение числа бит на коф-т за счет кодирования методом Хаффмана (арифметическое сжатие).
                        0
                        Сжатие достигается путем отбрасывания младших бит у коэффициентов ДКП высокочастотных составляющих


                        Сначала режут высокочастотные компоненты преобразования ДКП, а потом квантуют низкочастотные. Грубо говоря, из 64 коэффициентов ДКП преобразования 8х8 оставляют 5-6, остальные обнуляют. Потом оставшиеся 5-6 квантуют. После квантования бинаризация строк, затем уже сжатие бинарных строк без потерь различными методами: это может быть и алгоритм Хаффмана, а может быть и простое Run-Length кодирование.

                        Арифметическое сжатие — это уже другой, более сложный алгоритм. Применяется начиная с H.264.

                        Для преобразования двумерной матрицы коэффициентов в одномерную используют порядок обхода зигзагом (см. логотип ffmpeg).
                +9
                Очень просто: при переводе предложение было ужато и там потерялась немного информации.
                +4
                Он пришел в футболке с надписью «Пришел, увидел, купил»

                вот ведь… тролль ))))
                  +7
                  Будущий математик и изобретатель родился уже в Израиле

                  Поправьите — тогда это был ещё не Израиль, а Подмандатная Палестина.
                    +1
                    Уже почти 30 лет минуло, как я реализовывал LZW на C (генерация сжатого TIFF для первого отечественного слайд-сканера). Алгорит простой и элегантный. Спасибо дедам!
                      0
                      Вот я придумал (изобрел?) алгоритмы улучшения качества прогноза на текстовых данных (та же суть, что GPT, но без нейронных сетей). Может некторые из них уже где-нибудь и обсуждались, но не суть. Интересно, что мне нужно сделать, что бы их запатентовать? Если я их просто на хабре опишу, то их просто начнут другие использовать, а обо мне даже не вспомнят.
                        0

                        Пробуйте обратиться в патентное бюро. Но вообще если вы выкладываете в открытый доступ с нужной лицензией, то украсть это сложно.

                          0
                          Предполагаю, что с одной стороны при этом будет много бумажной волокиты, которую под силам разгрести только опытным юристам или тем кто с университетских кругов общается с такими бюро и имеет там знакомства. Как минимум нужно быть где-нибудь рядом с таким бюро, занимающимся именно таким направлением, а не по электронной или почтовой переписке это делать.

                          А с другой стороны, это существенно не простое взаимодействие разных алгоритмов, и будут ли там вникать в такие сложности? В общем, думаю что при этом просто потону в разбирательствах и до регистрации не дойдет, а описания где-нибудь останутся.
                        +1
                        Родоначальником методов сжатия данных без потерь был Дэвид Хаффман
                          0
                          Должно быть, Зив сказочно богат? Увы, нет.
                          А разве должен быть сказочно богат? Извините, а за что?
                          Аналогия: найдите того кто решил квадратное уравнение и сделайте его сказочно богатым.

                          При этом премии у Зива имеются, к каждой премии идут гонорары, иногда приличные иногда так себе.
                          Премия Израиля… 75 тысяч шекелей
                          Медаль Ричарда Хэмминга… хз
                          Премия Маркони… 100 тысяч долларов США
                          Фонд Эдуарда Рейна
                          Премия за фундаментальные исследования. Гонорар 25 тысяч евро.
                          Технологическая премия. Гонорар 30 тысяч евро.
                          Культурная премия. Гонорар 10 тысяч евро.
                          Премия Шеннона… хз
                          Премия Париса Канеллакиса… $10 тыс.
                          Ротшильдовская премия… хз
                          BBVA Foundation Frontiers of Knowledge Awards… 400 тыс. евро
                          Медаль почёта IEEE… хз

                          там где стоит «хз» — сходу ценник найти не удалось, ищите сами кому не лень
                          однако же поверхностное нагугленное позволяет сходу оценить масштаб «трагдии» этого наибеднейшего деда ибо ага, похоже он совсем чютка так и не дотянул до нобелевских сумм, какое горе!!! очень жаль бедного дедушку, ну очень жаль
                            0
                            можно зарабатывать моного денег, но при этом не быть богатым. пропивать, например :) или вести научную/благотворительную деятельность «на свои».
                            Зато дед — уважаемый человек с большой семьёй, позитивно вошедший в историю.
                            0
                            «Ну до чего ж на нашего Буншу Ланового похож!» к/ф «Иван Васильевич меняет профессию».

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое