Вступление

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

В результате напишем простенький архиватор. Об этом уже была статья на Хабре, но без практической реализации. Теоретический материал текущего поста взят из школьных уроков информатики и книги Роберта Лафоре «Data Structures and Algorithms in Java». Итак, все под кат!

Дисклеймер: исследование началось в 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% игр можно найти уже готовые программы для распаковки.

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

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