Всем привет, меня зовут Пётр, я инженер компании Nixys. На современных проектах используется огромное разнообразие баз данных: реляционные, ключ-значение, документоориентированные. Особое место среди них занимают колоночные базы данных, ярким представителем которых является ClickHouse. Это мощный инструмент, который способен обрабатывать миллиарды строк в секунду при минимальном времени ответа. Однако, для максимальной эффективности ClickHouse необходимо понимать ряд фундаментальных моментов для того, чтобы использовать его по назначению. В этой серии статей мы разберем особенности работы ClickHouse, которые помогут в выжимании максимума из этой базы. И сегодня начнём с фундаментальных теоретических моментов, чтобы составить максимально полное общее впечатление, которое поможет нам в дальнейшем.
Сжатие данных *
Упаковываем и распаковываем информацию
Новости
Разбираем самый маленький JPEG в мире
Недавно на Хабре была опубликована статья Разбираем самый маленький PNG в мире. Интересно, а какой самый маленький файл JPEG? В ответах на StackOverflow и Reddit можно встретить размеры 107, 119, 125, 134, 141, 160 байтов. Все они представляют серый прямоугольник 1 на 1. И кто прав? Все правы, просто такая разница объясняется различными режимами кодирования и степенью строгости соответствия стандарту. Описание всех нюансов разрослось до целой статьи cо всеми необходимыми подробностями для более-менее хорошего знакомства с самыми маленькими jpeg-ами. После краткой теории разберем 159-байтный файл на КДПВ, а затем рассмотрим способы его уменьшения.
Разбираем самый маленький PNG в мире
Самый миниатюрный PNG в мире весит 67 байт и представляет собой один чёрный пиксель. Выше вы видите его в 200-кратном увеличении.
Красота, не так ли?
Состоит этот файл из четырёх частей:
- Сигнатура PNG, одинаковая во всех файлах этого формата: 8 байт.
- Метаданные изображения, включая его размеры: 25 байт.
- Данные пикселя: 22 байта.
- Маркер «конец изображения»: 12 байт.
Далее я опишу этот файл подробнее и постараюсь объяснить принцип работы формата PNG.
В качестве небольшой затравки скажу, что в конце предстоит неожиданный поворот. Хотя, надеюсь, вам и без того интересно побольше узнать о PNG.
Почему текст в нижнем регистре сжимается лучше
Буквы в нижнем и верхнем регистре содержат одинаковое количество данных — по 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
(Наверно, это глупая идея. Но иногда даже самые глупые идеи приводят к неожиданным результатам.)
Текст шекспировской трагедии «Ромео и Джульетта» состоит примерно из 146 тысяч символов. Благодаря английскому алфавиту каждый символ можно описать одним байтом. Так что размер текстового файла в обычном Unicode составляет примерно 142 КБ.
В статье Adventures With Compression её автор JamesG размышляет о соревнованиях по сжатию текста и предлагает интересную мысль...
Сжатие целых чисел
Цель статьи осветить state of the art методы сжатия целых чисел, чтобы сэкономить в будущем время исследования алгоритмов и терминологии. При этом описание части алгоритмов может быть упрощено для понимания. Сравнение алгоритмов тоже находится вне рамках этой статьи. Подробнее можно почитать в ссылках.
Многие из упомянутых ниже алгоритмов используются в прикладных задачах: сжатие битмап, обратных индексов, просто массивов данных.
Распаковываем файл gzip вручную. Часть 2
В этой части мы, как и в первой, распакуем файл 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 вручную
В этой небольшой статье мы создадим файл 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 интернета», который убедительно косит под интеллект
ИИ чат‑боты любят ловить глюки и выдавать всякую чушь. Так массово, что словом 2023 года признали «галлюционировать». В чем причина такого явления? Является ли генеративный ИИ интеллектом (спойлер — и да, и нет)? И что общего у ChatGPT и копировального аппарата Xerox? Разбираемся, осмысляя неочевидный нюанс в логике работы больших языковых моделей.
Как настольная игра и небоскребы вдохновили на разработку QR-кода
Про QR код на том же Хабре есть огромное количество информации. Ничего удивительного: сейчас сложно найти отрасль, где бы он не применялся. Тут и банковские операции, и идентификация товаров, и цифровые визитки. Преимущества очевидны: считывается мгновенно любым смартфоном, причем даже если треть QR кода повреждена, а еще хранит до 2935 байт двоичного кода.
Но сегодня поговорим не про технические нюансы. Вы знали, что его придумали благодаря любви к играм и небоскребам? Если не знали, устраивайтесь поудобнее — поговорим об истории появления QR кода.
Ещё раз про алгоритм сжатия Хаффмана
К написанию этой заметки меня сподвигло почти полное отсутствие информации на русском языке относительно эффективной реализации алгоритма оптимального префиксного кодирования алфавита с минимальной избыточностью, известного по имени своего создателя как алгоритм Хаффмана. Этот алгоритм в том или ином виде используется во многих стандартах и программах сжатия разнообразных данных.
Дорогая техника для прослушивания Lossless Audio. Оно того стоит?
Вы слушаете почти всю свою музыку в «сжатом» формате (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 и с чем его
Сжать и не пожалеть: как работает сжатие без потерь
Более 9 миллиардов гигабайт информации ежедневно путешествуют по интернету, заставляя постоянно искать все новые и новые методы упаковки данных. Самые эффективные решения используют подходы, которые позволяют достичь большей плотности за счет "потерь" информации в процессе сжатия. В то же время очень мало внимания уделяется сжатию без потерь. Почему? Ответ прост - методы сжатия без потерь уже невероятно эффективны. С их помощью работает буквально всё, от формата PNG до утилиты PKZip. И это все благодаря студенту, что захотел пропустить экзамен.
Ближайшие события
Наполняем до краев: влияние порядка столбцов в таблицах на размеры баз данных PostgresQL
При оценке требований базы данных к оборудованию требуется учет многих факторов. И здесь у Postgres есть одна интересная особенность, которая почти всегда ускользает от внимания разработчиков, потому что она искусно спрятана между столбцами таблиц.
Алгоритмы компрессии данных: принципы и эффективность
Автор статьи: Артем Михайлов
В современном информационном обществе объем данных стремительно растет, и с каждым годом все больше информации генерируется и обрабатывается. В связи с этим, важным аспектом стало умение эффективно управлять данными, чтобы не только сохранить информацию, но и оптимизировать ее использование и передачу. Одним из основных инструментов для достижения этой цели является компрессия данных.
Компрессия данных — это процесс сокращения объема данных без потерь или с минимальной потерей информации. Путем применения алгоритмов и методов компрессии, мы можем существенно уменьшить размер данных, сохраняя при этом их суть и основные характеристики. Это может быть полезно во множестве ситуаций, начиная от экономии места на хранилище и ускорения передачи данных до минимизации затрат на интернет-трафик и повышения производительности систем обработки и анализа информации.
Кодеки новой эпохи: HEVC, AV1, VVC и нейросети
Хотя новые стандарты кодеков появляются каждые десять лет, все они основаны на пиксельной математике — манипулировании значениями отдельных пикселей в видеокадре для удаления информации, не важной для восприятия. Другие математические операции уменьшают объём данных после первоначального кодирования.
В новом поколении кодеков алгоритмы машинного обучения используются для анализа и понимания визуального содержания видео, выявления избыточных данных и более эффективного сжатия. Вместо написанных вручную алгоритмов, тут применяют методы Software 2.0, основанные на обучении. Данная область развивается на протяжении десятилетий, но в последние годы получила сильный толчок. Все знают, что в 2017 году произошёл прорыв в разработке ИИ благодаря изобретению трансформеров. В свою очередь, они основаны на концепции внимания, которую придумали в 90-е. Эта техника впервые позволила соотносить друг с другом отдельные части текста или видеокадра.
Dedup Windows vs Linux, MS снова “удивит”?
Меня давно заинтриговала тема дедупликации данных. Это произошло в далеком 2016 году, когда передо мной встала задача впихнуть не впихуемое, на продакшн-серверах. Но обнаружить доступное решение оказалось невероятно сложно (на тот момент невозможно). Со временем у меня возникли и личные задачи, когда я хотел уменьшить объем третьей или четвертой копии данных, чтобы сэкономить место на диске. Но, возможно, я просто одержим датахордингом, и это тоже не исключено.
Как стажировка в большой компании может преобразить студенческий проект
Добрый день! Меня зовут Дмитрий Грязнов, я студент УрФу и начинающий разработчик.
Вместе с товарищами мы подумали, что всем студентам и школьникам, которые ищут в интернете информацию, был бы полезен сервис, который может делать смысловую выжимку из текста любого объёма. Мы решили разработать именно такое приложение и выступить с этой идеей на конкурсе «Большие вызовы для студентов». Собрали ансамбль моделей, изучили, много чего переработали.
Коротко: мы используем пайплайн из сжимающих T5, Pegasus, экстракции TextRank, парафразер Bart. Сначала один алгоритм определяет вес каждого предложения и передаёт на вход абстрактивной модели 20% самых значимых предложений. А затем второй перефразирует полученный текст, чтобы сделать его более связанным. Очень много интеграционного кода и тюнинга, чтобы это всё заработало нормально. Сейчас расскажу, как дело было.
Как заразить видео. Поиск уязвимостей в декодерах H.264
Современные стандарты сжатия видео — настоящее чудо скрытой сложности и результат десятилетий научной работы. Спецификация H.264 — это около 800 страниц правил, определяющих, как декодировать видео. Но чем больше сложности, тем выше риски для безопасности, легче пропустить ошибку в битовом потоке, который слишком труден для понимания и декодирования.
Если посмотреть на экосистему декодирования, то здесь в связке работают инструменты на нескольких уровнях из аппаратных ускорителей на CPU и GPU (список производителей аппаратных декодеров), драйверов и привилегированных программных компонентов. Все вместе они образуют сложнейший неоднородный коктейль привилегированного, практически нетестируемого и уязвимого кода.
В итоге мы приближаемся к тому, что вирусы можно будет незаметно интегрировать в видеоролики и распространять через популярные видеоплатформы, эксплуатируя уязвимости в аппаратных декодерах на смартфонах и в программных декодерах браузеров на ПК.
RSync на стероидах с поддержкой Windows
На Хабре периодически рассказывают о новых инструментах для синхронизации данных. Это интересная тема. Такие программы используются:
- для синхронизации файлов на разных устройствах,
- дедупликации,
- резервного копирования,
- сжатия.
Малейшая оптимизация даёт экономию трафика, места, ускоряет синхронизацию и общую производительность любых систем. Всё, везде и сразу. В эпоху веб-приложений и клиент-серверной архитектуры со множеством девайсов, которые работают в единой инфраструктуре, синхронизация — Святой Грааль, одна из базовых технологий в компьютерной области.
Кроме того, инструменты синхронизации интересны с алгоритмической точки зрения. Любопытно, как люди умудряются оптимизировать базовые алгоритмы типа
rsync
, которые вроде бы работают идеально. Но нет, всегда можно придумать что-то получше.