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

[lvd]

Ситуация: есть некий файл, его хочется запаковать LZ-методом.
Файл гружу в память и для каждого байта строю набор всех подходящих к нему LZ-кодов (длина, смещение, размер кода в битах).

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

Вопрос: как? =)

Делаю пакер megalz на сях.

[Advertiser]

[valker]

Ситуация: есть некий файл, его хочется запаковать LZ-методом.
Файл гружу в память и для каждого байта строю набор всех подходящих к нему LZ-кодов (длина, смещение, размер кода в битах).

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

Вопрос: как? =)

Делаю пакер megalz на сях.

Платформа какая?

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

[caro]

Ситуация: есть некий файл, его хочется запаковать LZ-методом.

Посмотри исходники, надеюсь поможет.

[lvd]

Платформа какая?

Какая разница - если на сях пишу... Не спек уж точно! =) Жрёт память по-чёрному, так что не дос тоже. :)

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

Ну да - и как этот путь минимальной длины искать? ;)

[lvd]

Посмотри исходники, надеюсь поможет.

Хм... там даже и намёка нет на оптимальный выбор цепочки... =)

[caro]

Хм... там даже и намёка нет на оптимальный выбор цепочки... =)

Приведено три варианта, которые на одном и том же тестовом файле дают разные результаты паковки.
Думаю готовый вариант решения задачи не стоит ждать

[lvd]

Приведено три варианта, которые на одном и том же тестовом файле дают разные результаты паковки.

Из которых один - с хаффманом после ЛЗ, а другой - с арифм. кодированием после ЛЗ. У меня только ЛЗ =)

Думаю готовый вариант решения задачи не стоит ждать

Да вот Хрумер дал один намёк в емыле - буду туда копать =)

[elf/2]

вот тут есть n-ное количество статей на тему non-greedy/lazy parsing'а для LZ* алгоритмов:
http://www-koi.compression.ru/download/lz.html

они дают не оптимальный результат, но сжатие улучшают выбирая более правильные цепочки...

[valker]

Какая разница - если на сях пишу... Не спек уж точно! =) Жрёт память по-чёрному, так что не дос тоже.

Ну да - и как этот путь минимальной длины искать?

Если чистый С, то реализовать алгоритм Дейкстры (он подходит для неотрицательных весов).
Если С++, то возьми BGL (Boost Graph Library), там этот алгоритм (и многие другие) уже реализован.

Удачи!

[Hrumer]

Valker: оптимальность кодирвания может быть как минимум 2 типов: опимальность в смысле размера упакованного файла, и оптимальность в смысле минимизации количества пар(длина смещение) и литералов. Какая у тебя имеется ввиду?