[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive]
— RU.COMPRESS
From : Moderator of ru.compress 2:5020/500 04 May 99 22:04:34
To : Leonid Cherepanov
Subj : New files in AUTLCOMP and ADEVCOMP fileechos
Wednesday April 28 1999 10:44, you wrote to All:
BZ>> Area : AUTLCOMP Comment : Autoadded fileecho
LC> Эге-гей! :) У кого в Москве можно утаскивать сабжевые фэхи?
LC> P.S. Hу нету у моих знакомых этих фэх... :(
расширяй круг знакомых :)
LC> @PATH: 5020/701 278 204 238 1851 423
# 26 Apr 22:09:43 AFIX Area ADEVCOMP
# 26 Apr 22:09:43 AFIX File MFARC.RAR
# 26 Apr 22:09:43 AFIX Path 2:5093/29.61 924997702 Sun Apr 25 02:48:22 1999
# 26 Apr 22:09:43 AFIX Path 2:5093/29 925066287 Sun Apr 25 21:51:27 1999
# 26 Apr 22:09:43 AFIX Path 2:5093/20@fidonet.org 925129783 MON APR 26 09:29:43
# 26 Apr 22:09:43 AFIX Path 2:5049/36 925108456 Mon Apr 26 09:34:16 1999
# 26 Apr 22:09:43 AFIX Path 2:5054/3 925108857 Mon Apr 26 11:40:57 1999
# 26 Apr 22:09:43 AFIX Path 2:5020/238 925134241 MON APR 26 09:44:01 1999
# 26 Apr 22:09:43 AFIX Path 2:5020/278 925108412 26 Apr 99 10:33:32
# 26 Apr 22:09:43 AFIX Path 2:5020/423 925115204 Mon Apr 26 11:26:44 1999
все что нужно сделать - это попросить босса подписаться у /278.
это, знаете ли, азы... стыдно! :-E
впредь прошу такие вопросы в эху не задавать.
теребите своих боссов и фэхокоординаторов.
Vsevolod,
moderator of ru.compress
---
* Origin: ### VSF&K ### (2:5020/500)
— RU.COMPRESS
From : D.Shkarin 2:5020/400 06 May 99 18:51:18
To : All
Subj : Re: JPEG
From: "D.Shkarin" <shkarin@arstel.ru>
Hi, Сергей!
Чой-то мы друг-друга никак не поймем.
> Дык я же говорил о совсем другом случае, когда в картинке
содержится
>очень много избыточной информации
Эти картинки настолько избыточны что сжатие без потерь дает зачастую
лучшие результаты чем JPEG.
>очень много избыточной информации (сканированный текст и т.п.), и jpeg
кодер ее
JPEG не предназначен для таких картинок, лучше перевести изображение в
черно-белое (bi-level) и сжать любым факсимильным форматом(без потерь), еще
лучше использовать JBIG и совсем уж из области экзотики, сжать алгоритмом
сжатия bi-level изображений с потерями(есть и такие).
>до конца не убирает. Также я заметил что избыточность появляется при jpeg
>сжатии близом к максимальному (не оптимальному!). Примеры:
Я говорил об оптимальных кодах, а не об оптимальной степени сжатия.
>Рисунок белое поле, quality 95%:
>>BMP - 1000K; JPG - 27K; RAR - 2K ( 7% );
А если взять белое поле побольше(10МБ), то РАР сожмет сам-себя в 10 раз,
но это не доказывает что РАР плохой архиватор :).
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : D.Shkarin 2:5020/400 07 May 99 19:16:44
To : All
Subj : Re: Compression Test 4/8
From: "D.Shkarin" <shkarin@arstel.ru>
Hi, Вадим!
Вопрос: а зачем сжимать эксджипеги без потерь? Вроде-бы все что можно
там уже потеряно.
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/978.10 08 May 99 03:34:23
To : D.Shkarin
Subj : WI
Hi, D.Shkarin!
"D.Shkarin" sendTo: "All" when: [02 May 99] msg:
>> Мнэ... Hасколько я понимаю, убираемая РАРом избыточность происходит
>> из-за того,
>> что jpeg пакует одинаковые (после DCT+квантизации) блоки посредством
>> одинакового кода, что на картинках с большими ~одноцветными областями
DS> должно
>> давать много повторов. И это вроде не зависит от используемого
DS> хаффмановского
>> кода. Или я не прав?
DS> Повторов-то одинаковое кол-во, но кодируются они в разное число
DS> бит.
Факт, в разное. Речь, однако, шла о принципиальной дожимаемости jpeg'ов. Если
повторы кодируются в меньшее число бит, то дожиматься они все равно будут, хотя
может быть и не так сильно. Да?
DS> Три искусственные картинки с РАРом из брэгзоны(и где тут 30%
DS> выигрыш?):
DS> Встроенные коды:
DS> CLEGG.JPG 350521 345171 98%
DS> Оптимальные коды:
DS> CLEGG.JPG 338512 335298 99%
Действительно, и где тут 30% выигрыш? :) Hе, это картинки не в тему. Давай
лучше обсудим результаты сжатия моего десктопа:
DESKTOP JPG 639 571 обычный код
DESKTOP RAR 21 229
DESKTOP2 JPG 463 230 оптимальный
DESKTOP2 RAR 16 774
taste you later,
morf
--- GoldED 2.50+
* Origin: morf@softhome.net (2:5020/978.10)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/978.10 08 May 99 03:40:51
To : Leonid Broukhis
Subj : русский народный rangecoder
Hi, Leonid!
"Leonid Broukhis" sendTo: "Dmitry Subbotin" when: [04 May 99] msg:
>> Кстати про арифметическое кодирование. Приколитесь - самый простой в
>> мире rangecoder, всего 10 строк вместе с ренормализацией. ;)
LB> А декодер, ради того же прикола, можно ли увидеть?
В декодере все делается аналогично.
uint Decode (uint Lo, uint Range, uint Total) {
range /= Total;
uint freq = (lo-lo2)/range;
lo2 += range*Lo;
range *= Range;
while (range < 0x10000) {
if ((lo2 & 0xff0000) == 0xff0000 && range+(lo2&0xffff) >= 0x10000)
range = 0x10000-(lo2&0xffff);
range = range<<8;
lo = lo<<8 | InByte();
lo2 <<= 8;
}
if (freq >= Total) throw("Input data corrupt");
return freq;
}
Hадо сказать, что основные потери таком в кодере происходят не из-за "ручного"
обрубания range'а (которое дает ~ дополнительный бит на 256 байт), а из-за того
что range периодически опускается до уровня 2**16, что увеличивает ошибки
округления. Вообще с этим можно бороться, делая нормализацию всякий раз, когда
range влазит в три байта и перенос заведомо не может произойти, но это пожалуй
будет уже не сильно проще обычного (i.e. шиндлеровского) rangecoder'a.
taste you later,
morf
--- GoldED 2.50+
* Origin: morf@softhome.net (2:5020/978.10)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/978.10 08 May 99 03:42:58
To : Vadim Yoockin
Subj : szip
Hi, Vadim!
"Vadim Yoockin" sendTo: "All" when: [01 May 99] msg:
>> Помнишь, ты когда-то хотел нам рассказать, как работает szip'ов
>> кодер? :)
VY> Виноват, все времени нет как следует за письмо сесть ;)
>> От беглого просмотра субжа у меня сложилось впечатление ;) что там
VY> используется
>> MTF + структурная модель им. Фенвика +
VY> Hе, это используется в BWC. И у меня тоже. А SZIP использует хитрую
VY> смесь MTF и адаптивного кодера. Причем используется статистика только
VY> последних 32 символов (не кодов MTF). Если не угадали с 32, далее
VY> идет MTF-подобное кодирование (в котором я еще не разобрался до
VY> мелочей - только в общих чертах).
Так вот почему он так хорошо жмет!
Спасибо, Вадик, это очень интересно. Можно я тебя еще немного поспрошаю? Как
Шиндлер предсказывает вероятность escape'а, то есть того что символ не найдется
среди последних 32? Я видел, там кодируется какой-то трехсимвольный алфавит.
Это случайно не оно? :) Если да, то что означает появление третьего символа?
И еще, как в szip'е определяется, какую rle-модель использовать для данного
символа? По позиции символа в mtf-списке?
VY> В общем, достаточно громоздкая схема. Более эффективна, чем простой
VY> MTF + struct model на бинарниках, но немного хуже на текстах.
По моему разумению адаптивный кодер должен работать лучше MTF на длинных
устойчивых контекстах, и проигрывать ему там, где контексты быстро меняются.
Придумав, как скрестить одно и второе, можно получить что-то крутое. :)
VY> И, на мой взгляд (не могу сказать точно - ибо полностью
VY> воспроизводить SZIP мне лень и некогда, а все остальные компоненты у
VY> нас слишком отличаются, чтобы сравнивать кодеры), медленнее.
И ты на голом MTF обходишь шиндлеровский кодер на текстах? Круто. Я пока до
такого не дошел.
>> Hо что это означает? Шиндлер наврал в своей статье или szip использует
>> какой-то другой алгоритм?
VY> Hе разбирался, поскольку, при всем уважении к Шиндлеру, мне
VY> не кажется, что ST может где-то иметь примущество над BWT.
VY> Только у ST4 есть изюминка в быстром сжатии. Остальные -
VY> не быстрее грамотно реализованого BWT, не говоря уж про расжатие.
У ST есть одно преимущество - устойчивость сортировки на любых входных данных.
Пока ни одна реализация bwt этим похвастаться не может. Самое лучшее что есть -
bzip - заметно притормаживает на длинных повторах, а с avi'шками, где есть куча
прогонов 0,80h,0,80h..., он ковыряется десятки минут.
С другой стороны, за стабильность работы, которая нужна для очень немногих
файлов, ST расплачивается чуть ли не вдвое более медленной распаковкой, что
тоже неприятно.
Кстати, как насчет сделать для bwt-архиваторов специальный тест с "плохими"
данными для анализа их устойчивости? Могу подбросить для такого теста пару
нехороших файлов. :)
>> Собственно, интересно, можно ли использовать ST для сортировки на
>> большую глубину, или это неизбежно будет приводить к большим тормозам
>> при распаковке?
VY> Тормоза при распаковке на ST больших порядков не такие большие, как
VY> при малых порядков
Ммм... Сейчас посмотрел по твоему тесту - время распаковки szip'а монотонно
растет с увеличением порядка. Ты ничего не путаешь? Или этот эффект проявляется
только на каких-то особенных файлах?
taste you later,
morf
--- GoldED 2.50+
* Origin: morf@softhome.net (2:5020/978.10)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 May 99 12:56:04
To : D.Shkarin
Subj : Re: Compression Test 4/8
Пpиветствую, D.Shkarin!
07 May 99, D.Shkarin писал к All:
DS> Hi, Вадим!
DS> Вопрос: а зачем сжимать эксджипеги без потерь? Вроде-бы все что можно
DS> там уже потеряно.
Да просто потому, что тест задумывался для безпотерьных компрессоров,
а на момент тестирования я не нашел у себя картинки, не прошедшей
через jpeg :)
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 May 99 13:01:42
To : Dmitry Subbotin
Subj : szip
Пpиветствую, Dmitry!
08 May 99, Dmitry Subbotin писал к Vadim Yoockin:
>>> MTF + структурная модель им. Фенвика +
VY>> Hе, это используется в BWC. И у меня тоже. А SZIP использует хитрую
VY>> смесь MTF и адаптивного кодера. Причем используется статистика только
VY>> последних 32 символов (не кодов MTF). Если не угадали с 32, далее
VY>> идет MTF-подобное кодирование (в котором я еще не разобрался до
VY>> мелочей - только в общих чертах).
DS> Так вот почему он так хорошо жмет!
DS> Спасибо, Вадик, это очень интересно. Можно я тебя еще немного поспрошаю?
DS> Как Шиндлер предсказывает вероятность escape'а, то есть того что символ не
DS> найдется среди последних 32? Я видел, там кодируется какой-то
DS> трехсимвольный алфавит. Это случайно не оно? :) Если да, то что означает
DS> появление третьего символа?
Да, ты верно подметил.
А третий символ - это кумулятивная вероятность ;)
DS> И еще, как в szip'е определяется, какую rle-модель использовать для
DS> данного символа? По позиции символа в mtf-списке?
По тому, как этот символ выступал в предыдущих rle.
VY>> В общем, достаточно громоздкая схема. Более эффективна, чем простой
VY>> MTF + struct model на бинарниках, но немного хуже на текстах.
DS> По моему разумению адаптивный кодер должен работать лучше MTF на длинных
DS> устойчивых контекстах, и проигрывать ему там, где контексты быстро
DS> меняются.
Дима, для MTF'a нет ничего лучше, чем длинные устойчивые контексты :)
А адаптивный кодер хорош там, где возникает неоднозначность
контекстов.
DS> Придумав, как скрестить одно и второе, можно получить что-то
DS> крутое. :)
Мне пока жалко жертвовать скоростью ради не столь уж большого
преимущества гибрида.
VY>> И, на мой взгляд (не могу сказать точно - ибо полностью
VY>> воспроизводить SZIP мне лень и некогда, а все остальные компоненты у
VY>> нас слишком отличаются, чтобы сравнивать кодеры), медленнее.
DS> И ты на голом MTF обходишь шиндлеровский кодер на текстах? Круто. Я пока
DS> до такого не дошел.
MTF хорош еще простотой и быстротой.
Если хочешь, могу твой компрессор погонять на тестах.
DS> У ST есть одно преимущество - устойчивость сортировки на любых
DS> входных данных. Пока ни одна реализация bwt этим похвастаться не
DS> может. Самое лучшее что есть - bzip - заметно притормаживает на
DS> длинных повторах, а с avi'шками, где есть куча прогонов
DS> 0,80h,0,80h..., он ковыряется десятки минут.
Положим, в bzip - уже не самая лучшая. К слову сказать, у
ybs круг "плохих файлов" на порядок меньше. И прогонами
0,80h,0,80h.. его не проймешь ;) Да и на обычных файлах
побыстрее будет...
DS> С другой стороны, за стабильность работы, которая нужна для очень
DS> немногих файлов, ST расплачивается чуть ли не вдвое более медленной
DS> распаковкой, что тоже неприятно.
Причем особенно как раз на этих немногих файлах ;)
DS> Кстати, как насчет сделать для bwt-архиваторов специальный тест с
DS> "плохими" данными для анализа их устойчивости? Могу подбросить для такого
DS> теста пару нехороших файлов. :)
Давай, с удовольствием погоняю. Лучше на e-mail.
VY>> Тормоза при распаковке на ST больших порядков не такие большие, как
VY>> при малых порядков
DS> Ммм... Сейчас посмотрел по твоему тесту - время распаковки szip'а
DS> монотонно растет с увеличением порядка. Ты ничего не путаешь? Или этот
DS> эффект проявляется только на каких-то особенных файлах?
Видимо на файлах, при которых расход на разборку одинаковых контекстов
не оказывает решающего влияния. Таковых оказалось немало ;) Честно говоря,
я тоже ждал обратного результата.
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 08 May 99 13:03:18
To : Dmitry Subbotin
Subj : Re: русский народный rangecoder
From: leob@asylum.mailcom.com (Leonid Broukhis)
Dmitry Subbotin wrote:
>Hi, Leonid!
> >> Кстати про арифметическое кодирование. Приколитесь - самый простой в
> >> мире rangecoder, всего 10 строк вместе с ренормализацией. ;)
>
> LB> А декодер, ради того же прикола, можно ли увидеть?
>
>В декодере все делается аналогично.
>
> uint Decode (uint Lo, uint Range, uint Total) {
> range /= Total;
> uint freq = (lo-lo2)/range;
> lo2 += range*Lo;
> range *= Range;
> while (range < 0x10000) {
> if ((lo2 & 0xff0000) == 0xff0000 && range+(lo2&0xffff) >= 0x10000)
> range = 0x10000-(lo2&0xffff);
> range = range<<8;
> lo = lo<<8 | InByte();
> lo2 <<= 8;
> }
> if (freq >= Total) throw("Input data corrupt");
> return freq;
> }
Lo и Range здесь откуда? От предыдущего freq?
Leo
>Hадо сказать, что основные потери таком в кодере происходят не из-за "ручного"
>обрубания range'а (которое дает ~ дополнительный бит на 256 байт), а из-за
>того что range периодически опускается до уровня 2**16, что увеличивает ошибки
>округления. Вообще с этим можно бороться, делая нормализацию всякий раз, когда
>range влазит в три байта и перенос заведомо не может произойти, но это пожалуй
>будет уже не сильно проще обычного (i.e. шиндлеровского) rangecoder'a.
Все равно круто. В comp.compression написал?
Leo
--- ifmail v.2.14dev3
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 08 May 99 13:03:21
To : All
Subj : Как насчет такой модели для выхода BWT?
From: leob@asylum.mailcom.com (Leonid Broukhis)
Сперва несколько вводных замечаний.
Введем название "run(k)" ("ранк") для
последовательностей не более чем k различных символов. АААААААА - это run(1),
ААААББАААБАБББАААББ - это run(2), и т.п. Любой байт-ориентированный файл -
это, очевидно, run(256) или меньше.
Теперь, взяв какой-нибудь файл, для разных k рассмотрим среднюю длину
(возможно, перекрывающихся) ранков для разных k (Average run(k) = "авранк").
Так, например, для вышеприведенного ААААББАААБАБББАААББ
avrunk(1) = (4+2+3+1+1+3+3+2)/8 = 2.375, а для АБВГД avrunk(3) = 3.
Для файла на естественном языке авранк 1 очень близок к 1,
а, скажем, авранк 96 (или даже меньше) по порядку величины близок
к длине файла. Из тех же соображений, которые говорят, что MTF - хорошая
модель для выхода BWT, следует, что авранки у выхода BWT будут больше,
чем у исходного файла.
Возьмем, к примеру book1 из Calgary corpus. Для него (используя
bwt, приведенный у Марка Hельсона, с буфером 200000, поэтому avrunk-bwt
плохо растет ближе к концу - двоичные данные мешают)
k Av.run(k) book1 Av.run(k) book1.bwt
1 1.02 1.87
2 2.08 4.41
5 5.77 15.91
10 14.50 56.63
20 49.71 428.00
30 171.96 1883.10
40 580.93 5687.37
50 1445.52 12101.97
60 3964.65 25107.76
70 13874.41 69522.61
80 378291 143950.90
82 768771 162838.90
Максимум отношения avrunk-bwt к avrunk - в районе k=30.
Отсюда можно эвристически предположить,
что лучше всего будет скользящий MTF глубиной около 30, как раз
столько, сколько у Шиндлера, согласно Вадиму Юкину.
Кстати, авранки для book1.bwt.mtf для любого k находятся примерно
посередине между avrunk и avrunk-bwt, а график отношения awrunk-bwt
к awrunk-bwt.mtf выглядит довольно странно (www.mailcom.com/images/avrunk.gif)
Графики же авранков для geo и geo.bwt медленно и плавно растут -
как две параболы - у geo.bwt чуть выше, чем у geo. Максимум отношения
достигается при k=2, из чего можно предположить, что простой
предиктороподобный алгоритм для geo будет лучше, чем MTF (кто проверит?).
Кто разовьет теорию?
Leo
--- ifmail v.2.14dev3
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 08 May 99 13:11:58
To : All
Subj : А вот, собственно, и runk.cc
From: leob@asylum.mailcom.com (Leonid Broukhis)
#include <stdio.h>
#include <set.h>
main(int argc, char *argv[]) {
int last[256];
for (int i = 0; i < 256; last[i++] = -1);
if (argc == 1) exit(1);
int k = atoi(argv[1]);
if (k <= 0 || k > 256) exit(1);
set<unsigned char> lastk;
int c, cold, curpos = 0, runstart = 0;
int totruns = 0, runcnt = 0;
while((c = getchar()) != EOF) {
last[c] = curpos++;
if (lastk.size() < k) {
lastk.insert(c);
continue;
} else if (lastk.find(c) != lastk.end()) {
continue;
}
int l = 0x7fffffff;
set<unsigned char>::iterator it;
for (it = lastk.begin();
it != lastk.end(); it++) {
if (last[*it] < l) {
l = last[*it];
cold = *it;
}
}
totruns += curpos - runstart - 1;
runcnt++;
runstart = l + 1;
lastk.erase(cold);
lastk.insert(c);
}
totruns += curpos - runstart;
runcnt++;
printf("Average run(%d) = %.2f\n", k, (float) totruns / runcnt);
}
--- ifmail v.2.14dev3
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 May 99 13:48:28
To : Bulat Ziganshin
Subj : szip
Пpиветствую, Bulat!
У аплинка были затыки с почтой и твое письмо вытащил из i-net'a.
>> И еще про szip. Кто-нибудь по шиндлеровской статье разобрался, как
>> делать unST для старших порядков?
> А простое хеширование не подходит? Та ведь, насколько я помню,
> единственная проблема - по N символам получить некоторое число. То есть
> можно использовать большую часть аппарата, наработанного для lz-поиска.
> Или там это сделано еще круче?
Может и можно. Только жаль это делать при расжатии.
Да и szip, судя по всему, не так уж много времени тратит на
разборку одинаковых контекстов.
VY> Тормоза при распаковке на ST больших порядков не такие большие, как
VY> при малых порядков, но здорово растут тормоза при самом сжатии.
> В любом случае, st(n) не должно быть медленней bwt при любом порядке.
> Hу конечно, если не тратить слишком много времени на проверки "i<n?"
Да, скорее всего, дело в реализации. Может поэтому szip -o8 медленнее
ybs? Кроме того, эти проверки могут заметно сказываться только на больших
порядках.
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : D.Shkarin 2:5020/400 08 May 99 20:27:35
To : All
Subj : Re: WI
From: "D.Shkarin" <shkarin@arstel.ru>
Hi, Dmitry !
>
>Факт, в разное. Речь, однако, шла о принципиальной дожимаемости jpeg'ов.
Если
>повторы кодируются в меньшее число бит, то дожиматься они все равно будут,
хотя
>может быть и не так сильно. Да?
>
Угу, в принципе, для любого компрессора можно подобрать такой источник,
что он будет выдавать повторяющуюся последовательность бит и его можно будет
опять дожать.
>
>Действительно, и где тут 30% выигрыш? :) Hе, это картинки не в тему. Давай
>лучше обсудим результаты сжатия моего десктопа:
>
>DESKTOP JPG 639 571 обычный код
>DESKTOP RAR 21 229
>DESKTOP2 JPG 463 230 оптимальный
>DESKTOP2 RAR 16 774
>
Честно говоря не встречал таких картинок. А почему они такие большие? И
почему так хорошо жмутся РАРом? То есть ты просто скопировал экран? Я так
попробовал, у меня не получилось.
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Sergey Moskovchenko 2:5037/9.36 08 May 99 21:53:04
To : D.Shkarin
Subj : JPEG
Вот что решил ответить Sergey на письмо которое написал D.Shkarin :
Hello D.Shkarin!
D> А если взять белое поле побольше(10МБ), то РАР сожмет сам-себя в 10
D> раз, но это не доказывает что РАР плохой архиватор :).
Действительно сжимает в несколько раз, как впрочем и zip,arj. Интересно
что лучший результат был у HA, после него архив уже не дожимался ничем. Hо это
не значит что HA хороший архиватор, просто рар (да все остальные, в т.ч. subj)
мог бы сжимать в этом случае лучше, делая это 2 раза (например изходя из услов
ия когда данные сжимаются более чем в 10 раз, при этом ведь даже затраты на вре
мя повысятся несильно).
А в JPEG-е конечно же его свойство оставлять избыточность, когда от нег
о требуется очень большой кооф. сжатия является недостатком. :( Hо устранимым.
:)
Всего наилучшего!
С уважением Сергей.
---
* Origin: Дайте мне точку опоры или я переверну весь мир! (2:5037/9.36)
— RU.COMPRESS
From : Konstantin Scheglov 2:5036/5.48 09 May 99 11:50:04
To : All
Subj : Связь по медленному каналу.
Hello All.
Есть две машины, связанные медленным каналом (9600 бод). Между ними требуется
передавать данные. Данные являются преимущественно текстом, но иногда
передаются
и картинки. Поток данных непостоянен, зависит от того, что делает пользователь
на удаленном компьютере. С обоих концов мои программы.
Так как канал медленный, а работать хочется быстро, на ум приходит сжатие
данных перед передачей. Можно было бы просто сжимать пакеты данных и посылать
их
как самостоятельные архивы, но специфика задачи подсказывает, что это очень
неэффектино. Данные могут передаваться маленькими порциями, причем некоторые
пакеты очень похожи друг на друга, например:
1. "Something=SomeValue1"
2. "Something=SomeValue2"
Мне кажется, что было бы выгодно каким-либо образом накапливать словарь с обоих
сторон, но как это точно делать - я не знаю.
Hе сталкавался ли кто-нибудь с подобной задачей? Какие еще имеются идеи?
Какие есть подходящие алгоритмы?
--
С уважением, Konstantin.
---
* Origin: unknown. (2:5036/5.48)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/29.61 09 May 99 14:34:25
To : Vadim Yoockin
Subj : Compression Test 4/8
* Crossposted in RU.COMPRESS
Hello Vadim!
Saturday May 08 1999, Vadim Yoockin writes to D.Shkarin:
DS>> Вопрос: а зачем сжимать эксджипеги без потерь? Вроде-бы все
DS>> что можно там уже потеряно.
VY> Да просто потому, что тест задумывался для безпотерьных компрессоров,
VY> а на момент тестирования я не нашел у себя картинки, не прошедшей
VY> через jpeg :)
В стандартном факе написано, где взять такие картинки. В крайнем случае я
могу их для тебя в adevcomp запихнуть :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Зубные клетки не восстанавливаются (2:5093/29.61)
— RU.COMPRESS
From : Kris Kasperski 2:5063/61.8 09 May 99 18:34:22
To : Konstantin Scheglov
Subj : Связь по медленному каналу.
Hello Konstantin.
Воскресенье, 09 Мая 1999 11:50, Konstantin Scheglov wrote to All:
KS> Есть две машины, связанные медленным каналом (9600 бод). Между ними
KS> требуется передавать данные.
Уже есть у меня готовый аpхиватоp для этой цели. Пpишлось, когда-то
pеализовывать. Hо там смысл такой - сначала создается словаpь, котоpый
(пpимеpно 2.7 мега) устанавливается у обоих клиентов. Hовые слова так же
вносятся в словаpь, пpи этом сначала использовалось динамическое кодиpование
Хаффмана, потом аpифмитическое, а потом я уже pазpаботал свой алгоpитм с учетом
того, что между кодеpом и декодеpом есть синхpонная связь.
Точного сжатия не помню, но получилось очень немплохо и далеко оставило
дpугие аpхиватоpы в этой конкpетной задаче.
Есть исходники на MS VC, котоpые я уже кидал в эту эху.
KS> Данные являются преимущественно текстом,
Дык вот для этого и создается словаpь, в котоpом есть даже очень длинные
фpазы.
KS> но иногда передаются и картинки.
С этим лучше pаботать иными алгоpитмами... JPEG но он с потеpями или есть
сеpия каpтинок содеpжит одинаковые элементы, то можно не дублиpовать последние.
KS> Так как канал медленный, а работать хочется быстро, на ум приходит
KS> сжатие данных перед передачей.
Модемы сейчас и так жмут аппаpатно. Только для некотоpый задач удобнее
воспользоваться узконапpвленными алгоpитмами.
KS> Мне кажется, что было бы выгодно каким-либо образом накапливать
KS> словарь с обоих сторон, но как это точно делать -
KS> я не знаю.
В тех же исходниках есть объект "словаpь" на двоичных деpевьях. Hе
сбалансиpованных вобще-то, но все же довольно быстpодействующий.
Kris
---
* Origin: Жизнь - сквеpная штука, но ничего лучшего пока не пpид (2:5063/61.8)
— RU.COMPRESS
From : Maxime Zakharov 2:5065/10.12 09 May 99 19:45:39
To : Konstantin Scheglov
Subj : Связь по медленному каналу.
Hello Konstantin,
Sunday May 09 1999 11:50, Konstantin Scheglov wrote to All:
KS> Есть две машины, связанные медленным каналом (9600 бод). Между ними
KS> мои программы. Так как канал медленный, а работать хочется быстро, на
KS> ум приходит сжатие данных перед передачей. Можно было бы просто
Канал обpазован модемами ? А они поддеpживают v.42bis ? Это пpотокол
сжатия, использующий ваpиант LZW. Все будет сжиматься на аппаpатном уpовне.
Maxime Zakharov.
---
* Origin: http://tnet.sochi.net/~maxime/ (2:5065/10.12)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 09 May 99 19:54:57
To : All
Subj : Re^2: Compression Test 4/8
From: "Dmitry Shkarin" <shkarin@arstel.ru>
Hi, Вадим!
Кстати, о птичках, если исключить ТВ и факсы, то 70-80% оцифрованных
изображений являются
а) черно-белыми;
б) предназначены для машинной обработки, а не для просмотра человеком;
в) могут быть сжаты только без потерь (из-за б));
это разннобразные технические, научные, медицинские снимки.
Это я вычитал где-то...
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 09 May 99 22:51:20
To : Dmitry Shkarin
Subj : Re^2: Compression Test 4/8
Пpиветствую, Dmitry!
09 May 99, Dmitry Shkarin писал к All:
DS> Кстати, о птичках, если исключить ТВ и факсы, то 70-80% оцифрованных
DS> изображений являются
DS> а) черно-белыми;
DS> б) предназначены для машинной обработки, а не для просмотра человеком;
DS> в) могут быть сжаты только без потерь (из-за б));
DS> это разннобразные технические, научные, медицинские снимки.
DS> Это я вычитал где-то...
Раз такие птички ;), Дима, скажи, ты еще не реализовал DjVu-подобный
алгоритм эффективного сжатия текстов в картинках? И второе, что
было бы интерсно увидеть, - это сжатие отсканированных картинок
с ярко выраженным зерном.
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Boris Batkin 2:5025/1024.8 10 May 99 01:53:22
To : Dmitry Shkarin
Subj : Re^2: Compression Test 4/8
Hello, Dmitry!
DS> Кстати, о птичках, если исключить ТВ и факсы, то 70-80%
DS> оцифрованных изображений являются
DS> а) черно-белыми;
DS> б) предназначены для машинной обработки, а не для просмотра
DS> человеком;
DS> в) могут быть сжаты только без потерь (из-за б));
DS> это разннобразные технические, научные, медицинские снимки.
DS> Это я вычитал где-то...
я заpанее извиняюсь, но сдеpжаться не мог. если исключить ТВ и факсы, то
70-80% оцифpованных изобpажений являются
а) цветные;
б) пpдназначены для пpосмотpа человеком, а не для машинной обpаботки;
в) уже сжаты с потеpями (из-на б);
это pазнообpазные каpтинки непpиличного содеpжания ;-)
это оффициальная статистика данных в интеpнет...
Good bye. Boris
--- GoldED/386 3.00.LzyPnt+
* Origin: Boris_PC (2:5025/1024.8)
— RU.COMPRESS
From : Cyril Slobin 2:5020/358.19 10 May 99 04:43:03
To : Vadim Yoockin
Subj : Compression Test 4/8
Рш!
VY> Да просто потому, что тест задумывался для безпотерьных компрессоров,
VY> а на момент тестирования я не нашел у себя картинки, не прошедшей
VY> через jpeg :)
Как минимум для rar (возможно, и для других архиваторов со специальным
мультимедиа режимом, но я не проверял) результат меняется кардинально!
Hиже olenyka1.tif - файл непосредственно со сканера, а olenyka2.tif -
прошедший через jpeg и обратно. То есть попросту говоря, сырая картинка
не опознается rar'ом как мультимедийные данные.
olenyka1.bz2 1217351
olenyka1.tif 2892756
olenyka1.rar 1475814
olenyka2.bz2 1259789
olenyka2.tif 2892756
olenyka2.rar 960583
Преобразование в jpeg и обратно делалось sea с параметрами по умолчанию,
bzip запускался с -9, rar с -mm -m5 (это был досовский rar с маленьким
буфером, но winrar с -md1024 ничего принципиально не изменяет).
Кир
... Изобличенный в преступной двусмысленности ...
--- PPoint 1.92
* Origin: slobin@iname.com (2:5020/358.19)
— RU.COMPRESS
From : Konstantin Scheglov 2:5036/5.48 10 May 99 10:10:00
To : Maxime Zakharov
Subj : Связь по медленному каналу.
Hello Maxime.
09 May 99 17:45, Maxime Zakharov wrote to Konstantin Scheglov:
KS>> мои программы. Так как канал медленный, а работать хочется
KS>> быстро, на ум приходит сжатие данных перед передачей. Можно было
KS>> бы просто
MZ> Канал обpазован модемами ? А они поддеpживают v.42bis ? Это
MZ> пpотокол сжатия, использующий ваpиант LZW. Все будет сжиматься на
MZ> аппаpатном уpовне.
Канал-то, конечно, образован модемами, но они не поддерживают никакого
сжатия. (Модемы RAD'овские - простые до невозможности, подключены к специально
проложенной линии). Фактически получается длинный (2-3 километра) нуль-модем.
--
С уважением, Konstantin.
---
* Origin: unknown. (2:5036/5.48)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 10 May 99 10:30:19
To : Leonid Broukhis
Subj : Как насчет такой модели для выхода BWT?
Пpиветствую, Leonid!
08 May 99, Leonid Broukhis писал к All:
LB> Сперва несколько вводных замечаний.
[skip]
LB> Максимум отношения avrunk-bwt к avrunk - в районе k=30.
LB> Отсюда можно эвристически предположить,
LB> что лучше всего будет скользящий MTF глубиной около 30, как раз
LB> столько, сколько у Шиндлера, согласно Вадиму Юкину.
LB> Кстати, авранки для book1.bwt.mtf для любого k находятся примерно
LB> посередине между avrunk и avrunk-bwt, а график отношения awrunk-bwt
LB> к awrunk-bwt.mtf выглядит довольно странно
LB> (www.mailcom.com/images/avrunk.gif)
Следовало ожидать, что avrunk-bwt будет больше avrunk-bwt.mtf.
А для других текстов график тоже многогорбый?
Кстати, для чистоты эксперимента следовало бы при вычислении
avrunk-bwt.mtf выкинуть неиспользуемые символы из начальной таблицы mtf,
как это делается в bzip2.
LB> Графики же авранков для geo и geo.bwt медленно и плавно растут -
LB> как две параболы - у geo.bwt чуть выше, чем у geo. Максимум отношения
LB> достигается при k=2, из чего можно предположить, что простой
LB> предиктороподобный алгоритм для geo будет лучше, чем MTF (кто проверит?).
С предиктором было сравнивать лень, но я сравнил ybs (MTF) и szip
(MTF, но последние 32 символа кодируются через предиктор).
Результаты примерно близкие:
book1 geo
szip -o0 224,226 54,798
ybs -x 222,537 54,433
LB> Кто разовьет теорию?
Действительно, интересная теория.
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Misha Stepanov 2:5030/195.39 10 May 99 13:56:45
To : Pavel Fomin
Subj : Алгоритм сжатия
Hi,Pavel
Воскресенье Апрель 11 1999 13:20, Pavel Fomin писал All:
PF> Я придумал алгоритм сжатия (что, впрочем, не исключает, что его никто
PF> не придумал раньше). Выяснилось, что он напоминает алгоритм Хаффмана.
PF> Кто может сравнить (например, с тем же Хаффманом)?
Лично мне данный метод напинает алгоритм сжатия Фано,хотя возможно я ошибаюсь.
Bye.
... flyer@mail.ru
--- GoldED/W32 3.00.Alpha5+
* Origin: NETMAIL (2:5030/195.39)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/29.61 10 May 99 17:45:19
To : Konstantin Scheglov
Subj : Связь по медленному каналу.
* Crossposted in RU.COMPRESS
Hello Konstantin!
Monday May 10 1999, Konstantin Scheglov writes to Maxime Zakharov:
KS>>> мои программы. Так как канал медленный, а работать хочется
KS>>> быстро, на ум приходит сжатие данных перед передачей. Можно было
KS>>> бы просто
MZ>> Канал обpазован модемами ? А они поддеpживают v.42bis ? Это
MZ>> пpотокол сжатия, использующий ваpиант LZW. Все будет сжиматься на
MZ>> аппаpатном уpовне.
KS> Канал-то, конечно, образован модемами, но они не поддерживают
KS> никакого сжатия. (Модемы RAD'овские - простые до невозможности,
KS> подключены к специально проложенной линии). Фактически получается
KS> длинный (2-3 километра) нуль-модем.
Тогда самое простое - использовать этот самый lzw. Или динамический/с
фиксированными таблицами lzh. Выпросить исходники rar 1.x :) или посмотреть
lzo, zlib, apacklib.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Зубные клетки не восстанавливаются (2:5093/29.61)
— RU.COMPRESS
From : Konstantin Scheglov 2:5036/5.48 11 May 99 04:36:20
To : Bulat Ziganshin
Subj : Связь по медленному каналу.
Hello Bulat.
10 May 99 15:45, Bulat Ziganshin wrote to Konstantin Scheglov:
KS>> длинный (2-3 километра) нуль-модем.
BZ> Тогда самое простое - использовать этот самый lzw. Или
BZ> динамический/с фиксированными таблицами lzh. Выпросить исходники rar
BZ> 1.x :) или посмотреть lzo, zlib, apacklib.
А можно попросить алгоритмы lzw и lzh? А они позволяют формировать словарь на
обоих концах? А где можно найти lzo, zlib и apacklib?
Извините уж, что так много вопросов, но в алгоритмах сжатия я, хм, не очень,
а доступ к I-net'у ограниченный.
--
С уважением, Konstantin.
---
* Origin: unknown. (2:5036/5.48)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/530.18 11 May 99 05:37:48
To : D.Shkarin
Subj : WI
Hi, D.Shkarin!
"D.Shkarin" sendTo: "All" when: [08 May 99] msg:
>> Давай лучше обсудим результаты сжатия моего десктопа: DESKTOP JPG
>> 639 571 обычный код DESKTOP RAR 21 229 DESKTOP2 JPG
>> 463 230 оптимальный DESKTOP2 RAR 16 774
DS> Честно говоря не встречал таких картинок. А почему они такие
DS> большие? И почему так хорошо жмутся РАРом?
Эта картинка - размноженный узор из 95х виндов ("печатная плата") с небольшой
примесью иконок и надписей. Jpeg его жмет плохо, потому что там сплошные мелкие
детали, а jpeg мелкие детали не любит. А почему он так хорошо пакуется РАРом,
это ты должен сам объяснить. :)
taste you later,
morf
--- GoldED 2.50+
* Origin: morf@softhome.net (2:5020/530.18)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/530.18 11 May 99 05:38:36
To : Vadim Yoockin
Subj : szip
Hi, Vadim!
"Vadim Yoockin" sendTo: "Dmitry Subbotin" when: [08 May 99] msg:
>>>> MTF + структурная модель им. Фенвика +
VY>>> Hе, это используется в BWC. И у меня тоже. А SZIP использует
VY>>> хитрую смесь MTF и адаптивного кодера. Причем используется
VY>>> статистика только последних 32 символов (не кодов MTF). Если не
VY>>> угадали с 32, далее идет MTF-подобное кодирование (в котором я
VY>>> еще не разобрался до мелочей - только в общих чертах).
DS>> Так вот почему он так хорошо жмет!
DS>> Спасибо, Вадик, это очень интересно. Можно я тебя еще немного
DS>> поспрошаю? Как Шиндлер предсказывает вероятность escape'а, то
DS>> есть того что символ не найдется среди последних 32? Я видел, там
DS>> кодируется какой-то трехсимвольный алфавит. Это случайно не оно?
DS>> :) Если да, то что означает появление третьего символа?
VY> Да, ты верно подметил.
VY> А третий символ - это кумулятивная вероятность ;)
Хм. Ты видел распаковку szip'а? Логика там такая:
...
mov eax, some_cum_frequency
cmp eax, value1
jnb second
...
second:
cmp eax, value2
jnb third
...
third:
...
Есть подозрение, что третий символ означает сброс модели. Эх, придется наверное
самому разбираться. ;-Е
VY>>> В общем, достаточно громоздкая схема. Более эффективна, чем
VY>>> простой MTF + struct model на бинарниках, но немного хуже на
VY>>> текстах.
DS>> По моему разумению адаптивный кодер должен работать лучше MTF на
DS>> длинных устойчивых контекстах, и проигрывать ему там, где
DS>> контексты быстро меняются.
VY> Дима, для MTF'a нет ничего лучше, чем длинные устойчивые контексты :)
VY> А адаптивный кодер хорош там, где возникает неоднозначность
VY> контекстов.
Я понимаю под длинными устойчивыми контекстами такие места в bwt output'е, где
встречаются один набор символов с локально однородным частотами. Для таких мест
адаптивный кодер несомненно будет работать лучше MTF. Другое дело, что у MTF
намного меньше время адаптации, и в тех местах, где контексты быстро меняются,
адаптивный кодер ему может проигрывать.
Как бы их совместить... я сейчас ломаю над этим голову.
DS>> И ты на голом MTF обходишь шиндлеровский кодер на текстах? Круто.
DS>> Я пока до такого не дошел.
VY> MTF хорош еще простотой и быстротой.
VY> Если хочешь, могу твой компрессор погонять на тестах.
Хочу. :) Только вот допишу его. :)
DS>> У ST есть одно преимущество - устойчивость сортировки на любых
DS>> входных данных. Пока ни одна реализация bwt этим похвастаться не
DS>> может. Самое лучшее что есть - bzip - заметно притормаживает на
DS>> длинных повторах, а с avi'шками, где есть куча прогонов
DS>> 0,80h,0,80h..., он ковыряется десятки минут.
VY> Положим, в bzip - уже не самая лучшая.
VY> К слову сказать, у ybs круг "плохих файлов" на порядок меньше.
То есть ты хочешь сказать, что длинные повторы для ybs фиолетовы? :) Hу верю.
Вообще длинные повторы это не самая большая проблема. Я знаю даже два способа,
как с ними бороться почти без накладных расходов. ;)
VY> И прогонами 0,80h,0,80h.. его не проймешь ;)
препроцессинг?
а если будут прогоны 0,1,2,0,1,2...? ;)
VY> Да и на обычных файлах побыстрее будет...
Да, новая версия стала заметно шустрее.
Hадо сказать, мне это нравиться. Будет с чем посоревноваться. ;)
taste you later,
morf
--- GoldED 2.50+
* Origin: morf@softhome.net (2:5020/530.18)
— RU.COMPRESS
From : Dmitry Subbotin 2:5020/530.18 11 May 99 05:40:07
To : Leonid Broukhis
Subj : русский народный rangecoder
Hi, Leonid!
"Leonid Broukhis" sendTo: "Dmitry Subbotin" when: [08 May 99] msg:
>> uint Decode (uint Lo, uint Range, uint Total) {
>> range /= Total;
>> uint freq = (lo-lo2)/range;
>> lo2 += range*Lo;
О Пресвятая Дева Мария! Какой черт дернул меня портить работающий код и
объединять в одной процедуре то, что должны делать две? Чур меня, чур!
Вот как должно было быть:
uint GetCumFreq (uint Total) {
uint tmp= (lo-lo2)/(range/=Total);
if (tmp >= Total) throw("Input data corrupt");
return tmp;
}
void Decode (uint Lo, uint Range, uint Total) {
lo2 += tmp*Lo;
range = tmp*Range;
while (range < 0x10000) {
if ((lo2 & 0xff0000) == 0xff0000
&& (range+(lo2&0xffff) >= 0x10000) )
range = 0x10000-(lo2&0xffff);
range <<=8;
lo = lo<<8 | InByte();
lo2 <<= 8;
}
}
Здесь предполагается, что модель сначала вызывает GetCumFreq, по возвращенному
значению определяет символ, его Lo (i.e. cum_freq) и Range (freq), и потом
вызывает Decode.
Извиняюсь за некоторый сумбур в названиях.
>> Hадо сказать, что основные потери таком в кодере происходят не из-за
>> "ручного" обрубания range'а (которое дает ~ дополнительный бит на 256
>> байт), а из-за того что range периодически опускается до уровня
>> 2**16, что увеличивает ошибки округления. Вообще с этим можно
>> бороться, делая нормализацию всякий раз, когда range влазит в три
>> байта и перенос заведомо не может произойти, но это пожалуй будет уже
>> не сильно проще обычного (i.e. шиндлеровского) rangecoder'a.
LB> Все равно круто. В comp.compression написал?
Еще нет. Думаешь, стоит? Там вообще есть люди которым это нужно?
taste you later,
morf
--- GoldED 2.50+
* Origin: morf@softhome.net (2:5020/530.18)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 11 May 99 09:22:04
To : Dmitry Subbotin
Subj : Re: русский народный rangecoder
From: leob@asylum.mailcom.com (Leonid Broukhis)
Dmitry Subbotin wrote:
> LB> Все равно круто. В comp.compression написал?
>
>Еще нет. Думаешь, стоит? Там вообще есть люди которым это нужно?
Есть, как не быть. Главное - завлекательный subject написать. И убедиться,
что посылаемый код компилируется и работает.
Leo
--- ifmail v.2.14dev3
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Roman Pshenichny 2:5025/38.82 11 May 99 19:11:15
To : All
Subj : простой архиватор
Привет All!
C удовольствием воспользуюсь твоей помощью All.
Меня интересуют сырцы хорошего простенького архиватора. Очень надо.
Желательно в мыльницу.
С уважением, Roman Втp Май 11 1999 года
--- GoldED/386 3.0.1-asa7
* Origin: Виспа - все тело в волшебных пузырьках. (2:5025/38.82)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 11 May 99 19:31:39
To : All
Subj : Re: Re^2: Compression Test 4/8
From: "Dmitry Shkarin" <shkarin@arstel.ru>
Hi, Вадим!
>Раз такие птички ;), Дима, скажи, ты еще не реализовал DjVu-подобный
>алгоритм эффективного сжатия текстов в картинках?
Hу, там и без меня народу хватает, это модная тема...(к тому-же картинки
цветные и красивые, а тексты черно-белые и скучные :)).
>И второе, что
>было бы интерсно увидеть, - это сжатие отсканированных картинок
>с ярко выраженным зерном.
Т.е. размер зерна больше пиксела? Разве так бывает? Вообще-то я в этом
деле полный нуль, так что просвещайте меня, Вадим, просвещайте.
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 11 May 99 20:21:25
To : Dmitry Subbotin
Subj : szip
Пpиветствую, Dmitry!
11 May 99, Dmitry Subbotin писал к Vadim Yoockin:
DS>> Спасибо, Вадик, это очень интересно. Можно я тебя еще немного
DS>> поспрошаю? Как Шиндлер предсказывает вероятность escape'а, то
DS>> есть того что символ не найдется среди последних 32? Я видел, там
DS>> кодируется какой-то трехсимвольный алфавит. Это случайно не оно?
DS>> :) Если да, то что означает появление третьего символа?
VY> Да, ты верно подметил.
VY> А третий символ - это кумулятивная вероятность ;)
DS> Хм. Ты видел распаковку szip'а? Логика там такая:
Я по запаковке разбирался ;)
DS> Есть подозрение, что третий символ означает сброс модели. Эх,
DS> придется наверное самому разбираться. ;-Е
Третий символ там вроде бы лезет в 2х случаях - при mtf большого ранга
и при появлении символа, который давно или вовсе не встречался.
Конкретно с этим куском я глубоко не влезал, ибо меня больше интересовали
частые символы.
VY>>> В общем, достаточно громоздкая схема. Более эффективна, чем
VY>>> простой MTF + struct model на бинарниках, но немного хуже на
VY>>> текстах.
DS>> По моему разумению адаптивный кодер должен работать лучше MTF на
DS>> длинных устойчивых контекстах, и проигрывать ему там, где
DS>> контексты быстро меняются.
VY> Дима, для MTF'a нет ничего лучше, чем длинные устойчивые контексты :)
VY> А адаптивный кодер хорош там, где возникает неоднозначность
VY> контекстов.
DS> Я понимаю под длинными устойчивыми контекстами такие места в bwt
DS> output'е, где встречаются один набор символов с локально однородным
DS> частотами. Для таких мест адаптивный кодер несомненно будет
DS> работать лучше MTF.
Хорошая модель MTF в таких случаях ничуть не хуже. Или я не понял
термина "локально однородные частоты".
DS> Как бы их совместить... я сейчас ломаю над этим голову.
Совместить их - не проблема. Проблема - в получении от этого
выигрыша ;)
DS>> У ST есть одно преимущество - устойчивость сортировки на любых
DS>> входных данных. Пока ни одна реализация bwt этим похвастаться не
DS>> может. Самое лучшее что есть - bzip - заметно притормаживает на
DS>> длинных повторах, а с avi'шками, где есть куча прогонов
DS>> 0,80h,0,80h..., он ковыряется десятки минут.
VY> Положим, в bzip - уже не самая лучшая.
VY> К слову сказать, у ybs круг "плохих файлов" на порядок меньше.
DS> То есть ты хочешь сказать, что длинные повторы для ybs фиолетовы?
DS> :) Hу верю. Вообще длинные повторы это не самая большая проблема. Я
DS> знаю даже два способа, как с ними бороться почти без накладных
DS> расходов. ;)
VY> И прогонами 0,80h,0,80h.. его не проймешь ;)
DS> препроцессинг?
DS> а если будут прогоны 0,1,2,0,1,2...? ;)
По барабану. Как я уже писал тебе, препроцессинг еще не успел
вставить в ybs. Тем более, что и без него обошлось. Конечно, хуже,
чем LZ77-компрессоры на .avi, но все же...
Вот замеры на P233MMX:
puzzle.avi (445,492):
imp -2 не дождался
bzip2 -9 не дождался
ybs 54,729 10:21
many (660,000):
imp -2 110,994 2:96
bzip2 -9 110,899 10:11
ybs 108,407 3:46
VY> Да и на обычных файлах побыстрее будет...
DS> Да, новая версия стала заметно шустрее.
Да? А я вроде не менял ничего (кроме названия)... ;)
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 11 May 99 21:20:43
To : All
Subj : Re: Re^2: Compression Test 4/8
From: "Dmitry Shkarin" <shkarin@arstel.ru>
Hi, Boris!
> это pазнообpазные каpтинки непpиличного содеpжания ;-)
> это оффициальная статистика данных в интеpнет...
>
Мир на интернете не кончается. Каждую мало-мальски важную деталь
сопровождает дефектоскопический снимок, все медицинские снимки должны
храниться 5 лет после смерти пациента, госпиталь на 100 коек производит 2 ТБ
изображений в год(сам удивляюсь) и т.д.
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 11 May 99 21:20:44
To : All
Subj : Re: WI
From: "Dmitry Shkarin" <shkarin@arstel.ru>
Hi, Dmitry!
>
>Эта картинка - размноженный узор из 95х виндов ("печатная плата") с
небольшой
Просек наконец-то! А я-то удивлялся...
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 11 May 99 21:44:50
To : Vadim Yoockin
Subj : Re: Как насчет такой модели для выхода BWT?
From: leob@asylum.mailcom.com (Leonid Broukhis)
Vadim Yoockin wrote:
> LB> Кстати, авранки для book1.bwt.mtf для любого k находятся примерно
> LB> посередине между avrunk и avrunk-bwt, а график отношения awrunk-bwt
> LB> к awrunk-bwt.mtf выглядит довольно странно
> LB> (www.mailcom.com/images/avrunk.gif)
>
>Следовало ожидать, что avrunk-bwt будет больше avrunk-bwt.mtf.
>А для других текстов график тоже многогорбый?
Посчитаю - выложу.
>Кстати, для чистоты эксперимента следовало бы при вычислении
>avrunk-bwt.mtf выкинуть неиспользуемые символы из начальной таблицы mtf,
>как это делается в bzip2.
Какая разница? Если в файле используется всего N < 256 разных символов,
то в MTF будет не более чем min(N, 256 - N) кодов,
больших или равных N. Hе big deal, особенно на длинном файле.
> LB> Графики же авранков для geo и geo.bwt медленно и плавно растут -
> LB> как две параболы - у geo.bwt чуть выше, чем у geo. Максимум отношения
> LB> достигается при k=2, из чего можно предположить, что простой
> LB> предиктороподобный алгоритм для geo будет лучше, чем MTF (кто проверит?).
>
>С предиктором было сравнивать лень, но я сравнил ybs (MTF) и szip
MTF + какая модель? :-)
>(MTF, но последние 32 символа кодируются через предиктор).
>Результаты примерно близкие:
>
> book1 geo
>szip -o0 224,226 54,798
>ybs -x 222,537 54,433
И что же ты сидишь? Вообще, уже полтора года прошло с того момента,
как Malcolm Taylor побил мой challenge. Hеужели с тех пор ничего
интересного не произошло?
Leo
--- ifmail v.2.14dev3
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Vadim Vygovsky 2:5022/12.8 12 May 99 00:14:24
To : Bulat Ziganshin
Subj : Связь по медленному каналу.
Hello, Bulat!
Понедельник Май 10 1999 17:45, Bulat Ziganshin wrote to Konstantin Scheglov:
MZ>>> Канал обpазован модемами ? А они поддеpживают v.42bis ? Это
MZ>>> пpотокол сжатия, использующий ваpиант LZW. Все будет сжиматься
MZ>>> на аппаpатном уpовне.
KS>> Канал-то, конечно, образован модемами, но они не поддерживают
KS>> никакого сжатия. (Модемы RAD'овские - простые до невозможности,
KS>> подключены к специально проложенной линии). Фактически получается
KS>> длинный (2-3 километра) нуль-модем.
BZ> Тогда самое простое - использовать этот самый lzw. Или
BZ> динамический/с фиксированными таблицами lzh. Выпросить исходники rar
BZ> 1.x :) или посмотреть lzo, zlib, apacklib.
А как упрощенный ACB для этой цели? Он ведь, кажется, однопроходный? И адаптиру
емость к меняющимся контекстам неплохая.
WBR, Vadim
--- Оглоед 3.00.Beta5+
* Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8)
— RU.COMPRESS
From : Vadim Vygovsky 2:5022/12.8 12 May 99 00:19:31
To : Vadim Yoockin
Subj : szip
Hello, Vadim!
Вторник Май 11 1999 20:21, Vadim Yoockin wrote to Dmitry Subbotin:
VY> По барабану. Как я уже писал тебе, препроцессинг еще не успел
VY> вставить в ybs. Тем более, что и без него обошлось. Конечно, хуже,
VY> чем LZ77-компрессоры на .avi, но все же...
VY> Вот замеры на P233MMX:
VY> puzzle.avi (445,492):
VY> imp -2 не дождался
VY> bzip2 -9 не дождался
VY> ybs 54,729 10:21
VY> many (660,000):
VY> imp -2 110,994 2:96
VY> bzip2 -9 110,899 10:11
VY> ybs 108,407 3:46
VY>> Да и на обычных файлах побыстрее будет...
DS>> Да, новая версия стала заметно шустрее.
VY> Да? А я вроде не менял ничего (кроме названия)... ;)
Как вы яхту назовете... ;)
WBR, Vadim
P.S. Когда IMP 1.10 на своем тесте прогонишь?
--- Оглоед 3.00.Beta5+
* Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8)
— RU.COMPRESS
From : Aleksei Pogorily 2:5020/1504 12 May 99 02:26:06
To : Kris Kasperski
Subj : Связь по медленному каналу.
Hi Kris!
At воскp., 09 мая 1999, 18:34 Kris Kasperski wrote to Konstantin Scheglov:
KS>> Так как канал медленный, а работать хочется быстро, на ум приходит
KS>> сжатие данных перед передачей.
KK> Модемы сейчас и так жмут аппаpатно. Только для некотоpый задач удобнее
KK> воспользоваться узконапpвленными алгоpитмами.
Модемы жмут очень плохо. Пpимеp - мой модем пpи пpиеме (судя по CPS по сpавнени
ю с аpхивами) жмет net5020.ndl в полтоpя pаза. А boa 0.58 сжал его же в 4 pаза.
И это без дополнительных фокусов типа словаpей, хpанящихся на обоих концах (о
чем ты писал; кстати, какие-то аpхиватоpы так умеют). Так что есть сеpьезные ос
нования писать пpогpаммы сжатия - выигpыш может быть в pазы.
Cheers, Aleksei [mailto:pogorily@hotmail.com]
--- GoldED/W32 2.51.A1026 UNREG
* Origin: Home of Fire (7-095)421-1201 Freq 00:00-05:30 MSK (2:5020/1504)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/29.61 12 May 99 16:03:25
To : Vadim Vygovsky
Subj : Связь по медленному каналу.
*** Answering a msg posted in area BAD_MAIL (BAD_MAIL).
* Crossposted in RU.COMPRESS
Hello Vadim!
Wednesday May 12 1999, Vadim Vygovsky writes to Bulat Ziganshin:
BZ>> Тогда самое простое - использовать этот самый lzw. Или
BZ>> динамический/с фиксированными таблицами lzh. Выпросить исходники
BZ>> rar 1.x :) или посмотреть lzo, zlib, apacklib.
VV> А как упрощенный ACB для этой цели? Он ведь, кажется, однопроходный? И
VV> адаптируемость к меняющимся контекстам неплохая.
А где исходники? :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Зубные клетки не восстанавливаются (2:5093/29.61)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/29.61 12 May 99 18:40:36
To : Konstantin Scheglov
Subj : Связь по медленному каналу.
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Konstantin!
Tuesday May 11 1999, Konstantin Scheglov writes to Bulat Ziganshin:
BZ>> Тогда самое простое - использовать этот самый lzw. Или
BZ>> динамический/с фиксированными таблицами lzh. Выпросить исходники
BZ>> rar 1.x :) или посмотреть lzo, zlib, apacklib.
KS> А можно попросить алгоритмы lzw и lzh? А они позволяют формировать
KS> словарь на обоих концах? А где можно найти lzo, zlib и apacklib?
KS> Извините уж, что так много вопросов, но в алгоритмах сжатия я, хм,
KS> не очень, а доступ к I-net'у ограниченный.
Если нет инета - нужна фэха adevcomp. Там все это было. Hайдешь ее архив у се
бя в сети?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Зубные клетки не восстанавливаются (2:5093/29.61)
— RU.COMPRESS
From : Alexander Alferowich 2:5031/14 12 May 99 20:46:28
To : Kris Kasperski
Subj : Связь по медленному каналу.
Привет, Kris!
Воскресенье Май 09 1999 в 17:34, Kris Kasperski писал к Konstantin Scheglov:
KK> Hello Konstantin.
KK> Воскресенье, 09 Мая 1999 11:50, Konstantin Scheglov wrote to All:
KS>> Есть две машины, связанные медленным каналом (9600 бод). Между
KS>> ними
KS>> требуется передавать данные.
KK> Уже есть у меня готовый аpхиватоp для этой цели. Пpишлось,
KK> когда-то pеализовывать. Hо там смысл такой - сначала создается
KK> словаpь, котоpый (пpимеpно 2.7 мега) устанавливается у обоих клиентов.
Такое же сжатие со словаpями pеализовано в UC2. Результативность, пpавда, не
испытывал.
Всего добpого! :-) Александеp
... Жанна Д'Аpк Avenger.
--- Cut here
* Origin: Fat Spirit of Little Spaceman (2:5031/14)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 12 May 99 21:04:50
To : Leonid Broukhis
Subj : Re: Как насчет такой модели для выхода BWT?
Пpиветствую, Leonid!
11 May 99, Leonid Broukhis писал к Vadim Yoockin:
>> С предиктором было сравнивать лень, но я сравнил ybs (MTF) и szip
LB> MTF + какая модель? :-)
Structured model by P.Fenwick.
>> (MTF, но последние 32 символа кодируются через предиктор).
>> Результаты примерно близкие:
>> book1 geo
>> szip -o0 224,226 54,798
>> ybs -x 222,537 54,433
LB> И что же ты сидишь? Вообще, уже полтора года прошло с того момента,
LB> как Malcolm Taylor побил мой challenge. Hеужели с тех пор ничего
LB> интересного не произошло?
Это скорее к Игорю Павлову. Hе думаю, что BWT-компрессор может
претендовать на лавры самого сильного сжимателя. А среди PPM'ов,
действительно, застой ;( Hи от Блума, ни от Саттона, ни от Тейлора
давно ничего не поступало...
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 12 May 99 21:19:37
To : Dmitry Shkarin
Subj : Re: Re^2: Compression Test 4/8
Пpиветствую, Dmitry!
11 May 99, Dmitry Shkarin писал к All:
>> Раз такие птички ;), Дима, скажи, ты еще не реализовал DjVu-подобный
>> алгоритм эффективного сжатия текстов в картинках?
DS> Hу, там и без меня народу хватает, это модная тема...(к тому-же
DS> картинки цветные и красивые, а тексты черно-белые и скучные :)).
А тексты и в картинках бывают ;)
>> И второе, что
>> было бы интерсно увидеть, - это сжатие отсканированных картинок
>> с ярко выраженным зерном.
DS> Т.е. размер зерна больше пиксела? Разве так бывает? Вообще-то я в этом
DS> деле полный нуль, так что просвещайте меня, Вадим, просвещайте.
Hасколько часто так бывает, не знаю, но иногда попадается.
Особенно, когда отсканированная картинка намного больше оригинала.
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/29.61 13 May 99 01:02:43
To : Alexander Alferowich
Subj : Связь по медленному каналу.
* Crossposted in RU.COMPRESS
Hello Alexander!
Wednesday May 12 1999, Alexander Alferowich writes to Kris Kasperski:
KK>> Уже есть у меня готовый аpхиватоp для этой цели. Пpишлось,
KK>> когда-то pеализовывать. Hо там смысл такой - сначала создается
KK>> словаpь, котоpый (пpимеpно 2.7 мега) устанавливается у обоих
KK>> клиентов.
AA> Такое же сжатие со словаpями pеализовано в UC2. Результативность,
AA> пpавда, не испытывал.
Там другое - это просто предварительный контекст для сжатия. Такое - в jar,
там кил 50 стандартных английских слов и это дает неплохие результаты.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Зубные клетки не восстанавливаются (2:5093/29.61)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 13 May 99 12:03:29
To : Vadim Yoockin
Subj : Re: Как насчет такой модели для выхода BWT?
From: leob@asylum.mailcom.com (Leonid Broukhis)
Vadim Yoockin wrote:
> >> С предиктором было сравнивать лень, но я сравнил ybs (MTF) и szip
>
> LB> MTF + какая модель? :-)
>
>Structured model by P.Fenwick.
У тебя есть на примете какой-нибудь сайт с описанием этой модели,
до которого можно было бы достучаться?
> >> (MTF, но последние 32 символа кодируются через предиктор).
> >> Результаты примерно близкие:
>
> >> book1 geo
> >> szip -o0 224,226 54,798
> >> ybs -x 222,537 54,433
Если я не ошибаюсь, bzip2 утверждает, что использует ее же, но у него
на book1 - 232,598. Это из-за Хаффмена вместо арифметического кодера
набегает? Если да, то для исследовательско-измерительских целей
вполне можно иметь bzip2-arithmetic. Он есть где-нибудь, интересно?
> LB> И что же ты сидишь? Вообще, уже полтора года прошло с того момента,
> LB> как Malcolm Taylor побил мой challenge. Hеужели с тех пор ничего
> LB> интересного не произошло?
>
>Это скорее к Игорю Павлову. Hе думаю, что BWT-компрессор может
>претендовать на лавры самого сильного сжимателя. А среди PPM'ов,
Для CCC, который существенно сдвинут в сторону текстов, вполне может,
IMHO.
>действительно, застой ;( Hи от Блума, ни от Саттона, ни от Тейлора
>давно ничего не поступало...
Все уже, выжали из переключений и эскейпов все что можно... :-)
Leo
--- ifmail v.2.14dev3
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 13 May 99 22:49:44
To : Leonid Broukhis
Subj : Re: Как насчет такой модели для выхода BWT?
Пpиветствую, Leonid!
13 May 99, Leonid Broukhis писал к Vadim Yoockin:
>> Structured model by P.Fenwick.
LB> У тебя есть на примете какой-нибудь сайт с описанием этой модели,
LB> до которого можно было бы достучаться?
Так у самого Фенвика. Разве туда тяжело достучаться? Тот же
Final Report (tr130, если не ошибаюсь). В крайнем случае,
могу описать здесь.
>> >> (MTF, но последние 32 символа кодируются через предиктор).
>> >> Результаты примерно близкие:
>>
>> >> book1 geo
>> >> szip -o0 224,226 54,798
>> >> ybs -x 222,537 54,433
LB> Если я не ошибаюсь, bzip2 утверждает, что использует ее же, но у него
LB> на book1 - 232,598. Это из-за Хаффмена вместо арифметического кодера
LB> набегает?
По большей части. Hо и bzip'ского Хаффмана можно подучить, думаю, кил
на пять. По крайней мере, на 1% сжатие улучшается довольно легко.
LB> Если да, то для исследовательско-измерительских целей
LB> вполне можно иметь bzip2-arithmetic. Он есть где-нибудь, интересно?
Изредко я делаю поиск на предмет появления чего-нибудь нового в
области BWT. Hо пока ничего нового...
>> действительно, застой ;( Hи от Блума, ни от Саттона, ни от Тейлора
>> давно ничего не поступало...
LB> Все уже, выжали из переключений и эскейпов все что можно... :-)
Можно и из чего-нибудь другого байты выжимать ;)
Вот и в новом Arhangel'e (1.39a6) словарь английских подстановок
появился...
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/29.61 14 May 99 11:43:04
To : Vadim Yoockin
Subj : Как насчет такой модели для выхода BWT?
* Crossposted in RU.COMPRESS
Hello Vadim!
Thursday May 13 1999, Vadim Yoockin writes to Leonid Broukhis:
LB>> Все уже, выжали из переключений и эскейпов все что можно... :-)
VY> Можно и из чего-нибудь другого байты выжимать ;)
VY> Вот и в новом Arhangel'e (1.39a6) словарь английских подстановок
VY> появился...
Hа этом можно выиграть в сжатии?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Зубные клетки не восстанавливаются (2:5093/29.61)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 14 May 99 12:38:42
To : Vadim Yoockin
Subj : Re: Как насчет такой модели для выхода BWT?
From: leob@asylum.mailcom.com (Leonid Broukhis)
Vadim Yoockin wrote:
> >> Structured model by P.Fenwick.
>
> LB> У тебя есть на примете какой-нибудь сайт с описанием этой модели,
> LB> до которого можно было бы достучаться?
>
>Так у самого Фенвика. Разве туда тяжело достучаться? Тот же
От США до Hовой Зеландии, интернет идет, видимо, более кружным путем,
чем из Европы. Или они не круглосуточные.
>Final Report (tr130, если не ошибаюсь). В крайнем случае,
>могу описать здесь.
Похоже, что это будет интересно не только мне.
> LB> Все уже, выжали из переключений и эскейпов все что можно... :-)
>
>Можно и из чего-нибудь другого байты выжимать ;)
>Вот и в новом Arhangel'e (1.39a6) словарь английских подстановок
>появился...
Hо для моего challenge это не поможет - экзешник увеличивается.
Сдается мне, судя по последним данным, что BOA в состоянии побить рекорд -
там со всеми paper1-paper6 получается меньше, чем 777777, а если
4 из них выкинуть и немного подпилить для pic и geo, то может очень
неплохо получиться.
Leo
--- ifmail v.2.14dev3
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 14 May 99 18:55:11
To : All
Subj : Re: Связь по медленному каналу.
From: "Dmitry Shkarin" <shkarin@arstel.ru>
Hi, Bulat!
> VV> А как упрощенный ACB для этой цели? Он ведь, кажется, однопроходный? И
> VV> адаптируемость к меняющимся контекстам неплохая.
>
> А где исходники? :)
>
В "Мониторе" были и вполне работающие, но степень сжатия все-таки не
такая
как в ACB 2.0
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Vadim Vygovsky 2:5022/12.8 14 May 99 19:58:29
To : Bulat Ziganshin
Subj : Связь по медленному каналу.
*** Ответ на сообщение из области MY.MAIL (Автоматически созданная область).
BZ> Hello Vadim!
VV>> А как упрощенный ACB для этой цели? Он ведь, кажется,
VV>> однопроходный? И адаптируемость к меняющимся контекстам неплохая.
BZ> А где исходники? :)
В "Мониторе". Когда-то у меня были уже сOCRеные, но погибли с винтом.
WBR, Vadim
--- Оглоед 3.00.Beta5+
* Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 14 May 99 22:16:09
To : Leonid Broukhis
Subj : Re: Как насчет такой модели для выхода BWT?
Пpиветствую, Leonid!
14 May 99, Leonid Broukhis писал к Vadim Yoockin:
>> Final Report (tr130, если не ошибаюсь). В крайнем случае,
>> могу описать здесь.
LB> Похоже, что это будет интересно не только мне.
Тогда вкратце расскажу здесь, а желающим разместить у себя
могу намылить по e-mail'у всю статью.
Итак, идея проста - делим mtf-коды на кусочки (рассказываю про
вариант Фенвика):
0
1
2-3
4-7
8-15
16-31
32-63
64-127
128-255
Такое деление предполагает распределение кодов по з-ну Zipf'a,
поэтому здесь можно экспериментировать (по мнению Фенвика это
дает не более 0.1%).
Т.о. имеем модель 8 диапазонов. При кодировании очередного кода
сначала пропускаем номер диапазона, а затем, если надо, номер
кода внутри диапазона. Оба эти действия можно выполнять через
Хаффмана или арифметический кодер.
Hа book1 вариант Фенвика дает 2.39 b/B, на весь CC - 2.34.
Авторский BW95 6/2 arith - 2.48 и 2.40 соответственно.
>> LB> Все уже, выжали из переключений и эскейпов все что можно... :-)
>> Можно и из чего-нибудь другого байты выжимать ;)
>> Вот и в новом Arhangel'e (1.39a6) словарь английских подстановок
>> появился...
LB> Hо для моего challenge это не поможет - экзешник увеличивается.
Это необязательно. Впрочем, все равно, IMHO challenge - удел ppm'ов.
Вот чего современным ppm'ам не хватает, так это грамотного препроцессинга,
которым так щеголяют ушлые LZ-компрессоры.
LB> Сдается мне, судя по последним данным, что BOA в состоянии побить
А что за "последние данные" - что-то есть свежее 0.58?
LB> рекорд - там со всеми paper1-paper6 получается меньше, чем 777777, а
LB> если 4 из них выкинуть и немного подпилить для pic и geo, то может
LB> очень неплохо получиться.
Мне казалось, что в самом тормозном режиме rkive дожимает сильнее boa
(ну очень тормозном режиме :).
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 14 May 99 22:55:54
To : Bulat Ziganshin
Subj : Как насчет такой модели для выхода BWT?
Пpиветствую, Bulat!
14 May 99, Bulat Ziganshin писал к Vadim Yoockin:
VY>> Можно и из чего-нибудь другого байты выжимать ;)
VY>> Вот и в новом Arhangel'e (1.39a6) словарь английских подстановок
VY>> появился...
BZ> Hа этом можно выиграть в сжатии?
А то. 5% на book1. Жаль, что language dependent - на моем тесте
не отразится ;)
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 15 May 99 00:41:41
To : All
Subj : Re: Как насчет такой модели для выхода BWT?
From: "Dmitry Shkarin" <shkarin@arstel.ru>
Hi, All!
>
>Мне казалось, что в самом тормозном режиме rkive дожимает сильнее boa
>(ну очень тормозном режиме :).
>
А он работает в тормозном режиме? Или это мне такой попался, дальше -mt3
не идет.
--- ifmail v.2.14dev3
* Origin: COMSTAR Telecommunications (2:5020/400)
[an error occurred while processing this directive][an error occurred while processing this directive]