Сейчас 2019 год, и нам пора бы принять решение относительно GIF (нет, речь не об этом решении! Здесь мы никогда не договоримся! — тут речь о произношении в английском, для нас это не актуально — прим. перев.). GIFы занимают огромное количество места (обычно по несколько мегабайт!) что, если вы веб-разработчик, полностью противоречит вашим желаниям! Как веб-разработчик, вы хотите минимизировать вещи, которые пользователям нужно скачать, чтобы сайт загружался быстро. По той же причине вы минимизируете JavaScript, оптимизируете PNG, JPEG, а иногда и конвертируете JPEG в WebP. Но что же делать со старичком GIFом?

Изображения формата JPEG встречаются повсюду в нашей цифровой жизни, но за этим покровом осведомлённости скрываются алгоритмы, устраняющие детали, не воспринимаемые человеческим глазом. В итоге получается высочайшее визуальное качество при наименьшем размере файла – но как конкретно всё это работает? Давайте посмотрим, чего именно не видят наши глаза!

Легко принять, как само собой разумеющееся, возможность отправить фотку другу, и не волноваться по поводу того, какое устройство, браузер или операционную систему он использует – однако так было не всегда. К началу 1980-х компьютеры умели хранить и показывать цифровые изображения, однако по поводу наилучшего способа для этого существовало множество конкурирующих идей. Нельзя было просто отправить изображение с одного компьютера на другой и надеяться, что всё заработает.

Задача сжатия данных в своей простейшей форме может относиться к числам и их обозначениям. Числа можно обозначать числительными («одиннадцать» для числа 11), математическими выражениями («два в двадцатой» для 1048576), строковыми выражениями («пять девяток» для 99999), именами собственными («число зверя» для 666, «год смерти Тьюринга» для 1954), или произвольными их комбинациями. Годится любое обозначение, по которому собеседник сможет однозначно определить, о каком числе речь. Очевидно, что сообщить собеседнику «факториал восьми» эффективнее, чем эквивалентное обозначение «сорок тысяч триста двадцать». Здесь возникает логичный вопрос: какое обозначение для заданного числа самое короткое?

Философ Бертран Рассел в 1908 опубликовал «парадокс Берри», который затрагивает вопрос обозначений чисел с противоположной стороны: какое самое маленькое число, для обозначения которого недостаточно восьмидесяти букв?
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 34⁸⁰ обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 34⁸⁰ чисел. Значит, некое число, не большее чем 34⁸⁰, обозначить таким образом невозможно.

Значит, этому числу будет соответствовать обозначение «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв», в котором всего 78 букв! С одной стороны, это число обязано существовать; с другой, если это число существует, то его обозначение ему не соответствует. Парадокс!

Эта статья может быть интересна тем, кто занимается сжатием данных или хочет написать собственный архиватор.



Статья написана, в основном, по материалам блога, который ведёт Fabian Giesen.

Меня зовут Илья Гольдфарб, я разработчик интерфейсов Яндекса. Мне интересно следить за тем, как развиваются инструменты для сборки фронтенда, поэтому я стараюсь изучать изменения в каждом релизе популярных решений.

В преддверии выхода пятой версии webpack я хочу рассказать о его, казалось бы, минорном релизе 4.26.0 от 19 ноября 2018 года, где неожиданно и без объявления войны изменилась версия минификатора по умолчанию. Раньше это был пакет UglifyJS, теперь же используется Terser, форк UglifyES — ветки UglifyJS, которая может сжимать и ES5, и ES6 код. Terser появился, когда основной майнтейнер отказался поддерживать и развивать UglifyES. Впрочем, UglifyJS тоже прекратил свое развитие с августа 2018 года, когда был выпущен последний релиз. В новом форке исправили некоторые баги и немного отрефакторили код.

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

Вся эта история подвигла меня провести маленькое личное исследование сжатия. Вот вопросы, которые я задал:

• Что лучше сжимает ES5, Terser или UglifyJS?
• Что быстрее загружается: сжатая версия ES5 от Terser или от UglifyJS?
• Какая версия весит больше: ES5 или ES6? И как на это влияет TypeScript?
• Большая ли разница между настройками по умолчанию и ручной настройкой?
• А если не webpack? Кто выдаёт сборку меньшего размера, Rollup или webpack?

Вступление

В данной статье я расскажу вам о широко известном алгоритме Хаффмана, и вы наконец разберетесь, как все там устроено изнутри. После прочтения вы сможете своими руками(а главное, головой) написать архиватор, сжимающий реальные, черт подери, данные! Кто знает, быть может именно вам светит стать следующим Ричардом Хендриксом!

Да-да, об этом уже была статья на Хабре, но без практической реализации. Здесь же мы сфокусируемся как на теоретической части, так и на программерской. Итак, все под кат!

Дисклеймер: исследование началось в 2013 году, так что если считаете некоторые методы глупыми и опасными — вы правы, так и было. Тем не менее, я многому научился в процессе.

Вступление
Всё началось за несколько месяцев до рождения моего первого ребёнка. Мы с женой всегда хотели купить крутой фотоаппарат Leica и вдруг поняли, что если не купим сейчас, то уже долго не сможем это сделать. Поэтому мы заказали камеру M240 и… бум, нас поставили в очередь на полгода. Вскоре мне надоело ждать, и я начал изучать их сайт. Моё внимание сразу привлёк раздел с файлами. Ну, вы можете догадаться, почему… Прошивки!

Я увидел незашифрованный и несжатый файл (m8-2_005.upd), который начинается с магии PWAD. Узнаёте? Да, всё правильно, это формат Doom Patch WAD. Кажется, ребята любят классику. Формат очень хорошо документирован, так что распарсить его оказалось совсем несложно.

Автор электронной книги — Эдди Османи, один из руководителей разработки Google Chrome

tl;dr

Cжатие изображений всегда должно быть автоматизировано

Оптимизацию графики обязательно надо автоматизировать. О ней легко забыть, рекомендации меняются, да и сам контент может легко проскользнуть мимо конвейера сборки. Для автоматизации при сборке используйте imagemin или libvips. Есть и много других.

Большинство CDN (например, Akamai) и сторонних решений вроде Cloudinary, imgix, Fastly Image Optimizer, Instart Logic SmartVision и ImageOptim API предлагают комплексные автоматизированные решения для оптимизации изображений.

На чтение статей и настройку конфигурации вы потратите время, которое дороже оплаты их услуг (у Cloudinary есть бесплатный тариф). Но если всё-таки не хотите отдавать работу на аутсорсинг по соображениям стоимости или из-за дополнительной latency, то выбирайте приведённые выше варианты с открытым исходным кодом. Проекты Imageflow или Thumbor предлагают альтернативу на собственном хостинге.

Свойства простых чисел редко позволяют работать с ними иначе, чем в виде заранее вычисленного массива — и желательно как можно более объемного. Естественный формат хранения в виде целых чисел той или иной разрядности страдает при этом некоторыми недостатками, которые становятся существенными при росте объема данных.

 

Так, формат 16-разрядных беззнаковых целых при размере такой таблицы около 13 килобайт вмещает всего лишь 6542 простых числа: вслед за числом 65531 идут значения более высокой разрядности. Такая таблица годится разве что в качестве игрушки.

 

Наиболее ходовой в программировании формат 32-разрядных целых выглядит значительно солиднее — он позволяет хранить около 203 млн простых. Но такая таблица занимает уже около 775 мегабайт.

 

Еще больше перспектив у 64-разрядного формата. Однако при теоретической мощности порядка 1e+19 значений, таблица имела бы размер 64 экзабайта.

В предыдущей статье мы обсудили кодек Opus, который работает на очень низких битрейтах. Но другой кодек стремится достичь ещё более низких битрейтов — это Codec 2.

Codec 2 предназначен для кодирования только речи. И хотя битрейт впечатляет, звук не такой качественный, как в случае Opus, что можно услышать в аудиопримерах. Тем не менее, в сочетании с нейросетью (WaveNet) кодек демонстрирует впечатляющие результаты.


Слои нейронной сети WaveNet

В конце прошлого месяца 2ГИС начал отображать подъезды. Входы в организации мы показываем аж с 2013 года, а подъезды — вроде бы те же входы. Так почему только сейчас? Все внутренние продукты и процессы готовы, всего-то нужно дособрать ещё чуть-чуть да подправить отображение в UI.

Кроме стандартного ответа «Были другие приоритеты» есть и не совсем стандартный: «Не всё так просто». Эта статья про то, какие были сложности и как мы их решили.

Этот пост относится к моей статье о вычислении точек на кривых Безье с помощью линейной интерполяции текстур. Расширенный метод распространяется на поверхности Безье и (многомерные) многочлены.

Первоначальное наблюдение состояло в том, что если произвести выборку по диагонали текстуры 2×2, то в качестве выходных данных получатся точки на квадратичной кривой Безье, а опорные точки кривой являются значениями пикселей, как на изображении ниже. Когда я говорю, что вы получаете квадратичную кривую Безье, то выражаюсь буквально и точно. Происходящее можно представить так: интерполяция текстуры буквально выполняет алгоритм де Кастельжо. (Примечание: если в примере ниже значения “B” не равны, то вторая опорная точка будет средним из этих двух значений: расширение злоупотребляет этим, чтобы аппроксимировать больше кривых в меньшее количество пикселей).

AV1 — это новый универсальный видеокодек, разработанный Альянсом за открытые медиа (Alliance for Open Media). Альянс взял за основу кодек VPX от Google, Thor от Cisco и Daala от Mozilla/Xiph.Org. Кодек AV1 превосходит по производительности VP9 и HEVC, что делает его кодеком не завтрашнего, а послезавтрашнего дня. Формат AV1 свободен от любых роялти и всегда останется таковым с разрешительной лицензией свободного и открытого ПО.

Тройственная платформа

Кто следил за развитием Daala, тот знает, что после формирования Альянса за открытые медиа (AOM) Xiph и Mozilla предложили наш кодек Daala как один из базисов для нового стандарта. Кроме него, компания Google представила свой кодек VP9, а Cisco представила Thor. Идея заключалась в том, чтобы создать новый кодек в том числе на основе этих трёх решений. С того момента я не публиковал никаких демо о новых технологиях в Daala или AV1; в течение долгого времени мы мало что знали об окончательном кодеке.

Около двух лет назад AOM проголосовал за то, чтобы основать фундаментальную структуру нового кодека на базе VP9, а не Daala или Thor. Компании-члены альянса хотели в кратчайший срок получить полезный кодек без роялти и лицензирования, поэтому выбрали VP9 как наименее рискованный вариант. Я согласен с таким выбором. Хотя Daala выдвинули кандидатом, но я всё-таки думаю, что и устранение блочных артефактов трансформацией внахлёст (lapping arrpoach), и техники частотной области в Daala тогда (да и сейчас) ещё недостаточно созрели для реального развёртывания. В Daala по-прежнему оставались нерешённые технические вопросы, а выбор в качестве отправной точки VP9 решал большинство этих проблем.

Не так давно в Яндекс приезжал Геннадий Пехименко — профессор Университета Торонто и PhD Университета Карнеги-Меллон. Он прочитал лекцию об алгоритмах кодирования, которые позволяют обходить проблему ограничения памяти GPU при обучении глубоких нейронных сетей.


— Я вхожу в несколько групп Университета Торонто. Одна из них — Computer Systems and Networking Group. Есть еще моя собственная группа — EcoSystem Group. Как видно из названий групп, я не специалист непосредственно в машинном обучении. Но нейронные сети сейчас достаточно популярны, и людям, которые занимаются компьютерной архитектурой и сетями, компьютерными системами, приходится сталкиваться с этими приложениями на постоянной основе. Поэтому последние полтора-два года этой темой я тоже плотно занимаюсь.

«Вот бы распаковать эти игровые архивы и посмотреть что там внутри!», — наверное думал про себя, хотя бы раз, каждый геймер, который хотел понять, как устроена его любимая игра.

К счастью, сегодня большинство разработчиков не только не препятствуют изучению своих игр, но даже наоборот, делают всё, для того, чтобы игроки изменяли и дополняли игры сами. Но даже если официальной документации нет, то для 99% игр можно найти уже готовые программы для распаковки.

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

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

Обновления безопасности

Компания Microsoft выпустила обновления безопасности для операционных систем Windows, исправляющие критические уязвимости в процессорах Intel, AMD и ARM, которые исправляют раскрытые на днях уязвимости Meltdown и Spectre. Патчи могут привести к снижению производительности на затронутых системах и не только. Ниже будут приведены 2 скриншота и пояснения к ним.

Экспресс-тест на примере 7-Zip

Внезапно ваш диск под завязку забит фотографиями и видео, а впереди новые поездки. Что делать, покупать новый, арендовать дисковое пространство на облаке, или может лучше сжать видео файлы через ffmpeg?

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

На Yelp хранится более 100 миллионов пользовательских фотографий, от картинок ужинов и причёсок до одной из наших последних фич, #yelfies. Эти изображения составляют основную часть трафика для пользователей приложения и веб-сайта, а их хранение и передача обходятся недёшево. Стараясь предоставить людям наилучший сервис, мы усиленно работали над оптимизацией всех фотографий и добились среднего уменьшения размера на 30%. Это экономит людям время и трафик, а также сокращает наши расходы на обслуживание этих изображений. Ах да, и мы сделали это без ухудшения качества фотографий!

Исходные данные

Yelp хранит пользовательские фотографии уже 12 лет. Мы сохраняем lossless-форматы (PNG, GIF) как PNG, а все остальные форматы в JPEG. Для сохранения файлов используются Python и Pillow, а загрузки фотографий начинаются примерно с такого сниппета:

# do a typical thumbnail, preserving aspect ratio
new_photo = photo.copy()
new_photo.thumbnail(
    (width, height),
    resample=PIL.Image.ANTIALIAS,
)
thumbfile = cStringIO.StringIO()
save_args = {'format': format}
if format == 'JPEG':
    save_args['quality'] = 85
new_photo.save(thumbfile, **save_args)

Для многих не секрет, что большинство изображений в форматах JPEG и PNG содержат избыточную информацию, которая может быть удалена без потери качества. Обычно это достигается за счет эвристических алгоритмов перебора различных параметров компрессии и выбора наименее затратного варианта. Применение оптимизаторов особенно важно на файлах, которые используются на посещаемых сайтах, для экономии дискового пространства, трафика и уменьшения времени загрузки страниц у пользователей. Программ такого типа довольно много и мы поставили себе цель найти какие же оптимизаторы сжимают лучше и работают быстро.

В тесте принимали участие следующие программы.

Для PNG:

1. Leanify 0.4.3 (x64)
2. pingo v0.79c
3. pinga v0.09
4. OptiPNG 0.7.6
5. pngout
6. PngOptimizer 2.5 (x64)
7. advpng aka AdvanceCOMP v1.23
8. ECT 0.6 (x64)
9. TruePNG 0.6.2.2
10. pngwolf-zopfli 1.1.1 (x64)

Для JPEG:

1. Leanify 0.4.3 (x64)
2. pingo v0.79c
3. ECT 0.6 (x64)
4. mozjpeg 3.2 (x64)
5. jhead 3.00
6. jpegoptim v1.4.4 (x64)
7. jpegtran

Об авторе. Арчи Рассел (Archie Russell) — инженер бэкенда во Flickr

Одна из самых затратных статей в работе сервиса вроде Flickr — это хранение. За последние годы мы описывали различные техники для снижения стоимости: использование COS, динамическое изменение размера на GPU и перцептивное сжатие. Эти проекты были очень успешны, но мы продолжали терять много денег на хранении данных.

В начале 2016 года мы поставили перед собой задачу выйти на новый уровень — продержаться целый год вообще не закупая новые носители информации. Используя различные техники, нам это удалось.

История затрат

Небольшие арифметические расчёты на салфетке показывают, что затраты на хранение представляют собой предмет реального беспокойства. В день с высокой посещаемостью пользователи Flickr загружают до 25 млн фотографий. Каждая из них требует в среднем 3,25 МБ, что в сумме составляет 80 ТБ. Наивно размещая их на облачном хостинге вроде S3 фотографии одного дня потянут на $30 тыс. в год и продолжат генерировать затраты каждый последующий год.