Сжатие и упаковка. hrum3.5, hrust1, hrust2, laser compact x.x.

[Shadow Maker]

Буду потестить! Надо каких-нибудь адаптаций под тырдос с заставками поделать-посмотреть.

[Eugene85]

Всем привет.

От нечего делать решил реализовать на PC оптимальный компрессор для формата Hrust 2. Придумал алгоритм, выполняющий максимальное теоретически возможное сжатие. Думал, что сделаю открытие, а тут оказывается уже придумали optimal lzh :) Ну да ладно, не пропадать же добру. Выкладываю здесь.

Хотя кое-что интересное в моей реализации всё же есть. Когда делал перебор дистанций для выбора наилучшей ссылки, я задумался о том, как сделать это красивее, чем полным перебором со сравнением строк в каждой позиции. В mhmt это сделано почти прямо: цикл по дистанциям, а в нём цикл, сканирующий строку до первого расхождения. "Почти", потому что реализовано раннее отсечение с помощью хэш-функции. На определённом виде входных файлов (с большой избыточностью) mhmt подвисает надолго. Я нашёл способ сделать это один проход (использовав т.н. Z-функцию).

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

Напоследок изложу результаты сравнения сжатия Hrust 1 (mhmt) и Hrust 2, полученную на ~3500 типичных спектрумовских файлах. Разница в размере сжатых файлов - от -6% до +6%; в среднем Hrust 2 проигрывает 0.8%.

В сравнении с оригинальным компрессором Hrust 2 оптимальный выигрывает в среднем 3.5%.

[Hrumer]

Eugene85, Огого! и через 15 лет новые версии . Если требуется более высокая скорость, посмотри на MMC - Morphing Match Chain.(вроде в 2010 году придумали). Например, вот тут: http://fastcompression.blogspot.ru/p...tch-chain.html. Я пока не разбирался что и как оно там подробно устроено, но скорость сжатия вырастает значительно.

Если тормозит только на последовательностях байт типа "AAAAAA", то можно ускорить поиск по особому. Вот тут немного затронут этот вопрос: http://www.zxpress.ru/article.php?id=8569.

[Eugene85]

посмотри на MMC

Не представляю, как он может помочь. Как я понял, оно позволяет найти одну или несколько лучших совпадений, а мне нужно перебрать ВСЕ совпадения.

Если тормозит только на последовательностях байт типа "AAAAAA"

Да нет, как я уже сказал, в моей реализации скорость не зависит от характера данных. Вот mhmt, например, подвисает на таких.

[Shadow Maker]

А можно реализовать еще и идентичный hrust2.1? Чтобы получались одинаковые с hrust2.1 файлы.

[Eugene85]

Shadow Maker,
теоретически, конечно, можно, но я это делать не хочу, т.к. не вижу смысла. Простите, а зачем оно вам? Любопытно просто...

[Shadow Maker]

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

[Eugene85]

Shadow Maker,
Сделай мне снапшот (.sna), я прикручу к нему эмулятор z80 и оформлю всё это в exe'шник Задача будет решена

[Alexandr Medvedev]

я прикручу к нему эмулятор z80 и оформлю всё это в exe'шник Задача будет решена

Уже давно прекрутили. http://zx-pk.ru/showpost.php?p=88926&postcount=7

[Eugene85]

Сделал оптимальный компрессор для формата Hrust 1. Жмёт чуть лучше, чем mhmt (в среднем на 0.4%).