Hacker News Digest

Статья в интерактивном формате объясняет, как работает Burrows-Wheeler Transform (BWT) — алгоритм, который лежит в основе сжатия bzip2 и инструментов выравнивания последовательностей bowtie/bwa. Суть BWT в том, что он группирует идентичные символы, а затем позволяет точно восстановить исходную строку. Для демонстрации автор кодирует слово «banana» и показывает, как появление символа $ вращает матрицу, делая обратное преобразование возможным. В статье также показано, как поиск подстроки сводится к просмотру первого и последнего столбцов, и как это используется в биоинформатике для выравнивания ДНК-чтения.

• BWT позволяет искать подстроку за O(l) времени и имеет O(n) памяти, что делает его одним из самых элегантных алгоритмов, которые я когда-либо встречал.
• Сложность в понимании BWT часто заключается в том, что «сортировать» означает лексикографически сортировать все вращения, а не просто сортировать строку.
• Публикация алгоритма была отвергнута, и вместо этого он был опубликован как DEC тех. отчет, что является интересным фактом.
• Суффиксные массивы и BWT взаимно-обратны, и это свойство используется для поиска подстроки в O(l) времени.
• Несмотря на то, что BWT сам по себе не сжимает данные, он является ключевым шагом в bzip2 и других алгоритмах сжатия без потерь.

Разработчик создал конкурентный энкодер BZip2 на Ada, добавив в третьей части неожиданный элемент машинного обучения для оптимизации энтропийного кодирования. Вместо стандартного подхода он использовал нейросеть для предсказания вероятностей символов, что позволило улучшить сжатие данных. Это решение оказалось эффективнее традиционных статистических методов, демонстрируя гибкость подхода.

Ключевой идеей стало применение простой двухслойной нейросети, обученной на лету, что дало прирост в 2–3% по сравнению с классическим Huffman-кодированием. Такой гибридный метод показывает, как даже базовое ML может решать узкоспециализированные задачи, где точность предсказаний критична. Практический вывод: машинное обучение может быть интегрировано в низкоуровневые системы для нетривиального улучшения производительности.

• Автор выражает разочарование отсутствием связи между обсуждаемым алгоритмом BZip2/BZip3 и языком программирования Ada в статье.
• Несколько пользователей жалуются на чрезмерно навязчивую и мешающую чтению рекламу на сайте.
• Обсуждается использование блокировщиков рекламы (AdBlock, Pi-hole, NextDNS) как необходимое средство для комфортного просмотра сайтов.
• Один пользователь отмечает, что не видит рекламы без блокировщика, что вызывает удивление у других.
• Упоминается, что даже ФБР рекомендует использовать блокировщики рекламы в целях безопасности.

День 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 отмечает «магическую» обратимость преобразования при минимуме дополнительных данных.