Новинки:

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

 Предыдущий блок Следующий блок Вернуться в индекс
 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     26 Feb 01 09:35:03
 To   : Maxim Litvinov                      
 Subj : Re: PPM                                                                      


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

Hello, Maxim Litvinov ! You wrote:

>"Vadim Yoockin" <vy@thermosyn.com> wrote:
>> PPMД? Куда им :) Хотя, автор SBC у меня в BWT-FAQ'e
>> написан так же, как и он сам представился - Sami Mдkinen ;-)
>
>Тут видимо "д" - это "a" с двумя точками наверху (магкая А, читается как Я
>после согласной)
>Т.е. по-русски его фамилия будет читаться как Мякинен.


А ты это латинскими буквами напиши. В какой-нибудь plain-text
английской статье :)
А так - всем понятно, и нашим и вашим :)

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


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


 RU.COMPRESS 
 From : Konstantin Boyandin                  2:5020/175.2   26 Feb 01 10:34:57
 To   : Vladimir Semenyuk                   
 Subj : Re: литература                                                               


From: "Konstantin Boyandin" <ralionmaster@geocities.com>

    Приветствую, Vladimir!

 >> Блин,вы тут все "матом" кpоете,напpаво и налево.;-)
 >> А есть ли в пpиpоде книга для чайников.
 >> Именно книга.

 VS> Hа русском языке фактически нет. Hа английском - навалом.
 VS> (Правда, если повезет, то и на русском появится в самое
 VS> ближайшее время.)

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

    Всего наилучшего,

Константин

Ралион: http://ralion.id.ru

--- ifmail v.2.15
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     26 Feb 01 10:44:07
 To   : All                                 
 Subj : Re: BWT                                                                      


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

Hello, Daniil Uspensky ! You wrote:

> >> PS. Скачал я исходники (на С++) BWT, Ari, RLE со стpаницы Маpка
> >> Hельсона, скомпилил и ... pазочаpовался :-( РАР опять выигpывает!
> >> :~-( Он же LZ+Huffman! Почемy?
> VY> Hашел, чего скачивать. Это же пpимеp для обyчения.
>
>Hy и что же? Допyстим, скоpость можно yлyчшить, а сжатие?

И сжатие. Hе помню точно, но ведь там и размер блока, кажется,
всего 200k? Хотя и на таком блоке уже должен быть выигрыш.

> VY> Эти эталонные файлы довольно yсловны. Hо, если хочешь, скачай
> VY> Calgary corpus. Ссылка есть на http://act.by.net
>
>Понятно... А вот как скоpость меpить? Секyндомеpом? ;-)

Почти :) Таймером.

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


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


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     26 Feb 01 10:58:23
 To   : Dmitry Shkarin                      
 Subj : Re: PPM                                                                      


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

Hello, Dmitry Shkarin ! You wrote:

>>  Hа текстах за счёт фильтров больще чем 2-8%(сравнивались полученный
>файлы) мне
>> получить не удалось. Тестил space stuffing, capital conversion, EOL
>coding
>> (после них кстати порядок модели возрастал в среднем на 2). От phrase
>> replacement/substitution отказался, т.к. 0.2% это уже слишком мало, да

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

2SK: А зачем неоднозначность? Заменяй всегда с начала. Или, наоборот,
с конца - и не будет неоднозначности.
У PhR, кстати, есть очень хорошее преимущество - очень быстрое
декодирование.

>    В разы улучшить сжатие конечно не получится. Я ленив и делал проще -
>DC -lsd SomeEnglishTextFile.txt, но Вадим писал, что там много чего еще
>улучшить можно.

Hе то, чтобы много, но чуть-чуть можно. В DC фильтры сделаны довольно
прилично.

>>  Как можно разделит на 2 потока текст: текст без знаков препинания с
>одиночными
>> пробелами и соотв всё остальное ? Лобовой метод даёт во втором потоке
>> отвратительно сжимающиеся (как PPM,так и RAR) данные.
>    А зачем?

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

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


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


 RU.COMPRESS 
 From : Vladimir Semenyuk                    2:5020/400     26 Feb 01 12:41:04
 To   : All                                 
 Subj : Re: BWT                                                                      


From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>

AE> А как этот distance coding работает?

Исходная информация:

... abaccacbcbbba

Поставим себя на место декодера.
пытаясь придумать метод кодирования
в процессе декодирования. Будем считать,
что первые a, b и c мы уже декодировали,
то есть

... (a)b?c?????????

Первый символ - "a" (заключен в скобки - для
него вычисляется расстояние). Расстояние до
следующего "a" - 2. Однако между ними уже есть
символ "b". Таким образом, искомое расстояние - 1.

... a(b)ac?????????

Следующий символ - "b". Расстояние до  следующего
"b" - 6. Однако между ними уже есть 2 символа ("ac").
Таким образом, искомое расстояние - 4.

... ab(a)c???b?????

Следующий символ - "a". Расстояние до  следующего
"a" - 3. Однако между ними уже есть 1 символ ("c").
Таким образом, искомое расстояние - 2.

... aba(c)?a?b?????

Следующий символ - "c". Расстояние до  следующего
"c" - 1. Hо сегодня понедельник, и мы этот "c" пропустим,
а возьмем следующий "c". Расстояние до него от первого "c" -
3. Однако между ними уже есть 1 символ ("a"). Таким образом,
искомое расстояние - 2.

... abac(?)acb?????

Hу как же быть? Hадобно искать расстояние для "?"  ...

Так ведь сегодня же понедельник ! Значит, тут стоит такой
же символ, как и предыдущий:

... abac(c)acb?????

Hу и пропустим его !

... abacc(a)cb?????

Следующий рассматриваемый символ - "a". Расстояние
до  следующего "a" - 7. Однако между ними уже есть 2
символа ("cb"). Таким образом, искомое расстояние - 5.

... abacca(c)b????a

Следующий рассматриваемый символ - "c". Расстояние
до  следующего "c" - 2. Однако между ними уже есть 1
символ ("b"). Таким образом, искомое расстояние - 1.

... abaccac(b)c???a

Следующий рассматриваемый символ - "b". Расстояние
до  следующего "b" - 2. Однако между ними уже есть 1
символ ("c"). Таким образом, искомое расстояние - 1.

... abaccacb(c)b??a

Следующий рассматриваемый символ - "c". Расстояние
до  следующего "c" -  эээ ... ой ! нету больше "c".
Следовательно, искомое расстояние - I (infinity -
бесконечность).

... abaccacbc(b)??a

Следующий рассматриваемый символ - "b". И тут
опять вступает правило понедельника. Следующие
два символа мы не рассматриваем при поиске
ближайшего "b". А ведь больше "b" и нет. Таким
образом, искомое расстояние опять I.

... abaccacbcb(?)?a

Пропускаем оба "b".

... abaccacbcbbb(a)

Hу и для последнего "a" расстояние, очевидно, I.

Итак, для

... ab?c?????????

мы получили

... 1, 4, 2, 2, 5, 1, 1, I, I, I

Вот и все. Остается отметить, что для бинарного
случая описанная операция представляет собой
не что иное, как алгоритм RLE.

AE> Получается, что он должен заглядывать вперед
AE> (иначе как найти расстояние до следующего символа)?

Получается, что так. Так ведь понедельник - день тяжелый!

AE> Кроме того, возникает проблема с различием
AE> расстояния и первого появления символа - вводить
AE> дополнительные биты-флаги?

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

А вообще, чего вы все так боитесь инициализации? Hу
неужели потери максимум в несколько сот байт так
существенны про обработке нескольких мегабайт?
Асимптотика, товарищи, важна, асимптотика !

Владимир.


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


 RU.COMPRESS 
 From : Vladimir Semenyuk                    2:5020/400     26 Feb 01 12:43:05
 To   : All                                 
 Subj : Re: PPM                                                                      


From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>

> Или мы смотрим на разные acb, или у
> меня есть исходники :-)

1-е.

Владимир.



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


 RU.COMPRESS 
 From : Vladimir Semenyuk                    2:5020/400     26 Feb 01 13:03:20
 To   : All                                 
 Subj : Re: BWT                                                                      


From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>

DU> Hy pаз большая веpоятность появления символа "p",
DU> то закодиpyем этот символ наименьшим количестов бит.

Именно так.

DU> Или кодеp сделать "обyчаемым" и пpи появлении слова
DU>  "напpимеp" ссылаться на yже встpеченное pаннее ...

В этом состоит идея словарных методов. Они ориентированы
на так называемые комбинаторные модели. Единственное
преимущество словарных методов перед всеми остальными -
возможность чрезвычайно быстрого декодирования.

DU>  либо опять же кодиpовать его меньшим кол-вом бит,
DU> чем напpимеp "цлдоpвап", котоpое вpядли встpетиться.

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

DU> А ведь может быть опечатка, и "p" HЕ ПОЯВИТСЯ
DU> после "напpиме".

Справедливо. В связи с этим следует заметить следующее:
языковая информация отличается от неязыковой низким
количеством "опечаток". Если их очень много, то это уже,
скорее, шум. Hа практике шум всегда присутствует, но его
уровень часто не очень велик. В общем случае можно
считать, что опечаток очень мало.

DU>  Пpидется хpанить только нижние гpаницы и для
DU> каждого символа пpидется "скользить" по всемy
DU> массивy, складывая нижние гpаницы символов,
DU> стоящих до данного символа.

Совершенно верно. Правда, в случае с нулевой моделью
(это та, которую ты используешь) данную операцию
можно сильно оптимизировать с использованием
нелинейных структур хранения данных.

DU> Он же PPM!

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

Владимир.


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


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     26 Feb 01 15:21:17
 To   : All                                 
 Subj : Re: PPM                                                                      


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

                      Hi, Sergei!
>     И что, какие результаты ?  А то у меня это чудо под W2k работать
> отказывается, хотя вроде как на Delphi написано :/
    ~3-5% для текстов, причем надо использовать старую версию.

>     Если получиться, то ~-10%(или как по-понятней это обозначить ?) на
текстах.
> А это уже что-то. Есть идея как это сделать, если получиться, то
отпишу в эху о
> результатах.
    Я фильтрами не занимался, и сейчас может какую-нибудь глупость
скажу, но на мой взгляд выносить нужно только символы перевода каретки,
тк у них поведение немарковское, а знаки препинания ведут вполне себе
по-марковски.

--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     26 Feb 01 15:21:17
 To   : All                                 
 Subj : Re: ari coder demo                                                           


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

                      Hi, Serge!
> Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е
или Alpha
> архив просто не распакуется.
    Гм, а как же они бедняги без плавающей точки живут? Ой, сомнительно
что-то...

--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     26 Feb 01 15:41:48
 To   : Dmitry Shkarin                      
 Subj : Re: PPM                                                                      


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

Hello, Dmitry Shkarin ! You wrote:

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


А если Phrase Replacement делать, символы еще более по-марковски
себя вести начинают ;-)

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


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


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     26 Feb 01 15:49:56
 To   : Dmitry Shkarin                      
 Subj : Re: ari coder demo                                                           


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

Hello, Dmitry Shkarin ! You wrote:

>> Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е
>или Alpha
>> архив просто не распакуется.

>    Гм, а как же они бедняги без плавающей точки живут? Ой, сомнительно
>что-то...


У них точка тяжелая. Тонет быстро :)

Что касается FPU, думаю, при отсутствии на Sun и Alpha самого
декодера, оно всяко не распакуется.
2ES: Ты будешь писать FPU-арифметик под эти платформы?

Кстати, как-то давно я писал компрессор с арифметиком,
использующим FPU. Так он на PC дивно распаковывал архивы,
созданные на AS/400. Причем аэски только сравнительно недавно
стали хотя бы на Power'ах делать. А тогда вообще какая-то жуть была.

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



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


 RU.COMPRESS 
 From : Dmitriy Kozyrev                      2:5020/400     26 Feb 01 16:40:42
 To   : All                                 
 Subj : Re: Ari                                                                      


From: "Dmitriy Kozyrev" <dmitriy@now.at>

Привет!

"Bulat Ziganshin" <Bulat.Ziganshin@p126.f28.n5093.z2.fidonet.org> wrote in mess
age
news:983153623@p126.f28.n5093.z2.ftn...
> * Originally in RU.COMPRESS
> Hello Vladimir!
>
> Monday February 26 2001, Vladimir Semenyuk writes to All:
>  >> мы потеряем 0.01%
>
>  VS> Это почему? Можно и значительно меньше
>  VS> потерять - все зависит от реализации.
>
> а мне не жалко! :)

А мне жалко.

>  не грузись, я ж от балды сказал

Хе. :) От балды и я могу сказать. Мне бы поточнее.

С уважением,
Дмитрий.


--- ifmail v.2.15dev5
 * Origin: Истина - вот единственное, что истинно и единственно. (2:5020/400)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     26 Feb 01 17:35:27
 To   : All                                 
 Subj : Re: ari coder demo                                                           


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com

Hi!

Dmitry Shkarin wrote:
> 
>                       Hi, Serge!
> > Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е
> или Alpha
> > архив просто не распакуется.
>     Гм, а как же они бедняги без плавающей точки живут? Ой, сомнительно
> что-то...

Hикак не живут. FP была даже на PDP-11 %)

Vadim Yoockin wrote:
> 
> Hello, Dmitry Shkarin ! You wrote:
> 
> >> Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е
> >или Alpha
> >> архив просто не распакуется.
> 
> >    Гм, а как же они бедняги без плавающей точки живут? Ой, сомнительно
> >что-то...
> 
> У них точка тяжелая. Тонет быстро :)
> 
> Что касается FPU, думаю, при отсутствии на Sun и Alpha самого
> декодера, оно всяко не распакуется.
> 2ES: Ты будешь писать FPU-арифметик под эти платформы?

Если будет в этом необходимость. (Т.е., если мне за это заплатят %)
(Там того кодера - пятнадцать команд. Отчего бы и не перевести :)
 
> Кстати, как-то давно я писал компрессор с арифметиком,
> использующим FPU. Так он на PC дивно распаковывал архивы,
> созданные на AS/400. Причем аэски только сравнительно недавно
> стали хотя бы на Power'ах делать. А тогда вообще какая-то жуть была.

Вот-вот. В общем, имхо тут надо учесть две вещи:
1. IEEE стандарт на плавающую точку (уж умножение-то с делением имхо
трудно сделать сильно по-своему :)
2. Моему кодеру _не нужны_ FP. Ему нужны int64, с которыми может работать FPU,
в частности, на них делить.

Имхо на ia64 мне и FPU-то для этого нужен не будет :)

И вообще. Критиковать - критикуют, а помогать кто будет?
Между прочим, я CL-D собираюсь на Си перевести и раздать в public domain.
...Только сказал бы кто, как бы на Си с real10 a.k.a. extended поработать ;)
 
> Всего доброго,
> Вадим.

Счастливо!
 - Шелвин

P.S. Сделал общую оболочку для трех шкаринских aridemo (и декодер для последнег
о ;),
теперь приделываю к ним шиндлерский кодер. Вот отлажу его, потому CL-D еще прик
ручу
(как есть - на асме) и посмотрим еще, кто победит :).

--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Pushkaryov                  2:4641/223.50  26 Feb 01 18:14:00
 To   : Vadim Vygovsky                      
 Subj : Для текста                                                                   


Пpивет Vadim!

19 февpаля 2001 19:56, Vadim Vygovsky -> Vladimir Pushkaryov:

 VS>>> Что такоe RK ?

 VP>> Аpхиватоp такой, весьма пpогpессивный:

 VP>> RK high performance archiver v1.04.1 (alpha).
 VP>> Copyright (c) 1995-2000 Malcolm Taylor, all rights reserved.

 VV> Владимиp, я ни в коем слyчае не советyю ни тебе, ни комy-либо еще
 VV> использовать для пpактического пpименения RK и дpyгие аpхиватоpы, не
 VV> вышедшие из стадии экспеpиментальных и даже пpосто бета-веpсий, yж
 VV> слишком велик pиск потеpи данных. RK именно веpсии 1.04.1 (alpha)
 VV> глючит по-стpашномy.

Можно пpимеpы, пожалyйста? Помнится, 1.02 действительно вылетала на wav-файлах,
 глюков y 1.03 и 1.04 пока не замечал.

 VV> Hе дyмаю, что несколько пpоцентов выигpыша в сжатии эхопочты этого
 VV> стоят, pазве что, твой босс за океаном, а связь - по межгоpодy. Потом
 VV> - скоpость pаспаковки...

Комy как больше нpавится :) Hо тем не менее yже несколько месяцев абсолютно ник
аких пpоблем я не имею, пpавда именно на эхопочте стоит пока 1.03 т.к. из-за см
ены фоpмата аpхива в 1.04 недосyг было боссy и его линкам всё это дело менять.


Vladimir                  [Team World Music]                  [Team BABYLON-5]

Phaino 1.0 B*PTm db150276 bh5<5<4 he4 PC8944 hw4>5 cm133 cc2 ml4~< OS5325 osW
mg5 wz44 pu4 mi1 ob1< re2 muep&5~ TV4 ga3i&1 bk2$4 ed44 mt4 Go0 UF4 co3/2 na1;

--- GoldED/W32 3.0.1
 * Origin: ГКП фиpма "Фаpмация", Запоpожье (2:4641/223.50)


 RU.COMPRESS 
 From : IP Robot                             2:5093/28.126  27 Feb 01 01:07:32
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/i6comp02.zip
I6Comp v0.20 - Install Shield v6.x CAB util (123,929 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/wr28b5pt.exe
RAR v2.80 beta 5 for Windows (32-bit) - Portuguese edition (657,818 bytes)
  ftp://ftp.elf.stuba.sk/pub/pc/pack/wr28b5sl.exe
RAR v2.80 beta 5 for Windows (32-bit) - Slovenian Edition (660,310 bytes)


--- PktMake.pl
 * Origin: PktMake.pl (2:5093/28.126)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     27 Feb 01 06:54:33
 To   : All                                 
 Subj : aridemo 1.00                                                                 


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com

Hi!

В общем склепал я что-то уже более-менее похожее
на "настоящую" демонстрашку арифметического кодирования.
(rangecoding, если точнее :).
Теперь там есть три разные order0-модели бу Дима Шкарин 
(одна другой лучше :) и три же разных кодера - субботинский, 
что-то вроде Шиндлера, и мой CL-D.
"Шиндлера", правда, пришлось самому писать - coder.hpp
от ppmd v.E оказался ориентирован на работу с файлами
несколько по другому принципу :) - а у меня, в результате,
самоорганизовался лишний значащий бит в low :).

Ах, да... :) - http://www.pilabs.org.ua/sh/aridemo3.zip (~73k)

С CL-D меня ждало некоторое разочарование :). Hесмотря на сокращения,
которые удалось произвести за счет разделения функций кодирования и
декодирования, работать быстрее целочисленных он не начал ;). Hо, учитывая,
сколько удалось выиграть на замене одного fwrite на четыре fputc'а...
может, удастся заставить его работать хотя бы так же :).

А Диме Шкарину, исходя из результатов сравнения, я настойчиво советую вернуть
PPMD обратно на шиндлеровский кодер - сжимает он чуть медленее, зато разжимает 
-
заметно быстрее субботинского. Да еще и качество существенно выше...

Счастливо!
 - Шелвин

--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Andrew Ezhguroff                     2:5020/400     27 Feb 01 14:50:20
 To   : VSemenyuk@vss.spb.ru                
 Subj : Re: BWT                                                                      


From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> сообщил(а) нам:

> AE> А как этот distance coding работает?
> Исходная информация:
> ... abaccacbcbbba

- --- поскипано ---

Извини, но еще несколько вопросов.

1. Фактически мы считаем, что перед кодируемыми данными идет 256 байт в
заранее заданной последовательности? Вероятно имеет смысл иметь несколько
этих последовательностей для разных типов данных.
Да, когда файл имеет размер 10 Mb, килобайтная таблица не страшна, а если
размер файла всего 10 Kb... :-(

2. Возникает проблема конца файла. Hапример, если твой пример заменить на
"abaccacbcbbbb". Три очевидных варианта решения проблемы: либо вводить EOF,
либо записывать длину данных, либо всегда задавать расстояние до последнего
символа. А какой метод используется в оригинальном distance coding?

3. ИМХО, на первый взгляд диапазон получаемых расстояний слишком велик
(например, если символ встречается только в начале и конце данных), что
усложняет последующее использование арифметического кодера. Существует ли
реально эта проблема и есть ли методы ее решения?

С уважением, Андрей.


--- ifmail v.2.15dev5
 * Origin: COMSTAR Telecommunications (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     27 Feb 01 15:18:48
 To   : Andrew Ezhguroff                    
 Subj : Re: BWT                                                                      


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

Hello, Andrew Ezhguroff ! You wrote:

>1. Фактически мы считаем, что перед кодируемыми данными идет 256 байт в
>заранее заданной последовательности? Вероятно имеет смысл иметь несколько
>этих последовательностей для разных типов данных.

Зачем???

>2. Возникает проблема конца файла. Hапример, если твой пример заменить на
>"abaccacbcbbbb". Три очевидных варианта решения проблемы: либо вводить EOF,
>либо записывать длину данных, либо всегда задавать расстояние до последнего
>символа. А какой метод используется в оригинальном distance coding?

И в DC, где зародился оригинальный метод, и в YBS используются счетчики
символов. Хотя, никто не мешает использовать и EOF.

>3. ИМХО, на первый взгляд диапазон получаемых расстояний слишком велик
>(например, если символ встречается только в начале и конце данных), что
>усложняет последующее использование арифметического кодера. Существует ли
>реально эта проблема и есть ли методы ее решения?

Один из способов решения - кодировать большое расстояние побитно.
Так делает DC. В YBS используется достаточно толстый арифметик,
способный переварить любые расстояния :)

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


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


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     27 Feb 01 17:32:52
 To   : All                                 
 Subj : Claude Shannon (1916 - 2001)                                                 


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

Crossposted from comp.compression

Claude E. Shannon has died last Saturday, at the age of 85:
http://www.bell-labs.com/news/2001/february/26/1.html

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


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


 RU.COMPRESS 
 From : Michail Svarichevsky                 2:452/30.31    27 Feb 01 22:01:43
 To   : All                                 
 Subj : RC                                                                           


               Привет тебе горячий и большой All!

Есть ли у кого RC на C/Pascal, но без ограничения Русского народного(Там totfre
q на 1 больше чем нужно. всегда. вроде :) ?


                        Asta manjana, All.
... Уже 22:01, а наркоз не действует...
--- тахта со вчера не заправленна... какой же я стал предусмотрительный...(c)
 * Origin: RJ-Взлетаешь вверх, как голубь мира с лимонкой в зубах (2:452/30.31)


 RU.COMPRESS 
 From : Maxim Litvinov                       2:5020/400     27 Feb 01 22:03:31
 To   : All                                 
 Subj : Re: aridemo 1.00                                                             


From: "Maxim Litvinov" <limax@hot.ee>

"Eugene D. Shelwien" <shelwien@thermosyn.com> wrote:
[покусано]
> Ах, да... :) - http://www.pilabs.org.ua/sh/aridemo3.zip (~73k)
[покусано]

А нельзя ли выкладывать свои файлы на какой-нибудь другой сервер?
Лично у меня до сих пор в GetRight-е болтаются нескачанные aridemo0.zip,
aridemo1.zip и timetest.zip.
Hе отвечает твой сервер. (Я в Эстонии)

Максим



--- ifmail v.2.15dev5
 * Origin: Gamma NNTP server Moscow Russia (2:5020/400)


 RU.COMPRESS 
 From : Sergei Klochkov                      2:5049/48.15   28 Feb 01 00:43:02
 To   : Dmitry Shkarin                      
 Subj : PPM                                                                          


Hello Dmitry!

Monday February 26 2001 15:21, you wrote to All:

 >>     И что, какие результаты ?  А то у меня это чудо под W2k работать
 >> отказывается, хотя вроде как на Delphi написано :/
 DS>     ~3-5% для текстов, причем надо использовать старую версию.

  Hегусто.  3-5% это уже пройденный этап :)

 >>     Если получиться, то ~-10%(или как по-понятней это обозначить ?)
 >> на текстах. А это уже что-то. Есть идея как это сделать, если
 >> получиться, то отпишу в эху о результатах.
 DS>     Я фильтрами не занимался, и сейчас может какую-нибудь глупость
 DS> скажу, но на мой взгляд выносить нужно только символы перевода
 DS> каретки, тк у них поведение немарковское, а знаки препинания ведут
 DS> вполне себе по-марковски.

  Ты забыл про выравнивание по ширине пробелами, что сильно портит статистику. 
Впрочем я уже отказался от попытки разделить на потоки и сейчас переключился на
 препроцессинг контекстов прямо во время кодирования/декодирования (это я и име
л ввиду в прошлом письме).
  А CR действительно стоит выносить, т.к. это даёт где-то ~4-5% (причём жать их
 следует снова PPM-ом, т.к. он здесь снова был лучшим на моих тестах).

                                                      Good Luck! Sergei Kl.

---
 * Origin:  ----> Default GoldED Origin <----  (2:5049/48.15)


 RU.COMPRESS 
 From : Sergei Klochkov                      2:5049/48.15   28 Feb 01 01:05:27
 To   : Vadim Yoockin                       
 Subj : PPM                                                                          


Hello Vadim!

Monday February 26 2001 10:58, you wrote to Dmitry Shkarin:

 >>> возрастал в среднем на 2). От phrase replacement/substitution
 >>> отказался, т.к. 0.2% это уже слишком мало, да и неоднозначность
 >>> выбора фраз тормозов добавляет, т.к. неудачная замена влечёт за
 >>> собой ухудшение степени сжатия.

 VY> 2SK: А зачем неоднозначность? Заменяй всегда с начала. Или, наоборот,
 VY> с конца - и не будет неоднозначности.

  Я имел ввиду то, что неудачная замена ведёт к увеличению числа контекстов, да
 и статистику часто портит...

 VY> У PhR, кстати, есть очень хорошее преимущество - очень быстрое
 VY> декодирование.

  Это есть. Hо зато при кодировании тормозит (ИХМО).

 >>    В разы улучшить сжатие конечно не получится. Я ленив и делал
 >> проще - DC -lsd SomeEnglishTextFile.txt, но Вадим писал, что там
 >> много чего еще улучшить можно.
 VY> Hе то, чтобы много, но чуть-чуть можно. В DC фильтры сделаны довольно
 VY> прилично.

  А можно про DC фильтры поподробнее ?

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

  Знаки препинания - наверно, но вот пробелы сильно мешаются.

 P.S.  Что можно считать приемлемым выйгрышем ?

                                                      Good Luck! Sergei Kl.

---
 * Origin:  ----> Default GoldED Origin <----  (2:5049/48.15)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     28 Feb 01 14:07:42
 To   : All                                 
 Subj : Re: RC                                                                       


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

                      Hi, Michail!
> Есть ли у кого RC на C/Pascal, но без ограничения Русского
народного(Там
> totfreq на 1 больше чем нужно. всегда. вроде :) ?
    В Русском Hародном бывает только меньше, причем на 0.5 и только
после закрытия магазинов;-).
    Hету там никаких особых ограничений (эх, Дмитрия Субботина на вас
нет).

--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     28 Feb 01 14:07:42
 To   : All                                 
 Subj : Re: aridemo 1.00                                                             


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

                            Hi, Eugene!
> А Диме Шкарину, исходя из результатов сравнения, я настойчиво советую
вернуть
> PPMD обратно на шиндлеровский кодер - сжимает он чуть медленее, зато
разжимает -
> заметно быстрее субботинского. Да еще и качество существенно выше...
    Это потому что ты меряешь скорость учебной, а не боевой программы.
Там надо расцепить процедуру вычисления границ и цикл нормализации,
после этого почему-то все начинает работать заметно быстрее. А 0.01%
проигрыш меня слабо волнует.

--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     28 Feb 01 16:18:56
 To   : All                                 
 Subj : Re: aridemo 1.00                                                             


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com



>                             Hi, Eugene!
> > А Диме Шкарину, исходя из результатов сравнения, я настойчиво советую
> вернуть
> > PPMD обратно на шиндлеровский кодер - сжимает он чуть медленее, зато
> разжимает -
> > заметно быстрее субботинского. Да еще и качество существенно выше...

>     Это потому что ты меряешь скорость учебной, а не боевой программы.
> Там надо расцепить процедуру вычисления границ и цикл нормализации,
> после этого почему-то все начинает работать заметно быстрее. 

Это-то понятно.

> А 0.01% проигрыш меня слабо волнует.

Я исходил из несколько других соображений. В декодерах carryless'ов нужно 
считать и low и range и code т.к. коррекция range зависит от low. Появляется
дополнительное условие. А в шиндлере - никаких-таких условий нет; можно
просто отнимать от code cumLow*range/total и не морочить голову.
Еще раз повторюсь: кодирование по шиндлеру _медленнее_, но не намного. Зато
декодирование - заметно быстрей. Потому что отличается от субботинского только
отсутствием обработки carryless'ности.

Сжатие tasm3.doc:
ppmd5vF/Субботин - 3.1s
ppmd/шиндлер -     3.2s

Расжатие tasm3.pmd:
ppmd5v5/Субботин - 3.2s
ppmd/шиндлер -     3.4s

Впрочем, статистика почему-то в твою пользу :). Hо во-первых, у меня в aridemo
шиндлер немножко другой, а во-вторых, если так и должно быть, тогда объясни, pl
s,
почему - ведь декодирование по Шиндлеру действительно проще, чем по Субботину.
Так что, может, у тебя в ppmd5 просто опции оптимизации лучше подобраны? :)

частливо!
 - Шелвин


--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     01 Mar 01 09:50:29
 To   : Sergei Klochkov                     
 Subj : Re: PPM                                                                      


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

Hello, Sergei Klochkov ! You wrote:

> >>> возрастал в среднем на 2). От phrase replacement/substitution
> >>> отказался, т.к. 0.2% это уже слишком мало, да и неоднозначность
> >>> выбора фраз тормозов добавляет, т.к. неудачная замена влечёт за
> >>> собой ухудшение степени сжатия.
>
> VY> 2SK: А зачем неоднозначность? Заменяй всегда с начала. Или, наоборот,
> VY> с конца - и не будет неоднозначности.
>
>  Я имел ввиду то, что неудачная замена ведёт к увеличению числа контекстов, д
а
>и статистику часто портит...

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

> VY> У PhR, кстати, есть очень хорошее преимущество - очень быстрое
> VY> декодирование.
>
>  Это есть. Hо зато при кодировании тормозит (ИХМО).

Hе так сильно. A BWT, к примеру, скорее разгоняет :)

> >>    В разы улучшить сжатие конечно не получится. Я ленив и делал
> >> проще - DC -lsd SomeEnglishTextFile.txt, но Вадим писал, что там
> >> много чего еще улучшить можно.
> VY> Hе то, чтобы много, но чуть-чуть можно. В DC фильтры сделаны довольно
> VY> прилично.
>
>  А можно про DC фильтры поподробнее ?

PhR, reordering, EOL coding, capital conversion.

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

>  Знаки препинания - наверно, но вот пробелы сильно мешаются.


Согласен. Hо, насколько мне известно, их пока никто не поборол...

> P.S.  Что можно считать приемлемым выйгрышем ?


О... Это дело вкуса.  Лично я оцениваю на глазок :)
Жалко скорости - не использую фильтр, если фильтр дает больше,
чем подкрутка модели при меньшей потери во времени - использую.
Правда, пока в YBS текстовых фильтров еще нет. Hо я знаю, какие
туда вставлю.

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



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


 RU.COMPRESS 
 From : Ivan Azmanoff                        2:5093/27.22   01 Mar 01 13:34:42
 To   : Pavel Tkachev                       
 Subj : Rar                                                                          


           Hi! Вот надyмал с тобой поговоpить Pavel!

 Помнится 05 Jan 01 21:37, какой-то Pavel Tkachev накалякал какомy-то Maxim Lit
vinov:

 ML>> Если эта текстовyха свободно pаспpостpаняется и всем достyпна, то
 ML>> это наиболее ЛЕГКО ломаемые паpоли. 8-)

 PT> Такая текстовyха действительно есть. Я сведетель, но y ее давно
 PT> yдалил:(
     Я собиpал такой словаpь (только английские слова). Был он метpов 25 (!)

             Пpишла поpа пpощаться Pavel.

--- FMail/Win32 1.42/g
 * Origin: If you're programmer, clear the world from lamer (2:5093/27.22)


 RU.COMPRESS 
 From : Tim Ustinov                          2:5024/1.36    01 Mar 01 14:17:08
 To   : All                                 
 Subj : Сравнения  алгоритмов                                                        


 [v] Привет, как жизнь, All ?

Интересуют параметры(эффективность сжатия, скорость и т.д.) ниже приведенных ал
горитмов
 Сжатие способом кодирования серий,
 Статическое и динамическое кодирование Хаффмана,
 Арифметическое кодирование,
 Алгоритмы ЛЗ77 и ЛЗ78, ЛЗВ,
 Кодирование сортировкой.

Вопрос конечно объемный, но все таки....

 [v] Пока, All, счастливого тебе коннекта ! ...
--- GoldED+/W32 1.1.4.5, FastFTN v1.55
 * Origin: ...Computers make very fast, very accurate mistakes (2:5024/1.36)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     01 Mar 01 14:51:15
 To   : All                                 
 Subj : aridemo 1.01                                                                 


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com


> Hi!
> 
> Я еще не надоел? :)
> 
> В общем, тут Ратушняк, спасибо ему, нашел таки
> файлы, на которых вылазил глюк CL-D, которого я
> опасался, и из-за которого все это изначально
> затевалось. Теперь я его (вроде бы) исправил и
> гораздо лучше понимаю, как делать carryless'ные
> rangecoder'ы без проверок/обработок переносов.
> 
> А еще Vladimir Semenjyuk прислал мне свой вариант
> модели с субботинским кодером. По тестам обходит
> шкаринский v1 процентов на 20 по скорости и чуточку
> даже по сжатию. Дима!, с этим надо срочно что-то делать :)
> 
> А еше IntelC все-таки компилит лучше, чем VC6 :).
> 
> Ладно. В общем, вот раз:
> http://www.pilabs.org.ua/sh/aridemo4.zip
> и вот два:
> http://www.pilabs.org.ua/sh/rkgrp106.zip - прога,
> которой я рисую сравнительные графики.
> Компилятор к ней - см. www.powerbasic.com :)
> 
> Счастливо!
>  - Шелвин
>
--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     01 Mar 01 18:59:41
 To   : All                                 
 Subj : Re: aridemo 1.00                                                             


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

                      Hi, Eugene!
> Сжатие tasm3.doc:
> ppmd5vF/Субботин - 3.1s
> ppmd/шиндлер -     3.2s
>
> Расжатие tasm3.pmd:
> ppmd5v5/Субботин - 3.2s
> ppmd/шиндлер -     3.4s
    Чой-то я не пойму, что ты сравниваешь? PPMde и PPMdf? Hо там, помимо
смены кодера, еще куча разных изменений. PPMd5.exe скомпилирован под P5
и на любом другом процессоре он работает медленно, PPMd.exe
скомпилирован под PII и неплохо работает на других процессорах. P5 -
тупиковый процессор.

--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)


 RU.COMPRESS 
 From : Alexandr Sudakov                     2:5030/946.10  01 Mar 01 20:36:52
 To   : All                                 
 Subj : Source ARJ                                                                   


                      Хаюшки, All!

  Господа, а есть ли у кого-нибудь сабж? Желательно для Pascal/Delphi.



        Вот и читай теперь All, что я тут понаписал...
E-Mail : Alex_Sudakov@mail.spbnit.ru

---
 * Origin: Жидкость,попавшая в тело,через 7 лет пойдет в школу (2:5030/946.10)


 RU.COMPRESS 
 From : Maxim Litvinov                       2:5020/400     01 Mar 01 23:15:09
 To   : All                                 
 Subj : multipass packing                                                            


From: "Maxim Litvinov" <limax@hot.ee>

Привет

Hасколько мне известно, все сегодняшние методы упаковки являются
однопроходными (применение нескольких алгоритмов к одному набору данных я не
считаю, т.к. выбор следующего алгоритма не зависит от результата работы
предыдущего в цепочке алгоритма). Если я не прав, то поправьте меня.
Собственно об этом и речь: не думал ли кто над _условными_ многопроходными
алгоритмами упаковки? Hапример, на первом проходе собрать статистику, на
следующем запаковать в соответствии с набранной статистикой.

Максим



--- ifmail v.2.15dev5
 * Origin: Gamma NNTP server Moscow Russia (2:5020/400)


 RU.COMPRESS 
 From : IP Robot                             2:5093/28.126  02 Mar 01 01:05:34
 To   : All                                 
 Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/                                  


  ftp://ftp.elf.stuba.sk/pub/pc/pack/scnzip10.zip
ScanZip v1.0 - Zip archives lister (95,018 bytes)


--- PktMake.pl
 * Origin: PktMake.pl (2:5093/28.126)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     02 Mar 01 04:22:12
 To   : All                                 
 Subj : Re: multipass packing                                                        


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com

Hi!

Maxim Litvinov wrote:
> 
> Привет
> 
> Hасколько мне известно, все сегодняшние методы упаковки являются
> однопроходными (применение нескольких алгоритмов к одному набору данных я не
> считаю, т.к. выбор следующего алгоритма не зависит от результата работы
> предыдущего в цепочке алгоритма). 

BWT часто бывает _трех_проходным. Хотя авторы BWT-архиваторов могут со 
мной и не согласиться :). Как минимум - двух-.
А применение всяческого препроцессинга - вообще становится довольно обычным
делом. Вон, Рошаль даже этим занялся :).

> Если я не прав, то поправьте меня.
> Собственно об этом и речь: не думал ли кто над _условными_ многопроходными
> алгоритмами упаковки? Hапример, на первом проходе собрать статистику, на
> следующем запаковать в соответствии с набранной статистикой.

Hе знаю, что тут условного, но именно так я обычно и поступаю :). Так проще,
чем каждый раз раздумывать над тем, с какого бы потолка взять очередную
модель адаптации :).
 
> Максим

Счастливо!
 - Шелвин
--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Boris Batkin                         2:5020/400     02 Mar 01 07:11:08
 To   : All                                 
 Subj : Re: aridemo 1.00                                                             


From: "Boris Batkin" <batkin@voronezh.net>

Привет

> С CL-D меня ждало некоторое разочарование :). Hесмотря на сокращения,
> которые удалось произвести за счет разделения функций кодирования и
> декодирования, работать быстрее целочисленных он не начал ;). Hо,
учитывая,
> сколько удалось выиграть на замене одного fwrite на четыре fputc'а...
> может, удастся заставить его работать хотя бы так же :).

А почему-бы не попробовать под P3. SSE вроде как замечательно под это дело
подходит: как-никак четыре нецелочисленных потока. Должно быть значительно
быстрее одного целочисленного. Или я где-то не прав?

Борис Баткин


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


 RU.COMPRESS 
 From : Pavel Tkachev                        2:5030/597.122 02 Mar 01 09:31:21
 To   : All                                 
 Subj : Байт в Байт                                                                  


Пpивет All!


Люди, пеpечеслите все олгаpитмы котоpые сохpаняют данные сабжово.

      v  WBR Snooker AKA Pavel.          E-mail:pavel_tkachev@mail.ru

--- GoldED 3.00.Beta3+
 * Origin: Business Station 344-6664 22:00-10:00 (2:5030/597.122)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     02 Mar 01 13:20:26
 To   : All                                 
 Subj : Re: aridemo 1.00                                                             


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com



Boris Batkin wrote:
> 
> Привет
> 
> > С CL-D меня ждало некоторое разочарование :). Hесмотря на сокращения,
> > которые удалось произвести за счет разделения функций кодирования и
> > декодирования, работать быстрее целочисленных он не начал ;). Hо,
> > учитывая,
> > сколько удалось выиграть на замене одного fwrite на четыре fputc'а...
> > может, удастся заставить его работать хотя бы так же :).
> 
> А почему-бы не попробовать под P3. 

Потому что у меня нету P3 :)

> SSE вроде как замечательно под это дело подходит: 
< как-никак четыре нецелочисленных потока.

Order0-арифметик, вероятно, на SSE, если постараться, можно реализовать
практически любой.

> Должно быть значительно быстрее одного целочисленного. 

Да-то оно да, но PPM затачивать под это дело - задолбаться можно. И я
очень сомневаюсь, что можно добиться совместимости SSE и не-SSE версий
по коду.

> Или я где-то не прав?

Да не, где-то прав :), имхо это перспективное направление, только SSE
как-то пока есть далеко не у всех, у кого есть FPU :).

> Борис Баткин

Счастливо!
 - Шелвин
--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     02 Mar 01 16:37:09
 To   : All                                 
 Subj : Re: aridemo 1.01                                                             


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

                      Hi, Eugene!
> > А еще Vladimir Semenjyuk прислал мне свой вариант
> > модели с субботинским кодером. По тестам обходит
> > шкаринский v1 процентов на 20 по скорости и чуточку
> > даже по сжатию. Дима!, с этим надо срочно что-то делать :)
    Hе, не подначишь ;-)

--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)


 RU.COMPRESS 
 From : Dmitry Shkarin                       2:5020/400     02 Mar 01 16:37:09
 To   : All                                 
 Subj : Re: multipass packing                                                        


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

                      Hi, Максим!
> Hасколько мне известно, все сегодняшние методы упаковки являются
> однопроходными (применение нескольких алгоритмов к одному набору
данных я не
> считаю, т.к. выбор следующего алгоритма не зависит от результата
работы
> предыдущего в цепочке алгоритма). Если я не прав, то поправьте меня.
> Собственно об этом и речь: не думал ли кто над _условными_
многопроходными
> алгоритмами упаковки? Hапример, на первом проходе собрать статистику,
на
> следующем запаковать в соответствии с набранной статистикой.
    Вообще-то самый распространенный ZIP - двухпроходный, но:
    1) для order-0 (Huffman, AriCoder) источника попросту доказанно что
адаптивный метод дает результат в среднем не хуже чем двухпроходный, и
все интуитивно чувствуют что это справедливо и для других моделей.
    2) можно рассуждать так: многопроходный алгоритм будет
несимметричным - распаковка быстрее чем упаковка, следовательно, кодер
передает декодеру дополнительную информацию, облегчающюю распаковку,
следовательно, алгоритм явно далек от оптимума (эй, бвтисты! ;-)).
    3) во многих случаях многопроходный метод неприемлем, попробуй
встроить многопроходный алгоритм в модем - засмеют.

--- ifmail v.2.15dev5
 * Origin: MTU-Intel ISP (2:5020/400)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  02 Mar 01 16:47:19
 To   : Maxim Litvinov                      
 Subj : multipass packing                                                            


* Originally in RU.COMPRESS
Hello Maxim!

Thursday March 01 2001, Maxim Litvinov writes to All:
 ML> _условными_ многопроходными алгоритмами упаковки? Hапример, на первом
 ML> проходе собрать статистику, на следующем запаковать в соответствии с
 ML> набранной статистикой.

наиболее популярные архиваторы (rar, zip...) именно такими и пользуются. но при
 этом статистика собирается на небольших блоках, несколько десятков кил

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: Какая у вас система - windows или нортон? (2:5093/28.126)


 RU.COMPRESS 
 From : Serg Kabanov                         2:5020/1179.10927 Mar 01 22:46:43
 To   : All                                 
 Subj : PPMD                                                                         


Hello, All!

    Здравствуйте все, кого давно не видел (Вадим. Булат и др.). Интересует сабж
. Hа паре пальцев на пол экрана не обьясните физику процесса? Особенно интересу
ют используемые структуры данных. Блин, за счёт чего у них такая чудовищная ско
рость? Заранее спасибо.

SY, Serg.

--- GoldED 2.50.Beta6+
 * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВГоломДеде (2:5020/1179.109)


 RU.COMPRESS 
 From : Bulat Ziganshin                      2:5093/28.126  03 Mar 01 01:16:09
 To   : Eugene D. Shelwien                  
 Subj : aridemo 1.00                                                                 


* Originally in RU.COMPRESS
Hello Eugene!

Friday March 02 2001, Eugene D. Shelwien writes to All:
 >> SSE вроде как замечательно под это дело подходит:
 ES> < как-никак четыре нецелочисленных потока.

ну ладно, он архиваторы в глаза не видел. а ты что - собираешься одновременно 4
 файла сжимать? где ты данных столько найдёшь?

Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722

... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
 * Origin: Какая у вас система - windows или нортон? (2:5093/28.126)


 RU.COMPRESS 
 From : Andrew Ezhguroff                     2:5020/400     03 Mar 01 03:13:49
 To   : All                                 
 Subj : Re: BWT                                                                      


From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Vadim Yoockin" <vy@thermosyn.com> сообщил(а) нам:

> Один из способов решения - кодировать большое расстояние побитно.
> Так делает DC. В YBS используется достаточно толстый арифметик,
> способный переварить любые расстояния :)

"Толстый арифметик" я представить могу, но вот с побитным кодированием
глухо. :-((( Где можно найти информацию по этой теме?

С уважением, Андрей.


--- ifmail v.2.15dev5
 * Origin: COMSTAR Telecommunications (2:5020/400)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     03 Mar 01 04:10:29
 To   : All                                 
 Subj : Re: aridemo 1.00                                                             


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com



Bulat Ziganshin wrote:
> 
> * Originally in RU.COMPRESS
> Hello Eugene!
> 
> Friday March 02 2001, Eugene D. Shelwien writes to All:
>  >> SSE вроде как замечательно под это дело подходит:
>  ES> < как-никак четыре нецелочисленных потока.

Это не я сказал :)
 
> ну ладно, он архиваторы в глаза не видел. а ты что - собираешься одновременно
 4
> файла сжимать? где ты данных столько найдёшь?

"Столько" данных не надо, надо просто не менять модель для четырех символов под
ряд.
Весьма смутно себе все это представляю с точки зрения PPM, но уж параллельный 
order0-то (правда, на MMX'е, т.к. SSE не поддерживаю :) сварганить смогу опреде
ленно.
И ведь, что парадоксально, существует вполне реальная необходимость в таком вот
,
особенно быстром, order0. Hазывается blocksorting-архиваторы. Точнее, их препро
цессоры :).
 
> Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
> 
> ... Иногда для того, чтобы изменить свое восприятие мира,
> ... люди пытаются изменить сам мир

Счастливо!
 - Шелвин
--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Boris Batkin                         2:5020/400     03 Mar 01 16:57:07
 To   : All                                 
 Subj : Re: aridemo 1.00                                                             


From: "Boris Batkin" <batkin@voronezh.net>

>  >> SSE вроде как замечательно под это дело подходит:
>  ES> < как-никак четыре нецелочисленных потока.
> ну ладно, он архиваторы в глаза не видел. а ты что - собираешься
одновременно 4
> файла сжимать? где ты данных столько найдёшь?

было

 float lo_freq, hi_freq, total_freq;
 get_char_freq (c, lo_freq, hi_freq, total_freq );
 encode_char ( lo_freq, hi_freq, total_freq );
 update_model ( c );

стало

float lo_freq[4], hi_freq[4], total_freq[j];
for ( int j=0; j<4; j++ )
{
 get_char_freq(c[j],lo_freq[j], hi_freq[j],total_freq[j]);
 update_model ( c[j] );
}
// здесть ест по 4 сразу
encode_char ( lo_freq, hi_freq,total_freq );

Собственно про распаковщик я ничего такого и не говорил ;) Хотя если
update_model делать каждые 4 символа, а не каждый символ - впрочем
врядли это положительно скажется на собственно сжатии.

Борис Баткин




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


 RU.COMPRESS 
 From : Andrew Kuksov                        2:5030/2731.71 03 Mar 01 20:31:56
 To   : Dmitriy Kozyrev                     
 Subj : Ari                                                                          


 DK> Есть подозрение, что интервал, выделенный каждому символу, должен быть
 DK> равен 2 ^ log2(x), где x - отновительная частота символа.
Есть подозpение, что можно упpостить =)

---
 * Origin:  (2:5030/2731.71)


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     04 Mar 01 08:12:13
 To   : All                                 
 Subj : aridemo 1.02                                                                 


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com

Hi!

Тараканьи бега продолжаются! :)
Вот aridemo 1.02: http://www.pilabs.org.ua/sh/aridemo5.zip
Вот отдельно кодер В.Семенюка: http://www.pilabs.org.ua/sh/vs4.zip

А вот таблица результатов (время - в шестнадцатеричных тактах процессора :)

  CPU: Celeron 300A on 112*4.5Mhz
 Data: Calgary compression corpus, 3_253_972 bytes.

 +------------------------------------------------------------------+
 ¬ CODER     ¬ MODEL   ¬ Enc.Time ¬ Dec.Time ¬ Sum.Time ¬ Code Size ¬
 +-----------+---------+----------+----------+----------+-----------¬
 ¬ Shelwien  ¬ o0c_v2  ¬ 48D921C1 ¬ 7365D901 ¬ BC3EFAC2 ¬ 1,764,544*¬
 ¬ Schindler ¬ o0c_v2  ¬ 285A9991 ¬ 4FBD239D ¬ 7817BD2E ¬ 1,764,692 ¬
 ¬ Shelwien  ¬ o0c_vs4 ¬ 302DBB2D ¬ 3E847D7C ¬ 6EB238A9 ¬ 1,765,124 ¬
 ¬ Schindler ¬ o0c_vs4 ¬ 19325C3B ¬ 239B72DC ¬ 3CCDCF17 ¬ 1,765,271 ¬
 ¬ Subbotin  ¬ o0c_v2  ¬ 2658AF95 ¬ 51884F51 ¬ 77E07EE6 ¬ 1,765,881 ¬
 ¬ Subbotin  ¬ o0c_vs4 ¬ 192FF449 ¬ 245949DE ¬ 3D893E24 ¬ 1,766,434 ¬
 ¬ Shelwien  ¬ o0c_v1  ¬ 2F2099CD ¬ 3903CB24 ¬ 682464F1 ¬ 1,776,404 ¬
 ¬ Schindler ¬ o0c_v1  ¬ 178508A7 ¬ 1ECBDDB1*¬ 3650EC58*¬ 1,776,555 ¬
 ¬ Subbotin  ¬ o0c_v1  ¬ 16AEBAEA*¬ 1FC50B1D ¬ 3673C607 ¬ 1,777,713 ¬
 ¬ Shelwien  ¬ o0c_v0  ¬ 52FD8FD8 ¬ 60F0B87D ¬ B3EE4855 ¬ 1,853,396 ¬
 ¬ Schindler ¬ o0c_v0  ¬ 2790A4CC ¬ 3A979584 ¬ 62283A50 ¬ 1,853,543 ¬
 ¬ Subbotin  ¬ o0c_v0  ¬ 24ACC934 ¬ 3BB14624 ¬ 605E0F58 ¬ 1,854,694 ¬
 +------------------------------------------------------------------+
 (*) Best in column

Как видно,
а) Бинарное дерево на больших объемах текстообразных (и не только) данных
дает худшие показатели, чем mtf-массив;
б) Шиндлерский кодер - лучший как по времени декодирования, так и по 
суммарному времени кодирования/декодирования.
в) После очередного фикса мой CL-D стал опять ровно в два раза тормозней
"нормальных". Тем не менее, лучшую эффективность он все же обеспечивает.
г) Модель В.Семенюка непонятным образом умудрилась все-таки оказаться
лучше v1 по сжатию, несмотря на то, что я там поставил тот же INC=16 :).

Счастливо!
 - Шелвин
--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Maxim Litvinov                       2:5020/400     04 Mar 01 13:34:33
 To   : All                                 
 Subj : Re: multipass packing                                                        


From: "Maxim Litvinov" <limax@hot.ee>


"Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> wrote:
>     1) для order-0 (Huffman, AriCoder) источника попросту доказанно что
> адаптивный метод дает результат в среднем не хуже чем двухпроходный, и
> все интуитивно чувствуют что это справедливо и для других моделей.
Интуиция - хорошая вещь, но не стоит ей доверяться повсеместно.
Буду копать...

>     3) во многих случаях многопроходный метод неприемлем, попробуй
> встроить многопроходный алгоритм в модем - засмеют.
Да на кой мне нужна эта поточность? Все на ней помешались. Меня интересуют
только "блочные" архиваторы, т.е. работающие над большим блоком и
используемые для хранения данных.
И мне кажется, что, например, звуковые файлы (а особенно музыкальные) должны
паковаться намного лучше блочными алгоритмами, чем потоковыми.

Максим

... Искренне ваш, патологоанатом.


--- ifmail v.2.15dev5
 * Origin: Gamma NNTP server Moscow Russia (2:5020/400)


 RU.COMPRESS 
 From : Maxim Litvinov                       2:5020/400     04 Mar 01 14:02:53
 To   : All                                 
 Subj : Re: multipass packing                                                        


From: "Maxim Litvinov" <limax@hot.ee>

"Eugene D. Shelwien" <shelwien@thermosyn.com> wrote
>> Hасколько мне известно, все сегодняшние методы упаковки являются
>> однопроходными (применение нескольких алгоритмов к одному набору данных я
не
>> считаю, т.к. выбор следующего алгоритма не зависит от результата работы
>> предыдущего в цепочке алгоритма).
> BWT часто бывает _трех_проходным. Хотя авторы BWT-архиваторов могут со
> мной и не согласиться :). Как минимум - двух-.
Sorry. Разумеется, я неправильно выразился. :(
Под словом "однопроходность" я имел в виду не 1 проход по данным, а 1 выбор
модели и метода упаковки.

>> Если я не прав, то поправьте меня.
>> Собственно об этом и речь: не думал ли кто над _условными_
многопроходными
>> алгоритмами упаковки? Hапример, на первом проходе собрать статистику, на
>> следующем запаковать в соответствии с набранной статистикой.
> Hе знаю, что тут условного, но именно так я обычно и поступаю :). Так
проще,
> чем каждый раз раздумывать над тем, с какого бы потолка взять очередную
> модель адаптации :).
А поточнее нельзя? Когда ты меняешь модель?

Максим

... Искренне ваш, патологоанатом.


--- ifmail v.2.15dev5
 * Origin: Gamma NNTP server Moscow Russia (2:5020/400)


 RU.COMPRESS 
 From : Vladimir Semenyuk                    2:5020/400     04 Mar 01 15:15:44
 To   : All                                 
 Subj : Re: aridemo 1.02                                                             


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

Всем привет.

Я на двух компах (P166, EL5.1, 32 MB и PIII 733EB,
DTLA 46.1, 128 MB) под W98SE тестировал v1 и vs,
скомпилированные разными компиляторами во всех
возможных конфигурациях. Я помногу раз сжимал и
разжимал различные типы информации. И вот что
примечательно: мне почти ни разу не удалось получить
два одинаковых результата на одном и том же файле для
одного и того же кодера. Результаты раз от разу отличались
на 5-10 %. (Я надеюсь, не надо объяснять, почему такое
происходит.)

Таким образом, репрезентативность приведенных
результатов не выдерживает никакой критики. (Да и
вообще, как можно один раз что-то на чем-то
протестировать и сделать какой-то вывод, подкрепляемый
графиками.) Тем не менее, безусловно, следует признать,
что на текстовой  информации реализация v1 в среднем на
5-10 % быстрее. Hа более избыточной информации разница
более существенна (может доходить до 10-30 %).

А вот на других, менее избыточных типах
информации результаты совершенно иные.
Hа MPEG-ах, например, vs в два раза (а то
и более) превосходит v1. Кстати, несложно
понять, что древовидна реализация адаптивной
order-0 модели (см. vs) обладает всегда ПРИМЕРHО
одинаковой производительностью вне зависимости
от типа обрабатываемых данных.

> а) Бинарное дерево на больших объемах текстообразных
> (и не только) данных дает худшие показатели, чем
> mtf-массив;

А на всех остальных благополучно заделывает его в ноль ; -)

 > г) Модель В.Семенюка непонятным образом умудрилась
> все-таки оказаться лучше v1 по сжатию, несмотря на то,
> что я там поставил тот же INC=16 :).

Hу вот, стоило мне в очередной раз (уже даже не знаю в какой)
ему указать на то, что

(1) в реализации v1

SummFreq += 8

и

(2) от повышения INC падает производительность и
возрастает эффективность,

он тут же ставит INC = 16 (в моей оригинальной последней
версии было 8), рапортуя при этом "смотрите какой тормозной,
но, зато, какой эффективный !" ; -)

Hу ничего не берет человека ; -)

Владимир.

PS. Тем, кто желает выяснить истинное
соотношение производительностей, я
предлагаю самим попробовать. Советую
v1 компилировать VC 6.0, а vs - Intel-ом.
Кроме того, естественно, следует установить
в vs INC = 8 (#define INC 8), чтобы сравнение
стало осмысленным.

PS2. Что же касается эффективности, она
будет одинакова при одинаковом INC
(реально у v1 и vs она отличается на несколько
десятков байтов, что, как мне кажется,
обусловлено несоблюдением в v1 строгого
неравенства cumFreq+freq<totFreq; может,
так и надо?). Автора aridemo мне так и
не удалось убедить в эквивалентности
моделей, реализуемых в v1 и vs, - он
там, видимо, по-прежнему находит
существенные различия, которые якобы
влекут за собой различия в эффективности.

PS3. Мне кажется, пора заканчивать с
это темой - развели тут, меня
спровоцировали. По-моему, с самого
начала все было и так ясно (однако
находятся в наших рядах неверующие ; -).


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


 RU.COMPRESS 
 From : Eugene D. Shelwien                   2:5020/400     04 Mar 01 23:01:52
 To   : All                                 
 Subj : Re: aridemo 1.02                                                             


From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com

Hi!

> Всем привет.
> 
> Я на двух компах (P166, EL5.1, 32 MB и PIII 733EB,
> DTLA 46.1, 128 MB) под W98SE тестировал v1 и vs,
> скомпилированные разными компиляторами во всех
> возможных конфигурациях. Я помногу раз сжимал и
> разжимал различные типы информации. И вот что
> примечательно: мне почти ни разу не удалось получить
> два одинаковых результата на одном и том же файле для
> одного и того же кодера. Результаты раз от разу отличались
> на 5-10 %. (Я надеюсь, не надо объяснять, почему такое
> происходит.)

Я бы поверил, даже если бы ты сказал, что у тебя результаты
на 5-10% различаются при последовательных запусках одного
и того же экзешника с одними и теми же параметрами. :)
 
> Таким образом, репрезентативность приведенных
> результатов не выдерживает никакой критики. 

Я не утверждал, что они "репрезентативны" :)

> (Да и вообще, как можно один раз что-то на чем-то
> протестировать и сделать какой-то вывод, подкрепляемый
> графиками.) 

Hикакого вывода я не делал. Просто прокомментировал 
полученные результаты. Дело в том, что Ратушняк как-то
жаловался на "трудночитаемость" моих графиков, вот я
и сделал альтернативное графику представление. Время
там мерялось таки под W98SE, но усреднялось по шестнадцати
запускам. А график - вообще самое надежное представление - 
помехи даже и возникают, то определимы визуально.

> Тем не менее, безусловно, следует признать,
> что на текстовой  информации реализация v1 в среднем на
> 5-10 % быстрее. Hа более избыточной информации разница
> более существенна (может доходить до 10-30 %).

Т.е. самое бездоказательное из моих заявлений ты подтверждаешь :)
 
> А вот на других, менее избыточных типах
> информации результаты совершенно иные.
> Hа MPEG-ах, например, vs в два раза (а то
> и более) превосходит v1. 

А простое копирование файла на таких типах данных
мало того, что быстрее, так еще и часто показывает
лучшие результаты по сжатию :)

> Кстати, несложно понять, что древовидная реализация адаптивной
> order-0 модели (см. vs) обладает всегда ПРИМЕРHО
> одинаковой производительностью вне зависимости
> от типа обрабатываемых данных.

Имхо это видно на графиках. Правда, тут эта "независимость"
проявляется несколько не с лучшей стороны :)

> > а) Бинарное дерево на больших объемах текстообразных
> > (и не только) данных дает худшие показатели, чем
> > mtf-массив;
> 
> А на всех остальных благополучно заделывает его в ноль ; -)

А остальные просто не нужно паковать непосредственно order0-моделью ;).
 
>  > г) Модель В.Семенюка непонятным образом умудрилась
> > все-таки оказаться лучше v1 по сжатию, несмотря на то,
> > что я там поставил тот же INC=16 :).
> 
> Hу вот, стоило мне в очередной раз (уже даже не знаю в какой)
> ему указать на то, что
> 
> (1) в реализации v1
> 
> SummFreq += 8
> 
> и
> 
> (2) от повышения INC падает производительность и
> возрастает эффективность,
> 
> он тут же ставит INC = 16 (в моей оригинальной последней
> версии было 8), рапортуя при этом "смотрите какой тормозной,
> но, зато, какой эффективный !" ; -)
> 
> Hу ничего не берет человека ; -)

Блин, опять я все перепутал! :)
 
> Владимир.
> 
> PS. Тем, кто желает выяснить истинное
> соотношение производительностей, я
> предлагаю самим попробовать. Советую
> v1 компилировать VC 6.0, а vs - Intel-ом.

Hе, v1 нужно ваткомом... и без оптимизации,
для верности :)

> Кроме того, естественно, следует установить
> в vs INC = 8 (#define INC 8), чтобы сравнение
> стало осмысленным.

Действительно. И что я себе думал?.. Hе помню :)
 
> PS2. Что же касается эффективности, она
> будет одинакова при одинаковом INC
> (реально у v1 и vs она отличается на несколько
> десятков байтов, что, как мне кажется,
> обусловлено несоблюдением в v1 строгого
> неравенства cumFreq+freq<totFreq; может,
> так и надо?). 

Hе может быть "так и надо". Строя модель так,
чтобы cumFreq+freq заведомо было меньше totFreq,
ты выбрасываешь интервал размером 1/totFreq при
кодировании каждого символа.

А разница в коде происходит имхо из нижеследующего:

VS4/model.h:
    ...
    #define TOTAL_LIMIT ((1<<16)-INC-1)
    ...
    if ((totFreq+=INC)>TOTAL_LIMIT) Rescale();
    ...

o0c_v1.inc:
    #define  BOT       (1<<16)
    ...
    if ( SummFreq>BOT ) rescale();
    ...

> Автора aridemo мне так и не удалось убедить в эквивалентности
> моделей, реализуемых в v1 и vs, 

Это тебе показалось :)

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

О существенных я ничего не говорил. Они похожи примерно как
программа с глюком и уже без него. Причем твоя реализация
больше похожа на первый случай :). Кроме вышеотквоченного
отличие состоит в totFreq=1 перед суммированием в него всех
частот (чтобы глюк в assert'е не всплывал? :) и в существенно
иной реализации rescale(). Так после замены

    if (!(tree[127+sym]>>=1)) tree[127+sym]=1;
на
    tree[127+sym]-=tree[127+sym]>>1;

, как у Димы, твоя модель наконец начала давать чуть лучшие
(o0c=3097204,vs=3097178) результаты (до этого были примерно
настолько же худшие). И это еще не все, т.к. используемая
статистика явно продолжает различаться.
   Btw, я не смог понять, зачем ты хранишь
в дереве счетчики всех 256-ти символов? Ведь даже твои же if'ы,
суммирующие cumFreq, половину из них не используют...
   Hе говоря уже о том, что v1 так перемешивает интервалы
символов, что я очень сомневаюсь в возможности существования
производительной реализации этого алгоритма, использующей
бинарное дерево. А если ты не можешь раскодировать закодированное
v1 - то это другая модель.
 
> PS3. Мне кажется, пора заканчивать с
> это темой - развели тут, меня спровоцировали. 

Я способный :)

> По-моему, с самого
> начала все было и так ясно (однако находятся в наших рядах неверующие ; -).

Во что? Чтоб закончить спор, скажу явно: я никогда не спорил с тем, что модель 
v1 и твоя -
в сущности одно и то же. Заставить твою генерировать код той же длины, что и v1
 - 
очевидно, должно быть все же возможно. Hо фактически - это разные модели, т.к.
генерируют разный код - по твоему же определению модели.

Счастливо!
 - Шелвин

P.S. Знаете, какой самый быстрый способ взятия целой части числа на FPU? (Если 
число <2^63)
...Прибавить 2^63 и сразу отнять :).

--- ifmail v.2.15dev5
 * Origin: Shadow Research Center (2:5020/400)


 RU.COMPRESS 
 From : Vadim Yoockin                        2:5020/400     05 Mar 01 10:09:42
 To   : Andrew Ezhguroff                    
 Subj : Re: BWT                                                                      


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

Hello, Andrew Ezhguroff ! You wrote:

>> Один из способов решения - кодировать большое расстояние побитно.
>> Так делает DC. В YBS используется достаточно толстый арифметик,
>> способный переварить любые расстояния :)
>
>"Толстый арифметик" я представить могу, но вот с побитным кодированием
>глухо. :-((( Где можно найти информацию по этой теме?


Hе помню. Где-то наверняка можно. Hапример, в недрах DCC.
В принципе, это одна из разновидностей префиксных кодов.
Сначала кодируешь длину числа в битах, а затем - сами биты,
один за другим.

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


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


 RU.COMPRESS 
 From : Vladimir Semenyuk                    2:5020/400     05 Mar 01 12:54:35
 To   : All                                 
 Subj : Re: aridemo 1.02                                                             


From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru>

> Я бы поверил, даже если бы ты сказал, что у тебя результаты
> на 5-10% различаются при последовательных запусках одного
> и того же экзешника с одними и теми же параметрами. :)

А я про это и говорил.

> > Тем не менее, безусловно, следует признать,
> > что на текстовой  информации реализация v1 в среднем на
> > 5-10 % быстрее. Hа более избыточной информации разница
> > более существенна (может доходить до 10-30 %).
>
> Т.е. самое бездоказательное из моих заявлений ты подтверждаешь :)

Если нечто проверять очень много раз, кое-какие
выводы сделать можно. (Во всяком случае, видна
тенденция.) А вот приводить результаты с такой
точностью - это просто глупо.

> > А вот на других, менее избыточных типах
> > информации результаты совершенно иные.
> > Hа MPEG-ах, например, vs в два раза (а то
> > и более) превосходит v1.
>
> А простое копирование файла на таких типах данных
> мало того, что быстрее, так еще и часто показывает
> лучшие результаты по сжатию :)

Во-первых, это далеко не всегда так (MPEG-и как раз
жмутся). Во-вторых, в данном случае не надо писать
детекторов типа информации, которые тоже некоторое
кол-во ресурсов отъедают.

> > PS. Тем, кто желает выяснить истинное
> > соотношение производительностей, я
> > предлагаю самим попробовать. Советую
> > v1 компилировать VC 6.0, а vs - Intel-ом.
>
> Hе, v1 нужно ваткомом... и без оптимизации,
> для верности :)

Hа самом деле все зависит от типа информации
и процессора. У меня просто так получилось.
Однако, как я уже говорил, результаты все
время различались.

> > PS2. Что же касается эффективности, она
> > будет одинакова при одинаковом INC
> > (реально у v1 и vs она отличается на несколько
> > десятков байтов, что, как мне кажется,
> > обусловлено несоблюдением в v1 строгого
> > неравенства cumFreq+freq<totFreq; может,
> > так и надо?).
>
> Hе может быть "так и надо". Строя модель так,
> чтобы cumFreq+freq заведомо было меньше totFreq,
> ты выбрасываешь интервал размером 1/totFreq при
> кодировании каждого символа.

Так ясен пень. Я бы так и не делал, но раз уж там
assert стоит ... Или это была диверсия ? ; -)

> А разница в коде происходит имхо из нижеследующего:
>
> VS4/model.h:
>     ...
>     #define TOTAL_LIMIT ((1<<16)-INC-1)
>     ...
>     if ((totFreq+=INC)>TOTAL_LIMIT) Rescale();
>     ...
>
> o0c_v1.inc:
>     #define  BOT       (1<<16)
>     ...
>     if ( SummFreq>BOT ) rescale();
>     ...

И это тоже, но не в такой степени.

> О существенных я ничего не говорил. Они похожи примерно как
> программа с глюком и уже без него. Причем твоя реализация
> больше похожа на первый случай :). Кроме вышеотквоченного
> отличие состоит в totFreq=1 перед суммированием в него всех
> частот (чтобы глюк в assert'е не всплывал? :) и в существенно
> иной реализации rescale(). Так после замены
>
>     if (!(tree[127+sym]>>=1)) tree[127+sym]=1;
> на
>     tree[127+sym]-=tree[127+sym]>>1;
>
> , как у Димы, твоя модель наконец начала давать чуть лучшие
> (o0c=3097204,vs=3097178) результаты (до этого были примерно
> настолько же худшие).

Согласен.

> И это еще не все, т.к. используемая
> статистика явно продолжает различаться.
>    Btw, я не смог понять, зачем ты хранишь
> в дереве счетчики всех 256-ти символов? Ведь даже твои
> же if'ы, суммирующие cumFreq, половину из них не используют...

Hапиши по-другому - я же не против.

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

Ансамбль оценок вероятностей остается прежним => та же модель.

> Hо фактически - это разные модели, т.к. генерируют разный
> код - по твоему же определению модели.

Если я такое где-то писал, извини - ошибся. (Hеужели я
такое писал?) Две статистические модели эквивалентны,
если при одинаковых параметрах на каждом шаге кодирования
дают одинаковый ансамбль вероятностных оценок. Вот способ
кодирования - другое дело.

Владимир.


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