Где бы взять подробное описание LZMA?

Сомневаюсь, что алгоритмы семейства LZ позволяют распаковывать из произвольной части архива.

Прочитай в википедии про LZW -- тогда поймешь идею LZMA

> добавить распаковку с произвольного места (работа со state),

Если ты будешь помнить состояние словаря в разных точках архива, то с этих точек можно делать распаковку, но мне не ясна практическая польза такого подхода.

посмотри http://tukaani.org/lzma/ (исходники, нормальное описание грозится выдать в "ближайшей декаде") или http://www.encode.ru/forums/index.php?action=vthread&forum=1&topic=672

> Сомневаюсь, что алгоритмы семейства LZ позволяют распаковывать из произвольной части архива.

LZO умеет, если бы еще и сжимало сильно - вообще бы красота была.

> Прочитай в википедии про LZW -- тогда поймешь идею LZMA

LZW я в общем представлял. Его декодер гораздо проще LZMA, даже если смотреть по количеству кода.

> Если ты будешь помнить состояние словаря в разных точках архива, то с этих точек можно делать распаковку, но мне не ясна практическая польза такого подхода.

А мы точно говорим про LZMA? Как я понял, словарь только 1 раз читается... Для чего же там предусмотрены states?

А нужно это вот для чего: есть текстовый файл-"база", который весит 50 метров. Если его упаковать в lzma, то остается примерно полметра. Читать же файл надо на ограниченной конфигурации: примерно 33mhz + использовать как можно меньше памяти (желательно в 50кб уложиться), при этом заранее не известно, какую часть базы нужно будет прочитать. Может начало, а может и конец. Вот и была идея сделать массивчик states (возможно даже со словарями) и использовать его в качестве индекса для базы. LZO здесь вообще хорошо подходит - у него распаковка максимально простая и быстрая+распаковка частей "из каропки", но уровень сжатия мал, мне бы не более метра архив сделать.

Во времена доса была такая штука: ресурсы паковались в zip, откуда частями и читались. Тут нужно что-то похожее.

может, стоит PPM/PPMd посмотреть.

http://icculus.org/physfs/

конкретнее, прям вот так: http://hg.icculus.org/icculus/physfs/file/b0c91495af9b/lzma/

>Во времена доса была такая штука: ресурсы паковались в zip, откуда частями и читались. Тут нужно что-то похожее.

Так может и использовать классический LZ77, как это делают, например, в dictzip?

> http://www.encode.ru/forums/index.php?action=vthread&forum=1&topic=672

Книжку скачать не дает, зато наткнулся на balz. Автор хоть и преувеличивает его возможности, но жмет (как я понал, в ppm) почти на равных с lzma, сливая всего несколько процентов на текстовых данных. Зато в его исходниках есть комментарии. Спасибо за ссылку, буду ковырять.

> Так может и использовать классический LZ77, как это делают, например, в dictzip?

Нене, у меня место под базу тоже ограничено.

> конкретнее, прям вот так: http://hg.icculus.org/icculus/physfs/file/b0c91495af9b/lzma/

Это как раз из 7z sdk, ничего вкусного там нет

> LZO умеет, если бы еще и сжимало сильно - вообще бы красота была.

LZO вообще блочный

> А нужно это вот для чего: есть текстовый файл-"база", который весит 50 метров. Если его упаковать в lzma, то остается примерно полметра. Читать же файл надо на ограниченной конфигурации: примерно 33mhz + использовать как можно меньше памяти (желательно в 50кб уложиться), при этом заранее не известно, какую часть базы нужно будет прочитать.

Если словарь у тебя уложится в 50 кб (шансы есть, но мало), то проще всего потоково распаковать и выбросить все что не надо. С уменьшением словаря и сжатие уменьшится.

Итого: ты будешь страдать со своим алогоритмом, а результат все равно не влезет в 0.5М архива или 50к памяти.

Бери стандарный и выбрасывай лишнее.

мда, посмотрел ещё раз -- и правда. Ну может остальной каркас для "подгрузки ресурсов" можно использовать, а вместо lzma что-то другое вставить, хотя он всё равно может оказаться толстым

> желательно в 50кб уложиться

А у LZMA с таким словарём будет заметное преимущество перед deflate?

> Если словарь у тебя уложится в 50 кб (шансы есть, но мало), то проще всего потоково распаковать и выбросить все что не надо. С уменьшением словаря и сжатие уменьшится.

Ну, памяти (если очень прижмет) можно и добавить, скажем до 500кб (размера архива), но ведь словарь больше все равно не отожрет. Сейчас ограничил размер при сжатии: при размере словаря в 256кб (вротив дефолтных 8мб) степень компрессии упала всего на 9%. Ну а 256к я всегда могу держать в памяти, если сильно надо. Подозреваю, что это пиковое использование, т.е. в памяти не постоянно (по крайней мере при начале распаковки)

/me пытается придумать велосипед, дабы хоть какой-то seek-подобный метод был возможен, раз уж кусками читать нельзя... Без seek прозреваю дикие тормоза...

не понимаю чем именно обусловлен выбор LZMA. Когда-то давно на толкнулся на интересную штуку с исходниками SQX. в то время сжимал лучше рара. Если моя память мне не изменяет - то SQX под открытой лицензией.

Оно кстати паблик домэйм стало недавно, так что есть вероятность что тепер ЛЗМА будут пихать куда ни попадя.

Я слыхал про декомпрессор ядра сжатым ЛЗМА, но исходников не видал, теперь и не увижу, раз оно не ГПЛ.