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

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

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

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

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

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

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

Читать далее
Всего голосов 41: ↑41 и ↓0 +41
Комментарии 6

Новости

Эффективное обновление состояний в БД из сервисов потоковой обработки событий

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

Как хранить сложные сущности в БД? Что нужно сделать, чтобы не перезаписывать весь рекламный баннер для обновления одного лишь заголовка? Рассмотрим как минимум 5 независимых и взаимно совместимых идей для многократного снижения нагрузки на чтение и запись подобных объектов.

Меня зовут Юрий Печатнов, я уже 6 лет работаю в Яндексе и занимаюсь сервисами потоковой обработки. Это большие распределенные системы, читающие сообщения из большой распределенной очереди и создающие полезный выход. Полезным выходом могут быть сообщения в другой распределенной очереди и/или обновление состояний в БД. Поговорим о том, как их эффективно обновлять.

Читать далее
Всего голосов 6: ↑6 и ↓0 +6
Комментарии 9

Приглашаем на Ozon Tech Community BI Meetup

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

Всем привет!
Меня зовут Дмитрий, я руководитель группы разработки инструментов BI. 

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

И мы готовы ими поделиться. Приглашаем вас на Ozon Tech Community BI Meetup, 31 января в 19:00. Наша команда расскажет про основные сервисы работы с данными, о том, как нам пришёл в голову подход «платформизации», про создание функционала для сжатия данных, а также обсудим феномен data quality в обработке данных.

Читать далее
Всего голосов 5: ↑5 и ↓0 +5
Комментарии 0

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

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

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

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

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

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

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

В качестве небольшой затравки скажу, что в конце предстоит неожиданный поворот. Хотя, надеюсь, вам и без того интересно побольше узнать о PNG.
Читать дальше →
Всего голосов 140: ↑132 и ↓8 +124
Комментарии 112

Истории

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

Уровень сложности Простой
Время на прочтение 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

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

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

Читать далее
Всего голосов 41: ↑32 и ↓9 +23
Комментарии 28

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

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

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

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

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

Читать далее
Всего голосов 19: ↑17 и ↓2 +15
Комментарии 38

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

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

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

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

Читать далее
Всего голосов 42: ↑37 и ↓5 +32
Комментарии 22

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

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

В этой части мы, как и в первой, распакуем файл 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    ' ' 

Ну а подробности читайте далее.
Читать дальше →
Всего голосов 46: ↑44 и ↓2 +42
Комментарии 0

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

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

В этой небольшой статье мы создадим файл 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.
Читать дальше →
Всего голосов 60: ↑57 и ↓3 +54
Комментарии 14

Оптимизация хранения данных в Greenplum

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

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

Данная статья в первую очередь для тех, кто только начинает знакомство с оптимизацией в Greenplum и хочет разобраться на что стоит обратить внимание в первую очередь. Будут рассмотрены три ключевых аспекта: компрессию данных, распределение и партиционирование. Узнаем – как правильно применять эти стратегии, чтобы улучшить производительность запросов, снизить потребление ресурсов и повысить эффективность работы базы данных.

Читать далее
Всего голосов 4: ↑3 и ↓1 +2
Комментарии 7

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

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

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

Читать далее
Всего голосов 87: ↑84 и ↓3 +81
Комментарии 216

Как настольная игра и небоскребы вдохновили на разработку QR-кода

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

Про QR код на том же Хабре есть огромное количество информации. Ничего удивительного: сейчас сложно найти отрасль, где бы он не применялся. Тут и банковские операции, и идентификация товаров, и цифровые визитки. Преимущества очевидны: считывается мгновенно любым смартфоном, причем даже если треть QR кода повреждена, а еще хранит до 2935 байт двоичного кода. 

Но сегодня поговорим не про технические нюансы. Вы знали, что его придумали благодаря любви к играм и небоскребам? Если не знали, устраивайтесь поудобнее — поговорим об истории появления QR кода. 

Читать далее
Всего голосов 19: ↑19 и ↓0 +19
Комментарии 8

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

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

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

Читать далее
Всего голосов 39: ↑38 и ↓1 +37
Комментарии 13

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

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн

Сжатие сообщений в Apache Kafka

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

Apache Kafka способен обеспечивать невероятно высокую пропускную способность. Он славится такими впечатляющими достижениями, как поддержка 20 миллионов заказов в час для рассылки тестов на COVID гражданам США во время пандемии. Достичь такого уровня масштабируемости позволяет подход Kafka к партиционированию топиков.

Читать далее
Всего голосов 12: ↑8 и ↓4 +4
Комментарии 1

Дорогая техника для прослушивания Lossless Audio. Оно того стоит?

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

Вы слушаете почти всю свою музыку в «сжатом» формате (MP3 и AAC). Эти файлы экономят место, но опускают высококачественные детали оригинальных записей. Наверняка, вы задумывались, как найти несжатый звук (в форматах WAV и AIFF) и точное воспроизведение оригинальной студийной записи, а также встречали термин Lossless Audio или «аудио без потерь».

Хотя это ни в коем случае не новый термин, «Lossless» сравнительно недавно стал мейнстримом благодаря Apple, Amazon и Spotify, принявших его в своих последних аудиоаппаратных и программных продуктах и, понятное дело, рекламирующих его со всех своих платформ.

Аудио без потерь по-прежнему сжимает файлы, но использует специальный алгоритм, который может минимизировать размер ущерба для детализации. К типам файлов без потерь относятся FLAC (Free Lossless Audio Codec) и ALAC (Apple Lossless Audio Codec). Как говорят в Apple, Amazon и Spotify, у их Lossless Audio звук в исходном качестве. Что же это такое Lossless Audio и с чем его едят слушают? В чем разница между Lossless, Lossy и Hi-Res? какое оборудование сегодня есть для Lossless и сколько стоит? Обо всём этом подробно в этой статье.
Читать дальше →
Всего голосов 30: ↑21 и ↓9 +12
Комментарии 34

Сжать и не пожалеть: как работает сжатие без потерь

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

Более 9 миллиардов гигабайт информации ежедневно путешествуют по интернету, заставляя постоянно искать все новые и новые методы упаковки данных. Самые эффективные решения используют подходы, которые позволяют достичь большей плотности за счет "потерь" информации в процессе сжатия. В то же время очень мало внимания уделяется сжатию без потерь. Почему? Ответ прост - методы сжатия без потерь уже невероятно эффективны. С их помощью работает буквально всё, от формата PNG до утилиты PKZip. И это все благодаря студенту, что захотел пропустить экзамен.

Читать далее
Всего голосов 12: ↑12 и ↓0 +12
Комментарии 3

Приложения алгебры кортежей. Часть 2. Математическая модель вопроса

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

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

Об алгебре кортежей (АК) и ее использовании для логико-семантического анализа было рассказано в моей статье в Хабре. В комментариях к статье предлагалось обратить внимание на функцию SELECT в языке SQL, которая соответствует операции Selection (Выборка) в реляционной алгебре. Эта операцию можно рассматривать как один из вариантов математической модели вопроса.

Предлагаемый здесь вариант смысла вопроса заключается в том, что в вопросе заданы некоторые ограничения (область знания, ситуация, значения некоторых атрибутов и т.д.), которые требуется использовать для того, чтобы найти или вычислить значение определенного атрибута или проверить правильность заданных в вопросе соотношений. Эта семантика применима к восполняющим вопросам типа «Что?», «Где?», «Когда?», к уточняющим вопросам типа «Верно ли, что А?» и к ИЛИ-вопросам типа «Что правильно: А или Б?». Назовем такие вопросы ограничительными. Их можно считать вариантами известной в искусственном интеллекте задачи удовлетворения ограничений.

Читать далее
Всего голосов 2: ↑2 и ↓0 +2
Комментарии 4

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

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

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

И что же там прячется?
Всего голосов 59: ↑58 и ↓1 +57
Комментарии 19

Приложения алгебры кортежей. Часть 1. Гибкая система счисления с простыми основаниями

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

В настоящее время известно большое число систем счисления. Подробный перечень (не знаю, насколько полный) приведен в англоязычной Википедии. В этом списке я не нашел ту систему, которая будет изложена здесь. Она относится к классу систем с переменным основанием (mixed radix). Предлагаю ее назвать Flexible number system with a Prime Radixes, сокращенно FPR-системой счисления.

Но для того, чтобы ее понять, необходимы знания некоторых понятий алгебры кортежей (АК) и частично упорядоченных множеств хотя бы в том объеме, который имеется в соответствующей статье в Википедии. Об АК кратко было рассказано в статье «Как совместить логику и семантику в одной алгебраической системе». Там же есть ссылки на публикации с более подробным описанием АК.

В данной статье будут обоснованы следующие преимущества предложенной системы счисления:

• она универсальна - позволяет ТОЧНО выразить все (за исключением нуля) конечные целые и рациональные (с любым ненулевым целым числом в знаменателе) числа, а также некоторые классы иррациональных чисел;

• ее использование позволяет сократить вычислительную сложность алгоритма умножения чисел;

• в ней существенно уменьшается объем памяти для записи и хранения многих больших чисел.

Читать далее
Всего голосов 7: ↑5 и ↓2 +3
Комментарии 30

Сжатие данных управляет Интернетом. Вот как это работает

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

Желание одного студента не сдавать выпускной экзамен привело к появлению вездесущего алгоритма, который сжимает данные, не жертвуя при этом информацией.

Читать далее
Всего голосов 13: ↑11 и ↓2 +9
Комментарии 17

Вклад авторов