Huffman Archiver

Консольный архиватор на основе канонического алгоритма Хаффмана — сжатие без потерь с фиксированным заголовком 256 байт (длины кодов для каждого из 256 возможных байт). Реализован на Rust.

Возможности

• Сжатие произвольных файлов (алгоритм Хаффмана)
• Распаковка в исходный файл (без потерь)
• Канонические коды — компактный заголовок (256 байт вместо полного дерева)
• Обработка пустых файлов (корректная ошибка)
• Платформонезависимость (Linux, Windows, macOS)

Сборка и запуск

Требования:

• Rust (компилятор + Cargo), версия 1.85+
• Системные зависимости: build-essential (Linux), C++ Build Tools (Windows) или Xcode Command Line Tools (macOS)

Установка Rust (если ещё не установлен):

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Проверка версии:

rustc --version   # должно быть 1.85 или выше
cargo --version

Сборка:

cargo build --release

После сборки бинарник будет в target/release/huffman-archiver.

Запуск:

# Сжать файл
cargo run --release -- compress <входной_файл> <сжатый_файл>

# Распаковать
cargo run --release -- decompress <сжатый_файл> <выходной_файл>

Или напрямую:

./target/release/huffman-archiver compress input.txt output.huf
./target/release/huffman-archiver decompress output.huf restored.txt

При сжатии выводится степень сжатия:

Исходный размер: 12345 байт
Размер архива:   6789 байт
Степень сжатия:  54.99%

Формат сжатого файла

[ 8 байт  ]  исходный размер файла (big-endian u64)
[256 байт ]  длины канонических кодов (1 байт на символ, 0 = символ отсутствует)
[остальное]  битовый поток закодированных данных с выравнивающим паддингом

Заголовок всегда 264 байта. Алгоритм позволяет восстановить дерево Хаффмана и раскодировать поток, имея только длины кодов.

Архитектура

Проект состоит из пяти модулей:

Модуль	Назначение
frequency	Подсчёт частот байт во входном файле (чтение блоками по 4096 байт)
tree	Построение дерева Хаффмана (BinaryHeap), генерация канонических кодов (u128), восстановление дерева из длин кодов
bitio	Побитовое чтение/запись: BitWriter (буферизация с flush) и BitReader (чтение с EOF-обработкой)
encoder	Сжатие: подсчёт частот → построение кодов → запись заголовка + битового потока
decoder	Распаковка: чтение заголовка → восстановление дерева → побитовый обход до листа

Тестирование

# Все тесты (unit + integration)
cargo test

# С отладочным выводом
cargo test -- --nocapture

# Только модульные тесты
cargo test --lib

# Только интеграционные тесты
cargo test --test integration_test

Покрытие: 41 unit-тест + 8 integration-тестов. Тесты используют системную temp-директорию (std::env::temp_dir()), что гарантирует работу на любой платформе.

Бенчмарки

Для измерения производительности и степени сжатия используется Criterion:

# Запуск бенчмарков (занимает несколько минут)
cargo bench

# Только проверка компиляции (без прогона)
cargo bench --no-run

Бенчмарки тестируют сжатие и распаковку на 4 типах данных:

• english — английский текст (циклический)
• repeated — повторяющийся байт (0xAA)
• all_bytes — все 256 байт по циклу
• random — псевдослучайные данные через хеш-функцию

Размеры: 100, 1000, 10 000, 100 000 байт.

Производительность (матожидание времени, Criterion):

Тип	Сжатие 100	Сжатие 1K	Сжатие 10K	Сжатие 100K	Распаковка 100	Распаковка 1K	Распаковка 10K	Распаковка 100K
english	93 µs	147 µs	552 µs	2.03 ms	165 µs	563 µs	2.29 ms	18.3 ms
repeated	90 µs	127 µs	295 µs	1.30 ms	139 µs	185 µs	849 µs	4.57 ms
all_bytes	108 µs	148 µs	592 µs	2.74 ms	204 µs	771 µs	3.49 ms	31.0 ms
random	134 µs	208 µs	605 µs	2.64 ms	187 µs	801 µs	3.68 ms	31.9 ms

После прогона Criterion генерирует HTML-отчёт с графиками в target/criterion/report/.

Коэффициенты сжатия (выводятся при cargo bench):

=== Коэффициенты сжатия ===
Тип                    Исходный       Сжатый    Ratio
----------------------------------------------------
english                     100          320  320.00%
english                    1000          816   81.60%
english                   10000         5774   57.74%
english                  100000        55354   55.35%
repeated                    100          277  277.00%
repeated                   1000          389   38.90%
repeated                  10000         1514   15.14%
repeated                 100000        12764   12.76%
all_bytes                   100          348  348.00%
all_bytes                  1000         1264  126.40%
all_bytes                 10000        10264  102.64%
all_bytes                100000       100264  100.26%
random                      100          346  346.00%
random                     1000         1243  124.30%
random                    10000        10262  102.62%
random                   100000       100264  100.26%

На несжимаемых данных (равномерное распределение, случайные данные) размер предсказуемо увеличивается из-за фиксированного заголовка в 264 байта.

CI (GitHub Actions)

CI (GitHub Actions) проверяет каждый push и pull request в ветку main:

• fmt — cargo fmt --check
• clippy — cargo clippy -- -D warnings
• build — cargo build --verbose
• test — cargo test --verbose
• bench — cargo bench --no-run (проверка компиляции бенчмарков)

Матрица: ubuntu-latest, windows-latest и macos-latest.

Используемые материалы

Проект написан с нуля, сторонние зависимости не используются (кроме criterion для бенчмарков в dev-зависимостях). Алгоритм реализован по описанию канонического кода Хаффмана.

Лицензия

Распространяется под лицензией MIT. См. файл LICENSE.