Как стать автором
Обновить
1.8

Сжатие данных *

Упаковываем и распаковываем информацию

Сначала показывать
Порог рейтинга
Уровень сложности

RSync на стероидах с поддержкой Windows

Уровень сложностиСредний
Время на прочтение5 мин
Количество просмотров47K


На Хабре периодически рассказывают о новых инструментах для синхронизации данных. Это интересная тема. Такие программы используются:

  • для синхронизации файлов на разных устройствах,
  • дедупликации,
  • резервного копирования,
  • сжатия.

Малейшая оптимизация даёт экономию трафика, места, ускоряет синхронизацию и общую производительность любых систем. Всё, везде и сразу. В эпоху веб-приложений и клиент-серверной архитектуры со множеством девайсов, которые работают в единой инфраструктуре, синхронизация — Святой Грааль, одна из базовых технологий в компьютерной области.

Кроме того, инструменты синхронизации интересны с алгоритмической точки зрения. Любопытно, как люди умудряются оптимизировать базовые алгоритмы типа rsync, которые вроде бы работают идеально. Но нет, всегда можно придумать что-то получше.
Читать дальше →

Как мы создаём корпоративную почтовую систему нового поколения Mailion. Оптимизация стоимости хранения данных

Уровень сложностиСредний
Время на прочтение22 мин
Количество просмотров3.1K

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

Одна из наиболее ресурсоемких категорий софта сегодня — это системы хранения данных. К ним можно отнести как классические СУБД, так и хранилища различного назначения. В корпоративной почтовой системе Mailion мы используем объектное хранилище собственной разработки — Dispersed Object Store (DOS). Mailion поддерживает одновременную работу до миллиона пользователей, и подобный уровень нагрузки выдвигает существенные требования к производительности и экономической эффективности системы.

Под катом рассказываем, как мы искали оптимальную конфигурацию нашего объектного хранилища, и какие уроки извлекли из этого поиска.

Читать далее

Величайшие программисты XXI века. Юрки Алакуйяла — гений сжатия

Уровень сложностиПростой
Время на прочтение8 мин
Количество просмотров19K
Пару дней назад на Хабре обсуждали, что сжатие информации — главная концепция нашей жизни. И вот перед нами представитель этой самой индустрии. Человек, который видит мир через призму теории информации, энтропии, хаоса и закономерностей.

Мало кто слышал имя Юрки Алакуйяла (@jyzg), но все мы используем его разработки. Картинки JPEG частенько генерируются фантастическим JPEG-энкодером guetzli с применением психовизуальных моделей, а HTTP-трафик в интернете жмётся кодеком brotli, тоже лучшим в своём классе.

Д-р Юрки Алакуйяла — активный член опенсорсного сообщества и исследователь. Работает техлидом Google Research Europe (Швейцария). Среди последних разработок — алгоритмы сжатия JPEG XL, WebP lossless и др.
Читать дальше →

Революционный метод сжатия изображений

Уровень сложностиСредний
Время на прочтение5 мин
Количество просмотров24K

Всем привет! Курс компьютерной графики в том или ином виде присутствует в образовательной программе любой ИТ-специальности. В числе прочего там обязательно проходят форматы графических файлов и затрагивают алгоритмы сжатия изображений. Сегодня я расскажу о новом, современном методе сжатия изображений, который ещё не вошёл ни в один учебник.
Читать дальше →

Сжатие без потерь — главная концепция в нашей жизни

Уровень сложностиПростой
Время на прочтение7 мин
Количество просмотров21K

Бывало так, что из долгой поездки вы помните только несколько моментов? А все отпуска за много лет сливаются в единое целое? А из школьного класса помните фамилии только нескольких человек? Это вовсе не потеря памяти, как может показаться. Наоборот, это признак крайне развитого интеллекта, который научился эффективно сжимать данные.

На самом деле воспоминания из памяти можно вытянуть (разархивировать) через регрессивный гипноз. Просто в данный момент они не нужны, поэтому хранятся в сжатом виде на ленточных накопителях в дальних уголках памяти.

Все мы знаем и используем компьютерные архиваторы: ZIP, RAR, Brotli и т. д. Но мало кто видит в них модель интеллекта. Это даже как-то странно на первый взгляд. Хотя если подумать, то идеальное сжатие — это синоним понимания.
Читать дальше →

Как смотрели нюдсы на древних компьютерах?

Время на прочтение7 мин
Количество просмотров42K


Формат JPEG представили в 1993 году, а GIF — в 1987-м. Но тогда непонятно, как смотрели фотографии девушек на этой прекрасной машине образца 1983 года?

Такой вопрос пришёл мне от читателя обзора портативного компьютера Compaq Portable. Ответ оказался сложнее, чем мы думали. Давайте разберёмся.
Читать дальше →

Хакинг метрик качества видео или как с приходом ИИ все становится намного сложнее

Время на прочтение23 мин
Количество просмотров14K

Сейчас модно писать, что ML пришел туда и все стало отлично, DL пришел сюда и все стало замечательно. А к кому-то пришел сам AI, и там все стало просто сказочно! Возможна ли ситуация, когда к нам пришел волшебный ML/DL и все стало сложнее, тяжелее и на порядок запутаннее? Безусловно! Разберем такой пример.

Десятки лет при сравнении кодеков и алгоритмов обработки видео исследователи использовали старые добрые метрики PSNR и SSIM с довольно простыми формулами и были счастливы. Но прогресс невозможно остановить! На их место пришли новые метрики и… тут выяснилось, что они взламываются.

— Погодите, погодите… — скажет взволнованный читатель, — А как это вообще выглядит, взломать метрику??? 
— Добро пожаловать в 21 век, дорогой товарищ! Благодаря неудержимому прогрессу, сегодня можно хакнуть не только утюг, колонку, автопилот машины и домашний пылесос, но и метрику качества видео.

В этот момент собеседники обычно дружно спрашивают, кому это надо? О, поверьте, есть люди, которым не просто надо, а сильно надо! Представьте себе, что вы руководитель подразделения и у вас жесткие KPI (маркетинг требует обогнать конкурентов, от этого зависят нехилые годовые бонусы у всех сотрудников и особенно у вас). Чтобы улучшить видеокодек на условные 4%, требуются десятки человеко-месяцев труда весьма высокооплачиваемых инженеров, причем, бывает, получается, а бывает, не очень. И тут выясняется, что можно за пару недель работы одного зеленого стажера подшаманить метрику на 7%. Ваши действия? Вспоминается жизненный анекдот «тут-то мне карта и поперла»…

Далее мы популярно затронем взлом методом черного ящика, белого ящика, взлом недифференцируемых метрик (привет дистилляция!) и цирк с дифференцируемыми.

Впрочем обо всем по порядку…

Кому интересен цирк с конями взлом метрик — го под кат.

Читать далее

Сжатие изображений при помощи модели Stable Diffusion

Время на прочтение10 мин
Количество просмотров13K
image

Введение


На сегодняшний день Stable Diffusion является источником вдохновения для сообщества любителей опенсорсного машинного обучения и в то же время источником расстройства для художников всего мира. Мне стало любопытно, что ещё может сделать эта важная технология кроме того, как подвергать угрозе рабочие места профессиональных художников и дизайнеров.

В процессе экспериментов с моделью я обнаружил, что она подходит в качестве чрезвычайно эффективного кодека сжатия изображений с потерями. Прежде чем приступать к описанию своей методики и демонстрации кода, вот несколько результатов модели по сравнению с JPG и WebP с высокой степенью сжатия. Все изображения имеют разрешение 512x512 пикселей:
Читать дальше →

Сжимаем изображения без потерь: какой формат выбрать?

Время на прочтение8 мин
Количество просмотров33K

Одна из тестовых фотографий, сжатие без потерь на 41%

Для сжатия изображений без потерь принято использовать PNG. Его обычно применяют для логотипов, скриншотов, диаграмм, где есть сплошные области с одинаковым цветом. Такие области сжимаются лучше всего: все lossless-кодеки используют классический RLE, то есть кодирование повторов. В некоторых случаях это обеспечивает даже лучший коэффициент сжатия, чем JPEG. И никаких искажений.

Но PNG не используют для фотографий — файлы слишком большие. Однако сейчас, с появлением кодеков нового поколения, ситуация должна измениться. Фотографии будут кодировать без потерь в файлы меньшего размера, а PNG наконец-то уйдёт на покой (см. результаты тестирования в конце статьи).
Читать дальше →

Кто круче rsync? Интересные алгоритмы для синхронизации данных

Время на прочтение7 мин
Количество просмотров25K

Тридж, автор rsync

Что может быть приятнее, чем минимизировать объём бэкапа или апдейта? Это не просто экономия ресурсов, а чистая победа интеллекта над энтропией Вселенной. Исключительно силой разума мы уменьшаем размер файла, сохраняя прежний объём информации в нём, тем самым уменьшая поток фотонов в оптоволокне и снижая температуру CPU. Реальное изменение физического мира силой мысли.

Если без шуток, то все знают rsync — инструмент для быстрой синхронизации файлов и каталогов с минимальным трафиком, который пришёл на замену rcp и scp. В нём используется алгоритм со скользящим хешем, разработанный австралийским учёным, программистом и хакером Эндрю Триджеллом по кличке Тридж (на фото).

Алгоритм эффективный, но не оптимальный.
Читать дальше →

Архитектурные паттерны в распределенных высоконагруженных системах

Время на прочтение8 мин
Количество просмотров21K

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

Читать далее

Как развитие алгоритмов сжатия остановилось 20 лет назад, или о новом конкурсе на 200 тысяч евро

Время на прочтение18 мин
Количество просмотров74K

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

Пост набрал 206 «плюсов», вышел на 2 место топа недели и вызвал оживленную дискуссию, в которой мне больше всего понравился комментарий: «Коммерческого интереса эффективность по сжатию алгоритмов сжатия без потерь сегодня не представляет, в силу отсутствия принципиально более эффективных алгоритмов. Деньги сегодня — в сжатии аудио-видео. И там и алгоритмы другие. Тема сжатия без потерь удобна именно лёгкостью верификации алгоритма, и не слегка устарела. Лет на 20.» 

Поскольку я сам уже 20 лет в области сжатия видео, с ее бурным развитием мне спорить сложно. А вот что сжатие без потерь развиваться перестало… Хотя логика тут понятна каждому. Я до сих пор пользуюсь ZIP, все мои друзья пользуются ZIP с 1989 года — значит, ничего нового не появляется. Так ведь? Похоже рассуждают сторонники плоской земли. ))) Я не видел, знакомые не видели, и даже некоторые авторитеты утверждают, значит, это так! 

О том, как Intel просили меня не прекращать читать курс по сжатию, ибо людей нет новые алгоритмы делать, я в прошлый раз писал. Но тут и Huawei в ту же дуду дует! Вместо того, чтобы раздать призы и должности победителям, а затем успокоиться, поскольку развитие давно встало, эти эксцентричные люди посчитали конкурс крайне успешным и запустили новый с призовым фондом 200 тысяч EUR.

Развивались ли алгоритмы сжатия без потерь в последние 20 лет? Чем закончился прошлый конкурс и на сколько опередили baseline? Сколько денег получили русские таланты, а сколько зарубежные? И есть ли вообще жизнь на Марсе в сжатии без потерь? 

Кому интересно — добро пожаловать под кат! 
Читать дальше →

Защищает ли Netflix свой контент?

Время на прочтение9 мин
Количество просмотров31K

Наверное всё, что нужно знать про DRM, защиту контента и продвинутые водяные знаки.

Часть I, про DRM




Главная проблема для Netflix'а и других стримингов — слив контента на торренты, в общий доступ. Ну и последующее снижение количества подписчиков сервиса.

Чтобы избежать плачевной ситуации онлайн-кинотеатры защищают контент всеми силами, используя DRM и водяные знаки по указке правообладателей. Сначала расскажу про DRM.
Читать дальше →

Ближайшие события

Расширенные возможности MessagePack

Время на прочтение11 мин
Количество просмотров11K

MessagePack — бинарный формат сериализации данных, позиционируемый авторами как более эффективная альтернатива JSON. Благодаря своей компактности и скорости, его часто выбирают в качестве формата обмена данными в системах, где важна производительность. Простота реализации также способствует его широкому распространению — ваш любимый язык программирования, скорее всего, уже имеет несколько библиотек для работы с этим форматом.

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

Читать далее

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

Время на прочтение7 мин
Количество просмотров21K

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

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

Читать далее

Почему tar.xz-файлы, созданные с Python tar, оказались в 15 раз меньше, чем у macOS tar

Время на прочтение3 мин
Количество просмотров22K

Прим. перев.: это не совсем обычный перевод, потому что в его основе не отдельно взятая статья, а недавний случай со Stack Exchange, ставший главным хитом ресурса в этом месяце. Его автор задает вопрос, ответ на который можно отнести к базовым знаниям в области ИТ, но в то же время оказавшийся откровением для некоторых посетителей сайта.

Сжимая каталоги по ~1,3 ГБ, в каждом из которых по 1440 файлов JSON, я обнаружил 15-кратную разницу между размером архивов, сжатых с помощью tar на macOS или Raspbian 10 (Buster), и архивов, полученных при использовании библиотеки tarfile, встроенной в Python.

Читать далее

Windows 95 на двух флоппиках

Время на прочтение3 мин
Количество просмотров16K
В этом году мы отпраздновали четверть века с Windows 95. Её минимальная установка занимала 30 МБ; народные умельцы ужимали её до 5 МБ после удаления всех «лишних» файлов и сжатия UPX-ом оставшихся. А как насчёт двух флоппиков по 1.44 МБ, вместе с загрузчиком?



Общий подход я уже описывал в комментариях: создаётся RAMDRIVE, и на него разворачивается двухтомный SFX-архив. Но есть много тонкостей:

  1. Как видно на видео выше, распакованная папка Windows у меня занимает 6.2 МБ. Я взял за основу список файлов Micro95, и дополнительно удалил файлы, оказавшиеся необязательными — например, шрифты и драйвер dosnet.vxd. Кроме того, vmm32.vxd я распаковал, и удалил бывшие внутри него необязательные драйвера.
Читать дальше →

Ещё один велосипед: храним юникодные строки на 30-60% компактнее, чем UTF-8

Время на прочтение15 мин
Количество просмотров14K


Если вы разработчик и перед вами стоит задача выбора кодировки, то почти всегда правильным решением будет Юникод. Конкретный способ представления зависит от контекста, но чаще всего тут тоже есть универсальный ответ — UTF-8. Он хорош тем, что позволяет использовать все символы Юникода, не тратя слишком много байт в большинстве случаев. Правда, для языков, использующих не только латиницу, «не слишком много» — это как минимум два байта на символ. Можно ли лучше, не возвращаясь к доисторическим кодировкам, ограничивающим нас всего 256 доступными символами?

Ниже предлагаю ознакомиться с моей попыткой дать ответ на этот вопрос и реализацию относительно простого алгоритма, позволяющего хранить строчки на большинстве языков мира, не добавляя той избыточности, которая есть в UTF-8.
Читать дальше →

Discret 11: краткая история шифрования французского телеканала

Время на прочтение6 мин
Количество просмотров16K

Я провёл своё детство во Франции, много играл в футбол и слишком долго смотрел телевизор. В 80-х во Франции было три телеканала. Два из них, Antenne 2 и FR3, финансировались государством и были скучными, а TF1 был частным и показывал много японских мультиков. Моё поколение выросло на «Капитане Цубасе», «Святом Сейя», «Капитане Харлоке» и «Грендайзере».

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

Всё изменилось в 1984 году с появлением четвёртого канала. Canal Plus (Channel Plus) должен был совершить революцию на рынке телеканалов, показывая современные фильмы, спортивные трансляции со всего мира и не имея при этом рекламы. Для удовлетворения амбиций владельцев «Canal» должен был финансироваться ежемесячной абонентской платой подписчиков.

Техническая трудность такой схемы была совершенно понятна. Как гарантировать, что канал смогут смотреть только заплатившие абоненты, если его сигнал транслируется всем? Легко — достаточно закодировать его технологией под названием «Discret 11».

Моя реализация кольцевого буфера в NOR flash

Время на прочтение25 мин
Количество просмотров11K

Предыстория


Есть торговые автоматы собственной разработки. Внутри Raspberry Pi и немного обвязки на отдельной плате. Подключены монетоприёмник, купюроприёмник, банковский терминал… Управляет всем самописная программа. Вся история работы пишется в журнал на флешке (MicroSD), который потом передаётся через интернет (с помощью USB-модема) на сервер, там складывается в БД. Информация о продажах загружается в 1с, также есть простенький веб-интерфейс для мониторинга и т.п.


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


Проблема


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


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

Читать дальше →