[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive]
— 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)
[an error occurred while processing this directive][an error occurred while processing this directive]