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

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

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

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

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

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

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

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

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

Новости

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

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

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

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

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

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

Читать далее

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

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

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

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

Читать далее

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать далее

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

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

Это короткая история о том, насколько опасной может оказаться обычная распаковка 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. Разумеется, я выбрал второй вариант.

Читать далее

Delta-Rle-Huffman (DRH) Texture Format

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

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

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

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

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

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

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

Читать далее

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

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

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

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

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

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

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

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

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

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

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

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

Читать далее

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

Распаковываем файл gzip вручную. Часть 2

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

В этой части мы, как и в первой, распакуем файл gzip вручную, но теперь ещё и декодируем коды Хаффмана.

Для начала запишем данные на диск:

$ echo "hector the frantic father on an anchor or a rare fat cat sat on the ranch" > test-huff.txt
$ xxd test-huff.txt
00000000: 6865 6374 6f72 2074 6865 2066 7261 6e74  hector the frant
00000010: 6963 2066 6174 6865 7220 6f6e 2061 6e20  ic father on an
00000020: 616e 6368 6f72 206f 7220 6120 7261 7265  anchor or a rare
00000030: 2066 6174 2063 6174 2073 6174 206f 6e20   fat cat sat on
00000040: 7468 6520 7261 6e63 680a                 the ranch.

На этот раз файл получился размером 74 байта и содержит 13 символов:

a, c, e, f, h, i, n, o, r, s, t; пробел (0x20) и перевод каретки (0x0a).

В этой строке есть много повторений. Надеюсь, gzip это учтёт. Поскольку я работаю под Windows, то для распаковки использовал 7zip-zstd.

$ 7z a -mx9 test-huff.txt.gz .\test-huff.txt
$ xxd test-huff.txt.gz
00000000: 1f8b 0808 d76f 6565 0200 7465 7374 2d68  .....oee..test-h
00000010: 7566 662e 7478 7400 158b 410a 0031 0c02  uff.txt...A..1..
00000020: effb 0abf 2621 257b 69c1 e6ff d480 1e64  ....&!%{i......d
00000030: c6ca e823 7425 96b8 fb0f 2c7a 0967 8393  ...#t%....,z.g..
00000040: 2873 8710 9543 11ee 75ad cc51 237d 0fc7  (s...C..u..Q#}..
00000050: 9797 d64a 0000 00                        ...J...

Чтобы вы лучше поняли, как будет выглядеть декодирование, покажу первую строку декодированного потока gzip:

0101 1001 0001 1101 00111 010 000 1101 0101 1001 000
h    e    c    t    o     r   ' '   t    h  e    ' ' 

Ну а подробности читайте далее.
Читать дальше →

Распаковываем файл gzip вручную

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

В этой небольшой статье мы создадим файл gzip, после чего разберём его внутренние составляющие и просмотрим начинку. Избегая лишней сложности, в качестве содержимого для сжатия мы просто запишем в изначальный файл 8 символов a.

$ echo "aaaaaaaa" > test.out
$ xxd test.out
00000000: 6161 6161 6161 6161 0a     aaaaaaaa.

Файл получился размером 9 байт — 8 символов a плюс перевод каретки в конце.

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

$ gzip -1 test.out
$ xxd test.out.gz
00000000: 1f8b 0808 bf35 6a61 0403 7465 7374 2e6f  .....5ja..test.o
00000010: 7574 004b 4c84 002e 00b6 66d7 ad09 0000  ut.KL.....f.....
00000020: 00

Дисклеймер: эту статью я писал в целях обучения, так что мог допустить некоторые ошибки. Мне нравится заниматься низкоуровневым программированием, но моя основная деятельность сосредоточена на веб-разработке для Microsoft Teams.
Читать дальше →

Генеративный ИИ — это просто «замыленный JPEG интернета», который убедительно косит под интеллект

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

ИИ чат‑боты любят ловить глюки и выдавать всякую чушь. Так массово, что словом 2023 года признали «галлюционировать». В чем причина такого явления? Является ли генеративный ИИ интеллектом (спойлер — и да, и нет)? И что общего у ChatGPT и копировального аппарата Xerox? Разбираемся, осмысляя неочевидный нюанс в логике работы больших языковых моделей.

Читать далее

Ещё раз про алгоритм сжатия Хаффмана

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

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

Читать далее

Наполняем до краев: влияние порядка столбцов в таблицах на размеры баз данных PostgresQL

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

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

И что же там прячется?

Кодеки новой эпохи: HEVC, AV1, VVC и нейросети

Уровень сложностиСредний
Время на прочтение6 мин
Количество просмотров28K
Сжатие с учётом контекста, источник: WaveOne (сайт удалён)

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

В новом поколении кодеков алгоритмы машинного обучения используются для анализа и понимания визуального содержания видео, выявления избыточных данных и более эффективного сжатия. Вместо написанных вручную алгоритмов, тут применяют методы Software 2.0, основанные на обучении. Данная область развивается на протяжении десятилетий, но в последние годы получила сильный толчок. Все знают, что в 2017 году произошёл прорыв в разработке ИИ благодаря изобретению трансформеров. В свою очередь, они основаны на концепции внимания, которую придумали в 90-е. Эта техника впервые позволила соотносить друг с другом отдельные части текста или видеокадра.
Читать дальше →

Как стажировка в большой компании может преобразить студенческий проект

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

Добрый день! Меня зовут Дмитрий Грязнов, я студент УрФу и начинающий разработчик. 

Вместе с товарищами мы подумали, что всем студентам и школьникам, которые ищут в интернете информацию, был бы полезен сервис, который может делать смысловую выжимку из текста любого объёма. Мы решили разработать именно такое приложение и выступить с этой идеей на конкурсе «Большие вызовы для студентов». Собрали ансамбль моделей, изучили, много чего переработали.

Коротко: мы используем пайплайн из сжимающих T5, Pegasus, экстракции TextRank, парафразер Bart. Сначала один алгоритм определяет вес каждого предложения и передаёт на вход абстрактивной модели 20% самых значимых предложений. А затем второй перефразирует полученный текст, чтобы сделать его более связанным. Очень много интеграционного кода и тюнинга, чтобы это всё заработало нормально. Сейчас расскажу, как дело было.

Читать далее