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

[Alexander]

Здравствуйте, Владимир.

Прошу проверить задание 2.
Спасибо.

С уважением,
Александр

[Vladimir Rutsky]

Замечания:

1. Используйте здесь объявленную вами константу mb5:

uint32_t add_code(std::bitset<41943040> &big_bitset, uint32_t pos);

2. Все методы класса Huffman статические. В данном случае нет смысла использовать класс в качестве интерфейса --- оставьте две функции compress и decompress, а остальные детали реализации перенесите в huffman.cpp.

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

Сделайте сравнение в Huffman_comparison стабильным.

4. При сжатии/распаковке пустого файла не выводится статистика сжатия/распаковки.

5. Храните таблицу встречаемости символов и сжатый поток символов в двоичном виде.

6. Выводимая статистика сжатия/распаковки не соответствует требованиям условия задачи (например, размер таблицы при сжатии должен выводиться в последнюю очередь).

7. Нет необходимости записывать в архив количество байт в исходном файле --- его можно вычислить из таблицы встречаемости.

8. Не создавайте большие bitset-ы на стеке, создавайте их в куче. Стек обычно ограничен по размеру и использование его для хранения 5 МБ данных --- нетипичное использование.

9. Вы не освобождаете память, выделенную для хранения дерева, в случае, когда файл состоит из одного байта.

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

[Alexander]

К сожалению, не могу понять, с чем связан вывод не в двоичном виде - на сколько я понимаю, для этого достаточно поставить нужные флаги и использовать put/get/read/write, что, если я все доглядел, и происходит. В остальном поправил, спасибо за замечания.

[Vladimir Rutsky]

Александр, вывод в двоичном виде --- это запись "сырого" потока байт.

Когда вы пишете:

std::uint8_t x = 123;
stream << x;

Вы записываете в поток три байта --- 0x31 ('1'), 0x32 ('2'), 0x33 '3' --- представления числа 123 в десятичной системе счисления.

Результат такого способа вывода человеко-читаем, но не компактен.

Вывод в двоичном виде:

std::uint8_t x = 123;
stream.write(reinterpret_cast<char *>(&x), sizeof(x));

здесь в поток записывается один байт со значением 123 (0x7B, '{').

Такая сериализация быстрее, компактнее и не требует разделителя между полями.

Вам необходимо записывать все данные в двоичном виде именно в этом смысле.

Отрывать файл нужно в двоичном режиме --- это другая вещь, которая тоже необходима.

[Alexander]

Поправил, теперь выводится нормально.

Не слишком понял почему, но влияли данные строки. Поменяв это

//uint32_t n;
out.put((n >> 24) & 0xff);
out.put((n >> 16) & 0xff);
out.put((n >> 8) & 0xff);
out.put((n >> 0) & 0xff);

на это,

out.write(reinterpret_cast<char *>(&n), sizeof(n))

получил то, что надо. Возникает вопрос, с чем это, возможно, связано?
Единственное предположение, конечно, из-за не того типа n, но, так как все равно должно к char приводится, странно.

[Vladimir Rutsky]

Алекксандр, сжатие/распаковка теста fib.in работает некорректно. Посмотрите, пожалуйста.

[Alexander]

Так, сейчас вроде точно должно все верно работать: доходит до конца, сжимает, разжимает в тот же файл.

[Vladimir Rutsky]

Сомневаюсь, что перенос инклудов может пофиксить такую ошибку :)

[Alexander]

Хм, тогда очень странно :)
Я просто в разных местах открыл, потому в другом месте поправил, а из-за инклудов не понял, что цпп-шник не изменился.
Вы не могли бы пояснить, что означает некорректно в таком случае?

[Alexander]

Странно, потому что смоук тесты проходят, сам запускаю приложенным к решению мейкфайлом - результаты сжатия: 491042, 164189, 91. diff не выдает ничего, на глаз исходный и разжатый совпадают. Каких-то особых условий в условиях задачи я не нашел, потому не могу понять, в чем некорректность. Прошу пояснить, если это возможно.

[Vladimir Rutsky]

Какой компилятор и какой версии вы используете?

Причина ошибки в этой строке:

const static uint8_t maximal_length_of_code = 8;

[Alexander]

clang-800.0.42.1
Без этой строки вообще можно обойтись, например, в битсете напрямую 8 писать в качестве размера, а не через maximal_length_of_code.

[Vladimir Rutsky]

То есть auto bits = bitset<8>(code);?
А что, если code не влезет в 8 бит битсета?

[Alexander]

Будет непонятно что.
Спасибо

[Alexander]

Поправил на 64. В 64 он точно должен поместиться (иначе сам код в int64_t не помещается), а size отвечает за перенос с корректного места.
Странно, что у меня на машине работало, неужели, с таким конструктором можно было бы за пределы битсета обратиться?

[Vladimir Rutsky]

​Тут указано, что обращение за границы это undefined behavior, видимо, вам везло.

[Alexander]

Понятно, все для удобства :)

[Alexander]

Так как code еще в конструктор передается и получалось, что программа в некоторых случаях работает "корректно", то видимо уже в конструкторе может происходить обращение за пределы битсета (вернее, стандарт, видимо, это не предусматривает, а clang поступал именно так).
Еще раз спасибо за помощь

[Vladimir Rutsky]

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

[Vladimir Rutsky]

Milestone ha2-milestone2 deleted