Этот репозиторий состоит из реализаций кодирования и раскодирования по алгоритму Хаффмана. Кодирование и декодирование реализовано на C и так же на Typescript. Имеются консольные версии и web-демо (webassembly).
Сжатие проходит в два прохода по файлу - сначала считается статистика по частоте используемых байтов, затем строится дерево Хаффмана и далее вторым проходом по файлу идёт сжатие.
Распаковка проходит в один проход - читается заголовок, строится дерево по информации из заголовка и далее сжатый файл читается по битам.
Первые 4 байта - заголовок, фиксированные случайно выбранные 4 байта.
Далее 4 байта - размер оригинального файла.
После этого идёт поток битов для описания дерева. Дерево записывается простым обходом. Если это внутренний узел, то записать бит 0. Если это лист, то записать бит 1 и далее 8 битов на соответствующий байт. Всего должно получиться 255 внутренних узлов и 256 листов, т.е. 255*1 + 256*(1 + 8) = 2559 битов. После этого идёт контрольный нулевой бит для того чтобы заголовок закончился на целом байте.
Далее идёт поток битов для самих данных.
Последний байт дополняется до целого байта нулевыми битами если нужно.
Собирается через gcc на Windows (с mingw) или на Linux:
gcc -Wall -o main main.c
./main encode <имя входного файла> <имя сжатого выходного файла>
./main decode <имя сжатого входного файла> <имя выходного файла>
В main.c находится только CLI оболочка, а вся логика реализована в huffman.c.
Функция кодирования - это huffman_encode, принимает 3 параметра - указатель на буфер с входными данными, длина входного буфера, указатель на переменную куда запишется размер выходного буфера. Внутри функции выделяется память на выходной буфер (его длина как раз идёт в outlen), и далее функция возвращает указатель на выделенный блок памяти (либо NULL если произошла ошибка).
Функция декодирования - это huffman_decode, принимает 2 параметра - указатель на входной буфер и указатель на переменную куда запишется размер выходного буфера. Размер входного буфера определяется в заголовке (точнее, там определяется размер файла до сжатия). Так же аллоцирует память и возвращает указатель на буфер либо NULL.
Ядро находится в huffman.ts, CLI оболочка в main.ts. Для запуска нужен nodejs и typescript, можно предварительно собирать в js либо запускать сразу с ts-node
ts-node -T main.ts encode <some-input-file> <some-output-encoded-file>
ts-node -T main.ts decode <some-input-encoded-file> <some-output-decoded-file>
Тесты проверяют сжатие обоими версиями (C и TS), проверяют что файл распаковывается и совпадает с оригинальным. Запускаются тесты в ./test.sh
Собирается с emscripten в buildWeb.sh, доступна по адресу https://roginvs.github.io/huffman_coding/web/
Я не использовал webpack/react/etc чтобы не тянуть большие зависимости.
Интересно что я из C кода экспортировал malloc/free для того, чтобы иметь возможность получать в javascript буферы в аллокаторе из stdlib.
Webassembly реализация работает где-то раза в 4 быстрей чем javascript.
Почему-то WebAssembly версия падает на файле hpmor_ru.html.huffman.huffman (два раза сжатый ./test/hpmor_ru.html). При этом C версия пакует нормально и полученный файл так же распаковывается. Возможно где-то неправильно используется emscripten.
Update: Почему-то Webassembly теперь падает на hpmor_ru.html.huffman.huffman.huffman
Update2: Теперь почему-то вообще не падает, хотя wasm файл не поменялся.