Huffman Lab - Созданные файлы

Файлы:

• HuffmanCoder.java : Исходный код на Java (кодировщик/декодировщик для командной строки)
• test1_10same.txt : Текстовый файл с 10 одинаковыми символами ("1111111111")
• test2_20_3symbols.txt : Текстовый файл с 20 символами "11111111112222233333"
• FORMAT_DESCRIPTION.txt : Объяснение двоичного формата закодированного файла и принципов декодирования
• BUILD_AND_RUN.txt : Инструкции по компиляции и запуску, а также примеры кодирования/декодирования

СБОРКА И ЗАПУСК

1. Компиляция: Откройте терминал в директории, содержащей HuffmanCoder.java, и выполните: javac HuffmanCoder.java Это создаст HuffmanCoder.class (запрашиваемый бинарный class-файл).

2. Примеры кодирования:

   • Закодировать test1 (режим сырых байтов): java HuffmanCoder -e -i test1_10same.txt -o test1_10same.hfm
   • Закодировать test2 (режим Юникода, обрабатывать входные данные как кодовые точки UTF-8): java HuffmanCoder -e -u -i test2_20_3symbols.txt -o test2_20_3symbols.hfm
   • Закодировать скомпилированный class-файл (тест с бинарными данными): javac HuffmanCoder.java java HuffmanCoder -e -i HuffmanCoder.class -o HuffmanCoder_class.hfm (примечание: для бинарных файлов не используйте -u)

3. Декодирование:

   • Декодировать .hfm файл обратно в оригинал: java HuffmanCoder -d -i test2_20_3symbols.hfm -o test2_decoded.txt

4. Проверка: В UNIX-подобных системах можно сравнить оригинал и декодированный файл: cmp --silent originalfile decodedfile && echo "ФАЙЛЫ ИДЕНТИЧНЫ" || echo "ФАЙЛЫ РАЗЛИЧАЮТСЯ" Или используйте 'sha256sum' для сравнения контрольных сумм.

5. Примечания по Юникоду:

   • Используйте '-u' при кодировании, чтобы обрабатывать входной файл как текст UTF-8, где символами являются кодовые точки Юникода.
   • При декодировании режим (Юникод или байты) сохраняется в заголовке закодированного файла, поэтому передавать '-u' при декодировании не нужно.

Структура результирующего файла

Формат закодированного файла (бинарный) - описание для человека

Заголовок:

• 4 байта: ASCII-магия "HFM1" для идентификации формата
• 1 байт: режим (0 = режим сырых байтов, 1 = режим кодовых точек Юникода)

Раздел словаря:

• 4 байта: количество уникальных символов N (целое число, прямой порядок байтов)
• Затем N записей, каждая:
  • 4 байта: идентификатор символа (int)
    • Если режим==0 (сырые байты): идентификатор символа — это 0..255, представляющее исходное значение байта
    • Если режим==1 (Юникод): идентификатор символа — это кодовая точка Юникода (int)
  • 8 байт: частота (long) -- сколько раз этот символ встречается в исходном файле

Метаданные закодированного битового потока:

• 8 байт: общее количество закодированных бит (long)

Закодированные данные:

• Оставшиеся байты: конкатенация битов кодов Хаффмана для исходных символов, упакованные в байты, начиная со старшего бита (MSB-first). Первый закодированный бит является битом старшего разряда первого записанного байта. Последний байт, если необходимо, дополнен нулями справа (в младших разрядах).

Декодирование:

• Прочитайте частоты и восстановите дерево Хаффмана, используя тот же алгоритм, что и при кодировании.
• Прочитайте ровно 'общее количество закодированных бит' из битового потока и проходите по дереву бит за битом, чтобы извлечь символы.
• Если в словаре существует только один символ (во входных данных был только один уникальный символ), декодируйте, повторяя этот символ количество раз, равное его частоте.
• Для режима Юникода декодированные кодовые точки записываются в выходной файл в виде байтов UTF-8.

Примечания:

• Этот формат сохраняет частоты символов; следовательно, декодер может восстановить то же дерево Хаффмана.
• Реализация использует кодирование целых чисел и long в прямом порядке байтов (big-endian) с помощью процедур Java Data{Input,Output}Stream.