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

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

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

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

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

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

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

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

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

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

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

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

Sentence case: The cat sat on the mat

Title case: The Cat Sat on the Mat

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

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

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

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

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

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

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

$ 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.

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

$ 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...

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

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

$ 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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