ha2

[Мусатян Сабрина]

Здравствуйте,
Добавила свое решение по задаче Хаффмана.
По данному решению есть несколько вопросов: не совсем понимаю как пользоваться режимом binary: идея std::ios_base::binary то есть если я ставлю такой флаг перед чтением и записью то что происходит? Могу ли я допустим пытаться прочитать char, int и тому подобное и в чем будет разница? Так что предполагаю, что в задании я им вообще не пользуюсь.
Так же я не понимаю как писать по битам (если я получила строку с представлением моего символа в виде ноликов и единичек и хочу записать именно бит то как это сделать)
От того как писать по битам видимо зависит подсчет размера; я писала строку и считаю что я пишу 0 или 1 как по битам и в зависимости от этого вывожу размер; скорее всего моя идея неверна, так что прошу помощи в этом.
Смок тесты не проверяла, в связи вышеописаными вопросами (так как не до конца видимо понимаю идею задания и потому тестить сложно)

[Vladimir Rutsky]

Replying to musatyan.sabrina:

Здравствуйте,
Добавила свое решение по задаче Хаффмана.
По данному решению есть несколько вопросов: не совсем понимаю как пользоваться режимом binary: идея std::ios_base::binary то есть если я ставлю такой флаг перед чтением и записью то что происходит? Могу ли я допустим пытаться прочитать char, int и тому подобное и в чем будет разница? Так что предполагаю, что в задании я им вообще не пользуюсь.
Так же я не понимаю как писать по битам (если я получила строку с представлением моего символа в виде ноликов и единичек и хочу записать именно бит то как это сделать)
От того как писать по битам видимо зависит подсчет размера; я писала строку и считаю что я пишу 0 или 1 как по битам и в зависимости от этого вывожу размер; скорее всего моя идея неверна, так что прошу помощи в этом.
Смок тесты не проверяла, в связи вышеописаными вопросами (так как не до конца видимо понимаю идею задания и потому тестить сложно)

Если кратно, то запись числа в текстовом виде это:

std::uint32_t a = 10;
fout << a << "\n";

в двоичном:

std::uint32_t a = 10;
fout.write(reinterpret_cast<char *>(&a), sizeof(a));

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

В двоичном виде в файл записываются байты представления числа в памяти. При этом так как размер типа фиксирован (std::uint32_t --- имеет размер 32 бита или 4 байта), то писать символы разделители не требуется.

Текстовое представление существенно менее компактно, чем двоичное, не допускает запись произвольных данных (все данные нужно представить в текстовом виде).

Плюс запись в текстовом виде подвержена специальным преобразованиями: символ перевода строки \n в текстовом режиме в Linux будет записан как байт с кодом 0x0A, в Windows как два байта 0x0D, 0x0A, а в некоторых других ОС как один байт с кодом 0x0D. Открытие файла с флагом std::ios_base::binary отключает эти преобразования (std::ios_base::binary должен быть передан в ifstream):

std::ifstream fin(commands[2], std::ios_base::binary);

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

Биты сжатого потока необходимо упаковывать в байты (то есть 8 бит составят один байт в выходном файле).
Для упаковки в байты вам нужно будет повторить/изучить битовые операции с числами.
Если количество бит не кратно восьми, их можно, например, дополнить нулями.

Рассмотрим пример.
Пусть входной файл имеет содержимое сabccbc.
У символов будут следующие коды: c - 0, a - 10, b - 11 (после построения дерева Хаффмена и его обхода).
Значит сabccbc будет кодировано в 0101100110 --- это 10 бит информации.
10 бит можно разбить на 8 + 2 бита, упаковать в один байт первые 8 бит 01011001, а оставшиеся 2 бита пополнить нулями до полного байта: 00000010.

Итого длина сжатого потока будет 2 байта.

Замечания:

1. Не используйте альтернативное описание операторов в C++, используйте || вместо or:

//if (commands[1] != "-f" or commands[3] != "-o"){
if (commands[1] != "-f" || commands[3] != "-o"){

Альтернативное написание операторов предполагается для систем, где сложно набирать символы, вроде |.

2. Заголовочный файл должен содержать минимальный интерфейс для функций и классов, которые реализованы в cpp файле. В данном случае setCharCode и ASCIISYMBOLS --- это детали реализации, их стоит перенести в huffman.cpp. Также оставьте включение только необходимых для использования huffman.hpp заголовочных файлов (например, <iostream> и <vector> там не нужны).

3. Используйте тип size_t для индексов и размеров.

4. В классе huffman все функции статические, что делает его не особо полезным как класс --- лучше сделать свободные функции encode и decode.

Перенесите весь код отвечающий за кодирование/декодирование файла в huffman.cpp/huffman.hpp.
В main.cpp стоит только обрабатывать аргументы командной строки, вызывать encode()/decode(), и выводить статистику сжатия.

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

setCharCode(std::string const & c, int f)

6. При декодировании вы перебираете все коды и ищете подходящий, что неоптимально. Постройте префиксное дерево для кодов, и спускайтесь по нему для декодирования.

7. Читайте/записывайте данные в двоичном виде.

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

[Мусатян Сабрина]

Здравствуйте,
Удалось поработать над исправлениями только вчера вечером и сегодня ночью. В связи с большой нагрузкой в университете, не было до этого такой возможности.
У меня появилась проблема в смок тестах: не проходит тест видимо потому что в нем есть перевод строки, а у меня код их по видимому не запоминает. Как я поняла перевод строки во всех системах различный. Если я читаю строки getline, разве не должен был бы символ перевода прочитаться и соответственно закодироваться? Подскажите пожалуйста, как можно решить эту проблему?
Еще выдает ошибку на тесте 000000001.2, когда открываю тест, то он пустой. Подскажите пожалуйста, в чем тут может быть проблема?

Заранее благодарю

[Vladimir Rutsky]

Replying to musatyan.sabrina:

Здравствуйте,
Удалось поработать над исправлениями только вчера вечером и сегодня ночью. В связи с большой нагрузкой в университете, не было до этого такой возможности.
У меня появилась проблема в смок тестах: не проходит тест видимо потому что в нем есть перевод строки, а у меня код их по видимому не запоминает. Как я поняла перевод строки во всех системах различный. Если я читаю строки getline, разве не должен был бы символ перевода прочитаться и соответственно закодироваться? Подскажите пожалуйста, как можно решить эту проблему?

При чтении в двоичном виде не стоит использовать getline(), используйте fin.read() или fin.get(). Можете закоммитить ваш код в репозиторий, чтобы я мог дать более конкретные замечания?

Еще выдает ошибку на тесте 000000001.2, когда открываю тест, то он пустой. Подскажите пожалуйста, в чем тут может быть проблема?

Чем вы открываете файл с тестом?
Тесты содержат байты с различными значениями, в том числе "нечитаемыми" (см. ​https://ru.wikipedia.org/wiki/ASCII).
Обычный текстовый редактор либо покажет нечитаемые символы каким-то специальным образом, либо вообще пропустит их. Файл 000000001.2.in содержит 8 байт со значениями 0 и один байт со значением 1.
0 и 1 --- это одни из "нечитаемых" символов, поэтому их редакторы не должны нормально отображать.
Вы можете использовать редактор с поддержкой визуализации данных в шестнадцатеричном виде, чтобы посмотреть значения байт в файле.

Я в Linux/MacOS использую встроенный в Midnight Commander просмотрщик файлов для этого, либо в терминале xxd (в Ubuntu ставится вместе с vim):

$ xxd 000000001.2.in
00000000: 0000 0000 0000 0000 01                   .........
$ xxd abc.1.in 
00000000: 6162 63                                  abc

(0x61, 0x62, 0x63 --- шестнадцатеричные коды символов a, b, c соответственно).

либо hexdump:

$ hexdump 000000001.2.in
0000000 0000 0000 0000 0000 0001               
0000009
$ hexdump abc.1.in
0000000 6261 0063                              
0000003

[Мусатян Сабрина]

Исправила на cin.get(), теперь читает исходный файл корректно, но при этом (видимо из - за символа перевода строки) теперь неправильно кодирует, хотя без символа перевода до этого кодировал правильно. Закоммитила свой код (не проходит тесты где есть перевод строки). Посмотрите пожалуйста, в чем может быть проблема.
Получилось посмотреть файлы с тестами с помощью xxd - спасибо

Извините, что задаю вопросы после всех дедлайнов и благодарю за понимание.

[Мусатян Сабрина]

Нашла решение этой проблемы, но интересуют, являются ли такие преобразования корректными:

char c;
uint8_t ca;
input.read(reinterpret_cast<char *>(&ca), sizeof(ca));
c = ca;

Пришлю код до вечера пятницы(код стайл надо поправить)
Спасибо

[Vladimir Rutsky]

Replying to musatyan.sabrina:

Нашла решение этой проблемы, но интересуют, являются ли такие преобразования корректными:

char c;
uint8_t ca;
input.read(reinterpret_cast<char *>(&ca), sizeof(ca));
c = ca;

Да, использование reinterpret_cast в данном контексте корректно.

Проблема с переводом строки ранее у вас могла возникать из-за использования std::getline, который удаляет считанные переводы строки (но не всегда, например, в конце файла может не быть перевода строки).

[Мусатян Сабрина]

Здравствуйте,

Закоммитила исправления:
Остался вопрос можно ли так делать:

Верно ли так передавать указатели и обращаться к ним:
mapForCodes readTable(std::ifstream &input, size_t *helpSize){

uint32_t tableSize;
input.read(reinterpret_cast<char *>(&tableSize), sizeof(tableSize));
mapForFreq chars;
(*helpSize) += (SizeOfEachTableLine? * tableSize);
...

Если я это сделала неправильно, то скажите пожалуйста, как надо, я исправлю

Касательно замечаний:
1) исправлено
2)Если я правильно поняла, то в huffman.hpp нужно было оставить только две функции encode и decode (что и было сделано)
3)исправлено
4)сделала практически все отдельными функциями, остались только необходимые структуры дерева и для частот символов
5)исправлено
6)написала структуру дерева, что ускоряет алгоритм
7)исправлено

Проверено на смок тестас с использованием valgrind (все проходит).
Подскажите пожалуйста, правильно ли, что например для пустого файла все равно необходимо записать вспомогательную информацию и в итоге получается, что фактически сжатый файл больше, чем исходный (так же на файлах маленьких размеров таблица занимает минимум 12 байт и возникает та же ситуация)

Я говорю про следующую статистику (для пустого файла):

Running: /Users/sabrina/Desktop/cscenter/c++/ha2/ha2/huffman -c -f empty.0.in -o compressed
0
0
12
* Running: /Users/sabrina/Desktop/cscenter/c++/ha2/ha2/huffman -u -f compressed -o decompressed
0
0
12

[Vladimir Rutsky]

Здравствуйте!

Replying to musatyan.sabrina:

Здравствуйте,

Закоммитила исправления:
Остался вопрос можно ли так делать:

Верно ли так передавать указатели и обращаться к ним:
mapForCodes readTable(std::ifstream &input, size_t *helpSize){

uint32_t tableSize;
input.read(reinterpret_cast<char *>(&tableSize), sizeof(tableSize));
mapForFreq chars;
(*helpSize) += (SizeOfEachTableLine? * tableSize);
...

Если я это сделала неправильно, то скажите пожалуйста, как надо, я исправлю

Не очень понимаю вопрос. Вы хотите внутри функции изменить helpSize так, чтобы снаружи функции это изменение отразилось? В таком случае да, передавайте переменную для изменения (helpSize) либо по указателю (адрес helpSize), либо по ссылке.

Подскажите пожалуйста, правильно ли, что например для пустого файла все равно необходимо записать вспомогательную информацию и в итоге получается, что фактически сжатый файл больше, чем исходный (так же на файлах маленьких размеров таблица занимает минимум 12 байт и возникает та же ситуация)

Я говорю про следующую статистику (для пустого файла):

Running: /Users/sabrina/Desktop/cscenter/c++/ha2/ha2/huffman -c -f empty.0.in -o compressed
0
0
12
* Running: /Users/sabrina/Desktop/cscenter/c++/ha2/ha2/huffman -u -f compressed -o decompressed
0
0
12

Сжатый файл может быть больше, чем исходный из-за записи таблицы частот (и в некоторых случаях из-за сжатых данных, при кодировании плохо сжимаемых данных), это не страшно.

[Мусатян Сабрина]

Да, это именно то, в чем и был мой вопрос.

Спасибо за ответы!

[Vladimir Rutsky]

Замечания:

1. Заголовочный файл должен быть самодостаточным. Вы используете в huffman.hpp std::ifstream/std::ofstream, но не включаете соответствующие заголовочные файлы.

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

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

3. При проверке с помощью valgrind обнаруживается чтение неинициализированных данных:

==21865== Conditional jump or move depends on uninitialised value(s)
==21865==    at 0x402731: writeBytesOfText(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, unsigned int*) (huffman.cpp:98)
==21865==    by 0x404060: encode(std::basic_ifstream<char, std::char_traits<char> >&, std::basic_ofstream<char, std::char_traits<char> >&) (huffman.cpp:147)
==21865==    by 0x401D95: main (main.cpp:45)
==21865== 

Если вы замените доступ к элементам text с [] на .at() в writeBytesOfText, то увидите ошибку:

// if (text[i + j] == '1'){
if (text.at(i + j) == '1'){

Я не указал замечание про стабильность std::priority_queue в первой проверке, а оно существенно --- исправьте, пожалуйста, в ближайшее время.
Также последнее замечание критично.

[Мусатян Сабрина]

1.Исправлено
2.Переписала компоратор, сравнение по string теперь гарантирует однозначность
3.Не смогла получить именно такое сообщение от валгринда(хотя пробовала запускать его с разными опциями). С помощью at(i + j) ошибку нашла и исправила.

[Vladimir Rutsky]

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

[Vladimir Rutsky]

Milestone ha2-deadline deleted