Кодирование Хаффмана

[Иван Кремнев]

Прошёл проверку с valgring.
У меня сразу возникли вопросы по cast'ам. Правомерно ли их использование в данном контексте?

[Vladimir Rutsky]

Это корректное использование reinterpret_cast:

		uint32_t alpha_size = alphabet_size();
...
		output.write(reinterpret_cast<char*>(&alpha_size), sizeof(alpha_size));

Здесь не подходит динамическое приведение типа (dynamic_cast) и не подразумевается статическое приведение типа (static_cast), здесь вы именно хотите посмотреть на область памяти, которая представлена указателем одного типа, как на массив байт --- reinterpret_cast предназначен именно для такой операции.

Замечения:

1. Нельзя пропускать значения аргументов по умолчанию при объявлении функции:

// huffman.hpp
struct ByteFrequency {
...
	ByteFrequency(uint8_t byte, uint32_t frequnecy, bool is_leaf,
		size_t left, size_t right);
...
// huffman.cpp
ByteFrequency::ByteFrequency(
	uint8_t byte = 0,
	uint32_t frequency = 0,
	bool is_leaf = true,
	size_t left = 0,
	size_t right = 0):
	
	basic_byte(byte),
	frequency(frequency),
	leaf(is_leaf),
	left(left),
	right(right) {}

Наоборот, вы можете их указывать только в декларации и всё будет работать.

2. Для получения размера поля класса нет необходимости получать инстанс класса:

//sizeof(((ByteCode*)nullptr)->code_length)
sizeof(ByteCode::code_length)

3. Выводимая статистика распаковки не соответствует условию задачи (сначала должен идти размер сжатых данных, затем размер распакованных).

Вопрос: всегда ли вам хватает uint32_t для представления кода символа?

Исправьте, пожалуйста, в течение 60 часов.

[Иван Кремнев]

Спасибо за замечания! Да, на предложенных тестах uint32_t вполне хватило, хотя, возможно, и впритык.
Все исправления выполнены.

[Vladimir Rutsky]

Replying to kremnev.ivan:

Спасибо за замечания! Да, на предложенных тестах uint32_t вполне хватило, хотя, возможно, и впритык.

Можете придумать тест, на котором uint32_t не хватит?

[Иван Кремнев]

Чтобы не хватило 32 битов для кодирования символов, дерево Хаффмана должно иметь глубину 33, по крайней мере. Самый быстрый способ набрать такую глубину -- построить дерево из 33*2+1 вершины, в котором будет одна главная ветвь, на которой будут висеть листья по всей её длине.

Различных байтов в исходном документе требуется как минимум 34. При этом каждый байт из более высокого уровня должен иметь частоту, не меньшую суммы частот всех байтов из нижнего уровня. То есть в исходном документе частоты байтов должны расти как минимум по закону
f_i = f₀ + f₁ + ... + f_i-1
Если f₀ = 1, f₁ = 1, то
f₂ = 1 + 1 = 2
f₃ = f₀ + f₁ + f₂ = 2*f₂ = 4
f₄ = f₀ + f₁ + f₂ + f₃ = 2*f₃ = 8
...
f₃₃ = 2³²

Получается, что минимальный исходный документ, требующий более 32 битов для кодирования по Хаффману содержит 34 различных байта с частотами 1, 1, 2, ... , 2³². Размер такого документа составляет
1 + 1 + 2 + 4 + ... + 2³² = 2³³ байтов, т.е. 8 Гб.

[Vladimir Rutsky]

Replying to kremnev.ivan:

Чтобы не хватило 32 битов для кодирования символов, дерево Хаффмана должно иметь глубину 33, по крайней мере. Самый быстрый способ набрать такую глубину -- построить дерево из 33*2+1 вершины, в котором будет одна главная ветвь, на которой будут висеть листья по всей её длине.

Различных байтов в исходном документе требуется как минимум 34. При этом каждый байт из более высокого уровня должен иметь частоту, не меньшую суммы частот всех байтов из нижнего уровня. То есть в исходном документе частоты байтов должны расти как минимум по закону
f_i = f₀ + f₁ + ... + f_i-1

В целом рассуждения хорошие, но данное утверждение неверно.
Например, символы, встречающиеся 1, 1, 2, 3, 5, 8 раз создадут описанное выше вытянутое дерево:

     20
    / \
   8   12
      / \
     5   7 
        / \
       3   4
          / \
         2   2
        / \
       1   1

Если f₀ = 1, f₁ = 1, то
f₂ = 1 + 1 = 2
f₃ = f₀ + f₁ + f₂ = 2*f₂ = 4
f₄ = f₀ + f₁ + f₂ + f₃ = 2*f₃ = 8
...
f₃₃ = 2³²

Получается, что минимальный исходный документ, требующий более 32 битов для кодирования по Хаффману содержит 34 различных байта с частотами 1, 1, 2, ... , 2³². Размер такого документа составляет
1 + 1 + 2 + 4 + ... + 2³² = 2³³ байтов, т.е. 8 Гб.

Можно доказать, что минимальный тест, дающий вытянутое дерево с кодами из более чем 32-бита будет более 5 МБ, что превышает ограничения, указанные в условии задачи.

Решение зачтено.

[Иван Кремнев]

Да, понял, где был не прав. Спасибо!

[Vladimir Rutsky]

Milestone ha2-milestone2 deleted