hw2

[Vladimir Rutsky]

Замечания:

1. Не используйте define:

#define int32 std::uint32_t
#define byte std::uint8_t

Вы можете достичь аналогичного поведения создав алиасы для типов:

typedef std::uint32_t int32;
typedef std::uint8_t byte;

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

Сделайте сравнение Node * стабильным (для всех вершин, не только листьев).

3. Выводимая статистика сжатия/распаковки некорректна. Например для ab.1.in

сжатие:

2
1
1024

распаковка:

2
2
1024

4. При сжатии пустого файла происходит ошибка доступа к памяти при проверке valgrind:

==9558== Conditional jump or move depends on uninitialised value(s)
==9558==    at 0x401C59: operator= (stl_bvector.h:86)
==9558==    by 0x401C59: getBits(unsigned char, std::vector<bool, std::allocator<bool> >&) (huffman.cpp:26)
==9558==    by 0x4028C2: decode(std::vector<unsigned char, std::allocator<unsigned char> > const&, std::vector<unsigned int, std::allocator<unsigned int> > const&) (huffman.cpp:101)
==9558==    by 0x4016F2: main (main.cpp:72)
==9558== 

5. Вы строите дерево включая все символы, даже те, которые не встречаются в исходном файле, что приводит к построению неоптимальных кодов (например, abababab.1.in должен упаковаться в один байт, а у вас упаковывается в два).

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

[shenbin.ilya]

Всё исправлено, подробнее по некоторым пунктам:
2) В случае равенства частот теперь производится сравнение по символу из самого левого листа дерева (т.к. все символы в листьях уникальны, а сравниваемые деревья не пересекаются, то между такими деревьями всегда можно поставить строгое неравенство).
3) Дважды считывался последний символ файла.
5) Если в исходном файле встречался только один уникальный символ, то к построению дерева добавляю еще один символ с нулевой частотой (исключительно ради удобства). Коды при этом остаются оптимальными. abababab.1.in теперь упаковывается в один байт.

[Vladimir Rutsky]

Замечания:

1. При распаковке вы выводите статистике не в том порядке.

2. Вы не освобождаете память от "лишних" узлов дерева, которые создаёте здесь:

 std::vector<Node *> nodes_array(256);
 for (int i = 0; i < 256; i++) {
     nodes_array[i] = new Node((byte) i, count_table[i]);
 }

[shenbin.ilya]

Исправил.
Лишние узлы теперь не создаю.

[Vladimir Rutsky]

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

[Vladimir Rutsky]

Milestone ha2-deadline deleted