Просмотр полной версии : Оптимальное LZ-кодирование
Ситуация: есть некий файл, его хочется запаковать LZ-методом.
Файл гружу в память и для каждого байта строю набор всех подходящих к нему LZ-кодов (длина, смещение, размер кода в битах).
Надо: выбрать оптимальную цепочку этих кодов и сгенерить самый короткий из возможных выходных запакованных файлов.
Вопрос: как? =)
Делаю пакер megalz на сях.
Ситуация: есть некий файл, его хочется запаковать LZ-методом.
Файл гружу в память и для каждого байта строю набор всех подходящих к нему LZ-кодов (длина, смещение, размер кода в битах).
Надо: выбрать оптимальную цепочку этих кодов и сгенерить самый короткий из возможных выходных запакованных файлов.
Вопрос: как? =)
Делаю пакер megalz на сях.
Платформа какая?
Возможно, поможет представление кода, как прохода по графу, а оптимальный в смысле длины кода, как путь по графу минимальной длины.
Ситуация: есть некий файл, его хочется запаковать LZ-методом.Посмотри исходники, надеюсь поможет.
Платформа какая?
Какая разница - если на сях пишу... Не спек уж точно! =) Жрёт память по-чёрному, так что не дос тоже. :)
Возможно, поможет представление кода, как прохода по графу, а оптимальный в смысле длины кода, как путь по графу минимальной длины.
Ну да - и как этот путь минимальной длины искать? ;)
Посмотри исходники, надеюсь поможет.
Хм... там даже и намёка нет на оптимальный выбор цепочки... =)
Хм... там даже и намёка нет на оптимальный выбор цепочки... =)Приведено три варианта, которые на одном и том же тестовом файле дают разные результаты паковки.
Думаю готовый вариант решения задачи не стоит ждать :)
Приведено три варианта, которые на одном и том же тестовом файле дают разные результаты паковки.
Из которых один - с хаффманом после ЛЗ, а другой - с арифм. кодированием после ЛЗ. У меня только ЛЗ =)
Думаю готовый вариант решения задачи не стоит ждать :)
Да вот Хрумер дал один намёк в емыле - буду туда копать =)
вот тут есть n-ное количество статей на тему non-greedy/lazy parsing'а для LZ* алгоритмов:
http://www-koi.compression.ru/download/lz.html
они дают не оптимальный результат, но сжатие улучшают выбирая более правильные цепочки...
Какая разница - если на сях пишу... Не спек уж точно! =) Жрёт память по-чёрному, так что не дос тоже. :)
Ну да - и как этот путь минимальной длины искать? ;)
Если чистый С, то реализовать алгоритм Дейкстры (он подходит для неотрицательных весов).
Если С++, то возьми BGL (Boost Graph Library), там этот алгоритм (и многие другие) уже реализован.
Удачи!
Valker: оптимальность кодирвания может быть как минимум 2 типов: опимальность в смысле размера упакованного файла, и оптимальность в смысле минимизации количества пар(длина смещение) и литералов. Какая у тебя имеется ввиду?
В дополнение: ага, понял о чем ты. Минимизация количества пар (длина смещение) и литералов не означает того, что получится файл минимальной длины. Но за то, скорее всего такой файл будет быстрее всего распаковываться. Хотя выигыш по скорости распаковки, наверное, составит менее 0.1%.
Valker: оптимальность кодирвания может быть как минимум 2 типов: опимальность в смысле размера упакованного файла, и оптимальность в смысле минимизации количества пар(длина смещение) и литералов. Какая у тебя имеется ввиду?
Hrumer, пасиб за посыл в нужном направлении в емыле :) Я отыскал то же самое уже потом в инфогуиде#6 =)
Valker, по сути алго дейкстры это то же самое что Хрумер мне предложил (и что в инфогуиде#6), только во втором случае он упрощён применительно к специфическому виду деревьев.
elf/2, ага 10х, выкачал всё, завтра доберусь до компа где выкачано и посмотрю =))
Valker: оптимальность кодирвания может быть как минимум 2 типов: опимальность в смысле размера упакованного файла, и оптимальность в смысле минимизации количества пар(длина смещение) и литералов. Какая у тебя имеется ввиду?
В смысле длины полученного кода в битах.
Надо: выбрать оптимальную цепочку этих кодов и сгенерить самый короткий из возможных выходных запакованных файлов.
в общем виде я эту задачу вывел и оформил способ её решения в http://zx.pk.ru/showthread.php?t=296
Там же отсылки на Хаффмана.
в общем виде я эту задачу вывел и оформил способ её решения в http://zx.pk.ru/showthread.php?t=296
Там же отсылки на Хаффмана.
Летят как-то Шерлок Холмс и доктор Ватсон на воздушном шаре в полном тумане. Вдруг появляется земля, и виден какой-то человек.
- Где мы находимся? - спрашивает Холмс у него.
- На воздушном шаре! - отвечает тот.
Через некоторые время Холмс говорит:
- Вы знаете, Ватсон, этот человек - математик!
- Почему вы так решили?
- Его ответ был абсолютно правильным и абсолютно бесполезным!
...
Мне совершенно не нужен хафман и рле. Исключительно лз-коды, исключительно найти оптимальную их цепочку, и как посоветовали многие - алгоритном Дейкстры. Без всяких теорий =)
Итак, предварительные результаты. Если старый megalz делал файлы на 10-20 байт длиннее (а то и менее 10 байт), чем хруст2, то с этим алго - уделывает хруст в сотни байт! Хрум3.5 вообще отдыхает (с вычитанием 150 байт из длины даже). Рип естественно всех поруливает - но на то он и хафман. Единственный прокол - на одном файле хруст всех уделал. Это был асм-выход компилятора msvc =)
2lvd: интересно было бы посмотреть на таблицу результатов.
Следующим этапом, видимо, будет рассмотрение других кодов - просто для эксперимента. У тебя какие именно коды используются? (долго смотреть в распаковщике)
Это был асм-выход компилятора msvc =)
Посмотри, там скорее всего прослеживается какая то структурность - может таблица большая специфическая.
2lvd: интересно было бы посмотреть на таблицу результатов.
Ща ещё чуть-чуть причешу код - и будет релиз =) там и таблицы рекламные будут, и файлы тестовые даже =) Если не заломает меня...
Следующим этапом, видимо, будет рассмотрение других кодов - просто для эксперимента.
Мне уже скорее всего влом будет =)
У тебя какие именно коды используются? (долго смотреть в распаковщике)
типа вот такого:
Формат пакованного файла:
первый байт копируется в выход
второй - ид¬т в биты
биты в байте битов - со старшего.
Если нужен бит, а его уже нет (все 8 кончились) - то новый байт выбирается
из потока. Оттуда же выбираются и байты, обозначенные <byte> - но только
после выборки всех битов ссылки.
В формате ссылок: <byte> - байт, который выбирается из потока
1<byte> - копировать <byte> в выход.
000abc - копировать 1 старый байт по смещению FFF8+[abc] от текущей позиции в выходе
(abc==000 - смещение FFF8, abc==111 - FFFF)
001<byte> - копировать 2 байта по смещению FF00+<byte> (-1..-256)
0100<byte> - копировать 3 байта по смещению FF00+<byte>
0101abcd<byte> - копировать 3 байта по смещению (F[abcd]-1)*256+<byte> (-257..-4352)
более длинные ссылки удобно представить в виде 3 частей:
префикс: 011
длина ссылки:
1a -> 4+[a]
01ab -> 6+[ab]
001abc -> 10+[abc]
0001abcd -> 18+[abcd]
00001abcde -> 34+[abcde]
000001abcdef -> 66+[abcdef]
0000001abcdefg -> 130+[abcdefg] (тут длина не более 255!)
смещение:
0<byte> - FF00+<byte> назад (-1..-256)
1abcd<byte> - (F[abcd]-1)*256+<byte> (-257..-4352)
Метка конца потока:
011000000001
примеры:
000111 - повторить последний байт
001<byte=FF> - повторить последний байт дважды (смещение=-1, длина 2) - совмещение LZ и RLE!!!!!
011 001101 10000<byte=0> - ссылка длиной %101+10 = 15 байт со смещением -4352
Мне совершенно не нужен хафман и рле. Исключительно лз-коды, исключительно найти оптимальную их цепочку, и как посоветовали многие - алгоритном Дейкстры. Без всяких теорий =)
Анекдот был конечно руль (-%, причём в тему (-%
Дело вовсе не в RLE и не в Хаффмане - дело в подходе - его можно и для цепочек LZ* использовать :-D, и придётся решать ту же задачу минимизации по связанным параметрам в нелинейном пространстве.
2lvd> внимательней почитай, там из общей теории следуют парочка интересных выводов, интересных для тебя в том числе. Поиск оптимальных команд языка LZ* - вообще задача экспертной системы и для файлов разного контента (текст, медиа, код) эта задача по разному решаться будет (т.е. давать разный результат, тот же пример привёл Caro вообще-то). Пример с тем же LC - его команды в общем то очень неплохо подобраны для сжатия картинок, однако сильно сомнительно что при помощи LC можно будет эффективно текст или код сжимать - у него управляющие коды под другое заточены.
А потому универсальной последовательности нет, именно это и следует из отсылки, которая была до математика и воздушного шара.
Если ты хочешь сделать чтото совсем мегауниверсальное, сделай, скажем, штук 256 наборов управляющих команд - каждая из которых будет подбираться под сжимаемый файл - и в конце у тебя будет неизменно блестящий результат - для распаковщика дискретного всё равно весь набор команд (256 таблиц) известен, а для распаковщика интегрированного с архивом так вообще тем более - он изначально будет заточен под заданную комбинацию.
Немного пофантазировав (то что было чуть выше это банальные реалии
:-D) можно сообразить такое: файл сжимаемый разбивается на блоки по несколько килобайт каждый из которых сжимается по оптимальной таблице - итого будет уже не просто блестящий - а просто отличный результат, непревзойдённый в принципе.
Немножко оффтопа - тут один товарищ тоже упаковщик писал... который все файлы в 32 байта сжимал (-; я так за него радовался, жалко он рабочий алгоритм - рабочий код - не показал... (-%
2lvd> внимательней почитай, там из общей теории следуют парочка интересных выводов, интересных для тебя в том числе. Поиск оптимальных команд языка LZ* - вообще задача экспертной системы и для файлов разного контента (текст, медиа, код) эта задача по разному решаться будет (т.е. давать разный результат, тот же пример привёл Caro вообще-то). Пример с тем же LC - его команды в общем то очень неплохо подобраны для сжатия картинок, однако сильно сомнительно что при помощи LC можно будет эффективно текст или код сжимать - у него управляющие коды под другое заточены.
А потому универсальной последовательности нет, именно это и следует из отсылки, которая была до математика и воздушного шара.
Если ты хочешь сделать чтото совсем мегауниверсальное, сделай, скажем, штук 256 наборов управляющих команд - каждая из которых будет подбираться под сжимаемый файл - и в конце у тебя будет неизменно блестящий результат - для распаковщика дискретного всё равно весь набор команд (256 таблиц) известен, а для распаковщика интегрированного с архивом так вообще тем более - он изначально будет заточен под заданную комбинацию.
Эээ. Я хочу (хотел) лишь под существующий распаковщик паковать наиболее оптимально. Вот и всё. Это получилось. Переписывать распаковщик в мои планы не входило. Вот.
Немножко оффтопа - тут один товарищ тоже упаковщик писал... который все файлы в 32 байта сжимал (-; я так за него радовался, жалко он рабочий алгоритм - рабочий код - не показал... (-%
Гы. Легко доказать, что такое невозможно. =)
хм. был конкурс с призом в мильон баксов тому, кто сделает архиватор, сжимающий любой файл хотя бы на 1 байт. ну и нашёлся умник, который сделал. формально прога удовлетворяла всем критерием и прошла все тесты :) только когда организаторы разобрались с тем простеньким алгоритмом, они гады денежку зажали :( жлобы
(если кто эту историю не слышал, могу запостить алгоритм)
хм. был конкурс с призом в мильон баксов тому, кто сделает архиватор, сжимающий любой файл хотя бы на 1 байт. ну и нашёлся умник, который сделал. формально прога удовлетворяла всем критерием и прошла все тесты :) только когда организаторы разобрались с тем простеньким алгоритмом, они гады денежку зажали :( жлобы
(если кто эту историю не слышал, могу запостить алгоритм)
Запости. Такого быть не может в принципе.
хм. был конкурс с призом в мильон баксов тому, кто сделает архиватор, сжимающий любой файл хотя бы на 1 байт. ну и нашёлся умник, который сделал. формально прога удовлетворяла всем критерием и прошла все тесты :) только когда организаторы разобрались с тем простеньким алгоритмом, они гады денежку зажали :( жлобы
(если кто эту историю не слышал, могу запостить алгоритм)Если я правильно помню он использовал имя файла, как дополнительную память.
Если я правильно помню он использовал имя файла, как дополнительную память.
Ха-ха, ну и правильно, что зажали, ибо читер подлый! =)
2caro: Да,похоже я слышал эту историю.. Кое-кто ыявлял определенный символ, который точно встречается в файле, и по нему разбивал файл на несколько. Сам символ, естественно в выходные файлы не записывался. Имена файлов, видимо, использовались для того, чтобы можно было правильно склеить эти файлы...
2caro: Да,похоже я слышал эту историю.. Кое-кто ыявлял определенный символ, который точно встречается в файле, и по нему разбивал файл на несколько. Сам символ, естественно в выходные файлы не записывался. Имена файлов, видимо, использовались для того, чтобы можно было правильно склеить эти файлы...
Не только имена, но и длины файлов - помечали места вставления символа, т.е. были дополнительными битами информации.
всё верно, был файл 1.txt с содержимым "Hello", стал 1-48.txt с содержимым "ello", потом стал 1-48-65.txt с "llo", и т.п...
Ха-ха, ну и правильно, что зажали, ибо читер подлый! =)не согласен. нечего было лопухаться, когда составляли правила. дал слово - держи!
не согласен. нечего было лопухаться, когда составляли правила. дал слово - держи!
Дык учтём инфу о длинах файлов - и всё. =)
2SMT: Как я слышал, изначально в правилах вообще не оговаривался этот пункт, а в дальнейшей переписке "автор" спора согласился, что после упаковки файла результат упаковки мог быть в нескольких файлах... Вот кастати, есть страничка где то в инете Леонида Брухиса(если не ошибаюсь) - там есть пари о сжатии...
Итак, прога написана. Собирается под мсвц, под гцц в линухе и на амиге SAS/C. Умеет паковать оптимальным методом, паковать 'жадным' методом, распаковывать.
Осталось только подобрать тестов-бенчмарков и написать ртфмы. Принимаются предложения по тестам-бенчмаркам (чтоб сравнить оптимальное кодирование с "жадным", которое даёт по длине такие же результаты, как и спековский MegaLZ, и с хрустом-хрумом-рипом) в виде самих файлов =)
Принимаются предложения по тестам-бенчмаркам
1) код пзу
2) картинки с разными типами текстур (ordered/floyd-steinberg)
3) тексты (чисто английские и англо-русские)
4) кодовые блоки (сырые и уже ужатые разными пакерами)
уже ужатые разными пакерами
они увеличиваются на 1/8, т.е. на 12,5%. всегда.
они увеличиваются на 1/8, т.е. на 12,5%. всегда.
зависит от пакера, которым ужаты. и от метода текущей упаковки. я когда тестировал арифметическое сжатие, пробовал хриповые файлы дожимать- 10..15% выигрывал. а вот для рипа результаты был гораздо хуже- буквально несколько байт (подозреваю что на заголовке)
зависит от пакера, которым ужаты. и от метода текущей упаковки. я когда тестировал арифметическое сжатие, пробовал хриповые файлы дожимать- 10..15% выигрывал. а вот для рипа результаты был гораздо хуже- буквально несколько байт (подозреваю что на заголовке)
А когда ты тестировал LZ-сжатие, насколько у тебя дожималось? =)
которая до шарика на вообще несжимаемых файлах рабочий алгоритм давал увеличение только на три байта [на самом деле чуток меньше] (-8 причём сама таблица сжатия оттуда занимала два с копейками - и ровно 1 бит последовательность добавляемая в сжимаемый файл упаковщиком - как раз та самая управляющая последовательность.
Так что действительно это зависит только от типа используемого упаковщика.
А когда ты тестировал LZ-сжатие, насколько у тебя дожималось? =)
ну я ж говорю- хруст на 10...15% ужимался (а это LZSS если я ничего не путаю). в частности, упакованный текст из 10кб ужимался примерно в 8.5. исходы проги лежат в одном из номеров infoguide.
ну я ж говорю- хруст на 10...15% ужимался (а это LZSS если я ничего не путаю). в частности, упакованный текст из 10кб ужимался примерно в 8.5. исходы проги лежат в одном из номеров infoguide.
Чё-та я не впёр - то ты арифм. cжатие тестировал, то LZSS... =)
ё-та я не впёр - то ты арифм. cжатие тестировал, то LZSS... =)
Внимательно читаем мой первый пост:
"я когда тестировал арифметическое сжатие, пробовал хриповые файлы дожимать"
Внимательно читаем мой первый пост:
"я когда тестировал арифметическое сжатие, пробовал хриповые файлы дожимать"
"Ты не умничай, ты пальцем покажи". ЧЕМ ты дожимал хрип на 10-15%? =)
Варианты ответов:
1. методом LZ*
2. арифм. кодированием.
3. *?
"Ты не умничай, ты пальцем покажи". ЧЕМ ты дожимал хрип на 10-15%? =)
Арифметическим кодированием! (палец показать в псевдографике не получается %)))
Арифметическим кодированием! (палец показать в псевдографике не получается %)))
Ну а тогда чего предлагаешь ЛЗ жать уже запакованное? Жми упакованное своим арифм. и всё. =)
Ну а тогда чего предлагаешь ЛЗ жать уже запакованное? Жми упакованное своим арифм. и всё. =)
для более полной статистики. очень часто в кодовых блоках встречаются запакованные куски (incbin'ы). посему стоит проверить и этот режим работы.
для более полной статистики. очень часто в кодовых блоках встречаются запакованные куски (incbin'ы). посему стоит проверить и этот режим работы.
Мне приходилось лепить кодовые блоки полностью незапакованными, так и запакованными по частям (запакованные инкбины). И могу сказать, что во втором случае мне не приходило в голову повторно жать запакованное! (жал только коды и данные с ними незапакованные которые).
А статистика тут простая - как правильно отметил jtn, увеличение будет на 1/8 за счёт того, что байты кодируются 9 битами. Плюс ОЧЕНЬ НЕЗНАЧИТЕЛЬНЫЙ выигрыш относительно 9/8 исходного размера за счёт СЛУЧАЙНЫХ РЕДКИХ совпадений.
объясните дураку, как можно инкбинить файлы в один кодовый блок, а потом его кусками паковать?
объясните дураку, как можно инкбинить файлы в один кодовый блок, а потом его кусками паковать?
Берёшь и инкбинишь. Потом компиляешь и отЛАЖИваешь. А когда дело до релиза доходит, то ручками, ручками =))
Не знаю, у кого как, а в хрусте1 "потери" на непакующихся данных составляют менее 12,5%...
Не знаю, у кого как, а в хрусте1 "потери" на непакующихся данных составляют менее 12,5%...
Ага, а у кого-то и так, что случайные данные паковать не умеет в принципе, бо делалось чтоб неслучайные сугубо паковать =)
Ага, а у кого-то и так, что случайные данные паковать не умеет в принципе, бо делалось чтоб неслучайные сугубо паковать =)
я ж предлагал набрать скажем по крайней мере три набора команд - один для изначально сжатых и плохо поддающихся сжатию данных (чтобы минимум добавлений было при переносе данных в упакованные), второй для нормальных файлов (там классические последовательности, хотя бы те же что в храсте) и третий скажем для мультимедии
Вот вам всем релиз! Отныне МегаЛЗ - лучший LZ-only пакер на спеке! =)))))
http://lvd.nm.ru/MegaLZ/
Сейчас буду смотреть... Сравнения с hrust1 не представлено :(
Для полноты картины...
http://web.gorny.ru/~hrum/zx/hrusttest/!hrust1.zip
hrust1 отстает в сумме где то на 3килобайта...
[QUOTE=lvd]Вот вам всем релиз! Отныне МегаЛЗ - лучший LZ-only пакер на спеке! =)))))
А для реального Спектрума можно сделать? :)
Что-то даже для писюка архив упаковщика большой или я в че-то не въехал?
А распаковщик, как я понимаю, остался спековский?
Aprisobal
06.01.2006, 23:19
Хотел давно тиснуть этот пост, но не было повода. А тут как раз LVD сделал MegaLZ. Мне он понравился, а особенно то, что есть packer под Win.
В общем для Commodore64 существует довольно сильный компрессор PuCrunch - http://www.cs.tut.fi/~albert/Dev/pucrunch/
Коротко о нём:
Pucrunch is a Hybrid LZ77 and RLE compressor, uses an Elias Gamma Code for lengths, mixture of Gamma Code and linear for LZ77 offset, and ranked RLE bytes indexed by the same Gamma Code. Uses no extra memory in decompression.Вот тестдрайв на файлах от MegaLZ_Benchmark - http://lvd.nm.ru/MegaLZ/ на чуть-чуть подправленном PuCrunch (убран заголовок из выходных файлов). Запускался с параметрами -c0 -d -fdelta
|Apri_PuCrunch
| |New MegaLZ
| | |Old MegaLZ
| | | |Bitbuster Extreme v0.1
| | | | |HRUST2.1
| | | | | |RIP v0.01
-------+-------+-------+-------+-------+-------+------
code-1 | 12403 | 12654 | 12863 | 12827 | 12865 | 12118
code-2 | 7818 | 7767 | 8034 | 8119 | 8012 | 7689
code-3 | 8257 | 8406 | 8524 | 8181 | 8291 | 7891
-------+-------+-------+-------+-------+-------+------
scrv-1 | 4603 | 4672 | 4724 | 4757 | 4705 | 4551
scrv-2 | 4121 | 4074 | 4148 | 4170 | 4144 | 4030
scrv-3 | 3660 | 3604 | 3688 | 3717 | 3722 | 3544
scrv-4 | 2146 | 2211 | 2314 | 2270 | 2359 | 2165
scrv-5 | 4405 | 4399 | 4479 | 4470 | 4486 | 4298
scrv-6 | 4344 | 4233 | 4324 | 4300 | 4345 | 4129
scrv-7 | 3789 | 3788 | 3899 | 3902 | 3921 | 3721
scrv-8 | 5278 | 5275 | 5340 | 5345 | 5308 | 5139
scrv-9 | 5028 | 4958 | 5043 | 5081 | 5048 | 4844
-------+-------+-------+-------+-------+-------+------
text-1 | 3862 | 3858 | 3986 | 4077 | 4004 | 3726
text-2 | 6748 | 7341 | 7663 | 7766 | 7549 | 6525
text-3 | 9172 | 10252 | 10681 | 11156 | 10360 | 8847
text-4 | 18567 | 20406 | 21417 | 22246 | 20892 | 17334
text-5 | 9478 | 10443 | 10919 | 11225 | 10618 | 9088
В некоторых тестах PuCrunch выигрывает MegaLZ, а в некоторых проигрывает ему. Очень хорошо жмет текстовые файлы.
Декомпрессор PuCrunch занимает 255байт(после моей небольшой доработки), но не релоцируем. В целом выигрывает у MegaLZ на 1.5кб.
См. в аттаче оригинальный PuCrunch, мною чуть подправленный Apri_Pucrunch+декомпрессор для Alasm'a и запакованные им файлы для сводного benchmark'a.
Хотел давно тиснуть этот пост, но не было повода. А тут как раз LVD сделал MegaLZ. Мне он понравился, а особенно то, что есть packer под Win.
В общем для Commodore64 существует довольно сильный компрессор PuCrunch
Да-да, знаю такой! Про него прочитал в C=hacking каком-то номере, и во многом от него зафанател созданием сего MegaLZ'а. И идейки по убыстрению пакования оттуда же тиснул некоторые :)
А как жмёт - хз, интересовался чисто теоретически. Прикольно что он лучше вышел, вроде-то убогонький 6502 =)
[QUOTE=lvd]Вот вам всем релиз! Отныне МегаЛЗ - лучший LZ-only пакер на спеке! =)))))
А для реального Спектрума можно сделать? :)
Можно. Но под 512кб тачки (не меньше) и сильно тормозной. Кстати, кто первый такое на спеке под тырдос сделает (файлы должны получаться такой же длины [или короче, хехе =], как на пцшном, вызванном без аргументов), тому от меня при личной встрече будет 6 бутылок 2литровых пепси. =)) Ещё условие - поддержка универсальных драйверов памяти аля аль-асм. Да, и распаковываться должно 'фирменным' 110байтовым, который в архиве. А то понаделаете там. :)
Что-то даже для писюка архив упаковщика большой или я в че-то не въехал?
Что значит большой? размер ехе который даёт мсвц6 - 53кб. Кроме того, там ещё есть ехе для линуха и для амиги.
А распаковщик, как я понимаю, остался спековский?
И не только!
Насчет хруста 2.1 хотелось бы сказать что это уже устаревшая версия. Последней модификацией от Alone Coder'а является версия 2!4. В ней исправлен фирменный баг с потерей плотности упаковки, добавлен алгоритм нахождения лучшей ссылки (lazy evaluation), окно 32Кб, плюс разные мелочи.
Так же сильное влияние оказывает уменьшение размера окна при нехватке памяти, что ухудшает сжатие.
Для сравнения я упаковал все тестовые файлы при помощи QC v4.00i (бетаверсия), в упаковщике которого присутствуют все вышеупомянутые исправления (кроме размера окна, там 16Кб, что обычно не влияет), а под упаковываемый файл выделяется 46Кб памяти, что максимум возможно
Результаты лучше оригинального хруста 2.1, правда не настолько чтобы догнать megaLZ. Но меня больше интересует упакощик в плане упаковки новых версий QC, для чего я скомпилировал последнюю бетаверсию (файл QC.C) и упаковал ее при помощи mehaLZ и QC4.00i. Результат: выиграл алгоритм hrust2!4 на 133 байта. ;)
Все упомянутое в вложенном файле.
Но меня больше интересует упакощик в плане упаковки новых версий QC, для чего я скомпилировал последнюю бетаверсию (файл QC.C) и упаковал ее при помощи mehaLZ и QC4.00i. Результат: выиграл алгоритм hrust2!4 на 133 байта. ;)
Нулей небось дохреня? =) А это с учётом длины депакера?
Можно. Но под 512кб тачки (не меньше) и сильно тормозной. Кстати, кто первый такое на спеке под тырдос сделает (файлы должны получаться такой же длины [или короче, хехе =], как на пцшном, вызванном без аргументов), тому от меня при личной встрече будет 6 бутылок 2литровых пепси. =)) Ещё условие - поддержка универсальных драйверов памяти аля аль-асм.
А вот тут есть варианты. Если уменьшить окно поиска на #100, то есть до #1000(можно будет использовать "закольцованную" таблицу поиска, как в hrum-hrust) и реализовать алгоритм оптимального подбора пар не для всего файла целиком, а для его фрагментов (размеры фрагмента определяются доступной памятью), то можно попытаться уложиться и в 128К... Замедление где то в 4 раза по сравнению с hrum. На некоторых файлах - до 50 раз, но с использованием спец. алгоритмов можно ускорить процесс. В любом случае, придется искать компромисс между скоростью, качеством паковки и объемом используемой памяти...
Выложите также плиз и проги хруст2!4 и хруст1, которыми вы жали, тут или в емыл (lvd dgap mipt ru). Я выложу всё на урл, где мегалз, если конечно, кто-то не будет против.
А вот тут есть варианты. Если уменьшить окно поиска на #100, то есть до #1000(можно будет использовать "закольцованную" таблицу поиска, как в hrum-hrust) и реализовать алгоритм оптимального подбора пар не для всего файла целиком, а для его фрагментов (размеры фрагмента определяются доступной памятью), то можно попытаться уложиться и в 128К... Замедление где то в 4 раза по сравнению с hrum. На некоторых файлах - до 50 раз, но с использованием спец. алгоритмов можно ускорить процесс. В любом случае, придется искать компромисс между скоростью, качеством паковки и объемом используемой памяти...
Согласен. Но если честно, то МНЕ влом хоть как делать заново MegaLZ на спеке. Всё равно сборка релизов обычно на ПЦ идёт, и взять файл из ТРД, зажать ехещкой и пхнуть обратно - не влом совершенно.
А вообще я предложил приз тому, кто это сделает на спеке, так что вперёд! =)) Если результат будет между длиной оригинального МегаЛЗа (или этого с -g) и минимальной - то кол-во бутылок пропорционально уменьшу =)
hrust1 недавно скачивал с zx.da.ru...
Нулей небось дохреня? =)
Посмотри сам. Файл QC.C прилагался к предыдущему сообщению.
А это с учётом длины депакера?
Без. Но длина депакера 207 байт, что длиннее megaLZ только на 97 байт. С приложенными депакерами все равно будет выигрыш на 36 байт. :-P
Исходник hrust 2!4 прилагаю.
Оптимальный LZH: http://zxpress.ru/article.php?id=8538
Вводная статья тут: http://zxpress.ru/article.php?id=8569
Оптимизация по скорости, которой пока нет ни в одном спектрумовском пакере: An improvement on hash-based algorithms for searching the longest-match string used in LZ77-type data compression http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.4787&rep=rep1&type=pdf
An improvement on hash-based algorithms for searching the longest-match string used in LZ77-type data compression http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.4787&rep=rep1&type=pdf
Бегло прочитал, правильно ли я понял, что памяти под таблицы надо в ~2 раза больше? Или хитрее?
Powered by vBulletin® Version 4.2.5 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot