Re: Про bzip2


Сайт о сжатии >> Форум #Компрессор# >> [Ответить] [Ответы]

Автор: Serge Osnach, <ench@netcity.ru>
Kiev, Ukraine, 23 апреля 2003 года в 11:48:48

В ответ на : Re: Про bzip2 от Vadim в 22 апреля 2003 года в 17:32:36:


> > > > bzip потребляет что-то около 6 байтов
> > > > на каждый байт блока (могу наврать).

> > > По моим прикидкам, можно сделать дополнительный расход памяти около 1 бита на каждый входной байт. Но времени на сортировку, конечно, потребуется изрядно :)
> > Не считая результата сортировки, естественно, и при достаточно большом блоке.

> > Кстати, потребление памяти вполне можно сократить примерно втрое на реальных данных, не особо и теряя в скорости.

> Надеюсь, это не банальное сокращение за счет размерности указателей на данных длиной до 256 байт? ;-) Понятное дело, на некоторых данных типа текстов можно обойтись без т.н. "квадрантов" - но это копеечная экономия, не втрое.

> (Между прочим, что ты имеешь в виду под реальными данными?)

Содержимое архивов на некоем компе/сервере. Замечу, именно архивов.

> Если нет - то какой способ сокращения расходов памяти ты имеешь в виду? Если не секрет, конечно :)

Сортировать блок по частям.

Например, сначала сортировать символы, у которых предыдущий, например, в интервале 0x00-0x40, потом -- с предудыщим символом в интервале 0x40-0x80...

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

> Кто-то же пишет BWT-компрессоры ;-) А новых LZ-пакеров, наоборот, что-то мало появляется. Кроме Игоря, никто LZ фактически не продвигает...

Вероятно, так происходит потому, что достаточно легко, используя BWT добиться результата, превосходящего Zip. А вот с LZ для того, чтобы обойти Zip, уже прийдется повозиться.

И потом, BWT -- хорошая тема для статьи или дисертации :)

> Что касается, преимуществ одних методов перед другими - ты же знаешь, на эту можно много говорить... Да, собственно, уже все сказано. Или у тебя есть новая информация? ;-)

Для массового применения BWT, к сожалению, не прижился (BZIP2 -- единственное исключение), обогнать лучшие PPM и CM ему не светит, для специализированных компрессоров LZ подходит куда больше, чем BWT по причине больших возможностей подгонки модели.

Однако, при относительной простоте реализации BWT позволяет добиться в среднем неплохих результатов.

> Каждый метод хорош по-своему. Кстати, BWT-пакеры лучше всех, как выяснилось, жмут геодезические данные (файл geo - не показатель, у меня есть реальные современные данные).
Где можно найти образец подобных данных?

Ответы:



Ответить на это сообщение

Тема:

Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.