Huffman

[Vladimir Rutsky]

Замечания:

1. Передавайте объекты, которые не планируете модифицировать по константной ссылке:

bool encode(std::string const & input_name, std::string const & output_name);

2. Используйте C++ версии заголовочных файлов Си: <climits.h> вместо <limits.h>.

3. Вместо макроса UINT32_MAX используйте C++ шаблонный вариант: std::numeric_limits<std::uint32_t>::max().

4. Вы строите дерево по всем символам, даже тем, которых нет во входном файле, что приводит к более длинным кодам символов. Например ababab.1.in должен сжиматься в один байт сжатых данных, а у вас получается два.

5. Выводимая статистика некорректна. Например при сжатии/распаковке 0D0A0A0A0B.in у вас пишутся несоответствующие друг-другу результаты.

Сжатие:

5
1
1024

Распаковка:

2
5
1024

6. Используйте структуру данных для построения дерева Хаффмена, например std::priority_queue (но не забудьте реализовать стабильный компаратор, т.к. std::priority_queue не гарантирует порядок извлечения элементов с одинаковым приоритетом).

Исправьте, пожалуйста, в ближайшее время.

[Vladimir Rutsky]

Павел, вы будете исправлять ваше решение?

[Kravtsov Pavel]

Да, за эту ночь исправлю

[Kravtsov Pavel]

Все исправлено, извиняюсь за задержку

[Vladimir Rutsky]

Замечания:

1. std::priority_queue не гарантирует, что при добавлении элементов с одним приоритетом они будут извлечены в каком-то определённом порядке, поэтому теоретически ваше решение может строить различные деревья при кодировании и декодировании, если у каких-то символов одинаковый частота встречаемости, при приведёт к ошибочному декодированию.

Сейчас ваш компаратор Node стабильно сравнивает только листья:

  bool operator < (Node const & other) const {
    if (frequency != other.frequency) {
      return frequency > other.frequency;
    } else {
      return byte > other.byte;
    }
  }

т.к. у не-листьев у вас неинициализированное поле byte.

2. При сжатии файла с одним байтом происходит чтение неинициализированной памяти:

==11475== Conditional jump or move depends on uninitialised value(s)
==11475==    at 0x4020CF: Encoder::write_data(std::basic_ifstream<char, std::char_traits<char> >&, std::basic_ofstream<char, std::char_traits<char> >&, Node*, unsigned long) (huffman.cpp:157)
==11475==    by 0x402C2B: Encoder::encode(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) (huffman.cpp:70)
==11475==    by 0x401940: main (main.cpp:28)
==11475== 

[Vladimir Rutsky]

Павел, вы внесёте последние исправления?

[Kravtsov Pavel]

Сейчас исправлю

[Vladimir Rutsky]

Решение зачтено, но с минусом из-за последних исправлений.

[Vladimir Rutsky]

Milestone ha2-deadline deleted