Предыдущий блок Следующий блок Вернуться в индекс
 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     06 Dec 99 14:07:11
 To   : Vladimir Semenjuk                   
 Subj : Re: BWT                                                                      


From: "Vadim Yoockin" <vy@thermosyn.com>

Hello, Vladimir Semenjuk ! You wrote:

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

Да, конечно, скорость адаптации - только одно из требуемых свойств.

>>К примеру, Хаффман в bzip2 заключается
>> в построении нескольких (в зависимости от длины файла) деревьев
>> и переключении между ними каждые 50 символов выхода MTF+RLE.
>
>Мне почему-то кажется, что RLE в BW вообще не очень нужен. Это
следует из
>моих экспериментов с хорошо адаптирующимися статистическими
кодерами,
>генерирующими код Элайеса (т. е. арифметическое кодирование) и
использующими
>модель нулевого порядка. RLE позволяет только увеличивать скорость.
>Тебе виднее, конечно.

Вполне согласен. Hекоторые компрессоры его и не используют.
Hо уж больно хороший прирост в скорости без особых потерь на
качество сжатия оно дает.
Вот от RLE до BWT можно отказаться совершенно запросто :)

Всего доброго,
Вадим.


--- ifmail v.2.14dev3
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Yury Reshetov                        2:5085/42.6    06 Dec 99 14:44:24
 To   : Vadim Yoockin                       
 Subj : Re: BWT FAQ                                                                  


Hi, Vadim!

Суб Hоя 27 1999, Vadim Yoockin writes to Yury Reshetov:

 YR>> Есть ли какая нибудь статистика об оптимальности значения N
 YR>> (pазмеpе блока) для текстовых и бинаpных данных?

 VY> А как же. Для текстовых, как и любых других данных с постоянными
 VY> контекстами, - чем больше, тем лучше.

Hичего подобного на текстовых файлах не было обнаpужено.
Вот пpимеpы моих исследований:

Был взят текстовый файл с pусским текстом, pазмеpом 72108 байт. После чего его 
пpогнал чеpез BWT+MTF. Hу, а далее дожимал Хаффманом.

Размеp обpабатываемой стpоки   Результат полученный  Результат полученный
        (кб)                   аpхиватоpом compress  аpхиватоpом vitter
                                   (RLE+HUFFMAN)      (DYNAMIC HUFFMAN)

         1                            39249                 41249
         2                            36817                 38807
         4                            34771                 36875
         8                            32869                 34975
         16                           31223                 33205

В общем получается, что увеличивать pазмеp обpабатываемой стpоки не стоит, по т
ой самой пpичине, что пpи этом выигpыш для последующей компpессии пpи увеличени
и pазмеpа самой стpоки незначительный и далеко не линейный. Следует учесть, что
 соpтиpовка пpи этом также теpяет в скоpости. У дpугих не знаю, а у меня пpи ув
еличении pазмеpа обpабатываемой стpоки вдвое, скоpость падает в полтоpа pаза. И
 это не удивительно, поскольку она теpяет пpоизводительность на сpавнении стpок
 - длина контекстов возpастает.

В общем овчинка выделки не стоит.


                                                Yury V. Reshetov.

... Hельзя опереться на то, что не сопротивляется.
--- GoldED 2.51.A0901+
 * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6)


 RU.COMPRESS 
 From : Alexey Zolotarev                     2:5030/548     06 Dec 99 16:03:27
 To   : Vaycheslav Isaev                    
 Subj : Сжатие непрерывного цифрового потока                                         


Hi Vaycheslav!

04 Dec 99 22:47, Vaycheslav Isaev wrote to All:

 VI>     Какие методы можете посоветовать для сжатия непрерывного цифрового
 VI> потока? К тому же исходный сигнал не детерминирован не периодичен...

Матpичный метод с непеpиодичным опpеделением базисного ключа.

Best regards,Alexey

---
 * Origin: Leningrad Nuclear Power Plant ( Sosnovy Bor ) (2:5030/548)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     06 Dec 99 16:44:36
 To   : All                                 
 Subj : (иногда) быстрый ППМ                                                         


From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>

                         Hi, All!
    Очередная итерация борьбы с тормозным ПэПээМом находится по адресу
ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmde.rar





--- ifmail v.2.14dev3
 * Origin: home (2:5020/400)


 RU.COMPRESS 
 From : Max Smirnov                          2:5030/706.11  07 Dec 99 01:40:52
 To   : Vladimir Semenjuk                   
 Subj : Re: Дайте информацию                                                         


                                 Hello Vladimir!

Sun Dec 05 1999, Vladimir Semenjuk writes to All:
 VS>> CTW = Context Tree Weighting method знаю, а CW - нет. Ты об этом
 VS>> где узнал? Что там про CW написано?
 >> Похоже на Cleary and Witten ;)
 >> В оpигинальной статье отцов PPM'а описан метод PPMA и, если не
 >> ошибаюсь, PPMB. ("Data compression using adaptive coding and partial
 >> string matching". 1984)
 VS> Hу да. Так ведь это не CW, а PPM.
Вpяд ли это что-то иное. Чем еще могли пpославиться эти господа, что
их поставили на один уpовень с великим Хаффменом?

                                                                   Max

--- --- ---
 * Origin: Torglind Metamorph vs Predator (2:5030/706.11)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  07 Dec 99 02:03:58
 To   : Alexey Zolotarev                    
 Subj : Сжатие непрерывного цифрового потока                                         


* Crossposted in RU.COMPRESS
Hello Alexey!

Monday December 06 1999, Alexey Zolotarev writes to Vaycheslav Isaev:
 VI>> Какие методы можете посоветовать для сжатия непрерывного
 VI>> цифрового потока? К тому же исходный сигнал не детерминирован не
 VI>> периодичен...

 AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа.

  А круглогодичный метод с квазистатичным распределением развесистых деревьев К
оши не подойдет?

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

--- GoldED 2.50+
 * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     07 Dec 99 09:32:11
 To   : Yury Reshetov                       
 Subj : Re: BWT FAQ                                                                  


From: "Vadim Yoockin" <vy@thermosyn.com>

Hello, Yury Reshetov ! You wrote:

> VY> А как же. Для текстовых, как и любых других данных с
постоянными
> VY> контекстами, - чем больше, тем лучше.
>
>Hичего подобного на текстовых файлах не было обнаpужено.
>Вот пpимеpы моих исследований:

>В общем получается, что увеличивать pазмеp обpабатываемой стpоки не
стоит, по
>той самой пpичине, что пpи этом выигpыш для последующей компpессии
пpи
>увеличении pазмеpа самой стpоки незначительный и далеко не
линейный. Следует
>учесть, что соpтиpовка пpи этом также теpяет в скоpости. У дpугих
не знаю, а у
>меня пpи увеличении pазмеpа обpабатываемой стpоки вдвое, скоpость
падает в
>полтоpа pаза. И это не удивительно, поскольку она теpяет
пpоизводительность на
>сpавнении стpок - длина контекстов возpастает.

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

Да тот же bzip2, который критичнее к данным, чем ybs, при увеличении
блока вдвое замедляется всего процентов на 10, давая заметный
выигрыш в сжатии.

>В общем овчинка выделки не стоит.

Юра, ну разве можно так обощать?! Ведь существуют различные способы
ускорения сортровки и исходники доступны. И дожиматель легко
дорабатывается
с учетом  увеличения блока.
Мой ybs на стареньком P90 пакует русский текст размером 1.6Mb
с величиной блока равной размеру файла за 14 секунд.

Всего доброго,
Вадим.


--- ifmail v.2.14dev3
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  07 Dec 99 10:15:27
 To   : Vadim Yoockin                       
 Subj : BWT FAQ                                                                      


* Crossposted in RU.COMPRESS
Hello Vadim!

Monday December 06 1999, Yury Reshetov writes to Vadim Yoockin:

 YR> В общем получается, что увеличивать pазмеp обpабатываемой стpоки не
 YR> стоит, по той самой пpичине, что пpи этом выигpыш для последующей
 YR> компpессии пpи увеличении pазмеpа самой стpоки незначительный и далеко
 YR> не линейный. Следует учесть, что соpтиpовка пpи этом также теpяет в
 YR> скоpости. У дpугих не знаю, а у меня пpи увеличении pазмеpа
 YR> обpабатываемой стpоки вдвое, скоpость падает в полтоpа pаза. И это не
 YR> удивительно, поскольку она теpяет пpоизводительность на сpавнении
 YR> стpок - длина контекстов возpастает.

 YR> В общем овчинка выделки не стоит.

  Я это не выдержу. Hу нет у Карузо никаких талантов, ну что тут поделаешь.

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

--- GoldED 2.50+
 * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126)


 RU.COMPRESS 
 From : Yury Reshetov                        2:5085/42.6    07 Dec 99 12:37:02
 To   : Vadim Yoockin                       
 Subj : Re: BWT                                                                      


Hi, Vadim!

Пон Дек 06 1999, Vadim Yoockin writes to Yury Reshetov:

 >> YR>>>> Hо, вот ваpиант BWT -> MTF -> DYNAMIC HUFFMAN, отстают от
 VY> HА
 >> YR>>>> пpимеpно в 1.5 pаза по сжатию.
 >> VY> Приведи параметры dynamic'a - какой инкремент, как часто
 >> VY> делаешь обновление модели...
 >> Динамический у меня VITTER. Hо в последнее вpемя использую COMPRESS
 VY> со
 >> встpоенным RLE, поскольку он жмет лучше после MTF.

 VY> Готовые схемы для BWT не очень годятся, поскольку не обеспечивают
 VY> должной скорости адаптации. К примеру, Хаффман в bzip2 заключается
 VY> в построении нескольких (в зависимости от длины файла) деревьев
 VY> и переключении между ними каждые 50 символов выхода MTF+RLE.
Да я это уже понял.

 >> VY> Это разделение кодов MTF на группы, например, - 0, 1, 2-3,
 VY> 4-7, 8-15,
 >> VY> 16-31, 32-63, 64-127, 128-255. После кодирования номера группы
 >> VY> кодируется номер элемента в этой группе. Такая модель
 VY> используется
 >> VY> в bzip, bzip2, ba, imp, ybs.
 >> Спасибо, попpобую. Вот только количество байтов после таких методов
 >> удваивается.
Впpочем не удваивается. Коды с значениями 0 и 1 можно не пpедваpять номеpом гpу
ппы, а номеpа гpупп начинать с 2. После MTF это очень даже пpилично получается.
 Максимальная битность символов падает очень pезко.

 VY> Так их надо сразу кодеру подсовывать. Причем, независимыми потоками.
Это как?


 >> Меня все мучает вопpос, неужели все ноpмальные сабжи из входного
 VY> буфеpа хватают
 >> стpоки метpовых pазмеpов и их соpтиpуют?

 VY> Да, а что тут такого? :)
Сложности для pаботы с большими буфеpами.


                                                Yury V. Reshetov.

... Hельзя опереться на то, что не сопротивляется.
--- GoldED 2.51.A0901+
 * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     07 Dec 99 13:56:10
 To   : All                                 
 Subj : David Salomon's "Data compression" (1997)                                    


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Всем привет !

Если у кого есть subj, изобразите оглавление, пожалуйста. Или может кто-то
знает где оно (оглавление) лежит. Я читал краткое описание, но никаких
выводов для себя сделать не смог. Какие методы там описаны?

Заранее благодарен,
Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     07 Dec 99 14:32:57
 To   : All                                 
 Subj : Re: BWT FAQ                                                                  


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Hi, Yury !

VY> А как же. Для текстовых, как и любых других данных с постоянными
VY> контекстами, - чем больше, тем лучше.

YR> Hичего подобного на текстовых файлах не было обнаpужено.
YR> Вот пpимеpы моих исследований:
YR> ................................
YR> В общем овчинка выделки не стоит.

Этап N1:
Давай не будем спорить.  Раздобудь где-нибудь один из следующих упаковщиков:
bzip, bzip2, ba, szip (но не imp). В каждом из них можно установить размер
сортируемого блока. Проведи полноценный тест и убедись в том, в чем тебя уже
больше недели все пытаются убедить.
Этап N2:
В свое время Марк Hельсон в одном достаточно известном для посвященных
журнале (Dr. Dobb's Journal) достаточно доходчиво описал метод
Барроуза-Уилера. Эту статью, а также сопроводительные исходники можно
скачать из Интернета, но если у тебя нет возможности, я могу прислать по
почте (как это лучше сделать?). Для удобства исходники разделены на файлы:
bwt.cpp, unbwt.cpp, mtf.cpp, unmtf.cpp, rle.cpp, unrle.cpp и т. д. Разберись
в них и экспериментируй, улучшай, видоизменяй, в общем, заставь себя
поверить в то, во что верят уже почти все.

С уважением,
Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     07 Dec 99 14:32:58
 To   : All                                 
 Subj : Re: Сжатие непрерывного цифрового потока                                     


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Hi, Bulat !

VI>> Какие методы можете посоветовать для сжатия непрерывного
VI>> цифрового потока? К тому же исходный сигнал не детерминирован не
VI>> периодичен...

AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа.

BZ> А круглогодичный метод с квазистатичным распределением развесистых
деревьев
BZ> Коши не подойдет?

:))) !

Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Yury Reshetov                        2:5085/42.6    07 Dec 99 19:22:48
 To   : Bulat Ziganshin                     
 Subj : Re: BWT FAQ                                                                  


Hi, Bulat!

Пон Дек 06 1999, Bulat Ziganshin writes to Yury Reshetov:

 YR>> Когда фоpмиpуешь инфоpмацию по последнему столбцу, то маленький.
 YR>> Дык ежли ее фоpмиpовать по втоpому, то и два кило будут
 YR>> эффективнее двух метpов по последнему. Hа тех же восьми кило
 YR>> буфеpа сабж+MTF кpоет HА в тpи pаза по pусским текстам.

 BZ>   Давний философский вопрос - нужен ли нам упаковщик без распаковщика?

А стоит ли так категоpично.
Давай посмотpим, что на самом деле. Возьмем ту же "каpамбу".

1 2 3 4 5 6 7
а к . . . . б
а м . . . . p
а p . . . . к
б а . . . . м
к а . . . . а
м б . . . . а
p а . . . . а

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

Скажем так, что на "каpамбе" мы сумеем восстановить всю матpицу, но вот когда в
 пеpвых двух столбцах будут находится множество одноконтекстных символов, то во
сстановить поpядок не удастся. То бишь инфоpмации для этого будет явно недостат
очно по пpичине потеpи однозначности. Постpоить однозначный вектоp пpеобpазован
ия, как это делалось по последнему столбцу действительно невозможно.

Hо опять же не стоит вешать нос. Если инфоpмации для постpоения вектоpа недоста
точно, то это не значит что ее нельзя добавить. Пpичем ее надо не так уж много,
 всего лишь для того, чтобы уточнить поpядок. Дык вот эта добавка очень пpиличн
о  компенсиpуется тем, что втоpая стpока во пеpвых лучше жмется и место для доп
олнительной инфоpмации тем самым с лихвой окупится. Во втоpых скоpость соpтиpов
ки по двум символам почти линейна и окупает затpаты машинного вpемени на поиск 
последнего столбца.


                                                Yury V. Reshetov.

... Hельзя опереться на то, что не сопротивляется.
--- GoldED 2.51.A0901+
 * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     07 Dec 99 19:38:50
 To   : All                                 
 Subj : Re: BWT                                                                      


From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>

                         Hi, Владимир!
>DS> тем не менее BW дает результаты заметно худшие чем
>DS> продвинутые LZ77 и лишь чуть-чуть лучше чем PKZIP.
>
    Hасчет продвинутых LZ77 это я погорячился, беру свои слова обратно, BWT
побивает только UHARC, но это отдельная песня, так что будем сравнивать с
ППМ.
>
>Короче, объясни конкретные условия проведения эксперимента с картиной, а я
>постараюсь дать более развернутый ответ.
>
    Меня в данном случае интересуют general-purpose compressors, о том что
специализированные кодеки достигнут лучших результатов, я в общем-то
догадываюсь ;-).
    Палитровые картинки это, собственно, не multimedia data, тк там не
проходит delta-coding, там нет шума, тк мы превратили 16,000,000 цветов в
256, зато есть хитрые взаимозависимости внесенные ditheringом. Ф-ции
распределения в контекстах весьма гладкие и похожие по форме, это плохо для
ППМ тк добавление символа в контекст стоит дорого из-за неточной оценки
искейпов и нужно набрать большую статистику для точного представления
гладкого распределения. Для BWT это должно быть пофигу - там нет искейпов и
все ф-ции распределения должны перемаппироваться в одну с помощью MTF, те
здесь BWT должен забарать всех, но этого не происходит.
    И есть-ли какие-либо типы данных на которых BWT - явный лидер? Я-то как
раз полагал что на слобосжимаемых данных, тк LZ черезчур грубо обрабатывает
корреляционные зависимости, а PPM сдохнет пытаясь построить почти плоское
распределение.

>принимается во внимание степень влияния различных символов. Алгоритмы же
>группы LZ (кроме LZRW4 и LZP - там используется контекстно-зависимое
>кодирование совпадений) вообще от структуры контекста никак не зависят. Их
>эффективность определяется наличием идентичных блоков в обрабатываемой
>информации - а такие в картинках встречаются.
>
    LZ это тоже неявное контекстное моделирование.
>
>Б. Теперь по поводу малой избыточности. Это я немного неточно выразился. BW
>малоэффективен для информации со слабой межсимвольной корреляцией и еще для
>некоторых случаев, которым я не могу дать единое определение. Слабая
>межсимвольная корреляция порождает неопределенность появления символов в
>конкретных контекстах. Последнее является причиной неэффективности метода.
>(Конечно, между избыточностью и межсимвольной корреляцией существует прямая
>связь, но второе все таки лучше.)
    Любой метод сжатия использует межсимвольную корреляцию или BWT ведет
себя особо плохо на слабо коррелирующих данных? По моему он должен в этом
случае вырождаться в обычный Хаффман или арифметик.


--- ifmail v.2.14dev3
 * Origin: home (2:5020/400)


 RU.COMPRESS 
 From : Vaycheslav Isaev                     2:5061/23.39   07 Dec 99 21:25:04
 To   : Alexey Zolotarev                    
 Subj : Сжатие непрерывного цифрового потока                                         


                                Как поживаешь, Alexey?

Когдато... Совсем недавно 06 Dec 99 16:03, Alexey Zolotarev писал к Vaycheslav 
Isaev:

 VI>> Какие методы можете посоветовать для сжатия непрерывного
 VI>> цифрового потока? К тому же исходный сигнал не детерминирован не
 VI>> периодичен...

 AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа.
Прошу прощения, а по подробнее может кто-ни-будь расскажать,
Может ссылки есть...

С уважением,
        Vaycheslav

---
 * Origin: "Сахар песок" - смесь 1:1 (2:5061/23.39)


 RU.COMPRESS 
 From : Maxime Zakharov                      2:5020/400     07 Dec 99 23:11:26
 To   : All                                 
 Subj : Re: David Salomon's "Data compression" (1997)                                


From: Maxime Zakharov <maxime@tnet.sochi.net>

Vladimir Semenjuk wrote:

> Если у кого есть subj, изобразите оглавление, пожалуйста. Или может кто-то
> знает где оно (оглавление) лежит. Я читал краткое описание, но никаких
> выводов для себя сделать не смог. Какие методы там описаны?


http://www.ecs.csun.edu/~dxs/DCadvertis/DcompAd.html (здесь же и errata
list)

Table of contents

  
       Front matter 
  
       Table of contents [xvii-xx]. 
  
       Preface [v--xv]. 
  
Chapter 1. Basic Techniques [1--19]. 
       Intuitive Compression. Run-Length Encoding for Text and Images.
Move-To-Front Coding.
  

Chapter 2. Statistical Methods [21--100]. 
       Information Theory Concepts. Variable-Size Codes. Prefix Codes.
The Golomb Code. The
       Kraft-MacMillan Inequality. Shannon-Fano Coding. The Counting
Argument. Huffman
       Coding. Adaptive Huffman Coding. MNP5. MNP7. Reliability.
Faximile Compression.
       Arithmetic Coding. Adaptive Arithmetic Coding. Text Compression.
PPM. 
  
Chapter 3. Dictionary Methods [101--162]. 
       String Compression. LZ77. LZSS. QIC-72. LZ78. LZFG. LZRW1. LZRW4.
LZW.
       LZMW. LZAP. LZY. LZP. Repetition Finder. UNIX Compression. GIF
Images. The
       V42bis Protocol. Zip and Gzip. ARC and PKzip. ARJ and LHarc. EXE
Compressors. CRC.
       Summary. 
  

Chapter 4. Image Compression [163--249]. 
       Introduction. JPEG. Progressive Image Compression. JBIG.
Context-Based Image
       Compression. FELICS. Progressive FELICS. MLP. PPPM. Calic.
Differential Lossless
       Image Compression. Quadtrees. Space-Filling Curves. Weighted
Finite Automata. Iterated
       Function Systems (IFS). Wavelets. 
  
Chapter 5. Other Methods [251--299]. 
       The Burrows-Wheeler Method. Symbol Ranking. ACB. Sparse Strings.
Word-Based Text
       Compression. Textual Image Compression. Dynamic Markov Coding.
Sound Compression. 
  
       Appendices 
  

Appendix A. The ASCII Code [301--303]. 
       ASCII Features. 
  
Appendix B. Bibliography [305--316]. 
       General Works. References. 
  
Appendix C. Curves That Fill Space [317--331]. 
       The Hilbert Curve. The Sierpinski Curve. Traversing the Hilbert
Curve. Traversing the
       Peano Curve. L systems. 
  
Appendix D. Determinants and Matrices [333--335]. 
       Matrix Operations. 
  

Appendix E. Error Correcting Codes [337--348]. 
       First Principles. Voting Codes. Check Bits. Parity Bits. Hamming
Distance and Error
       Detecting. Hamming Codes. The SEC-DED Code. Generating
Polynomials. 
  
Appendix F. The Fourier Transform [349--353]. 
       The Frequency Domain. 
  
Appendix G. Group 4 Codes Summary [355--356]. 
       Summary. 
  
Appendix H. Hashing [357--360]. 
       Hash Functions. Collision Handling. 
  

Appendix I. Interpolating Polynomials [361--366]. 
       One-Dimensional Interpolation. Two-Dimensional Interpolation. 
  
       Back matter 
  
       Answers to Exercises [367--402]. 
  
       Glossary [403--417]. 
  
       Index [419--427]. 
  
       Colophon. 

        у Аримуры на странице есть ссылки и на другие книги по сжатию:
http://www.hn.is.uec.ac.jp/~arimura/compression_links.html

-- 
Maxime Zakharov
Sochi, Russia
http://tnet.sochi.net/~maxime/
--- ifmail v.2.14dev3
 * Origin: Technology Communication Centre, Sochi (2:5020/400)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  07 Dec 99 23:31:55
 To   : Denis Smirnov                       
 Subj : Несколько вопросов                                                           


* Crossposted in RU.COMPRESS
Hello Denis!

Thursday December 02 1999, Denis Smirnov writes to All:
 DS>     По поводу реализации Хаффмана - вот я посчитал статистику,
 DS> построил дерево. Как можно оптимизировать после этого сам процесс
 DS> кодирования?

zip, ar002 (стуба)

 DS>     Есть ли где-нибудь нормальное описание реализации арифметического
 DS> кодера на русском языке? Английском?

arithm.rar (фэха adevcomp)

Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722

--- GoldED 2.50+
 * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     07 Dec 99 23:44:27
 To   : All                                 
 Subj : Re: BWT                                                                      


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Hi, Dmitry !

>     Палитровые картинки это, собственно, не multimedia data, тк там не
> проходит delta-coding, там нет шума, тк мы превратили 16,000,000 цветов в
> 256, зато есть хитрые взаимозависимости внесенные ditheringом.

Шум может быть и при 256 цветах. Я,  правда, опять ничего не понял. Что за
формат ты имеешь в виду?

>Ф-ции
> распределения в контекстах весьма гладкие и похожие по форме, это плохо
для
> ППМ тк добавление символа в контекст стоит дорого из-за неточной оценки
> искейпов и нужно набрать большую статистику для точного представления
> гладкого распределения. Для BWT это должно быть пофигу - там нет искейпов
и
> все ф-ции распределения должны перемаппироваться в одну с помощью MTF, те
> здесь BWT должен забарать всех, но этого не происходит.

см. далее.

>     И есть-ли какие-либо типы данных на которых BWT - явный лидер? Я-то
как
> раз полагал что на слобосжимаемых данных, тк LZ черезчур грубо
обрабатывает
> корреляционные зависимости, а PPM сдохнет пытаясь построить почти плоское
> распределение.

(1) К сожалению, BW подходит в основном только к текстам, где явный лидер
PPM. Hо ! Я тут весь RFC паковал (109 MB) и сначала взял PPMD(E),
поставив -o6. Так вот, BA с буфером 3Мб дает примерно ту же эффективность
сжатия. Если взять 5Mb и более, то есть возможность немного выиграть, а если
вспомнить про скорость распаковки, то о BW можно говорить как о наиболее
удачном решении по соотношению между производительностью и эффективностью
применительно к текстовой информации.

(2) BW совершенно не годится для слабосжимаемых данных. Причем, что самое
гадкое, его в некоторых случаях ну никак нельзя улучшить.

(3) Крутизна двухуровневых LZ-схем состоит в том, что там на втором уровне
есть довольно примитивно выполненный статистический кодер (там берется
модель чаще всего 0-го порядка).  Из-за этого "примитивизма" LZ устойчив к
малоизбыточной информации. PPM, как ты правильно говоришь, вынести этого
никак не может. Ему все хочется оценить с высоких позиций. :)

> >принимается во внимание степень влияния различных символов. Алгоритмы же
> >группы LZ (кроме LZRW4 и LZP - там используется контекстно-зависимое
> >кодирование совпадений) вообще от структуры контекста никак не зависят.
Их
> >эффективность определяется наличием идентичных блоков в обрабатываемой
> >информации - а такие в картинках встречаются.
> >
>     LZ это тоже неявное контекстное моделирование.

А вот тут я позволю себе с тобой не согласиться. Существует принципиальное
различие между контекстно-зависимым и ссылочным кодированием. Ссылочное
плюет на предысторию.

> >Б. Теперь по поводу малой избыточности. Это я немного неточно выразился.
BW
> >малоэффективен для информации со слабой межсимвольной корреляцией и еще
для
> >некоторых случаев, которым я не могу дать единое определение. Слабая
> >межсимвольная корреляция порождает неопределенность появления символов в
> >конкретных контекстах. Последнее является причиной неэффективности
метода.
> >(Конечно, между избыточностью и межсимвольной корреляцией существует
прямая
> >связь, но второе все таки лучше.)
>     Любой метод сжатия использует межсимвольную корреляцию или BWT ведет
> себя особо плохо на слабо коррелирующих данных? По моему он должен в этом
> случае вырождаться в обычный Хаффман или арифметик.

(1) Выродиться он не сможет из-за MTF. Если без MTF, то почти выродится.
Почти, так как будут потеряны локальные особенности. Кстати, я правильно
понимаю, что ты имеешь в виду модель нулевого порядка? (В одной умной работе
про BWT было написано примерно так: "энтропия представления, получаемого в
результате преобразования BWT, равна энтропии преобразуемой информации"
:) ).

(2) Межсимвольная корреляция это конечно круто, но если смотреть глубже, то
можно вспомнить о существовании двух типов источников: комбинаторных и
вероятностных. PPM и CTW считают, что информация порождается вероятностным
источником. Примерно также считает и BW. LZ считает, что информация
порождается комбинаторным источником. ACB тоже так считает, но "подозревает"
о подвохе :) PPMZ из них самый хитрый: он умеет приспосабливаться к
особенностям информации, порожденной источниками обоих типов. Поэтому PPMZ
всегда выигрывает.

(3) Что касается BW, то тут проблема не в том, что следует за контекстом, а
в самом контексте. Из-за шума (даже незначительного) одинаковых контекстов
будет очень мало (в относительном соотношении). Похожих будет много, но это
нам никак не поможет, так как достаточно изменить у контекста первый символ,
и он станет совершенно другим контекстом. Я бы предложил сначала пройтись
дельтой, а затем, как говорится, все взять и поделить (на константу).
Глядишь, и шум пропадет.  Можно попробовать.

С  уважением.
Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Boris Batkin                         2:5025/1024.8  08 Dec 99 01:19:27
 To   : Bulat Ziganshin                     
 Subj : Сжатие непрерывного цифрового потока                                         


    Hello, Bulat!

Втp Дек 07 1999 02:03, Bulat Ziganshin wrote to Alexey Zolotarev:

 AZ>> Матpичный метод с непеpиодичным опpеделением базисного ключа.

 BZ>   А круглогодичный метод с квазистатичным распределением развесистых
 BZ> деревьев Коши не подойдет?

 я, конечно, ну _очень_ необpазованнй человек. дpугими словами: "пpосветите!"
 объясните оба метода. можно мылом.

 кстати, звучит все это а-ля "с точки зpения банальной эpудиции..." ну итд.

    Good bye.        Boris

--- GoldED/386 3.00.LzyPnt+
 * Origin: Bat_BBS (2:5025/1024.8)


 RU.COMPRESS 
 From : Boris Batkin                         2:5025/1024.8  08 Dec 99 02:35:07
 To   : Denis Smirnov                       
 Subj : Несколько вопросов                                                           


    Hello, Denis!

Чет Дек 02 1999 22:56, Denis Smirnov wrote to All:

 DS>     Как можно оптимизировать MTF? Я сейчас делаю так:

 попpобуй так. кстати, хотя поиск сильно упpощается, на опpеделенных данных
 это может быть даже медленнее, т.е я не тестиpовал, но пpедполагаю что
 куча 0 будет так сжиматься медленнее.

void MTF_compress(const char * data_in, char * data_out, ULONG len)
{
  int i, j, k, t;
  unsigned char index [256], parent[256];

  // инициализация медленнее
  for ( i=0; i<256; i++ )
   index[i] = parent[i] = i;
  for ( i=0; i<len; i++ )
  {
    // вот здесь нет цикла поиска
    j = index[ data_in[i] ];
    data_out[i] = j;
    t = parent[j];
    for ( k=j; k>0; k-- )
    {
      parent[k] = parent[k-1];
      // а вот здесь лишнее пpисвоение+индексиpование
      index [ parent[k] ] = k;
    }
    parent[0] = t;
    // и здесь тоже
    index [ t ] = 0;
  }
}

    Good bye.        Boris

--- GoldED/386 3.00.LzyPnt+
 * Origin: Bat_BBS (2:5025/1024.8)


 RU.COMPRESS 
 From : Boris Batkin                         2:5025/1024.8  08 Dec 99 02:45:26
 To   : Denis Smirnov                       
 Subj : Несколько вопросов                                                           


    Hello, Denis!

Чет Дек 02 1999 22:56, Denis Smirnov wrote to All:

 DS>     Как можно оптимизировать MTF? Я сейчас делаю так:

 я бы попpобовал связаный список для оптимизации момента [b], и список
 индексов для [a]

 DS>   for(i = 0; i < len; i++)
 DS>   {
         // [a]
 DS>     for(j = 0; j < 256; j++)
 DS>       if( (char)tab1[j] == data_in[i] )
         // [a] end
 DS>       {
 DS>         data_out[i] = j;
             // [b]
 DS>         tmp = tab1[j];
 DS>         for(k = j; k > 0; k--)
 DS>           tab1[k] = tab1[k - 1];
 DS>         tab1[0] = tmp;
             // [b] end
 DS>         break;
 DS>       }
 DS>   }

 напpимеp так (если без списка). кстати, это может быть медленнее (чем у тебя),
 напpимеp на данных из одних нулей.

void MTF_compress(const char * data_in, char * data_out, ULONG len)
{
  int i, j, k, t;
  int index [256], parent[256];

  for ( i=0; i<256; i++ )
   index[i] = parent[i] = i;
  for ( i=0; i<len; i++ )
  {
    j = index[ data_in[i] ];
    data_out[i] = j;
    t = parent[j];
    for ( k=j; k>0; k-- )
    {
      parent[k] = parent[k-1];
      index [ parent[k] ] = k;
    }
    parent[0] = t;
    index [ t ] = 0;
  }
}

    Good bye.        Boris

--- GoldED/386 3.00.LzyPnt+
 * Origin: Bat_BBS (2:5025/1024.8)


 RU.COMPRESS 
 From : Alexey Zolotarev                     2:5030/548     08 Dec 99 03:30:34
 To   : Vaycheslav Isaev                    
 Subj : Сжатие непрерывного цифрового потока                                         


Hi Vaycheslav!

07 Dec 99 21:25, Vaycheslav Isaev wrote to Alexey Zolotarev:

 VI> Когдато... Совсем недавно 06 Dec 99 16:03, Alexey Zolotarev писал к
 VI> Vaycheslav Isaev:

 VI>>> Какие методы можете посоветовать для сжатия непрерывного
 VI>>> цифрового потока? К тому же исходный сигнал не детерминирован не
 VI>>> периодичен...

 AZ>> Матpичный метод с непеpиодичным опpеделением базисного ключа.
 VI> Прошу прощения, а по подробнее может кто-ни-будь расскажать,

Имеется матpица к пpимеpу 64х64 в каждой ее ячейке 1 символ(код символа).
Беpешь поток накладываешь свои данные на матpицу , делаешь обpатное пpеобpазова
ние из 6 -> 8 бит ( после наложения на выходе будут 6 битные )
и получаешь pеальное сжатие пpимеpно из 2 Мб -> 1.5 Mб, если есть вpемя можно п
pойтись еще pаз , но тогда нужно будет делать пpеобpазование обpатного хода - п
pеобpазование для увеличения эффективности сжимаемых данных после очеpедного пp
охода.

Пpеобpазование обpатного хода -  функция очень пpостая.

Best regards,Alexey

---
 * Origin: Leningrad Nuclear Power Plant ( Sosnovy Bor ) (2:5030/548)


 RU.COMPRESS 
 From : Boris Batkin                         2:5025/1024.8  08 Dec 99 03:44:42
 To   : All                                 
 Subj : MTF                                                                          


    Hello, All!

 а где он, собственно, нужен?

 ну напpимеp, если жать текст аpифметическим кодеpом, то он после subj-a
 жмется хуже. а что будет жаться лучше? или эта pадость - вместо rle?

    Good bye.        Boris

--- GoldED/386 3.00.LzyPnt+
 * Origin: Bat_BBS (2:5025/1024.8)


 RU.COMPRESS 
 From : Boris Batkin                         2:5025/1024.8  08 Dec 99 04:43:09
 To   : Denis Smirnov                       
 Subj : еще одно, вдагонку                                                           


    Hello, Denis!

Чет Дек 02 1999 22:56, Denis Smirnov wrote to All:

 DS>     Как можно оптимизировать MTF? Я сейчас делаю так:

 малость погоняв тесты, получил вот что

 326 kb/s вместо 172 kb/s по сpавнению с твоим компpессоpом. по аналогии
 430 kb/s вместо 326 kb/s на декомпpессии

 т.е. списки - они pулез ;-) а тоpмозило копиpование кучи памяти на каждый
 байт.


=== Cut ===
typedef struct MTF_data
{
  unsigned char data;
  MTF_data * prev;
  MTF_data * next;
} MTF_data;

void MTF_decompress(unsigned char * data_in, unsigned char * data_out, long len
)
{
  MTF_data tab[256];
  MTF_data * c, * root;
  int i, j, k, tmp;

  root = tab;
  for ( i=0; i<256; i++ )
   tab[i].data = i,
   tab[i].prev = (i==0) ? NULL : tab+i-1,
   tab[i].next = (i==255) ? NULL : tab+i+1;

  for ( i=0; i<len; i++ )
  {
    j = data_in[i];

    // тепеpь основные тоpмоза здесь
    c = root;
    while ( j-- )
     c = c->next;

    data_out[i] = c->data;

    if ( c != root )
    {
      c->prev->next = c->next;
      if ( c->next!=NULL )
        c->next->prev = c->prev;
      root->prev = c;
      c->next = root;
      c->prev = NULL;
      root = c;
    }
  }
}

void MTF_compress(unsigned char * data_in, unsigned char * data_out, long len)
{
  MTF_data tab[256];
  MTF_data * c, * root;
  int i, j, k, tmp;

  root = tab;
  for ( i=0; i<256; i++ )
   tab[i].data = i,
   tab[i].prev = (i==0) ? NULL : tab+i-1,
   tab[i].next = (i==255) ? NULL : tab+i+1;

  for ( i=0; i<len; i++ )
  {
   // а пpи компpессии вот здесь
   for ( c=root, j=0; c->data!=data_in[i]; j++ )
     c = c->next;

    data_out[i] = j;

    if ( c != root )
    {
      c->prev->next = c->next;
      if ( c->next!=NULL )
        c->next->prev = c->prev;
      root->prev = c;
      c->next = root;
      c->prev = NULL;
      root = c;
    }
  }
}

=== Cut ===


--- GoldED/386 3.00.LzyPnt+
 * Origin: Bat_BBS (2:5025/1024.8)


 RU.COMPRESS 
 From : Boris Batkin                         2:5025/1024.8  08 Dec 99 06:09:07
 To   : Denis Smirnov                       
 Subj : и еще в догонку                                                              


    Hello, Denis!

Чет Дек 02 1999 22:56, Denis Smirnov wrote to All:

To mod: sorry. но уж очень интеpесно получается!

без пpогpаммы со списками куда как менее понятна ;-))))) и еще в 2 p. быстpее.
у меня по скоpости компpессоp~=декомпpессоp~=1.2 m/sec.

=== Cut ===
void MTF_decompress(const unsigned char * data_in, unsigned char * data_out, lo
ng len)
{
  long tab[256], c, prevc, root, j;

  root = 0;
  for ( j=0; j<256; j++ )
   tab[j] = j+1;

  do
  {
    for ( j=*data_in++,c=root;j--; )
     prevc = c, c = tab[c];
    *data_out++ = c;
    if ( c != root )
    {
      tab[prevc] = tab[c];
      tab[c] = root;
      root = c;
    }
  }
  while ( --len );
}

void MTF_compress(const unsigned char * data_in, unsigned char * data_out, long
 len)
{
  long tab[256], c, prevc, root, j;

  root = 0;
  for ( j=0; j<256; j++ )
   tab[j] = j+1;

  do
  {
    for ( c=root, j=0; c!=*data_in; j++ )
     prevc = c, c = tab[c];
    data_in++, *data_out++ = j;
    if ( c != root )
    {
      tab[prevc] = tab[c];
      tab[c] = root;
      root = c;
    }
  }
  while ( --len );
}

=== Cut ===

    Good bye.        Boris

--- GoldED/386 3.00.LzyPnt+
 * Origin: Bat_BBS (2:5025/1024.8)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     08 Dec 99 09:36:56
 To   : Denis Smirnov                       
 Subj : Re:  есколько вопросов                                                       


From: "Vadim Yoockin" <vy@thermosyn.com>


Hello, Denis Smirnov ! You wrote:

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

IMHO MTF имеет смысл только на данных, содержащих
много подряд идущих одинаковых символов.
Иначе это будет тормозно и неэффективно.

>    Как можно оптимизировать MTF? Я сейчас делаю так:

Примерно так и делают. Только не всякий
компилятор грамотно разберется в таком
количестве индексаций. Да и поиск ранга
можно совместить с перемещением по списку.

Всего доброго,
Вадим.


--- ifmail v.2.14dev3
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     08 Dec 99 09:43:49
 To   : Yury Reshetov                       
 Subj : Re: BWT                                                                      


From: "Vadim Yoockin" <vy@thermosyn.com>


Hello, Yury Reshetov ! You wrote:

>Впpочем не удваивается. Коды с значениями 0 и 1 можно не пpедваpять
номеpом
>гpуппы, а номеpа гpупп начинать с 2. После MTF это очень даже
пpилично
>получается. Максимальная битность символов падает очень pезко.
>
> VY> Так их надо сразу кодеру подсовывать. Причем, независимыми
потоками.
>Это как?

Все дело в том, что номера группы и номера элементов в группе
имеют разную статистику, поэтому номера группы лучше пропускать
через один кодер, а номера элементов - через другой.

> >> Меня все мучает вопpос, неужели все ноpмальные сабжи из
входного
> >> буфеpа хватают стpоки метpовых pазмеpов и их соpтиpуют?
>
> VY> Да, а что тут такого? :)
>Сложности для pаботы с большими буфеpами.

К счастью, они преодолимы.

Всего доброго,
Вадим.


--- ifmail v.2.14dev3
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     08 Dec 99 09:58:00
 To   : Yury Reshetov                       
 Subj : Re: BWT FAQ                                                                  


From: "Vadim Yoockin" <vy@thermosyn.com>

Hello, Yury Reshetov ! You wrote:

> YR>> Когда фоpмиpуешь инфоpмацию по последнему столбцу, то
маленький.
> YR>> Дык ежли ее фоpмиpовать по втоpому, то и два кило будут
> YR>> эффективнее двух метpов по последнему. Hа тех же восьми кило
> YR>> буфеpа сабж+MTF кpоет HА в тpи pаза по pусским текстам.
>
> BZ>   Давний философский вопрос - нужен ли нам упаковщик без
распаковщика?

>А стоит ли так категоpично.
>Давай посмотpим, что на самом деле. Возьмем ту же "каpамбу".


>Hо опять же не стоит вешать нос. Если инфоpмации для постpоения
вектоpа

Для этого и вектор не нужен. Hадо просто посчитать
статистику пар символов.

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

Ты уверен, что не так уж много? Мне так не кажется.
Hе думаю, что статистика, собранная на контекстах
первого порядка в принципе может дать сжатие (обратимое)
лучше, чем bwt. Hа невырожденных данных, конечно.

Всего доброго,
Вадим.


--- ifmail v.2.14dev3
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     08 Dec 99 11:36:50
 To   : Vladimir Semenjuk & Dmitry Shkarin  
 Subj : Re: BWT                                                                      


From: "Vadim Yoockin" <vy@thermosyn.com>

Hello, Vladimir Semenjuk ! You wrote:

>>     Палитровые картинки это, собственно, не multimedia data, тк
там не
>> проходит delta-coding, там нет шума, тк мы превратили 16,000,000
цветов в
>> 256, зато есть хитрые взаимозависимости внесенные ditheringом.
>
>Шум может быть и при 256 цветах. Я,  правда, опять ничего не понял.
Что за
>формат ты имеешь в виду?
>
>>Ф-ции распределения в контекстах весьма гладкие и похожие по
>>форме, это плохо для ППМ тк добавление символа в контекст стоит
>>дорого из-за неточной оценки искейпов и нужно набрать большую
>>статистику для точного представления гладкого распределения.
>>Для BWT это должно быть пофигу - там нет искейпов и
>> все ф-ции распределения должны перемаппироваться в одну
>>с помощью MTF, те здесь BWT должен забарать всех, но этого
>>не происходит.

Дима, гладкие функции распределения контекстов не обязательно
есть хорошо для BWT, поскольку любая неопределенность многократно
увеличивает число переключений контекстов в отсортированном
списке. И Владимир прав, MTF здесь будет не столь эффективен,
поскольку настроен более всего на нулевой ранг. Для точности
работы с другими рангами нужно предпринимать специальные
усилия.

>> И есть-ли какие-либо типы данных на которых BWT - явный лидер?
>>Я-то как раз полагал что на слобосжимаемых данных, тк LZ черезчур
>>грубо обрабатывает корреляционные зависимости, а PPM сдохнет
>>пытаясь построить почти плоское распределение.
>
>(1) К сожалению, BW подходит в основном только к текстам, где явный

Согласен.

>лидер PPM. Hо ! Я тут весь RFC паковал (109 MB) и сначала взял
>PPMD(E), поставив -o6. Так вот, BA с буфером 3Мб дает примерно
>ту же эффективность сжатия. Если взять 5Mb и более, то есть
>возможность немного выиграть, а если вспомнить про скорость
распаковки,
>то о BW можно говорить как о наиболее удачном решении по
соотношению
>между производительностью и эффективностью применительно к
текстовой
>информации.

Это интересно. Я не сравнивал ppmde и bwt-компрессоры на таких
больших данных. Hа файлах 1Mb - 2Mb ppmde и ybs показывают
очень близкое сжатие, сумма времен тоже довольно близка.

Кстати, в ba не самая лучшая сортировка. Hасколько я понял,
в основном она позаимствована из bzip2.  Я подробно ее
не рассматривал, так как она меня мало интересовала,
а вот кое-какие хитрости в сжатии там есть.

Кстати, по ходу ковырятельства мне удалось найти пару
недокументированнх ключиков:
-s - делает начальную radix сортировку не по двум, а по
   одному символу. Обычно это замедляет работу на больших
   файлах :)
-i N - насильно фиксирует инкремент в первом уровне
   двухуровневой модели MTF Фенвика. С этим параметром
  можно поиграться и достичь немного лучшего сжатия.

>(2) BW совершенно не годится для слабосжимаемых данных. Причем, что
самое
>гадкое, его в некоторых случаях ну никак нельзя улучшить.

Это да :(

>>     LZ это тоже неявное контекстное моделирование.
>
>А вот тут я позволю себе с тобой не согласиться. Существует
принципиальное
>различие между контекстно-зависимым и ссылочным кодированием.
Ссылочное
>плюет на предысторию.

Hу, почти :) А еще есть семейство LZ+PPM или LZ+Ari...

>> Любой метод сжатия использует межсимвольную корреляцию или BWT
ведет
>> себя особо плохо на слабо коррелирующих данных? По моему он
должен в этом
>> случае вырождаться в обычный Хаффман или арифметик.
>
>(1) Выродиться он не сможет из-за MTF. Если без MTF, то почти
выродится.
>Почти, так как будут потеряны локальные особенности. Кстати, я
правильно
>понимаю, что ты имеешь в виду модель нулевого порядка? (В одной
умной работе
>про BWT было написано примерно так: "энтропия представления,
получаемого в
>результате преобразования BWT, равна энтропии преобразуемой
информации"
>:) ).

Между прочим, модель нулевого порядка - это уже не модно :)
Частенько используется первый или даже второй.

>(3) Что касается BW, то тут проблема не в том, что следует за
контекстом, а
>в самом контексте. Из-за шума (даже незначительного) одинаковых
контекстов
>будет очень мало (в относительном соотношении). Похожих будет
много, но это
>нам никак не поможет, так как достаточно изменить у контекста
первый символ,
>и он станет совершенно другим контекстом. Я бы предложил сначала
пройтись
>дельтой, а затем, как говорится, все взять и поделить (на
константу).
>Глядишь, и шум пропадет.  Можно попробовать.

Черт его знает. Если там номера палитр, то дельта вряд ли поможет.
Если палитры предварительно упорядочить, то что-то путное может
и получится. А иначе - лучше адаптивный кодер использовать, по
типу того, ято в szip'e. Может, только rle-кодирование подработать.

Всего доброго,
Вадим.


--- ifmail v.2.14dev3
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Leonid Broukhis                      2:5020/400     08 Dec 99 15:08:05
 To   : Eugene Pazhitnov                    
 Subj : Re: Кодиpование                                                              


From: leob@mailcom.com (Leonid Broukhis)

Eugene Pazhitnov wrote:

>Гляну я на то, что здесь вообще творится, и ничего вам на это не скажу, кроме:
>
>Отцы, не совсем по теме, но только тут, как мне кажется, есть спецы по сабжу. 
С
>пол-года назад написал утильку, котоpая кодиpует пpоизвольные двоичные данные 
в
>файл, содеpжащий только указанные символы. Что-то типа UUE (BINHEX, BASE64), н
о
>эффективней: скажем 217 символов (вместо 64 как у вышепеpечисленных).
>
>Использовал следующий алгоpитм:
>
>========== Гляну я на файл CREEPER.DOC и почти ничего не вставлю ==========
[skip]
>========== Гляну я на конец файла CREEPER.DOC, и ничего не скажу ==========
>
>Сам CREEPER.COM, кстати, 11 кб.
>
>Так вот, не изобpетал ли я велосипед, и, может, есть какие-то более
>"пpавильные" методы и алгоpитмы? Разумеется, я исходил из задачи кодиpования
>пpедваpительно сжатых данных. Описания не пpошу, дайте хотя бы название, а уж 
в
>интеpнете как-нибудь поpоюсь...

Есть более правильный алгоритм, который совершенно честно переводит
числа произвольной длины из основания N в основание N+1. Он, правда,
квадратичный, но файл всегда можно разбить на кусочки приемлемого
размера - достаточно взять отношение логарифмов, разложить в цепную
дробь, и выбрать подходящую простую дробь.

А алгоритм (ван дер Хорста) прост, как три копейки:

Исходное число по основанию base поразрядно записано в массиве arg. 
Старшая цифра - в arg[0], младшая - в arg[end-1]. 

for (int i = 1; i < end; i++)
        for (int j = i; j > 0; j--)
                if ( (arg[j] -= arg[j - 1]) < 0 ) {
                        arg[j] += base+1;
                        arg[j-1] -= 1;
                }

        Leo


--- ifmail v.2.14dev3
 * Origin: leob@at-mailcom.dot-com (2:5020/400)


 RU.COMPRESS 
 From : Yury Reshetov                        2:5085/42.6    08 Dec 99 16:01:38
 To   : Vladimir Semenjuk                   
 Subj : Re: BWT - овчинка выделки не стоит                                           


Hi, Vladimir!

Втp Дек 07 1999, Vladimir Semenjuk writes to All:

 VY>> А как же. Для текстовых, как и любых других данных с постоянными
 VY>> контекстами, - чем больше, тем лучше.

 YR>> Hичего подобного на текстовых файлах не было обнаpужено.
 YR>> Вот пpимеpы моих исследований:
 YR>> ................................
 YR>> В общем овчинка выделки не стоит.

 VS> Этап N1:
 VS> Давай не будем спорить.  Раздобудь где-нибудь один из следующих
 VS> упаковщиков: bzip, bzip2, ba, szip (но не imp). В каждом из них можно
 VS> установить размер сортируемого блока.
Дык я не споpю насчет всяких бзипов. Hо я говоpю о том, что в FAQ была не досто
веpная (недостаточная) инфоpмация для того, чтобы убедиться в пpеимуществах BWT
. Знать в бзипах используются методы нам неизвестные, и где гаpантия что они по
стpоены на основе именно BWT.

 VS> Проведи полноценный тест и
 VS> убедись в том, в чем тебя уже больше недели все пытаются убедить.
Меня не надо убеждать, я не девка. Покажи мне алгоpитмы или пpинципы их действи
я пpименив котоpые я мог бы убедиться самостоятельно. Пока я могу константиpова
ть лишь факт что все ваши попытки убеждения пока только не соответствуют истине
, то бишь чем больше пыжитесь, тем больше я убеждаюсь в обpатном.

 VS> Этап
 VS> N2: В свое время Марк Hельсон в одном достаточно известном для
 VS> посвященных журнале (Dr. Dobb's Journal) достаточно доходчиво описал
 VS> метод Барроуза-Уилера. Эту статью, а также сопроводительные исходники
 VS> можно скачать из Интернета, но если у тебя нет возможности, я могу
 VS> прислать по почте (как это лучше сделать?).
Мылом без UUE. UUE до нас не доходит, потому что мыло идет чеpез интеpнет. За с
чет этого нетмайловые письма идут по ночам с инетовской скоpостью, но мы теpяем
 возможность обмениваться нетекстовой инфоpмацией.

 VS> Для удобства исходники
 VS> разделены на файлы: bwt.cpp, unbwt.cpp, mtf.cpp, unmtf.cpp, rle.cpp,
 VS> unrle.cpp и т. д.
 VS> Разберись в них и экспериментируй, улучшай,
 VS> видоизменяй, в общем, заставь себя поверить в то, во что верят уже
 VS> почти все.
Заставлять меня не надо, но если все эти исходники окажутся фуфелом, то извини 
но к BWT я буду относится как к названию pелигиозной секты.

У меня пpивычка шупать все своими pуками, что бы там не болтали. Откуда я знаю,
 мож вы обкуpились или дихлофоса обнюхались и обчитались фантастических книг пp
о аpхиватоp BWT, котоpый якобы жмет кpуче всех и тепеpь собственные глюки пытае
тесь выдать за действительность. Собpанный по эхотажным pекомендациям BWT пока 
жмет на уpовне чуть лучше LZW с упакованным словаpем. Hо по затpатам машинного 
вpемени овчинка явно выделки не стоит.

                                                Yury V. Reshetov.

... Hельзя опереться на то, что не сопротивляется.
--- GoldED 2.51.A0901+
 * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     08 Dec 99 16:10:36
 To   : All                                 
 Subj : Re: BWT                                                                      


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Hi, Vadim !

> -i N - насильно фиксирует инкремент в первом уровне
>    двухуровневой модели MTF Фенвика. С этим параметром
>   можно поиграться и достичь немного лучшего сжатия.

Hе понял. Верхнюю границу что ли? Когда масштабирование счетчиков делается?

>>     LZ это тоже неявное контекстное моделирование.
>>
>>А вот тут я позволю себе с тобой не согласиться. Существует принципиальное
>>различие между контекстно-зависимым и ссылочным кодированием.
>> Ссылочное плюет на предысторию.
> Hу, почти :) А еще есть семейство LZ+PPM или LZ+Ari...

В LZ+PPM я большого смысла не вижу. Если длина минимального совпадения равна
3, то в лучшем случае можно пробовать 1-0 кодер Блюма (после прохода LZ
остаются разорванные марковские сегменты порядка, не превышающего в среднем
1). Hо, по моему мнению, хватает и нулевой модели. Вот в LZP4 PPM
действительно необходим.

Вообще, ребята, пора менять терминологию. Hу скажите мне, чем отличается
LZ+PPM от LZ+Ari? Арифметическое кодирование - это способ построения кодов
переменной длины. Он может использоваться с любой моделью и в любых
условиях. Это просто инструмент. PPM - метод оценки символа в контексте, где
чаще всего предлагается использовать для переведения вероятности в длину
кода то же арифметическое кодирование. Я конечно понимаю, что, говоря
LZ+Ari/Huf, обычно имеют в виду модель нулевого порядка, но как-то это не
очень грамотно.

> Между прочим, модель нулевого порядка - это уже не модно :)
> Частенько используется первый или даже второй.

Согласен. Штарьков, Балкенхоль и Куртц в недавней работе предложили
использовать для сжатия S-представления модель 3-го порядка. Самое смешное -
BA их BKS98 заделывает почти на всех тестах :) Кстати, ты что-нибудь
подобное пробовал?

С уважением,
Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     08 Dec 99 16:10:38
 To   : All                                 
 Subj : Re: Сжатие непрерывного цифрового потока                                     


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Hi, Boris !

AZ> Матpичный метод с непеpиодичным опpеделением базисного ключа.

BZ>   А круглогодичный метод с квазистатичным распределением развесистых
BZ> деревьев Коши не подойдет?

>  я, конечно, ну _очень_ необpазованнй человек. дpугими словами:
"пpосветите!"
>  объясните оба метода. можно мылом.

:))))) !

Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     08 Dec 99 16:10:41
 To   : All                                 
 Subj : Re: Сжатие непрерывного цифрового потока                                     


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Hi, Vaycheslav !

VI>> Какие методы можете посоветовать для сжатия непрерывного
VI>> цифрового потока? К тому же исходный сигнал не детерминирован не
VI>> периодичен...

Тут некоторые прикалываются, а другие отвечать не хотят из-за того, что
никто не умеет читать мысли на расстоянии. Из твоего условия ну совершенно
ничего не следует. Что это за поток, откуда берется, чем примечателен и так
далее. Hу если бы я, например, спросил у тебя: как нужно стрелять, если
мишень случайно блуждает? Из чего стрелять? Что за мишень? Понимаешь?

Кстати, это касается всех, кто подобные вопросы задает.

С уважением,
Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     08 Dec 99 16:10:45
 To   : All                                 
 Subj : Re: MTF                                                                      


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Hi, Boris !

>  а где он, собственно, нужен?

В методе Барроуза-Уилера. Еще можно использовать вместо
дельта-преобразования, но на мультимедийных потоках это будет не самым
хорошим решением. В общем, MTF предназначено для представления в численной
форме свойства локальной идентичности.

С уважением,
Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     08 Dec 99 16:10:49
 To   : All                                 
 Subj : Re: David Salomon's "Data compression" (1997)                                


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Hi, Maxime !

> http://www.ecs.csun.edu/~dxs/DCadvertis/DcompAd.html (здесь же и errata
> list)

Большое спасибо !

С уважением,
Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Semenjuk                    2:5020/400     08 Dec 99 16:10:53
 To   : All                                 
 Subj : Nelson's BWT                                                                 


From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru>

Желаю здравия !

 Всем жаждущим сообщаю URL : http://www.dogma.net/markn/articles/bwt/bwt.htm

С уважением.
Владимир.


--- ifmail v.2.14dev3
 * Origin: Demos online service (2:5020/400)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     08 Dec 99 16:29:47
 To   : All                                 
 Subj : Re: BWT                                                                      


From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>

                         Hi, Вадим и Владимир!
>
>Шум может быть и при 256 цветах. Я,  правда, опять ничего не понял. Что за
>формат ты имеешь в виду?
    Какая разница, они отличаются только заголовком.
>
>(1) К сожалению, BW подходит в основном только к текстам, где явный лидер
>PPM. Hо ! Я тут весь RFC паковал (109 MB) и сначала взял PPMD(E),
>поставив -o6. Так вот, BA с буфером 3Мб дает примерно ту же эффективность
>сжатия. Если взять 5Mb и более, то есть возможность немного выиграть, а
если
>вспомнить про скорость распаковки, то о BW можно говорить как о наиболее
>удачном решении по соотношению между производительностью и эффективностью
>применительно к текстовой информации.
>
    Ха! У меня все ходы записаны ;-). Я экспериментировал на 94 МБ русских
текстов, макс. размер файла 3.5МБ, результаты даны в тыс. байт:
   IMP     186.0 29026  66.0    PPMN-5     440.1 26965
    BA     331.2 27742 198.9    PPMN-6     595.3 27118
 PKZIP     146.1 39196  45.2
RKUC-8    1056.0 27118
RKUC-5     685.5 27225
RKUC-8x   1351.9 26102
RKUC-12x  1472.2 26086
        B             C             D           b     i E
1  110.9 44601    99.5 44573   115.6 44573   101.9 100.5 44343
2  107.4 36578    97.0 36544    95.2 36483    89.3  87.0 36392
3  118.4 30397   107.7 30358   103.0 30297    96.6  95.2 30130
4  164.0 28014   149.0 27924   136.9 27787   132.0 127.1 27445
5  224.4 27734   203.7 27524   181.5 27230   177.8 171.2 26740
6  282.7 28020   253.7 27716   221.6 27219   218.7 208.9 26633
7  340.5 28359   300.7 27995   257.6 27296   256.6 241.4 26662
    Или ты пытался сравнить их при одинаковых объемах памяти? Все равно на
текстах ППМ выиграет, при -o4.

>>     LZ это тоже неявное контекстное моделирование.
>
>А вот тут я позволю себе с тобой не согласиться. Существует принципиальное
>различие между контекстно-зависимым и ссылочным кодированием. Ссылочное
>плюет на предысторию.
>
    В смысле на дальнюю предысторию? Hа какую-то предысторию адаптивный
метод должен опираться. LZ77  в первоначальной формулировке эквивлентен ППМ
который сбрасывает статистику после каждой повторяющейся строки.
    Пример - CA.FDB из VYTEST, файл достаточно точно соответствует модели
ЛЗ77 и все ППМы тут в пролете(а PPMD в особенно глубоком:)), но попробуй
"ppmd e -m1 -o12 ca.fdb", ППМ начинает грубо эмулировать ЛЗ77.

>(1) Выродиться он не сможет из-за MTF. Если без MTF, то почти выродится.
>Почти, так как будут потеряны локальные особенности. Кстати, я правильно
>понимаю, что ты имеешь в виду модель нулевого порядка? (В одной умной
работе
    Ага, начинаю понимать, M2F уплощает ф-цию распределения, но это значит
что BW даже асимптотически не сходится(ППМ, ЛЗ обладают таким свойством).
    Это как-то совсем невесело, я разачарован...

>(В одной умной работе
>про BWT было написано примерно так: "энтропия представления, получаемого в
>результате преобразования BWT, равна энтропии преобразуемой информации"
>:) ).
>
    По моему правильно, для order-0 энтропии, как и для любой перестановки.

>(2) Межсимвольная корреляция это конечно круто, но если смотреть глубже, то
>можно вспомнить о существовании двух типов источников: комбинаторных и
>вероятностных. PPM и CTW считают, что информация порождается вероятностным
>источником. Примерно также считает и BW. LZ считает, что информация
>порождается комбинаторным источником. ACB тоже так считает, но
"подозревает"
>о подвохе :) PPMZ из них самый хитрый: он умеет приспосабливаться к
>особенностям информации, порожденной источниками обоих типов. Поэтому PPMZ
>всегда выигрывает.
>
    PPMZ не является отдельной схемой, это просто PPM*+LOE+SEE.
>и он станет совершенно другим контекстом. Я бы предложил сначала пройтись
>дельтой, а затем, как говорится, все взять и поделить (на константу).
>Глядишь, и шум пропадет.  Можно попробовать.
    Опять ты меня на специализированный кодек тянешь:), и шума там нет, и
дельта не проходит...
VY>Черт его знает. Если там номера палитр, то дельта вряд ли поможет.
VY>Если палитры предварительно упорядочить, то что-то путное может
VY>и получится. А иначе - лучше адаптивный кодер использовать, по
VY>типу того, ято в szip'e. Может, только rle-кодирование подработать.
    ... и палитра особо много информации не дает - точки слишком редко
расположены в цветовом пр-ве.

    ЗЫ А как это вы инициалы в цитирование вставляете, неужто вручную?
    ЗЗЫ А асимптотическая неоптимальность BW - это конечно удар наповал,
предупреждать надо! :)


--- ifmail v.2.14dev3
 * Origin: home (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     08 Dec 99 17:42:44
 To   : Vladimir Semenjuk                   
 Subj : Re: BWT                                                                      


From: "Vadim Yoockin" <vy@thermosyn.com>

Hello, Vladimir Semenjuk ! You wrote:

>> -i N - насильно фиксирует инкремент в первом уровне
>>    двухуровневой модели MTF Фенвика. С этим параметром
>>   можно поиграться и достичь немного лучшего сжатия.
>
>Hе понял. Верхнюю границу что ли? Когда масштабирование счетчиков
делается?

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

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

>>>А вот тут я позволю себе с тобой не согласиться. Существует
принципиальное
>>>различие между контекстно-зависимым и ссылочным кодированием.
>>> Ссылочное плюет на предысторию.
>> Hу, почти :) А еще есть семейство LZ+PPM или LZ+Ari...
>
>В LZ+PPM я большого смысла не вижу. Если длина минимального
совпадения равна
>3, то в лучшем случае можно пробовать 1-0 кодер Блюма (после
прохода LZ
>остаются разорванные марковские сегменты порядка, не превышающего в
среднем
>1). Hо, по моему мнению, хватает и нулевой модели. Вот в LZP4 PPM
>действительно необходим.

Hа некоторых данных они выступают лучше ppm'ов в номинации
"лучшее сжатие любой ценой"...
Честно говоря, я не являюсь приверженцем LZ+PPM, может
Игорь Павлов выступит в защиту своего ряда архиваторов? :)

>Вообще, ребята, пора менять терминологию. Hу скажите мне, чем
отличается
>LZ+PPM от LZ+Ari? Арифметическое кодирование - это способ
построения кодов
>переменной длины. Он может использоваться с любой моделью и в любых
>условиях. Это просто инструмент. PPM - метод оценки символа в
контексте, где
>чаще всего предлагается использовать для переведения вероятности в
длину
>кода то же арифметическое кодирование. Я конечно понимаю, что,
говоря
>LZ+Ari/Huf, обычно имеют в виду модель нулевого порядка, но как-то
это не
>очень грамотно.

Я до сих пор колеблюсь, когда пытаюсь классифицировать компрессоры
в рамках тестов... И хочется указать алгоритмы, вышедшие из LZARI
Окумуры, и порядку отдать должное... В общем, я готов принять любой
термин :)

>> Между прочим, модель нулевого порядка - это уже не модно :)
>> Частенько используется первый или даже второй.
>
>Согласен. Штарьков, Балкенхоль и Куртц в недавней работе предложили
>использовать для сжатия S-представления модель 3-го порядка. Самое
смешное -
>BA их BKS98 заделывает почти на всех тестах :)

Балкенхол грозится вскоре выпустить новую версию, в которой
отказался от mtf. Правда, объявленные рузультаты на book1
все равно уступают ba, который этот mtf использует (и ybs тоже) :)

>Кстати, ты что-нибудь подобное пробовал?

Да, конечно. Хотя, подозреваю, не уделил этому много внимания :)
Прежде всего не понравилась скорость. Да и использование
предыстории у меня и так есть, как и во многих приличножмущих
bwt-компрессорах.

Всего доброго,
Вадим.


--- ifmail v.2.14dev3
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     08 Dec 99 18:00:10
 To   : Dmitry Shkarin                      
 Subj : Re: BWT                                                                      


From: "Vadim Yoockin" <vy@thermosyn.com>

Hello, Dmitry Shkarin ! You wrote:

>>вспомнить про скорость распаковки, то о BW можно говорить как о
наиболее
>>удачном решении по соотношению между производительностью и
эффективностью
>>применительно к текстовой информации.
>>
>    Ха! У меня все ходы записаны ;-). Я экспериментировал на 94 МБ
русских
>текстов, макс. размер файла 3.5МБ, результаты даны в тыс. байт:
>   IMP     186.0 29026  66.0    PPMN-5     440.1 26965
>    BA     331.2 27742 198.9    PPMN-6     595.3 27118

Дима, на самом деле в ba сортировка довольно сырая
и чувствительная к длинным контекстам, о чем сам автор
честно предупреждал. Так что, даже не знаю, с чем
сравнивать. В ybs сортировка пока единственное, что
как следует обкатано (отчего он раза в полтора быстрее ba),
но доделать остальное пока руки не доходят. В imp'e сортировка
быстрая, но глухо виснет на длинных контекстах...

>  Или ты пытался сравнить их при одинаковых объемах памяти? Все
равно на
>текстах ППМ выиграет, при -o4.

Я тебе всегда говорил, что ppmd написан классно :)
Кстати, а какой размер блока? Дефолтный? Это мало...
Hадо на весь файл.

>    Пример - CA.FDB из VYTEST, файл достаточно точно соответствует
модели
>ЛЗ77 и все ППМы тут в пролете(а PPMD в особенно глубоком:)), но
попробуй
>"ppmd e -m1 -o12 ca.fdb", ППМ начинает грубо эмулировать ЛЗ77.

О, надо попробовать. Hо я таки внесу искажения в файл,
дабы компрессоры не привыкали к константам ;)

>    Ага, начинаю понимать, M2F уплощает ф-цию распределения, но это
значит
>что BW даже асимптотически не сходится(ППМ, ЛЗ обладают таким
свойством).
>    Это как-то совсем невесело, я разачарован...

Где-то в i-net'e я видел доказательство...
Сейчас пишу в спешке, потом, если надо, могу поискать.

>VY>Черт его знает. Если там номера палитр, то дельта вряд ли
поможет.
>VY>Если палитры предварительно упорядочить, то что-то путное может
>VY>и получится. А иначе - лучше адаптивный кодер использовать, по
>VY>типу того, ято в szip'e. Может, только rle-кодирование
подработать.
>    ... и палитра особо много информации не дает - точки слишком
редко
>расположены в цветовом пр-ве.

Ага, я увидел. Hо адаптивный-то кодер оказался лучше :)

>    ЗЫ А как это вы инициалы в цитирование вставляете, неужто
вручную?

У меня они вставляются только из под фидошного голдеда...

>    ЗЗЫ А асимптотическая неоптимальность BW - это конечно удар
наповал,
>предупреждать надо! :)


Hу, это зря. Какая-то оптимальность там, безусловно, есть :)

Всего доброго,
Вадим.



--- ifmail v.2.14dev3
 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)


 RU.COMPRESS 
 From : Denis Smirnov                        2:5020/1785.1  08 Dec 99 18:17:04
 To   : Boris Batkin                        
 Subj : Несколько вопросов                                                           


---- OS/2      Привет Boris!

Ответ на письмо от Boris Batkin к Denis Smirnov:

 BB>  попpобуй так. кстати, хотя поиск сильно упpощается, на опpеделенных данны
х
 BB>  это может быть даже медленнее, т.е я не тестиpовал, но пpедполагаю что
 BB>  куча 0 будет так сжиматься медленнее.

    Hа выходе BWT работает медленнее моего процентов на 10. Твой алгоритм оказы
вается неэффективным в случае любых длинных повторяющихся последовательностей :
-(

С уважением, Denis!
--- mailto:mithraen@mtu-net.ru ICQ: 45911752
 * Origin: Windows NT: Vapourware of the desperate and scared. (2:5020/1785.1)


 RU.COMPRESS 
 From : Denis Smirnov                        2:5020/1785.1  08 Dec 99 18:28:52
 To   : Boris Batkin                        
 Subj : Несколько вопросов                                                           


---- OS/2      Привет Boris!

Ответ на письмо от Boris Batkin к Denis Smirnov:

 BB>   int index [256], parent[256];
       ^^^
    Однако я тормоз. Забыл простейшие правила оптимизации. Проверив твой предыд
ущий исходник получил 10% замедление по отношению к своему алгоритму. Заменив в
 индексах char на int, как в этом твоем исходники получил 20% прирост скорости 
по отношению к моему. Рулез.

С уважением, Denis!
--- mailto:mithraen@mtu-net.ru ICQ: 45911752
 * Origin: Aurora install: Are you ready for e-business? (2:5020/1785.1)


 RU.COMPRESS 
 From : Alex Lisenko                         2:465/4.8      08 Dec 99 18:51:27
 To   : Vladimir Semenjuk                   
 Subj : Дайте информацию                                                             


          Здравствуй Vladimir!

 Суббота декабрь 04 1999, а Vladimir Semenjuk пишет All вот что:

 VS> А про словарные алгоритмы ты слышал?  Про LZ77, LZSS, LZW, например?

        У меня нет док по LZ77 LZSS, третий есть. Если не лень кинь на мыло.

 VS> Их значительно проще понять чем DMC и CTW. (Binary LZ - вообще
 VS> ерунда.)

        Hо у DMC, как я понял степень сжатия выше. Или не так?

 VS> Пример:

 VS> последовательность: "abcbabcaabdea"
 VS> сортируем по убыванию частоты: a(5), b(4), c(2), d(1), e(1)
 VS> 1 шаг: d + е -> u1.
 VS> результат: a(5), b(4), c(2), u1(2=1+1)
 VS> 2 шаг: c + u1 -> u2.
 VS> результат: a(5), b(4), u2(4=2+2)
 VS> 3 шаг: b + u2 -> u3.
 VS> результат: u3(6=4+4), a(5)
 VS> 4 шаг: u3+a -> u4.
 VS> результат: u4(11=6+5)

 VS> дерево Хаффмана:

 VS>           u4
 VS>         /      \
 VS>      u3       a
 VS>    /     \
 VS>  b       u2
 VS>          /   \
 VS>        c     u1
 VS>             /    \
 VS>           d      e

 VS> сопоставим  /-"0", \ -"1"
 VS> получаем префиксные коды:
 VS> a - {1}
 VS> b - {00}
 VS> c - {010}
 VS> d - {0110}
 VS> e - {0111}

 VS> Если ты правильно поймешь этот алгоритм, то проблем не возникнет. (Тут им
 VS> просто негде возникнуть.)

        У меня все равно по другому получается дерево.
        Всего хорошего,
              Alex Lisenko.

---
 * Origin: Origin sugarfree! (2:465/4.8)


 RU.COMPRESS 
 From : Denis Smirnov                        2:5020/1785.1  08 Dec 99 19:07:28
 To   : Boris Batkin                        
 Subj : и еще в догонку                                                              


---- OS/2      Привет Boris!

Ответ на письмо от Boris Batkin к Denis Smirnov:

 BB> To mod: sorry. но уж очень интеpесно получается!
 BB> без пpогpаммы со списками куда как менее понятна ;-))))) и еще в 2 p.
 BB> быстpее. у меня по скоpости компpессоp~=декомпpессоp~=1.2 m/sec.

    А если теперь еще и заточить его под двухуровневую модель?

С уважением, Denis!
--- mailto:mithraen@mtu-net.ru ICQ: 45911752
 * Origin: I went window shopping...and bought OS/2! (2:5020/1785.1)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     08 Dec 99 19:42:20
 To   : All                                 
 Subj : Re: BWT                                                                      


From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>

                         Hi, Вадим!
>
>Дима, на самом деле в ba сортировка довольно сырая
>и чувствительная к длинным контекстам, о чем сам автор
>честно предупреждал. Так что, даже не знаю, с чем
>сравнивать. В ybs сортировка пока единственное, что
>как следует обкатано (отчего он раза в полтора быстрее ba),
>но доделать остальное пока руки не доходят. В imp'e сортировка
>быстрая, но глухо виснет на длинных контекстах...
>
    Да, но при распаковке-то сортировка не участвует, у него получается, что
вторичное моделирование занимает больше времени чем сортировка.
    К Максиму Смирнову: если PPMN - non-public, то небось и его результаты
нельзя публиковать? Извиняюсь, это я не подумавши ляпнул...
>
>Я тебе всегда говорил, что ppmd написан классно :)
>Кстати, а какой размер блока? Дефолтный? Это мало...
>Hадо на весь файл.
>
    У всех все ставилось по максимуму, те размер блока BA - 5 МБ, у
PPMD - -m32, при -o7 он-бы и еще сжал, но начинает сбрасываться статистика
на больших файлах.
>>    Ага, начинаю понимать, M2F уплощает ф-цию распределения, но это
>значит
>>что BW даже асимптотически не сходится(ППМ, ЛЗ обладают таким
>свойством).
>>    Это как-то совсем невесело, я разачарован...
>
>Где-то в i-net'e я видел доказательство...
>Сейчас пишу в спешке, потом, если надо, могу поискать.
    Доказательство оптимальности или неоптимальности? Если неоптимальности,
то достаточно привести пример: order-0 источник с неравномерным
распределением, если оптимальности, то оно опровергается примером.


--- ifmail v.2.14dev3
 * Origin: home (2:5020/400)
 Предыдущий блок Следующий блок Вернуться в индекс