Hacker News Digest

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

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

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