Буду потестить! Надо каких-нибудь адаптаций под тырдос с заставками поделать-посмотреть.
Буду потестить! Надо каких-нибудь адаптаций под тырдос с заставками поделать-посмотреть.
Всем привет.
От нечего делать решил реализовать на 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%.
Eugene85, Огого! :) и через 15 лет новые версии :). Если требуется более высокая скорость, посмотри на MMC - Morphing Match Chain.(вроде в 2010 году придумали). Например, вот тут: http://fastcompression.blogspot.ru/p...tch-chain.html. Я пока не разбирался что и как оно там подробно устроено, но скорость сжатия вырастает значительно.
Если тормозит только на последовательностях байт типа "AAAAAA", то можно ускорить поиск по особому. Вот тут немного затронут этот вопрос: http://www.zxpress.ru/article.php?id=8569.
Не представляю, как он может помочь. Как я понял, оно позволяет найти одну или несколько лучших совпадений, а мне нужно перебрать ВСЕ совпадения.Цитата:
Сообщение от Hrumer
Да нет, как я уже сказал, в моей реализации скорость не зависит от характера данных. Вот mhmt, например, подвисает на таких.Цитата:
Сообщение от Hrumer
А можно реализовать еще и идентичный hrust2.1? Чтобы получались одинаковые с hrust2.1 файлы.
Shadow Maker,
теоретически, конечно, можно, но я это делать не хочу, т.к. не вижу смысла. Простите, а зачем оно вам? Любопытно просто...
Для идентичности сборки всяких старых проектов :) Чтобы компилялось красиво.
Shadow Maker,
Сделай мне снапшот (.sna), я прикручу к нему эмулятор z80 и оформлю всё это в exe'шник :) Задача будет решена
Уже давно прекрутили. http://zx-pk.ru/showpost.php?p=88926&postcount=7Цитата:
Сообщение от Eugene85
Сделал оптимальный компрессор для формата Hrust 1. Жмёт чуть лучше, чем mhmt (в среднем на 0.4%).