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

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

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

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

MP3 устарел. Будущее за современными lossless-кодеками

Уровень сложностиСредний
Время на прочтение7 мин
Количество просмотров14K
Сравнение производительности lossless-кодеков на материале CD-качества, то есть аудиофайлах PCM с битовой глубиной 16 бит и частотой дискретизации 44,1 кГц, источник

В своё время MP3 совершил революцию в распространении музыки. Больше не нужно было покупать дорогие компакт-диски. Достаточно поставить на ночь загрузку из «Напстера» — и к утру у тебя несколько файлов MP3, которые можно слушать совершенно бесплатно! Любые исполнители и альбомы. Это было невероятно.

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

Есть ряд lossless-кодеков, которые эффективнее .FLAC по степени сжатия.
Читать дальше →

Новости

Как уместить поиск по 30 тысячам слов в 64 КБ ОЗУ

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

Как уместить словарь размером 250 КБ в 64 КБ ОЗУ с возможностью выполнения быстрого поиска? Для справки: даже современные методики сжатия наподобие gzip -9 не могут сжать этот файл до размера меньше 85 КБ.

В 1970-х Дуглас Макилрой столкнулся с этой непростой задачей при реализации проверки правописания для Unix в AT&T. Из-за ограничений компьютера PDP-11 весь словарь должен был умещаться всего в 64 КБ ОЗУ. Кажется, подобную задачу решить невозможно.

Вместо того, чтобы использовать стандартные методики сжатия, Дуглас воспользовался преимуществами свойств данных, разработав алгоритм сжатия, отличавшийся от теоретического минимума сжатия всего на 0,03 бита. И по сей день этот рекорд остаётся непревзойдённым.

История spell в Unix — это не только любопытный исторический факт. Это мастер-класс по проектированию в условиях жёстких ограничений: анализа первооснов задачи, применения математических наблюдений и проектирования изящных решений, работающих в условиях строгого дефицита ресурсов.

Читать далее

Как сделать видео на стриминге легче и не погрязнуть в шакалах: опыт Кинопоиска

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

Привет! Меня зовут Михаил Мазанов, я отвечаю за технологический стек работы с медиаданными в Кинопоиске: от съёмок оригинальных проектов до доставки и просмотра видео на всех экранах. Для нашей пятой ежегодной конференции про стриминг PlayButton 2024 я готовил большой доклад про оптимизацию качества видео Кинопоиска, а для Хабра решил пересобрать его в виде статьи — для тех, кому текстовый формат предпочтительнее видео.

Кроме технических графиков, вас ждёт ещё и наглядная разница в работе алгоритмов сжатия на примере «Рика и Морти» и «Джона Уика».

Читать далее

Сжатие графики при помощи алгоритма LZ4

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

Привет, Хабр! Меня зовут Александр Крестинин, я разработчик встроенного ПО в компании Whoosh. Мы в embedded-команде не только переливаем биты из одного регистра в другой, но и решаем разные бизнес-задачи. Иногда попадаются головоломки. 

Однажды мы подумали, что было бы здорово выводить на экраны самокатов анимации и изображения — показывать инструкции, как пользоваться сервисом, как начать и закончить поездку, и чтобы запускать DOOM.

Зачем?

1) Сделать комфортнее. Удобно видеть инструкции на большом и ярком экране перед глазами, а не нырять за ними в приложение на смартфоне. 

2) Сделать безопаснее. Пользователь меньше отвлекается на телефон, крепче держится за самокат и внимательнее смотрит на всё, что вокруг.

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

Но тут возникает проблема. Микроконтроллер крайне ограничен в памяти и вычислительных ресурсах. Самая простая анимация занимает чрезмерно много места. А если внедрить в отрисовку алгоритмы сжатия, то вычислительная нагрузка увеличится и анимация будет сильно лагать.

Расскажу, как мы нашли решение этой задачи. Прошу под кат.

Читать далее

ZIP-бомба в формате Apache Parquet

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


Давние хаброжители помнят, как в 2015 году ZIP-бомба в формате PNG ненадолго вывела из строя Habrastorage. С тех пор появились новые разновидности этого «оружия»: например, разработаны нерекурсивные и компиляторные бомбы (29 байт кода → 16 ГБ .exe).

Подобного рода экспоиты можно встроить не только в формат ZIP или PNG, но и в других форматы файлов, которые поддерживают сжатие. Например, в формате Apache Parquet.
Читать дальше →

Аппаратное кодирование HEVC в FFmpeg — как быстро вникнуть и начать уже сейчас?

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

В прошлой статье, посвящённой изучению кодирования на HEVC в FFmpeg, мы разобрали большинство функций работы с видео и научились эффективно сжимать видео или ускорять процесс кодирования для различных задач, преимущественно в программном кодировании. На этот раз моё внимание привлекла тема аппаратного кодирования (ГПУ) в FFmpeg.

Буду рассматривать аппаратные кодеки Nvidia, AMD и Intel.
Читать дальше →

Записываем PNG без мам, пап и внешних библиотек

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

Я решал очередную техническую задачу и столкнулся с проблемой: нужно сохранять изображения, а у меня нет сериализаторов и я не могу использовать готовые библиотеки. Ситуацию ухудшает, что из доступных форматов только PNG, JPEG и WebP. Выбор пал на PNG.

Формат изображения PNG известен с 1996 года, а на Хабре опубликовано несколько статей о декодировании этого формата. И ни одной — о кодировании. Я расскажу, как сохранить PNG своими руками на случай, если вам тоже придется это делать. Например, в академических целях.

Под катом вас ждет подробный разбор каждого байта на множестве иллюстраций.
Читать дальше →

Стеганография в Linux — просто

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

Сегодня я хотел бы познакомить читателей Хабра с цифровой стеганографией. В нынешнем примере мы создадим, протестируем, проанализируем и взломаем стегосистемы. Я использую операционную систему Kali GNU/Linux, но кому интересна тема на практике, тот может повторить все то же в любом другом дистрибутиве Линукс.
Но для начала совсем немного теории.

Читать далее

Кодирование с кодеком HEVC простым языком — гайд на FFmpeg. Высокое качество, но низкий вес

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

Казалось бы, довольно простой вопрос: «Чем сжать видео?». На ум сразу приходят Handbrake, Movavi Converter или ещё что-нибудь пострашнее. Однако когда речь заходит о более гиковском подходе с упором на максимальное качество и экономию места, такие программы сложно назвать инструментами. Равно как и для обратной ситуации, когда картинку нужно сильно сжать и сохранить в целостности большую часть полезной информации. Все эти программы только лишь предоставляют набор наиболее общих конфигов для обычной съёмки и 2D.

В этой статье мы изучим, как при помощи самого большого сборника свободных библиотек FFmpeg научиться кодировать видео самому именно под ваши задачи.
Читать дальше →

Как я создал архиватор из задачки с техсобеса: сжатие файлов с помощью RLE

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

Привет, меня зовут Рома. Я работаю в отделе спецпроектов KTS на позиции Python backend-разработчика. 

Однажды мне взбрело в голову написать собственную имплементацию алгоритма сжатия RLE. В этой статье рассказываю подробнее про RLE: что это за зверь такой, где используется, чем плох, чем хорош, и какие неожиданные сложности могут возникнуть при попытке имплементации.

Читать далее

Как уничтожить вашу ОС с помощью TAR

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

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

▍ Ошибка


Недавно я экспериментировал с установкой Void Linux через chroot методом XBPS. Для подготовки базовой системы Void Linux на моём хосте с Fedora Linux требовался XBPS Package Manager. Одним из вариантов было скачать архив статически собранных инструментов из официального репозитория. Я выбрал https://repo-default.voidlinux.org/static/xbps-static-latest.x86_64-musl.tar.xz
Читать дальше →

Невероятно тупой способ взлома Wi-Fi в самолёте (зато бесплатно)

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

Самолёт поднялся на высоту трёх километров. Я вытащил свой ноутбук, надеясь воспользоваться Интернетом, а может, немного поработать, если станет совсем скучно.

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

Я вошёл в свой аккаунт JetStreamers Diamond Altitude, перешёл на страницу своего профиля и увидел кнопку редактирования. Она выглядела обычно: отбрасываемая тень, скруглённые углы, ничего особенного. С её помощью можно было поменять имя, адрес и так далее.

Но внезапно я понял, что это необычная кнопка. Она мошенническим образом позволит мне получить полный доступ к Интернету через мой аккаунт программы авиамиль. Это будет медленно и невероятно тупо, но сработает.

Многие коллеги просили меня выполнить ревью их пул-реквестов, потому что я оставлял комментарии типа «опоздало на две недели» или «мешает развёртыванию критического обновления». Но мои идеи тоже важны, поэтому я надел наушники и включил музыку для концентрации. Я забыл зарядить наушники, поэтому Limp Bizkit начал проигрываться через динамики ноутбука. К счастью, никто из пассажиров не был против, так что мы кайфовали вместе.

Прежде чем получить доступ ко всему Интернету через аккаунт программы авиамиль, мне нужно было написать несколько прототипов. Сначала я думал, что напишу их на Go, но потом понял, что если напишу их на Python, то смогу назвать получившийся инструмент PySkyWiFi. Разумеется, я выбрал второй вариант.

Читать далее

Дедупликация данных в Windows 10 и Windows 11 средствами Microsoft

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

Сегодня я кратко расскажу вам как включить дедупликацию данных в клиентских ОС - Windows 10 и Windows 11, добавив функционал из Windows Server, причем не какие-то сторонние бинарники, а оригинальные, подписанные файлы Microsoft, которые к тому же будут обновляться через Windows Update.

В этой статье не будет описания дедупликации данных, - разве что совсем кратко что это такое, и не будет сравнения решений разных вендоров. Я дам ниже ссылки на достойные, на мой взгляд, статьи других авторов и готов буду отвечать на вопросы, если их зададут ниже в виде комментария или в ПМ.

Начать знакомство рекомендую с базовой теории Введение в дедупликацию данных / Хабр (habr.com) от компании Veeam, затем почитать о том, что такое дедупликация Microsoft - Обзор и настройка средств дедупликации в Windows Server 2012 / Хабр (habr.com) - статья моего бывшего коллеги по Microsoft Георгия говорит о том, как настраивается дедупликация NTFS в Windows Server 2012. В последующих изданиях Windows Server 2012R2, 2016, 2019, 2022 и 2025 функционал развивался, появилась поддержка ReFS, стало возможно (неочевидным способом) дедуплицировать системный том, расширились компоненты управления, - но для конечного пользователя все остается там же. Установили одним кликом, включили для диска, забыли. В заключение подготовительной информации - тем кого действительно интересует кроссплатформенные решения и их сравнения, предложу ознакомиться со статьей Илии Карина - Dedup Windows vs Linux, MS снова “удивит”? / Хабр (habr.com) - его не должны заподозрить в рекламе Microsoft, его сравнение подходов, и результат меня самого удивил. У меня на такую большую исследовательскую работу сил и возможностей нет, - почитайте. И имейте в виду, что если вы используете последний Windows 11, то и компоненты дедупликации в нем будут последние, от Windows Server 2025, то есть с еще более впечатляющим результатом.

Читать далее

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

Delta-Rle-Huffman (DRH) Texture Format

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

Всем привет! В этой статье я опишу алгоритм работы формата сжатия изображений без потерь. Сжатие использует известные методики, которые и дали ему название. Проект начинался с простых экспериментов, которые вышли из под контроля. Не смотря на то, что формат чаще сжимает лучше чем png, никакого практического применения этот формат не имеет, оставаясь чисто академическим.

Внимание! В статье много картинок.

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

Дом, милый дом: нюансы работы с ClickHouse. Часть 1

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

Всем привет, меня зовут Пётр, я инженер компании Nixys. На современных проектах используется огромное разнообразие баз данных: реляционные, ключ-значение, документоориентированные. Особое место среди них занимают колоночные базы данных, ярким представителем которых является ClickHouse. Это мощный инструмент, который способен обрабатывать миллиарды строк в секунду при минимальном времени ответа. Однако, для максимальной эффективности ClickHouse необходимо понимать ряд фундаментальных моментов для того, чтобы использовать его по назначению. В этой серии статей мы разберем особенности работы ClickHouse, которые помогут в выжимании максимума из этой базы. И сегодня начнём с фундаментальных теоретических моментов, чтобы составить максимально полное общее впечатление, которое поможет нам в дальнейшем.

Читать далее

Разбираем самый маленький JPEG в мире

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

Недавно на Хабре была опубликована статья Разбираем самый маленький PNG в мире. Интересно, а какой самый маленький файл JPEG? В ответах на StackOverflow и Reddit можно встретить размеры 107, 119, 125, 134, 141, 160 байтов. Все они представляют серый прямоугольник 1 на 1. И кто прав? Все правы, просто такая разница объясняется различными режимами кодирования и степенью строгости соответствия стандарту. Описание всех нюансов разрослось до целой статьи cо всеми необходимыми подробностями для более-менее хорошего знакомства с самыми маленькими jpeg-ами. После краткой теории разберем 159-байтный файл на КДПВ, а затем рассмотрим способы его уменьшения.

Читать далее

Разбираем самый маленький PNG в мире

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

Самый миниатюрный PNG в мире весит 67 байт и представляет собой один чёрный пиксель. Выше вы видите его в 200-кратном увеличении.

Красота, не так ли?

Состоит этот файл из четырёх частей:

  1. Сигнатура PNG, одинаковая во всех файлах этого формата: 8 байт.
  2. Метаданные изображения, включая его размеры: 25 байт.
  3. Данные пикселя: 22 байта.
  4. Маркер «конец изображения»: 12 байт.

Далее я опишу этот файл подробнее и постараюсь объяснить принцип работы формата PNG.

В качестве небольшой затравки скажу, что в конце предстоит неожиданный поворот. Хотя, надеюсь, вам и без того интересно побольше узнать о PNG.
Читать дальше →

Почему текст в нижнем регистре сжимается лучше

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

Буквы в нижнем и верхнем регистре содержат одинаковое количество данных — по 1 байту каждая.

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

Пример: я взял главную страницу Hacker News и переписал заголовок каждой статьи, капитализировав только первые буквы в предложениях (sentence case) вместо первых букв во всех словах (title case). Это позволило мне снизить размер на 31 байт.

Sentence case: The cat sat on the mat

Title case: The Cat Sat on the Mat

Как может замена нескольких заглавных букв на строчные снижать объём? Всё дело в сжатии.

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

Читать далее

Сжимаем текст в изображения PNG

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

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

Текст шекспировской трагедии «Ромео и Джульетта» состоит примерно из 146 тысяч символов. Благодаря английскому алфавиту каждый символ можно описать одним байтом. Так что размер текстового файла в обычном Unicode составляет примерно 142 КБ.

В статье Adventures With Compression её автор JamesG размышляет о соревнованиях по сжатию текста и предлагает интересную мысль...

Читать далее

Сжатие целых чисел

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

Цель статьи осветить state of the art методы сжатия целых чисел, чтобы сэкономить в будущем время исследования алгоритмов и терминологии. При этом описание части алгоритмов может быть упрощено для понимания. Сравнение алгоритмов тоже находится вне рамках этой статьи. Подробнее можно почитать в ссылках.

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

Читать далее