Hacker News Digest

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

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

• OpenZL использует SDDL для описания структуры данных, что позволяет применять специализированные методы сжатия, значительно улучшая компрессию по сравнению с общими алгоритмами (zstd, xz).
• Инструмент эффективен для структурированных и колоночных форматов (Parquet, CSV), но требует описания формата данных через SDDL, C++ или Python код.
• Поддерживает сжатие без потерь, гарантирует точное восстановление данных, планирует добавление потоковой обработки и работы с чанками.
• Вызывает интерес для сжатия геномных данных, JSON (после преобразования), логов и других структурных форматов, но не оптимален для случайных текстовых файлов.
• Реализация включает открытый код (BSD-3-Clause), документацию и white paper; активно развивается, включая будущую поддержку языковых привязок (Python, .NET).

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

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

• Критика недостаточной визуализации динамических блоков и таблиц Хаффмана в gzip/deflate, отсутствие пояснений к параметрам и символам.
• Запросы на улучшение: добавление легенды для цветов, объяснение формата backreference (например, "x4<-135"), поддержка многоблочных текстов.
• Обсуждение технических проблем: несоответствие подсчёта байтов, отсутствие паддинга, предложения по визуализации Brotli и zopfli.
• Упомянуты альтернативные инструменты для визуализации deflate, отмечена сложность кодирования динамических таблиц Хаффмана.
• Шуточные комментарии о тестовых данных (Bee Movie script) и замечания об опечатках в названиях (zlib vs Z-Lib).

Режим --long в Zstandard значительно улучшает сжатие геномных последовательностей, но требует удаления символов новой строки внутри записей.

Специализированные методы сжатия ДНК, такие как MiniPhy, достигают коэффициента сжатия (CR) 91, но работают медленно. Zstandard со стандартными настройками сжимает в 10 раз быстрее, но с CR всего 3.

Использование --long без удаления переносов дало скромное улучшение — CR 3.8. После удаления переносов (seqtk seq -l 0) CR вырос до 11. С максимальным размером окна (--long=31) CR достиг 31, уменьшив размер данных с 2.46ТБ до 80ГБ при увеличении времени сжатия на 80% по сравнению со стандартными настройками.

Хотя --long не дотягивает до специализированных методов, он предлагает хороший баланс между скоростью и эффективностью сжатия для больших файлов с повторяющимися последовательностями. Главное — предварительно удалить переносы строк.

• Удаление незначащих переносов строк в формате FASTA значительно улучшает сжатие Zstd, так как они нарушают поиск длинных совпадений.
• Zstd — байтовый компрессор, не учитывающий семантику данных, поэтому случайные переносы строк снижают его эффективность.
• Использование больших размеров окна (--long) в Zstd улучшает сжатие геномных данных, но требует больше памяти и совместимых настроек при распаковке.
• FASTA и FASTQ критикуются как неэффективные форматы, но остаются популярными из-за простоты и широкой поддержки.
• Для обработки больших геномных данных часто рекомендуется конвертировать FASTA/FASTQ в бинарные или колоночные форматы (например, Parquet).
• Создание специализированных словарей или препроцессинг данных могут значительно улучшить сжатие для специфичных структур.
• Геномные данные обладают высокой избыточностью из-за общих последовательностей у разных видов, что эффективно используется компрессорами.
• Многие инструменты биоинформатики используют внутренние бинарные форматы, но FASTA остаётся стандартом для обмена данными.
• Проблемы с устаревшими форматами и инструментами в биоинформатике частично связаны с трудностями финансирования их поддержки.

Две версии Parquet

DuckDB недавно описали, как SQL-движки, не реализовав полностью спецификацию Parquet, тормозят её развитие. То же происходит в экосистеме: после выхода моей библиотеки Carpet я включил v2 по умолчанию, но быстро откатил изменение — устаревший Pandas не читал такие файлы.

Почему v2 не внедрён

Спецификация готова, но нет согласия, какие именно фичи считать «ядром» v2. Обсуждение в apache/parquet-format длится четвёртый год. Смешиваются два независимых направления:

• новые кодировки (RLE_DICTIONARY, DELTA_BYTE_ARRAY) — ломают только столбец;
• новая структура страниц (Data Page V2) — ломает весь файл.

Логические типы (например, VARIANT) не привязаны к версии формата.

Альтернативы

В ML-среде Parquet и ORC стали тесны, поэтому появились форматы Nimble (Facebook) и LV2 (LanceDB), но в data-engineering Parquet остаётся королём.

Производительность v2

Достаточно выставить WriterVersion.PARQUET_2_0.

Датасет	Алгоритм	v1, МБ	v2, МБ	Δ
Италия	без сжатия	564	355	–37 %
Италия	SNAPPY	220	198	–10 %
NYC	без сжатия	760	511	–33 %
NYC	SNAPPY	542	480	–11 %

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

• Parquet разделён на две версии: v2 экономит место и ускоряет чтение, но экосистема (Spark, Iceberg, Delta Lake и др.) всё ещё в основном на v1.
• Справочная реализация — гигантская Java-библиотека с 74 000 строк кода на каждую комбинацию кодировки, что вызывает сомнения в оптимальности.
• Совместимость между библиотеками (PyArrow, Fastparquet, Spark) долго была проблемой, как и разные версии Scala в Spark.
• Даже простые оптимизации (мета-данные о сортировке) фактически не используются, а многие разработчики не знали о существовании v2.
• Несмотря на критику, Parquet всё равно крупный шаг вперёд по сравнению с предыдущими форматами, и вопросы скорее в медленной эволюции стандарта, чем в самой идее.

День 2: строим дерево Хаффмана

Переписал bz2.adb на чистые структуры:
Bit_Writer, MTF, RLE, Burrows_Wheeler, Huffman.
Каждая структура = пакет + скрытый тип + конструктор Create, методы Encode, Flush, Reset.

Huffman

• Считаем частоты 256 байт + 2 служебных символа (RUNA, RUNB).
• Строим дерево: Node (частота, символ, левый, правый).
• Сортируем список узлов по частоте, склеиваем два минимальных, повторяем, пока не останется один корень.
• Коды длиной ≤ 20 бит (требование BZip2).
• Генерируем таблицу Code_Length[0..257] и Code_Value[0..257].

Оптимизация

• Если дерево выдаёт слишком длинные коды, увеличиваем частоты всех символов на 1 и перестраиваем — быстро сходится.
• Память: дерево живёт только во время построения, затем храним только таблицы.

Интеграция
Huffman.Encode получает поток MTF/RLE-символов, пишет в Bit_Writer:

1. 16-битная маска 0x425A ("BZ").
2. 8-битная версия 0x68.
3. Таблица длин кодов (передаём как 4-битные значения).
4. Сами данные: коды Хаффмана + биты RLE-последовательностей.

Итог за день

• 400 строк Ada, 0 зависимостей.
• Код компилируется gnatmake -O2 bz2.adb за 0.3 с.
• Тест: echo "abracadabra" | ./bz2 > out.bz2, bunzip2 принимает без ошибок.

Завтра: многопоточность и буферизация.

• Участники обсуждают, нужно ли при обращении BWT хранить индекс первого символа: Nayuki утверждает, что это необходимо, а vintermann указывает на полностью биективный вариант без индекса.
• Amy_petrik подчеркивает, что BWT переводит строку в «пространство суффиксных деревьев», что позволяет быстро искать внутри сжатых BZ2-файлов и лежит в основе современных ДНК/РНК-алгоритмов выравнивания.
• Horizon2025 отмечает «магическую» обратимость преобразования при минимуме дополнительных данных.

• В 70‑х некоторые системы (например, PDP‑10) имели 9‑битовые байты, но стандарт закрепился за 8 битами. Если бы байт был 9‑битным, ряд исторических случайностей сыграли бы нам на руку.

• IPv4: при 9‑битовых байтах адрес IPv4 был бы 36‑битным (~64 млрд адресов). Этого хватило бы до 2030‑х без массового NAT и тормозов с IPv6; позже проблему решили бы мягкими рыночными механизмами.

• UNIX time: 32‑битные метки ломаются в 2038, а 36‑битные прожили бы до 3058. Отрицательные охватывали бы времена с 882 года — достаточно для исторических нужд.

• Юникод: вместо 16‑битных 65 тыс. символов было бы 18‑битных 262 тыс. — хватило бы без болезненной унификации CJK; сейчас всех символов ~155 тыс. UTF‑9 стал бы скорее компрессией и уступил бы GZip; либо однобайтно‑двухбайтная схема при умеренной экономии на эмодзи.

• Указатели и память: 36‑битные ОС дали бы до 32 ГБ на процесс (вместо 2 ГБ у 32‑битных). Серверы всё равно виртуализируют; меньшие указатели экономят память и ускоряют код, хотя строки стали бы длиннее — общий баланс близок к нулю.

• Прочие выигрыши:

  • 18‑битные AS‑номера не иссякли бы; порты/PID/UID просторнее.
  • Кодирование инструкций x86/A64 чуть опрятнее; Thumb работал бы лучше.
  • Полуточные 18‑битные числа прижились бы раньше; экзотика 4–5 бит не взлетела бы.
  • Расширенный ASCII влез бы с греческим и стал бы «натовской» кодовой страницей; UTF‑9 привилегировал бы почти всю Западную Европу.
  • Права Unix умещались бы в один байт (без «липких» битов). Оctal стал бы нормой вместо hex.
  • 18‑битный цвет 6/6/6 даёт различия на грани восприятия; потеря альфа‑канала неприятна.

• Издержки? Существенных нет: адресация по битам не используется; деления на девять не требуется; размеры страниц/блоков ОС могли бы остаться прежними, ядру не пришлось бы менять основы работы.

• Обсуждение крутится вокруг гипотетического мира с 9-битными байтами: часть участников отмечает аппаратную неудобность непоказательных (не 2^n) размеров и сложность для мультипликаторов, адресации и сдвигов.
• Скептики считают аргументы «добавим по одному биту и всё станет лучше» натянутыми: решения о размерах всё равно принимались бы иначе, а выигрыш в 12.5% не компенсирует издержки и усложнение.
• Приводятся исторические примеры: PDP-8/10 с 12/36-битными словами, 6-битные коды, термин «octet» для однозначности; упоминается даже N64 с «внутренними» 9-битными байтами для GPU.
• По сетям: 36-битный IPv4 дал бы ~64 млрд адресов, но это лишь отсрочка дефицита; проблемы ASLR и безопасности 32-битной адресации 36 битами решаются слабо, переход на 64 бита всё равно был бы.
• Есть идеи альтернатив: 10-битные байты, тернарные системы, 9-й бит как признак продолжения для варинтов/инструкций, либо как служебный (ECC/контроль/метка данных).
• Отмечают экономику кремния: лишние провода/логика удорожают дизайн; если уже расширять шину, логичнее идти к степеням двойки (например, к 16 битам на «байт»).
• Итоговый тон дискуссии: 9 бит могли бы немного смягчить отдельные «почти-не-хватает» пороги (16/32-бит), но в целом это привнесло бы больше сложностей, чем пользы; ключ — лучше прогнозировать размеры, а не «маскировать» ошибки лишним битом.

I remember that when I was first learning Spanish in high school, I found a piece of (Windows) software that pelted you with a series of pairs of an infinitive and a tense, and you had to conjugate the infinitive accordingly. (Spanish conjugation typically changes the end of the