Вход | Регистрация

Информационные технологии :: Математика и алгоритмы

Каким алгоритмом лучше всего кодировать словарь?

Каким алгоритмом лучше всего кодировать словарь?
Я
   megabax
 
25.10.16 - 19:40
Добрый день. Делаю лабу по методу сжатия данных. Сжимаю текст методом Хаффмана, словарь тоже надо бы сжать. Метод надо выбрать самому. Какой алгоритм сжатия словаря посоветуете? Арифметическое кодирование, коды Райса Гоши или, может вообще лучше взять коды Фибоначи?
 
 
   Garykom
 
1 - 25.10.16 - 20:02
какой еще в жпо словарь в методе хаффмана? когда там уникальные символы и биты и нечего сжимать совершенно
   Garykom
 
2 - 25.10.16 - 20:05
(1)+ причем соответствие символ - цепочка бит хранить не требуется, хватает только правильной последовательности символов по возрастанию, биты кодирования восстановить можно всегда
   Garykom
 
3 - 25.10.16 - 20:18
лучше ANS сделай, там прикольное кодирование дробным числом бит каждого символа, получается наилучшее сжатие для символов с одинаковой частотой, но алгоритм расшифровки сложнее и учитывает предыдущий символ при сжатии/распаковке
   megabax
 
4 - 25.10.16 - 20:18
(2) Это если предопределенный словарь, который храниться и на кодере, и на декодере, тогда да, в запакованный файл его помещать не требуется. Но если в кодере и декодере словарь не храниться, а создается динамический по кодируемому тексту, то его надо в результирующий файл поместить. Препод сказал, что нужно оба варианта сделать и сравнить.
Но помещать словарь в заархиврованный файл как есть типа моветон и его тоже надо как-то сжать.
   megabax
 
5 - 25.10.16 - 20:19
(3) ANS - это арифметическое кодирование что ли, там где отрезок 0,1 делиться на кучу частей?
   Garykom
 
6 - 25.10.16 - 20:24
(4) ты хотя бы https://ru.wikipedia.org/wiki/Код_Хаффмана прочитал и понял?

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

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

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

и кто то не понял препода или преподу рановато учить ему бы самому подучиться...
   megabax
 
7 - 25.10.16 - 20:24
(1) А! Понял. Биты можно отдельным блоком запаковать в файл (да, действительно их уже не сжать), и отдельным потом блоком буквы. Буквы, не знаю только, имеет ли смыл еще и арифметическим кодированием сжать...
   Garykom
 
8 - 25.10.16 - 20:26
(7) да не нужны нафик никакие биты... тебе исходные уникальные символы нужны в каком порядке ты их начал кодировать все большим числом бит
   Garykom
 
9 - 25.10.16 - 20:27
(8)+ для простоты "распаковки" да можно биты тоже засунуть с символами, чтобы не повторять алгоритм Хаффмана перед распаковкой
   Garykom
 
10 - 25.10.16 - 20:31
 
 Рекламное место пустует
   megabax
 
11 - 25.10.16 - 20:33
(9) А, спасибо, понял.
Получается, я могу не засовывать биты в файл, но при распаковке мне придется для словаря повторить алгоритм нахождения битовых кодов, и все. Поскольку символы уже будут в нужном порядке отсортированы. Но если надо ускорить распаковку то можно и биты засунуть. Кстати, я заметил, что распаковывает алгоритм гораздо быстрее чем упаковывает, видимо это как раз связно с процедурой определения битовых кодов.
   Garykom
 
12 - 25.10.16 - 20:36
(11) ага, размер "словаря" в архиве смешной же и по сути кол-во символов уникальных в тексте
   Garykom
 
13 - 25.10.16 - 20:38
А кодирование по Хаффману с одинаковым словарем на источнике и получателе это глупость.
Точнее сжатие будет только для текстов с одинаковыми вероятностями повторения символов и как в "словаре".

Чуть другой текст и легко получим вместо сжатия дичайшее увеличение размера.
   megabax
 
14 - 25.10.16 - 20:41
(13) "Чуть другой текст и легко получим вместо сжатия дичайшее увеличение размера." - ну вот и проверю в ходе выполнения лабы это экспериментально :)
   Torquader
 
15 - 25.10.16 - 21:37
Нет, ну и ежу понятно, что когда мы кодируем символы или байты (то есть объекты, выровненные по байтам), то вместо словаря можно записать цепочку этих объектов с вероятностями появления.
Но, если рассмотреть задачу "в общем случае", то мы имеем словарь для кодирования одной последовательности бит через другую последовательность бит. Причём, никто не говорит, что исходные последовательности бит будут все одинаковой длины - можно рассмотреть случай, когда длина у них разная, в зависимости от повторения в тексте - только вот одна проблема - если длина разная, то очень тяжело (если не вообще невозможно) анализировать текст на наличие и частоту появления последовательностей.
   Loky9
 
16 - 25.10.16 - 22:44
Словари ограниченной длины, количество комбинаций в них конечно. Можно завести "глобальный" каталог словарей.
   Garykom
 
17 - 25.10.16 - 22:46
(15) дык не ежам наверно же понятно что такой "словарь" нету никакого смысла пытаться "сжимать" ))
ибо результат будет скорее отрицательный
   Garykom
 
18 - 25.10.16 - 22:46
(17)+ другое дело что если структуру которая хранит в себе "словарь" нуна как то оптимально бинарно сериализовать!
   Ислам
 
19 - 26.10.16 - 00:50
(0) Скачай винрар, переименуй чтобы препод не догадался, сдай.

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует