Добрый день. Делаю лабу по методу сжатия данных. Сжимаю текст методом Хаффмана, словарь тоже надо бы сжать. Метод надо выбрать самому. Какой алгоритм сжатия словаря посоветуете? Арифметическое кодирование, коды Райса Гоши или, может вообще лучше взять коды Фибоначи?

какой еще в жпо словарь в методе хаффмана? когда там уникальные символы и биты и нечего сжимать совершенно

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

лучше ANS сделай, там прикольное кодирование дробным числом бит каждого символа, получается наилучшее сжатие для символов с одинаковой частотой, но алгоритм расшифровки сложнее и учитывает предыдущий символ при сжатии/распаковке

(2) Это если предопределенный словарь, который храниться и на кодере, и на декодере, тогда да, в запакованный файл его помещать не требуется. Но если в кодере и декодере словарь не храниться, а создается динамический по кодируемому тексту, то его надо в результирующий файл поместить. Препод сказал, что нужно оба варианта сделать и сравнить.
Но помещать словарь в заархиврованный файл как есть типа моветон и его тоже надо как-то сжать.

(3) ANS - это арифметическое кодирование что ли, там где отрезок 0,1 делиться на кучу частей?

(4) ты хотя бы https://ru.wikipedia.org/wiki/Код_Хаффмана прочитал и понял?

там "словарь" это последовательность уникальных символов, например для "мама мыла раму":
"м" - 4,
"а" - 4,
" " - 2,
"ы" - 1,
"л" - 1,
"р" - 1,
"у" - 1

будет "словарь": "ма ылру" и при кодировке CP1251 будет максимум 256 символов )), весь "словарь" это сама последовательность и всегда можно восстановить

если эту последовательность не передать с кодируемым текстом то нифуя нельзя нифего восстановить

и кто то не понял препода или преподу рановато учить ему бы самому подучиться...

(1) А! Понял. Биты можно отдельным блоком запаковать в файл (да, действительно их уже не сжать), и отдельным потом блоком буквы. Буквы, не знаю только, имеет ли смыл еще и арифметическим кодированием сжать...

(7) да не нужны нафик никакие биты... тебе исходные уникальные символы нужны в каком порядке ты их начал кодировать все большим числом бит

(8)+ для простоты "распаковки" да можно биты тоже засунуть с символами, чтобы не повторять алгоритм Хаффмана перед распаковкой

(5) https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems

(9) А, спасибо, понял.
Получается, я могу не засовывать биты в файл, но при распаковке мне придется для словаря повторить алгоритм нахождения битовых кодов, и все. Поскольку символы уже будут в нужном порядке отсортированы. Но если надо ускорить распаковку то можно и биты засунуть. Кстати, я заметил, что распаковывает алгоритм гораздо быстрее чем упаковывает, видимо это как раз связно с процедурой определения битовых кодов.

(11) ага, размер "словаря" в архиве смешной же и по сути кол-во символов уникальных в тексте

А кодирование по Хаффману с одинаковым словарем на источнике и получателе это глупость.
Точнее сжатие будет только для текстов с одинаковыми вероятностями повторения символов и как в "словаре".

Чуть другой текст и легко получим вместо сжатия дичайшее увеличение размера.

(13) "Чуть другой текст и легко получим вместо сжатия дичайшее увеличение размера." - ну вот и проверю в ходе выполнения лабы это экспериментально :)

Нет, ну и ежу понятно, что когда мы кодируем символы или байты (то есть объекты, выровненные по байтам), то вместо словаря можно записать цепочку этих объектов с вероятностями появления.
Но, если рассмотреть задачу "в общем случае", то мы имеем словарь для кодирования одной последовательности бит через другую последовательность бит. Причём, никто не говорит, что исходные последовательности бит будут все одинаковой длины - можно рассмотреть случай, когда длина у них разная, в зависимости от повторения в тексте - только вот одна проблема - если длина разная, то очень тяжело (если не вообще невозможно) анализировать текст на наличие и частоту появления последовательностей.

Словари ограниченной длины, количество комбинаций в них конечно. Можно завести "глобальный" каталог словарей.

(15) дык не ежам наверно же понятно что такой "словарь" нету никакого смысла пытаться "сжимать" ))
ибо результат будет скорее отрицательный

(17)+ другое дело что если структуру которая хранит в себе "словарь" нуна как то оптимально бинарно сериализовать!

(0) Скачай винрар, переименуй чтобы препод не догадался, сдай.