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

[Hrumer]

В дополнение: ага, понял о чем ты. Минимизация количества пар (длина смещение) и литералов не означает того, что получится файл минимальной длины. Но за то, скорее всего такой файл будет быстрее всего распаковываться. Хотя выигыш по скорости распаковки, наверное, составит менее 0.1%.

[lvd]

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

Hrumer, пасиб за посыл в нужном направлении в емыле Я отыскал то же самое уже потом в инфогуиде#6 =)
Valker, по сути алго дейкстры это то же самое что Хрумер мне предложил (и что в инфогуиде#6), только во втором случае он упрощён применительно к специфическому виду деревьев.
elf/2, ага 10х, выкачал всё, завтра доберусь до компа где выкачано и посмотрю =))

[valker]

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

В смысле длины полученного кода в битах.

[GriV]

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

в общем виде я эту задачу вывел и оформил способ её решения в http://zx.pk.ru/showthread.php?t=296

Там же отсылки на Хаффмана.

[lvd]

в общем виде я эту задачу вывел и оформил способ её решения в http://zx.pk.ru/showthread.php?t=296

Там же отсылки на Хаффмана.

Летят как-то Шерлок Холмс и доктор Ватсон на воздушном шаре в полном тумане. Вдруг появляется земля, и виден какой-то человек.
- Где мы находимся? - спрашивает Холмс у него.
- На воздушном шаре! - отвечает тот.

Через некоторые время Холмс говорит:
- Вы знаете, Ватсон, этот человек - математик!
- Почему вы так решили?
- Его ответ был абсолютно правильным и абсолютно бесполезным!


...
Мне совершенно не нужен хафман и рле. Исключительно лз-коды, исключительно найти оптимальную их цепочку, и как посоветовали многие - алгоритном Дейкстры. Без всяких теорий =)

[lvd]

Итак, предварительные результаты. Если старый megalz делал файлы на 10-20 байт длиннее (а то и менее 10 байт), чем хруст2, то с этим алго - уделывает хруст в сотни байт! Хрум3.5 вообще отдыхает (с вычитанием 150 байт из длины даже). Рип естественно всех поруливает - но на то он и хафман. Единственный прокол - на одном файле хруст всех уделал. Это был асм-выход компилятора msvc =)

[Advertiser]

[Hrumer]

2lvd: интересно было бы посмотреть на таблицу результатов.
Следующим этапом, видимо, будет рассмотрение других кодов - просто для эксперимента. У тебя какие именно коды используются? (долго смотреть в распаковщике)

[Hrumer]

Это был асм-выход компилятора msvc =)

Посмотри, там скорее всего прослеживается какая то структурность - может таблица большая специфическая.

[lvd]

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

[GriV]

Мне совершенно не нужен хафман и рле. Исключительно лз-коды, исключительно найти оптимальную их цепочку, и как посоветовали многие - алгоритном Дейкстры. Без всяких теорий =)

Анекдот был конечно руль (-%, причём в тему (-%
Дело вовсе не в RLE и не в Хаффмане - дело в подходе - его можно и для цепочек LZ* использовать :-D, и придётся решать ту же задачу минимизации по связанным параметрам в нелинейном пространстве.