Оптимальное LZ-кодирование
Ситуация: есть некий файл, его хочется запаковать LZ-методом.
Файл гружу в память и для каждого байта строю набор всех подходящих к нему LZ-кодов (длина, смещение, размер кода в битах).
Надо: выбрать оптимальную цепочку этих кодов и сгенерить самый короткий из возможных выходных запакованных файлов.
Вопрос: как? =)
Делаю пакер megalz на сях.
--- Кто съел всю уху?
С любовью к вам, Yandex.Direct
Размещение рекламы на форуме способствует его дальнейшему развитию
Платформа какая?Сообщение от lvd
Возможно, поможет представление кода, как прохода по графу, а оптимальный в смысле длины кода, как путь по графу минимальной длины.
Какая разница - если на сях пишу... Не спек уж точно! =) Жрёт память по-чёрному, так что не дос тоже. :)
Ну да - и как этот путь минимальной длины искать? ;)Возможно, поможет представление кода, как прохода по графу, а оптимальный в смысле длины кода, как путь по графу минимальной длины.
--- Кто съел всю уху?
Если чистый С, то реализовать алгоритм Дейкстры (он подходит для неотрицательных весов).Какая разница - если на сях пишу... Не спек уж точно! =) Жрёт память по-чёрному, так что не дос тоже.
Ну да - и как этот путь минимальной длины искать?
Если С++, то возьми BGL (Boost Graph Library), там этот алгоритм (и многие другие) уже реализован.
Удачи!
Valker: оптимальность кодирвания может быть как минимум 2 типов: опимальность в смысле размера упакованного файла, и оптимальность в смысле минимизации количества пар(длина смещение) и литералов. Какая у тебя имеется ввиду?
В дополнение: ага, понял о чем ты. Минимизация количества пар (длина смещение) и литералов не означает того, что получится файл минимальной длины. Но за то, скорее всего такой файл будет быстрее всего распаковываться. Хотя выигыш по скорости распаковки, наверное, составит менее 0.1%.
Последний раз редактировалось Hrumer; 15.12.2005 в 17:53.
Hrumer, пасиб за посыл в нужном направлении в емылеЯ отыскал то же самое уже потом в инфогуиде#6 =)
Valker, по сути алго дейкстры это то же самое что Хрумер мне предложил (и что в инфогуиде#6), только во втором случае он упрощён применительно к специфическому виду деревьев.
elf/2, ага 10х, выкачал всё, завтра доберусь до компа где выкачано и посмотрю =))
--- Кто съел всю уху?
В смысле длины полученного кода в битах.
Посмотри исходники, надеюсь поможет.
Хм... там даже и намёка нет на оптимальный выбор цепочки... =)
--- Кто съел всю уху?
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)
Ваши права
Ответить с цитированием
