ZCon

[Turbo]

В этой теме можно обсудить ваш подход к решению этой задачи.

Применяли ли вы какие-то наработки из архиваторов или писали свое решение?

[Stanislav Markevich]

Я использовал готовый исходник LPAQ (у него самый маленький исходник был из семейства PAQ). Пожатый бинарник превратил в строку алгоритмом base128. Итого с исходным текстом распаковщика ~38 кб.

[zhengxi]

[Stanislav Markevich]

[rand08]

Сначала накидал LZW, вышло ~50Кб.
Потом написал SR, стало ~42Кб. Теоретически можно было уменьшить результат ещё на 2-3Кб.
PS. А юзать готовые исходники lpaq неинтересно

[pperm]

я использовал преобразование BWT и сжимал повторения...
Дальше кодировал эту строку... т.е каждому символу выдовал число от 1, частота символа в последних нескольких просмотренных... И кодировал текущий символ из этих характеристим с момощью Хаффмана... получил 39035... использовал только 128 различных символов... т.е в итоге файл у меня получился размеров 41038

[Werewolf]

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

zhengxi, странно, вот именно 0 у меня компилятор на spoj не сжевал, из-за этого последовательности вида "\05" приходилось преобразовывать в "\0005", иначе компилятор думал, что это символ с кодом 5. Кроме \0 заменил \n, \r, \" и \\. Остальное компилятор нормально воспринял )
_________________
Þá skelfur askr Yggdrasils, ok engi hlutr er þá óttalaus á himni eða jörðu.

[petrovich]

текст сжал Zip-ом, алгоритм deflate реализовал самостоятельно ранее. Больше всего времени ушло на замену идентификаторов и удаление пробелов в исходном тексте. Получилось чуть больше 40000. Как я понял, Zip --- не самое лучшее решение для сжатия текста.

[zhengxi]

[Werewolf]