Оптимальное LZ-кодирование

[Hrumer]

Можно. Но под 512кб тачки (не меньше) и сильно тормозной. Кстати, кто первый такое на спеке под тырдос сделает (файлы должны получаться такой же длины [или короче, хехе =], как на пцшном, вызванном без аргументов), тому от меня при личной встрече будет 6 бутылок 2литровых пепси. =)) Ещё условие - поддержка универсальных драйверов памяти аля аль-асм.

А вот тут есть варианты. Если уменьшить окно поиска на #100, то есть до #1000(можно будет использовать "закольцованную" таблицу поиска, как в hrum-hrust) и реализовать алгоритм оптимального подбора пар не для всего файла целиком, а для его фрагментов (размеры фрагмента определяются доступной памятью), то можно попытаться уложиться и в 128К... Замедление где то в 4 раза по сравнению с hrum. На некоторых файлах - до 50 раз, но с использованием спец. алгоритмов можно ускорить процесс. В любом случае, придется искать компромисс между скоростью, качеством паковки и объемом используемой памяти...

[Advertiser]

[lvd]

Выложите также плиз и проги хруст2!4 и хруст1, которыми вы жали, тут или в емыл (lvd dgap mipt ru). Я выложу всё на урл, где мегалз, если конечно, кто-то не будет против.

[lvd]

А вот тут есть варианты. Если уменьшить окно поиска на #100, то есть до #1000(можно будет использовать "закольцованную" таблицу поиска, как в hrum-hrust) и реализовать алгоритм оптимального подбора пар не для всего файла целиком, а для его фрагментов (размеры фрагмента определяются доступной памятью), то можно попытаться уложиться и в 128К... Замедление где то в 4 раза по сравнению с hrum. На некоторых файлах - до 50 раз, но с использованием спец. алгоритмов можно ускорить процесс. В любом случае, придется искать компромисс между скоростью, качеством паковки и объемом используемой памяти...

Согласен. Но если честно, то МНЕ влом хоть как делать заново MegaLZ на спеке. Всё равно сборка релизов обычно на ПЦ идёт, и взять файл из ТРД, зажать ехещкой и пхнуть обратно - не влом совершенно.

А вообще я предложил приз тому, кто это сделает на спеке, так что вперёд! =)) Если результат будет между длиной оригинального МегаЛЗа (или этого с -g) и минимальной - то кол-во бутылок пропорционально уменьшу =)

[Hrumer]

hrust1 недавно скачивал с zx.da.ru...

[Spectre]

Нулей небось дохреня? =)

Посмотри сам. Файл QC.C прилагался к предыдущему сообщению.

А это с учётом длины депакера?

Без. Но длина депакера 207 байт, что длиннее megaLZ только на 97 байт. С приложенными депакерами все равно будет выигрыш на 36 байт. :-P

Исходник hrust 2!4 прилагаю.

[alone]

Оптимальный 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...=rep1&type=pdf

[Hrumer]

An improvement on hash-based algorithms for searching the longest-match string used in LZ77-type data compression http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf

Бегло прочитал, правильно ли я понял, что памяти под таблицы надо в ~2 раза больше? Или хитрее?