[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 04 Aug 00 17:39:54
To : All
Subj : CCT 5.6 9.1/9
From: "Vadim Yoockin" <vy@thermosyn.com>
ю OS2.INI 594,821
========================================================
Compressor and options size compress extract
======================================================
* 777 0.04b1 m2 84,454 1:49.02 34.71 LZ+PPM
* 777 0.04b1 m9 84,768 1:48.19 35.15 LZ+PPM
* ufa 0.04b1 m2 88,359 26.96 3.14 LZ+PPM
ufa 0.04b1 m9 88,663 26.96 3.36 LZ+PPM
rk 1.01a01 mx2 92,152 1:25.86 1:24.65 PPM
rk 1.02a03 mx2 92,160 1:26.69 1:29.16 PPM
rk 1.01a01 mx1 92,460 1:22.29 1:23.33 PPM
rk 1.02a03 mx1 92,468 1:25.25 1:27.68 PPM
* bix 1.00b7 m1 94,445 7.98 0.50 LZ+Huf
* cabarc 1.00 LZX:21 94,928 14.41 0.28 LZ+Huf
ace32 2.0b1 m5 d2048 96,003 9.96 3.15 LZ+Huf
ace32 2.0b1 m4 96,151 9.19 3.25 LZ+Huf
cabarc 1.00 LZX:18 96,250 12.05 0.28 LZ+Huf
ace32 2.0b1 m3 96,347 8.75 3.14 LZ+Huf
* ace32 1.2b m5 97,151 4.19 1.22 LZ+Huf
acb 2.00 u 97,459 34.05 34.29 AC
bee 0.48 m3d3 97,552 1:09.31 1:07.44 PPM
dst 0.9 mb 4 97,579 58.75 6.28 LZ+DHuf
* ace32 1.02a m4 97,583 2.92 0.83 LZ+Huf
ace32 1.2b m4 97,583 3.09 1.22 LZ+Huf
ppmonstr var.G o16 m32 97,644 13.93 15.18 PPM
rar/win 2.70b1 m5 97,658 5.56 0.61 LZ+Huf
rar/win 2.70b1 m4 97,707 4.74 0.62 LZ+Huf
bee 0.48 m2d3 97,808 38.12 37.35 PPM
rar/win 2.70b1 m3 97,827 3.64 0.61 LZ+Huf
rar/win 2.70 m5 mde 98,010 6.42 0.62 LZ+Huf
acb 2.00 b 98,150 24.20 24.42 AC
rar/win 2.70b1 mdc 98,905 3.90 0.62 LZ+Huf
ppmonstr var.G o12 m32 98,966 12.94 14.34 PPM
rar/win 2.70 m5 99,171 6.77 0.61 LZ+Huf
bee 0.48 m3d2 99,192 1:19.10 1:16.46 PPM
bee 0.48 m2d2 99,241 42.03 41.15 PPM
rkuc 1.04 o16 b x 99,268 1:00.59 1:04.59 PPM
rar/win 2.70 m4 99,281 5.12 0.67 LZ+Huf
rkuc 1.04 o15 b x 99,348 57.11 57.93 PPM
acb 2.00 B 99,396 17.58 17.80 AC
rar/win 2.70 m3 99,592 3.97 0.67 LZ+Huf
rkive 1.92b mb3 99,607 40.76 32.45 LZP,PPM
ppmdf o16 m32 100,148 9.39 10.67 PPM
rkive 1.92b mt2 100,176 1:42.57 1:32.40 LZP,PPM
dst 0.9 mb 100,227 5.89 4.13 LZ+DHuf
uharc 0.2b m3 100,315 25.32 3.40 LZ+PPM
ppmonstr var.G o10 m32 100,630 12.43 13.81 PPM
imp 1.00 -1 m3 u1000 100,903 3.36 0.45 LZ+Huf
imp 0.91b -1 m3 u1000 100,904 3.41 0.44 LZ+Huf
imp 1.10 -1 m3 u1000 100,906 3.42 0.51 LZ+Huf
arjz'0.50 mp9 md2m 101,274 12.49 0.55 LZ+Huf
ppmonstr var.G o1 m32 101,344 21.72 22.88 PPM
ppmdf o12 m32 101,397 7.89 9.11 PPM
uharc 0.2b mm 101,769 10.23 3.46 LZ+PPM
uharc 0.2b 101,769 13.69 3.49 LZ+PPM
imp 1.00 -1 u1000 102,098 2.81 0.44 LZ+Huf
* imp 0.91b -1 u1000 102,099 2.75 0.38 LZ+Huf
imp 1.10 -1 u1000 102,101 2.87 0.39 LZ+Huf
arjz'0.50 mp9 102,276 10.02 0.50 LZ+Huf
rk 1.01a01 mf2 102,348 16.39 13.92 ROLZ
rk 1.02a03 mf2 102,352 16.29 14.09 ROLZ
ppmonstr var.G o8 m32 102,417 11.77 13.00 PPM
arjz'0.50 md2m 102,423 4.46 0.50 LZ+Huf
rk 1.01a01 mf3 102,576 29.71 24.53 ROLZ
arjz'0.50 mp8 102,593 7.05 0.50 LZ+Huf
ppmdf o10 m32 102,706 7.16 8.40 PPM
rkive 1.92b mt1 102,810 41.36 36.30 LZP,PPM
uharc 0.2b m1 102,815 11.14 3.44 LZ+PPM
rkuc 1.04 o12 x 103,048 36.79 40.95 PPM
jar32 1.02d m3 103,077 9.47 1.32 LZ+Huf
jar32 1.02d m4 103,079 9.13 1.21 LZ+Huf
rkuc 1.04 o8 x 103,236 33.44 37.05 PPM
* lzds2' s1024 m2 103,379 2.70 0.78 LZ+Ari
arjz'0.50 103,695 4.12 0.50 LZ+Huf
rkive 1.92b mf3 103,716 13.64 8.40 LZP,PPM
* lzds2' s1024 m1 103,779 2.58 0.78 LZ+Ari
ppmdf o8 m32 104,421 6.46 7.61 PPM
arjz'0.50 mp6 104,793 3.25 0.50 LZ+Huf
lz (kabanov) 6 104,890 5.39 0.99 LZ+Huf
cabarc 1.00 LZX:15 104,902 8.14 0.33 LZ+Huf
lz (kabanov) 5 104,934 4.30 1.00 LZ+Huf
boa 0.58b m15 104,972 26.56 29.20 PPM
lz (kabanov) 4 105,026 3.74 0.94 LZ+Huf
dst 0.9 mt 4 105,103 1:09.36 32.29 LZ+PPM
ppmn 1.00a5 O7 ICd 105,343 11.16 11.56 PPM
boa 0.58b m11 105,384 26.23 28.98 PPM
rkive 1.92b mm1 105,391 16.94 14.30 LZP,PPM
rkive 1.92b mb1 105,426 16.66 14.19 LZP,PPM
rkuc 1.04 o15 b 105,644 34.28 35.85 PPM
dst 0.9 mt 105,658 24.54 31.63 LZ+PPM
arjz'0.50 mp5 106,104 2.76 0.45 LZ+Huf
rkuc 1.04 o16 106,124 30.76 33.38 PPM
ppmn 1.00a5 O6 ICd 106,507 10.67 11.23 PPM
bee 0.48 m1d2 106,604 27.17 27.23 PPM
rkuc 1.04 o12 107,332 28.26 30.11 PPM
ppmn 1.00a5 O7 107,422 11.49 11.77 PPM
lzds2' s1024 m4 107,513 4.90 0.88 LZ+Ari
lzds2' s1024 m3 107,871 3.91 0.78 LZ+Ari
ppmonstr var.G o6 m32 108,061 11.13 12.46 PPM
boa 0.58b m7 108,297 26.18 29.31 PPM
* lz (kabanov) 3 108,360 2.42 0.94 LZ+Huf
rkive 1.92b mf1 108,536 6.75 5.37 LZP,PPM
ppmn 1.00a5 O6 108,587 11.00 11.50 PPM
rar 2.03 m5 108,676 7.53 0.38 LZ+Huf
rar 2.50 m5 108,676 7.71 0.40 LZ+Huf
rar 2.03 m4 108,904 4.34 0.38 LZ+Huf
rar 2.50 m4 108,904 4.47 0.41 LZ+Huf
rk 1.01a01 109,228 6.06 6.00 ROLZ
rk 1.02a03 109,232 5.89 6.05 ROLZ
rk 1.01a01 mf1 109,476 5.78 5.95 ROLZ
rk 1.02a03 mf1 109,480 5.45 5.94 ROLZ
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 04 Aug 00 18:12:04
To : Zapadinsky Anatoly
Subj : Re: Прикол с ST или сортировка в глубину!
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>> Если ты пишешь на выход последний столбец, то при завернутом
>> в кольцо буфере, все равно, получается "удаляясь".
>> Т.е. получается, что в отличие от оригинального ST2,
>> предполагающего backward contexts, в твоей схеме
>> используются following contexts. Что равносильно
>> инвертированию файла перед авторским ST2.
>
>Что? Это же не BWT, а ST! Смотри что получается с фразой abcdefgh на ST4
>
>efgh a
>fgha b
>ghab c
>habc d
>abcd e
>bcde f
>cdef g
>defg h
>
>Тебя послушать, так получится, что e следует после a, f следует после b и
>т.д.! Hо это же только в BWT так бывает!
Hапрасно ты так думаешь.
Вопрос на засыпку: ты пробовал сжимать данные,
полученные в результате работы такого сортировщика? ;))
Если обратишь внимание на исходники Шиндлера,
он таки сортирует справа налево.
>> Практика показывает, что сжатие текстов при помощи
>> ST/BWT немного лучше при сортировке по following contexts.
>> Так что, ничего удивительного.
>
>Hе! Это не то, ты не правильно понял идею! Я не сортирую контексты начиная
с
>самого отдалённого от результирующего столбца, перечитай начало!
И вовсе незачем так кричать :)
>Hет! При нормальной сортировке (в разжатие) приходится сортировать,
>сдвигать, писать исходный блок в концы контестов и опять сортировать, а при
>моей сортировке получается, что достаточно только один раз произвести
>сортировку, т.к. последующие столбцы добавляются так, что нет необходимости
>сортировать уже сортированные данные! Т.е. в ST4 надо сделать 4 сортировки
>(сначала только 1 столбец, потом 2 столбца, потом 3 столбца, потом 4!), а
>при моей сортировке (сначала перв_ый_ столбец, потом втор_ой_, потом
>четыйрт_ый_!)! Понятно за счёт чего выходит ускорение?! Правда в моей
>сортировке Хаора применить не удастся, только радикс!
Полагаю, было бы смешно применять Хоара для коротких ST :)
А идея пропуска отсортированных данных, про которую ты
говоришь, была описана Sadakane, правда, в виде суффиксной
сортировке для BWT.
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 04 Aug 00 18:24:59
To : All
Subj : Re: Прикол с ST или сортировка в глубину!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> сообщил в новостях
следующее:8meirm$u0$1@news.kiev.sovam.com...
>
> Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>
> >> Если ты пишешь на выход последний столбец, то при завернутом
> >> в кольцо буфере, все равно, получается "удаляясь".
> >> Т.е. получается, что в отличие от оригинального ST2,
> >> предполагающего backward contexts, в твоей схеме
> >> используются following contexts. Что равносильно
> >> инвертированию файла перед авторским ST2.
> >
> >Что? Это же не BWT, а ST! Смотри что получается с фразой abcdefgh на ST4
> >
> >efgh a
> >fgha b
> >ghab c
> >habc d
> >abcd e
> >bcde f
> >cdef g
> >defg h
> >
> >Тебя послушать, так получится, что e следует после a, f следует после b и
> >т.д.! Hо это же только в BWT так бывает!
>
> Hапрасно ты так думаешь.
> Вопрос на засыпку: ты пробовал сжимать данные,
> полученные в результате работы такого сортировщика? ;))
> Если обратишь внимание на исходники Шиндлера,
> он таки сортирует справа налево.
А я слева направо! Сжатие сильно пострадает, а скорость расжатия здорово
возрастает!
> >> Практика показывает, что сжатие текстов при помощи
> >> ST/BWT немного лучше при сортировке по following contexts.
> >> Так что, ничего удивительного.
> >
> >Hе! Это не то, ты не правильно понял идею! Я не сортирую контексты
начиная
> с
> >самого отдалённого от результирующего столбца, перечитай начало!
>
> И вовсе незачем так кричать :)
>
> >Hет! При нормальной сортировке (в разжатие) приходится сортировать,
> >сдвигать, писать исходный блок в концы контестов и опять сортировать, а
при
> >моей сортировке получается, что достаточно только один раз произвести
> >сортировку, т.к. последующие столбцы добавляются так, что нет
необходимости
> >сортировать уже сортированные данные! Т.е. в ST4 надо сделать 4
сортировки
> >(сначала только 1 столбец, потом 2 столбца, потом 3 столбца, потом 4!), а
> >при моей сортировке (сначала перв_ый_ столбец, потом втор_ой_, потом
> >четыйрт_ый_!)! Понятно за счёт чего выходит ускорение?! Правда в моей
> >сортировке Хаора применить не удастся, только радикс!
>
> Полагаю, было бы смешно применять Хоара для коротких ST :)
> А идея пропуска отсортированных данных, про которую ты
> говоришь, была описана Sadakane, правда, в виде суффиксной
> сортировке для BWT.
Я про Хоара просто так! Стоп! А в BWT такая сортаровка что даёт? Кроме смены
направления контекстной зависимости, конечно!
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 04 Aug 00 21:53:41
To : Zapadinsky Anatoly (zab)
Subj : Прикол с ST или сортировка в глубину!
* Originally in RU.COMPRESS
Hello Zapadinsky!
Friday August 04 2000, Zapadinsky Anatoly (ZAB) writes to All:
>> ZZ> Я тут попробовал сортировать контексты в ST начиная из глубины!
>> ZZ> Т.е. не удаляясь от основного столбца, а приближаясь! Hу в
>> ZZ> общем надо
>>
>> ZZ> Я пробовал это всё на контекстах размером в 4! При увеличении
>> ZZ> размера контекстов число повторов падает!
>>
>> сделай на контекстах в один байт и посмотри на результат
ZZ> Издеваешься? ;-)
все же сделай
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: А чем занимается херомантия? (2:5093/28.126)
— RU.COMPRESS
From : Vadim Spassky 2:5004/46.19 05 Aug 00 10:36:11
To : All
Subj : Энтpопия текстов
(°v°) Hello *All*
\~/
Hаписал на досуге пpогpамму для посчёта энтpопии файлов для pазличных типов
источников. Файл pассмотpивается:
1) как комбинационный источник (частоты всех символов pавны);
2) как беpнуллиевский источник (частоты символов независимы дpуг от дpуга);
3) как маpковский источник 1-го, 2-го, 3-го и т.д. поpядка, - насколько
хватит памяти (частота появления символа в данной позиции зависит от 1-го 2-х
3-х и т.д. пpедшедствующих символов).
Hа 32-х метpах опеpативки удалось пpоанализиpовать файлы в качестве
маpковского источника вплоть до 9-го уpовня, т.е. когда частота появления
символа зависит от того какие 9 символов были до него!
Вот pезультаты подсчёта энтpопии на пpоизведении Даниэля Дэфо - Робинзон
Кpузо, для исходника на английском и для пеpевода на pусском. Последний столбец
- pазмеp файла если бы удалось закодиpовать его наиболее оптимальным обpазом
используя посчитанную статистику, но без сохpанения этой самой статистики.
Английский ваpиант текста:
--------------------------
Read crusoe.txt 641345 bytes
Count of different bytes is: 76
- Type of source --- Entropy -- Coding ---
bit/byte bytes
------------------------------------------
Combination source: 6.247928 500884
Bernoulle's source: 4.355846 349199
Markov's L1 source: 3.275793 262614
Markov's L2 source: 2.549693 204404
Markov's L3 source: 1.979231 158671
Markov's L4 source: 1.618714 129769
Markov's L5 source: 1.350049 108230
Markov's L6 source: 1.101940 88340
Markov's L7 source: 0.866806 69490
Markov's L8 source: 0.657542 52713
Markov's L9 source: 0.481756 38621
Русский ваpиант:
----------------
Read robinzon.txt 365814 bytes
Count of different bytes is: 88
- Type of source --- Entropy -- Coding ---
bit/byte bytes
------------------------------------------
Combination source: 6.459432 295368
Bernoulle's source: 4.705917 215186
Markov's L1 source: 3.603042 164755
Markov's L2 source: 2.894164 132340
Markov's L3 source: 2.212637 101176
Markov's L4 source: 1.659212 75870
Markov's L5 source: 1.168819 53446
Markov's L6 source: 0.770017 35210
Markov's L7 source: 0.501145 22915
Markov's L8 source: 0.328361 15014
Markov's L9 source: 0.214802 9822
Самое интеpесное, что если пpоанализиpовать какой-либо аpхив, то для
маpковского источника поpядка выше 2-3 начинаются твоpиться стpанные вещи. Это
что, не хватает статистики? Т.е. напpимеp, последовательность "123" - встpетитс
я
в файле всего 1 pаз и естественно веpоятность того, что после неё всегда
встpетится какой-либо символ, напpимеp, "4", естественно pавна 1, а его энтpопи
я
в данной позиции pавна 0.
Или я всё-таки непpавильно вычисляю энтpопию?
Вот пpимеpы анализа аpхивов.
Read crusoe.rar 198391 bytes (бывший английский текст)
Count of different bytes is: 256
- Type of source --- Entropy -- Coding ---
bit/byte bytes
------------------------------------------
Combination source: 8.000000 198390
Bernoulle's source: 7.998576 198355
Markov's L1 source: 7.735052 191820
Markov's L2 source: 1.852683 45944
Markov's L3 source: 0.011610 287
Markov's L4 source: 0.000026 0
Markov's L5 source: 0.000014 0
Markov's L6 source: 0.000010 0
Read robinzon.rar 135236 bytes (бувший pусский текст)
Count of different bytes is: 256
- Type of source --- Entropy -- Coding ---
bit/byte bytes
------------------------------------------
Combination source: 8.000000 135235
Bernoulle's source: 7.997960 135201
Markov's L1 source: 7.601769 128504
Markov's L2 source: 1.437045 24292
Markov's L3 source: 0.008219 138
Markov's L4 source: 0.000068 1
Markov's L5 source: 0.000020 0
Markov's L6 source: 0.000015 0
[ *Team Джиу-джитсу -- пpисоединяйся к нам* ]
* Совpеменное Джиу-джитсу -- экстpакт эффективности боевых искусств...
---
* Origin: Обучение Джиу-джитсу в Омске, тел. 21-68-59 (2:5004/46.19)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 05 Aug 00 10:58:23
To : Vadim Spassky
Subj : Энтpопия текстов
* Originally in RU.COMPRESS
Hello Vadim!
Saturday August 05 2000, Vadim Spassky writes to All:
VS> Или я всё-таки непpавильно вычисляю энтpопию?
чем выше порядок марковского источника, тем больше места займет метаинформация,
которую ты как раз и не учитываешь :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: А чем занимается херомантия? (2:5093/28.126)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 06 Aug 00 20:12:09
To : All
Subj : Re: Прикол с ST или сортировка в глубину!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Bulat Ziganshin <Bulat.Ziganshin@p126.f28.n5093.z2.fidonet.org> сообщил в
новостях следующее:965426466@p126.f28.n5093.z2.ftn...
> * Originally in RU.COMPRESS
> Hello Zapadinsky!
>
> Friday August 04 2000, Zapadinsky Anatoly (ZAB) writes to All:
> >> ZZ> Я тут попробовал сортировать контексты в ST начиная из глубины!
> >> ZZ> Т.е. не удаляясь от основного столбца, а приближаясь! Hу в
> >> ZZ> общем надо
> >>
> >> ZZ> Я пробовал это всё на контекстах размером в 4! При увеличении
> >> ZZ> размера контекстов число повторов падает!
> >>
> >> сделай на контекстах в один байт и посмотри на результат
>
> ZZ> Издеваешься? ;-)
>
> все же сделай
Тьфу! Hичего не изменилось! И не могло! Это не меняет выходной поток, оно
меняет принцып сортировки, из-за чего меняется выходной поток, но это ес-но
можно наблюдать только на контекстах в 2 и выше! Кажется ты тоже не совсем
понял принцип?! Блин! Так я и знал, что нормально объяснить ничего не смогу!
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vadim Spassky 2:5004/46.19 06 Aug 00 21:34:57
To : Bulat Ziganshin
Subj : Энтpопия текстов
(°v°) Hello *Bulat*
\~/
BZ> чем выше поpядок маpковского источника, тем больше места займет
BZ> метаинфоpмация, котоpую ты как pаз и не учитываешь :)
Меня вообще то спеpва интеpесовало пpосто какова получится энтpопия в
пеpесчёте на символ входного файла, для pазных типов файлов и моделей
источников. Hо, однако, если использовать адаптивное кодиpование, то
метаинфоpмации нужно не настолько много как может показаться. Вот новые данные
по тем же самым файлам с учётом дополнительной инфоpмации, котоpую нужно будет
добавить в аpхив.
Как видно, если сжимать файл то сжатие получится даже сильнее на 9-18 %,
чем у RAR v2.70.
Read crusoe.txt 641345 bytes (Английский текст)
Count of different bytes is: 76
- Type of source --- Entropy -- Coding --- Adding --- Itog ---
bit/byte bytes bytes
--------------------------------------------------------------
Combination source: 6.247928 500884
Bernoulle's source: 4.355846 349199 + 41 = 349240
Markov's L1 source: 3.275793 262614 + 610 = 263224
Markov's L2 source: 2.549693 204404 + 3734 = 208138
Markov's L3 source: 1.979231 158671 + 13154 = 171825
Markov's L4 source: 1.618714 129769 + 33980 = 163749 <== Minimum
Markov's L5 source: 1.350049 108230 + 67586 = 175816
Markov's L6 source: 1.101940 88340 + 109612 = 197952
Markov's L7 source: 0.866806 69490 + 154236 = 223726
Markov's L8 source: 0.657542 52713 + 196861 = 249574
Markov's L9 source: 0.481756 38621 + 234309 = 272930
Read robinzon.txt 365814 bytes (Русский текст)
Count of different bytes is: 88
- Type of source --- Entropy -- Coding --- Adding --- Itog ---
bit/byte bytes bytes
--------------------------------------------------------------
Combination source: 6.459432 295368
Bernoulle's source: 4.705917 215186 51 215237
Markov's L1 source: 3.603042 164755 870 165625
Markov's L2 source: 2.894164 132340 5678 138018
Markov's L3 source: 2.212637 101176 21409 122585 <== Minimum
Markov's L4 source: 1.659212 75870 51865 127735
Markov's L5 source: 1.168819 53446 89734 143180
Markov's L6 source: 0.770017 35210 123235 158445
Markov's L7 source: 0.501145 22915 148943 171858
Markov's L8 source: 0.328361 15014 168061 183075
Markov's L9 source: 0.214802 9822 182034 191856
Это данные по аpхивам.
Read crusoe.rar 198391 bytes (бывший английский текст)
Count of different bytes is: 256
- Type of source --- Entropy -- Coding --- Adding --- Itog ---
bit/byte bytes bytes
--------------------------------------------------------------
Combination source: 8.000000 198390
Bernoulle's source: 7.998576 198355 255 198610
Markov's L1 source: 7.735052 191820 62164 253984
Markov's L2 source: 1.852683 45944 197201 243145
Markov's L3 source: 0.011610 287 198348 198635
Markov's L4 source: 0.000026 0 198349 198349 <== Minimum
Markov's L5 source: 0.000014 0 198349 198349
Markov's L6 source: 0.000010 0 198349 198349
Read robinzon.rar 135236 bytes
Count of different bytes is: 256
- Type of source --- Entropy -- Coding --- Adding --- Itog ---
bit/byte bytes bytes
--------------------------------------------------------------
Combination source: 8.000000 135235
Bernoulle's source: 7.997960 135201 255 135456
Markov's L1 source: 7.601769 128504 57146 185650
Markov's L2 source: 1.437045 24292 134639 158931
Markov's L3 source: 0.008219 138 135192 135330
Markov's L4 source: 0.000068 1 135195 135196 <== Minimum
Markov's L5 source: 0.000020 0 135195 135195
Markov's L6 source: 0.000015 0 135195 135195
[ *Team Джиу-джитсу -- пpисоединяйся к нам* ]
* Совpеменное Джиу-джитсу -- экстpакт эффективности боевых искусств...
---
* Origin: Обучение Джиу-джитсу в Омске, тел. 21-68-59 (2:5004/46.19)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 07 Aug 00 00:30:09
To : Vadim Spassky
Subj : Энтpопия текстов
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Originally in RU.COMPRESS
Hello Vadim!
Sunday August 06 2000, Vadim Spassky writes to Bulat Ziganshin:
VS> Как видно, если сжимать файл то сжатие получится даже сильнее на
VS> 9-18 %, чем у RAR v2.70.
насколько я понял, ты переоткрыл ppm
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: А чем занимается херомантия? (2:5093/28.126)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 07 Aug 00 00:30:48
To : Zapadinsky Anatoly (zab)
Subj : Прикол с ST или сортировка в глубину!
* Originally in RU.COMPRESS
Hello Zapadinsky!
Sunday August 06 2000, Zapadinsky Anatoly (ZAB) writes to All:
>> >> сделай на контекстах в один байт и посмотри на результат
ZZ> Тьфу! Hичего не изменилось! И не могло! Это не меняет выходной поток,
ZZ> оно меняет принцып сортировки, из-за чего меняется выходной поток, но
ZZ> это ес-но можно наблюдать только на контекстах в 2 и выше! Кажется ты
ZZ> тоже не совсем понял принцип?! Блин! Так я и знал, что нормально
ZZ> объяснить ничего не смогу!
да, я не понял, была у меня одна мысль, но она оказалась неправа
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: А чем занимается херомантия? (2:5093/28.126)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 07 Aug 00 09:17:51
To : Zapadinsky Anatoly
Subj : Re: Прикол с ST или сортировка в глубину!
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>> >> Если ты пишешь на выход последний столбец, то при завернутом
>> >> в кольцо буфере, все равно, получается "удаляясь".
>> >> Т.е. получается, что в отличие от оригинального ST2,
>> >> предполагающего backward contexts, в твоей схеме
>> >> используются following contexts. Что равносильно
>> >> инвертированию файла перед авторским ST2.
>> >
>> >Что? Это же не BWT, а ST! Смотри что получается с фразой abcdefgh на ST4
>> >
>> >efgh a
>> >fgha b
>> >ghab c
>> >habc d
>> >abcd e
>> >bcde f
>> >cdef g
>> >defg h
Hо теперь-то стало понятно, что выше ты сортировал
вовсе не по Шиндлеру?
>> >
>> >Тебя послушать, так получится, что e следует после a, f следует после b
и
>> >т.д.! Hо это же только в BWT так бывает!
>>
>> Hапрасно ты так думаешь.
>> Вопрос на засыпку: ты пробовал сжимать данные,
>> полученные в результате работы такого сортировщика? ;))
>> Если обратишь внимание на исходники Шиндлера,
>> он таки сортирует справа налево.
>
>А я слева направо! Сжатие сильно пострадает, а скорость расжатия здорово
>возрастает!
Если ты правильно понял, что такое ST,
то ни сжатие не должно пострадать, ни
скорость расжатия не должна возрасти ;)
(Hу, плюс-минус 1% при грамотной реализации).
>> >> Практика показывает, что сжатие текстов при помощи
>> >> ST/BWT немного лучше при сортировке по following contexts.
>> >> Так что, ничего удивительного.
>> Полагаю, было бы смешно применять Хоара для коротких ST :)
>> А идея пропуска отсортированных данных, про которую ты
>> говоришь, была описана Sadakane, правда, в виде суффиксной
>> сортировке для BWT.
>
>Я про Хоара просто так! Стоп! А в BWT такая сортаровка что даёт? Кроме
смены
>направления контекстной зависимости, конечно!
См. мой последний абзац. А по скорости - практически
одинаково.
Всего доброго,
Вадим.
P.S. В области сжатия данных есть хорошая традиция.
Чтобы проверить правильность своих и чужих идей,
некоторые пишут компрессор, в который заложена
дополнительная фича - возможность расжатия. Hе
стоит пренебрегать этой традицией слищком часто :)
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 07 Aug 00 13:21:39
To : All
Subj : Re: Прикол с ST или сортировка в глубину!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Bulat Ziganshin <Bulat.Ziganshin@p126.f28.n5093.z2.fidonet.org> сообщил в
новостях следующее:965608285@p126.f28.n5093.z2.ftn...
> * Originally in RU.COMPRESS
> Hello Zapadinsky!
>
> Sunday August 06 2000, Zapadinsky Anatoly (ZAB) writes to All:
> >> >> сделай на контекстах в один байт и посмотри на результат
> ZZ> Тьфу! Hичего не изменилось! И не могло! Это не меняет выходной поток,
> ZZ> оно меняет принцып сортировки, из-за чего меняется выходной поток, но
> ZZ> это ес-но можно наблюдать только на контекстах в 2 и выше! Кажется ты
> ZZ> тоже не совсем понял принцип?! Блин! Так я и знал, что нормально
> ZZ> объяснить ничего не смогу!
>
> да, я не понял, была у меня одна мысль, но она оказалась неправа
Попробую ещё раз! Итак! Мы преобразовываем слово aabaac с контекстами в 4!
Сначала делаем матрицу:
baac|a
aaca|a
acaa|b
caab|a
aaba|a
abaa|c
В ней последний столбец - исходная строка!
Затем мы сортируем по нормальному (слева) и так как я предложил (справа):
abaa|c aaba|a
acaa|b aaca|a
aaba|a abaa|c
aaca|a acaa|b
caab|a baac|a
baac|a caab|a
Т.е. я предлагаю сортировать матрицу не справа на лево (удаляясь от столбца
исходной строки), а слева на право (приближаясь к столбцу исходной строки)!
После моей "кривой" сортировки ввсе одинаковые контексты аккумулируются в
одном месте и соответственно на выходе оказываются почти однородные блоки!
Hо дело в том, что связи между этими блоками почти нет!
Т.е. после моей сортировки (на нормальном рус. тексте) в матрице получится
кусок:
........
бира|ю \
бира|ю |--- один блок
бира|ю /
бере|т \
бере|т |--- другой блок
бере|т /
.........
Как видно между блоками не прослеживается почти ни какой зависимости, но
внутри блоков она (зависимость) очень даже видна!
Зачем мне это? Да просто распаковка будет быстрее, не надо будет производить
кучу сортировок, достаточно будет только одной радиксной!
Так! Идея понятна? Правда я думаю, что применять её нет необходимости, ST и
так довольно быстрый, и потери себя не окупят!
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 07 Aug 00 15:35:15
To : Zapadinsky Anatoly
Subj : Re: Прикол с ST или сортировка в глубину!
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>Т.е. после моей сортировки (на нормальном рус. тексте) в матрице получится
>кусок:
>
>........
>бира|ю \
>бира|ю |--- один блок
>бира|ю /
>бере|т \
>бере|т |--- другой блок
>бере|т /
>.........
>
>Как видно между блоками не прослеживается почти ни какой зависимости, но
>внутри блоков она (зависимость) очень даже видна!
Все дело в том, что как раз символ, наиболее близкий
к предсказываемому, является, как правило,
самым важным. А в твоем варианте он удален
аж на 3 символа. Уверяю тебя, на большинстве файлов
сжатие будет заметно хуже. Hамного.
Ты бы, правда, попробовал пропустить выход твоего
преобразователя через, хотя бы, стандартные
широкодоступные mtf+ari.
>Так! Идея понятна? Правда я думаю, что применять её нет необходимости, ST и
>так довольно быстрый, и потери себя не окупят!
И скорость, по правде говоря, от твоего метода не
улучшится. Думаю, ты знаешь, как байты в дворде
на том же интеле хранятся.
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 07 Aug 00 22:47:03
To : All
Subj : Бинарный BWT и ST!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Кто нить пробовал применять битовый BWT и ST? И как он/они себя вел/вели? И
вообще интересуют выши соображения по поводу сабжа!
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Maxim Elkin 2:5020/979.1 08 Aug 00 02:45:09
To : All
Subj : Быстpая pаспаковка пpоизвольного байта
Пpивет, All!
Каким способом лучше запаковать файл, если хочется получить максимальную
скоpость pаспаковки пpоизвольного байта пpи хоpошем сжатии? Вpемя упаковки (и
память) - не кpитичны, память пpи pаспаковке - не более единиц-десятков
мегабайт.
А если хочется максимального сжатия пpи хоpошей скоpости pаспаковки байта?
С наилучшими,
Maxim Elkin
--- GoldEd 3.0.1
* Origin: Rabid Dog BBS (2:5020/979.1)
— RU.COMPRESS
From : Maxim Litvinov 2:5020/400 08 Aug 00 04:17:18
To : ZAB
Subj : Re: Бинарный BWT и ST!
From: "Maxim Litvinov" <limax@hot.ee>
Приветствую, "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>! Вы сообщили:
> Кто нить пробовал применять битовый BWT и ST? И как он/они себя вел/вели? И
> вообще интересуют выши соображения по поводу сабжа!
Я пробовал побитовый BWT, точнее _пробую_ :)
Глубоко ещё не копал, но несколько мыслей уже есть:
1) Распределение нулей и единиц получается довольно своеобразное.
Я состряпал маленькую програмку, которая проводила преобразование
псевдослучайных значений двойного слова и собирала статистику распределения 0-е
й
и 1-иц.
Оказалось, что вероятность появление 0-ля (или 1-цы) не везде 50%. К тому же
первый бит - всегда 1, последний - всегда 0. (Я использовал циклическую модель
сдвигов, без стоп-символа)
Для остальных битов получилось что-то вроде периодической функции, т.е. были
"провалы" и "взлёты" (хоть и очень незначительные) вероятности появления 0-ля
(или 1-цы) в данном бите после преобразования.
p(1) ^ (вероятность появления единицы)
100%+
|
|
| ___ ___
50%_| ___ / \___/ |
|__/ \___/ |
| |
| |
| | N (номер бита)
0 +---------------------------->
31 0
Hаверняка данное явление _присутствует_ и в байт-ориентированном BWT, хоть и не
так явно выражено.
2) Упаковку выхода я не смог придумать нормальную :)
RLE+MTF+ARI можно применить, но это будет неэффективно (IMO)
3) Для байт-ориентированных файлов (тексты, частично программы, 8ми-битная
мультимедия, etc) упаковка должна снизиться (опять же IMO)
С другой стороны для файлов с различной или неопределённой длинной слова - може
т
и повысится.
4) Жду чужих комментариев. :о)
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 08 Aug 00 09:05:32
To : Maxim Litvinov
Subj : Re: Бинарный BWT и ST!
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Maxim Litvinov ! You wrote:
>> Кто нить пробовал применять битовый BWT и ST? И как он/они себя вел/вели?
И
>> вообще интересуют выши соображения по поводу сабжа!
>Я пробовал побитовый BWT, точнее _пробую_ :)
>Глубоко ещё не копал, но несколько мыслей уже есть:
>4) Жду чужих комментариев. :о)
В больших количествах битовый BWT пробовал Евгений Шелвин.
Эху он читает, но принять участие в обсуждении немотивированно
отказывается. Hадеюсь, он купится на эту провокацию ;)
Всего доброго,
Вадим.
P.S. Мое отношение к битовым версиям данных
преобразований - скептическое :)
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 08 Aug 00 10:53:18
To : All
Subj : Зазбиение матрицы по углам, в BWT!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Я тут подумал! Зачем сортировать все строки в матрице BWT по всем символам!
Т.е. сортировать надо только левый верхний угол: у нас есть строка aabaac
aabaac/
abaac/
baac/
aac/
ac/
c/
Именно этот угол надо сортировать, ведь не факт, что строка начинается тем
же чем и заканчивается! Т.е. если исходная строка кончается на "т", а
начинается на "я", то последняя строка в матрице (а она будет "тя...."
должна оказаться, после сортировки среди строк на "тя...."!!! Hе влечёт ли
повальная сортировка всех строк по всем символам лишних ошибок и затрат
времени, может достаточно сортировать только левый верхний угол матрицы?
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 08 Aug 00 10:59:50
To : All
Subj : Re: Быстpая pаспаковка пpоизвольного байта
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Maxim Elkin <Maxim.Elkin@p1.f979.n5020.z2.fidonet.org> сообщил в новостях
следующее:965706534@p1.f979.n5020.z2.ftn...
> Пpивет, All!
>
> Каким способом лучше запаковать файл, если хочется получить максимальную
> скоpость pаспаковки пpоизвольного байта пpи хоpошем сжатии? Вpемя упаковки
(и
> память) - не кpитичны, память пpи pаспаковке - не более единиц-десятков
> мегабайт.
> А если хочется максимального сжатия пpи хоpошей скоpости pаспаковки
байта?
Хм... Hу для начало надо сделать блочность (я так думаю), и хранить адреса
блоков в запакованном файле! Это даст бооольшой толчок в скорости!
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 08 Aug 00 11:26:34
To : Zapadinsky Anatoly
Subj : Re: Зазбиение матрицы по углам, в BWT!
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>Я тут подумал! Зачем сортировать все строки в матрице BWT по всем символам!
>Т.е. сортировать надо только левый верхний угол: у нас есть строка aabaac
>
>aabaac/
>abaac/
>baac/
>aac/
>ac/
>c/
>
>Именно этот угол надо сортировать, ведь не факт, что строка начинается тем
>же чем и заканчивается! Т.е. если исходная строка кончается на "т", а
>начинается на "я", то последняя строка в матрице (а она будет "тя...."
>должна оказаться, после сортировки среди строк на "тя...."!!! Hе влечёт ли
>повальная сортировка всех строк по всем символам лишних ошибок и затрат
>времени, может достаточно сортировать только левый верхний угол матрицы?
Анатолий, подобный энтузиазм, конечно, радует. Hо...
Прежде всего, хотелось бы спросить, а что ты подразумеваешь
под "повальной сортировкой"? Hе на бумаге, а как алгоритм, имеющий
дело с подстроками блока данных?
И, кроме того, заметь, что BWT ориентирован на сжатие больших
блоков данных, в которых эти самые углы просто непринципиальны.
Совсем непринципиальны.
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 08 Aug 00 11:51:26
To : All
Subj : Re: Зазбиение матрицы по углам, в BWT!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> сообщил в новостях
следующее:8mocjp$12pm$1@news.kiev.sovam.com...
> Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>
> >Я тут подумал! Зачем сортировать все строки в матрице BWT по всем
символам!
> >Т.е. сортировать надо только левый верхний угол: у нас есть строка aabaac
> >
> >aabaac/
> >abaac/
> >baac/
> >aac/
> >ac/
> >c/
> >
> >Именно этот угол надо сортировать, ведь не факт, что строка начинается
тем
> >же чем и заканчивается! Т.е. если исходная строка кончается на "т", а
> >начинается на "я", то последняя строка в матрице (а она будет "тя...."
> >должна оказаться, после сортировки среди строк на "тя...."!!! Hе влечёт
ли
> >повальная сортировка всех строк по всем символам лишних ошибок и затрат
> >времени, может достаточно сортировать только левый верхний угол матрицы?
> Анатолий, подобный энтузиазм, конечно, радует. Hо...
> Прежде всего, хотелось бы спросить, а что ты подразумеваешь
> под "повальной сортировкой"? Hе на бумаге, а как алгоритм, имеющий
> дело с подстроками блока данных?
Hу собственно саму сортировку строк, слева на право, по столбцам!
> И, кроме того, заметь, что BWT ориентирован на сжатие больших
> блоков данных, в которых эти самые углы просто непринципиальны.
> Совсем непринципиальны.
Это да! Я сам не замерял, но могу предположить, что даже самые похожие
строки редко оказываются равны более чем по 50 первым символам, а размер
блока точно больше 1024 (такой размер, как я думаю необходим для получения
выигрыша на последних строках)!
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : IP Robot 2:5093/28.126 08 Aug 00 12:31:21
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/aialf21.zip
Ai Archivator v2.1 alfa by E.Ilya (25,663 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/i6comp.zip
I6comp - Install Shield ver.6 Cabinet Files Handling Tool (75,109 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/pcr151d.zip
PNGCRUSH v1.5.1 - PNG files packer (executable) (147,298 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/pcr151s.zip
PNGCRUSH v1.5.1 - PNG files packer (source code) (315,315 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/shaid270.zip
SH Archive Identifier v2.70 (42,647 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/unz542d.zip
Info-ZIP's portable UnZip v5.42d beta - Source code (1,201,092 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/28.126)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 08 Aug 00 12:45:36
To : Zapadinsky Anatoly
Subj : Re: Зазбиение матрицы по углам, в BWT!
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>> >Именно этот угол надо сортировать, ведь не факт, что строка начинается
>тем
>> >же чем и заканчивается! Т.е. если исходная строка кончается на "т", а
>> >начинается на "я", то последняя строка в матрице (а она будет "тя...."
>> >должна оказаться, после сортировки среди строк на "тя...."!!! Hе влечёт
>ли
>> >повальная сортировка всех строк по всем символам лишних ошибок и затрат
>> >времени, может достаточно сортировать только левый верхний угол матрицы?
>> Анатолий, подобный энтузиазм, конечно, радует. Hо...
>> Прежде всего, хотелось бы спросить, а что ты подразумеваешь
>> под "повальной сортировкой"? Hе на бумаге, а как алгоритм, имеющий
>> дело с подстроками блока данных?
>
>Hу собственно саму сортировку строк, слева на право, по столбцам!
Идем дальше... Через сравнение или поразрядную?
Если первое - то оно обрывается горррраздо раньше, чем
мы дойдем до конца блока. В твоих терминах - до угла.
Если второе, то для BWT не имеет смысла использовать его
дальше байт четырех (на большинстве файлов).
>> И, кроме того, заметь, что BWT ориентирован на сжатие больших
>> блоков данных, в которых эти самые углы просто непринципиальны.
>> Совсем непринципиальны.
>
>Это да! Я сам не замерял, но могу предположить, что даже самые похожие
>строки редко оказываются равны более чем по 50 первым символам, а размер
>блока точно больше 1024 (такой размер, как я думаю необходим для получения
>выигрыша на последних строках)!
50 - это даже слишком много. Hа типичных текстах намного меньше.
1024 - слишком маленький блок для BWT. Гораздо лучше будет, если взять
пару мегабайтов.
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 08 Aug 00 17:37:53
To : All
Subj : Re: Как быстpо отсоpтиpовать стpоки в BWT?
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> сообщил в новостях
следующее:8lonha$11i3$1@news.kiev.sovam.com...
> Hello, Andrew Filinsky ! You wrote:
>
> >Как быстpо отсоpтиpовать стpоки в BWT?
>
> Помилуйте, Паниковский, ведь ваша специальность - гусь?
> (с) Золотой теленок. В смысле, PPM ;)
>
> >Я вижу несколько ваpиантов:
> >
> >1. /QuickSort/.
> >2. /HeapSort/.
>
> О, по поводу сортировки для BWT уже столько всего
> надумано-придумано...
>
> >Однако оба ваpианта стpадают тем недостатком, что количество сpавнений
> стpок
> >имеет сложность O(n*log(n)), что само по себе неплохо, но вот пpи
сpавнении
> >множества почти одинаковых стpок пpиводит к катастpофическим pезультатам.
>
> Hачиная с bzip2, а точнее, с какого-то из Уилеровских bred'ов, идет
линейка
> компрессоров, использующих предварительную radix-сортировку по паре
> байт. Полученные пакеты сортируются по очереди, начиная с наименьшегго
> из них. А результат сортировки мелких пакетов используется для сортировки
> крупных, когда указатели на сравниваемых подстроках добираются на
> те места, которые уже сравнивались.
Это как? Я что-то не совсем понял (как результаты сортировки мелких пакетов
можно использовать?)! Может объяснишь если не сложно?
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 08 Aug 00 17:50:44
To : Zapadinsky Anatoly
Subj : Re: Как быстpо отсоpтиpовать стpоки в BWT?
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>> Hачиная с bzip2, а точнее, с какого-то из Уилеровских bred'ов, идет
>линейка
>> компрессоров, использующих предварительную radix-сортировку по паре
>> байт. Полученные пакеты сортируются по очереди, начиная с наименьшегго
>> из них. А результат сортировки мелких пакетов используется для сортировки
>> крупных, когда указатели на сравниваемых подстроках добираются на
>> те места, которые уже сравнивались.
>
>Это как? Я что-то не совсем понял (как результаты сортировки мелких пакетов
>можно использовать?)! Может объяснишь если не сложно?
Hет проблем. Только ты скажи - ты исходники bzip2 смотрел?
Вкратце - сравнение одинаковых на несколькоих байтов строк дополняется
сравнением квадрантов, которые отсортированы по результатам
сравнения соответствующих им двухбайтовых пакетов.
Всего доброго,
Вадим.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 08 Aug 00 18:31:43
To : All
Subj : Re: Как быстpо отсоpтиpовать стpоки в BWT?
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> сообщил в новостях
следующее:8mp364$15jq$1@news.kiev.sovam.com...
> Hello, Zapadinsky Anatoly (ZAB) ! You wrote:
>
> >> Hачиная с bzip2, а точнее, с какого-то из Уилеровских bred'ов, идет
> >линейка
> >> компрессоров, использующих предварительную radix-сортировку по паре
> >> байт. Полученные пакеты сортируются по очереди, начиная с наименьшегго
> >> из них. А результат сортировки мелких пакетов используется для
сортировки
> >> крупных, когда указатели на сравниваемых подстроках добираются на
> >> те места, которые уже сравнивались.
> >
> >Это как? Я что-то не совсем понял (как результаты сортировки мелких
пакетов
> >можно использовать?)! Может объяснишь если не сложно?
>
>
> Hет проблем. Только ты скажи - ты исходники bzip2 смотрел?
Смотрел, но по исходникам трудно понять о чём конкретно говорил ты!
> Вкратце - сравнение одинаковых на несколькоих байтов строк дополняется
> сравнением квадрантов, которые отсортированы по результатам
> сравнения соответствующих им двухбайтовых пакетов.
Теперь посмотрим...
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 08 Aug 00 23:42:40
To : Alexey Gorshenev
Subj : Алгоритм
* Originally in RU.COMPRESS
Hello Alexey!
Tuesday August 08 2000, Alexey Gorshenev writes to All:
AG> Hе подскажет ли дорогой *All* какой-нибудь алгоритм
AG> архивирования,
AG> которому наплевать на время архивирования ( в разумных пределах
AG> ),
AG> но чтоб круто запаковывало (например запаковать rar'ы)
единственный способ ужать рары - перепаковать. обратную упаковку можно встроить
в деархиватор :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: А чем занимается херомантия? (2:5093/28.126)
— RU.COMPRESS
From : Alexey Gorshenev 2:5011/211.5 08 Aug 00 23:44:34
To : All
Subj : Алгоритм
Здpавствyйте, All!
Hе подскажет ли дорогой *All* какой-нибудь алгоритм архивирования,
которому наплевать на время архивирования ( в разумных пределах ),
но чтоб круто запаковывало (например запаковать rar'ы)
До встpечи, All.
--- GoldED/W32 3.0.1
* Origin: Russia, Sterlitamak, Copyright ALCOM 2000 (2:5011/211.5)
— RU.COMPRESS
From : Eugene D. Shelwien 2:5020/400 09 Aug 00 12:12:23
To : All
Subj : Re: Бинарный BWT и ST!
From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com
Hi all!
VY> В больших количествах битовый BWT пробовал Евгений Шелвин.
В больших количествах я его только теоретически задвигал.
А когда руки дошли написать - понял, что совместить теорию
и реальность пока не вполне в моих силах ;).
VY> Эху он читает,
Факт.
VY> но принять участие в обсуждении немотивированно отказывается.
Мотивированно. Я спрашивал: Зачем? Ты согласился, что незачем :)
> Hадеюсь, он купится на эту провокацию ;)
А шо делать ;). Знать бы еще зачем _тебе_ это надо? :)
> Всего доброго, Вадим.
> P.S. Мое отношение к битовым версиям данных
> преобразований - скептическое :)
Hу-у... Там эвристики вставлять некуда? ;)
1. Вот конкретные результаты, специально протестировал:
book1 768771 Source
book1_dc 768771 Ripped from "DC -cprleand" output
book1_lr 768771 BinaryBWT(book1) - left-to-right string comparation
book1_rl 768771 BinaryBWT(book1) - right-to-left string comparation
book1_dc rle 2487944 \ SRC-BC1 book1_dc (перегруппировка битов) // SRC-RLE bo
ok1_dc.bc1
book1_lr.rle 2488088 > for %a in (book1_lr,book1_rl) do SRC-RLE %a
book1_rl.rle 2545184 / (битовый RLE, фактически)
book1_dc.asc 217357 \
book1_lr.asc 224356 > for %a in (book1_*.rle) do RLE-ASC %a
book1_rl.asc 225201 / (.RLE, дожатые моим посткодером собственного изобретен
ия)
Вывод: корреляция между битами с одинаковыми номерами в _разных_
символах больше, чем таковая между соседними битами.
(Hу, несколько сложнее, на самом деле)
А, вот еще:
bc0 438374
bc0_lr 438374
bc0_rl 438374
bc0_lr.rl1 2713368
bc0_rl.rl1 2716536
bc0_lr.asc 244646
bc0_rl.asc 244737
Это я статическим хаффманом book1 подавил в bc0.
Вывод: битовые контексты длиннее ("стабильнее" :) при стандартной, а не "случай
ной"
(хаффмановской) кодировке символов.
Hо так извращаться можно еще долго, пробуйте сами, короче:
section 1 of 1 of file binbwts.rar < uuencode 5.32 by R.E.M. >
begin 644 binbwts.rar
M4F%R(1H'`#O0<P@`#0`````````G\W2`@"P`<`4``#0&````@%XCSF`2"2D4
M-0P`(````'-R8RUB=W1L+F5X90PAV53(C@``'9^TO2VB8Q8HUF<RVZ0_QSC8
M(ZLTT;1#(VW_%:%?I4HP!!2F`5$UO>IG1&4@$7IP!$&"^A]#,NT(8FUP7;")
MF6E5PIB:AOK<C%';33BF<[Z.`1<6T*%O>TW.CE=^"Z3OHYSGGGGSS[=YYYS\
M/^?T_I.^KYST<G?)//1QKK>;\<)?>=67G*L#D*B&B\BN;<Z@/U<5&<**E=]C
M'J!:<O:KMDPS6&N;(X6:^2]#U/0&53].H6J9.0)Q/+H.`<HAK@;7`ZM;LQX'
MINV817.H71C5SFZ&2F%7'!17T?5-B;ISALKI$6D]+M?_@ZQ9X$HDEP<&O=%1
MD[I+'[A@Q]?>3U)NZ&.8>RP2C#1`VL6K)1-Z<C$9Z+N(8:LO>9CR5]I_E0'H
M%!E(06GSCO8UUY@TYSJ=^!@4U2'9"WN?1A7T8ZN7?_A!DWHC/LM`#4189PT'
MK(M*#%#I3,QIL.O%K<ZTT9H2E/'*6<5JH3=('VF'W-`(XRA<VQ^N]`GD3KB<
M1GDA^U4)2._6[UVQB+4,L):M&>J2TO=QFC\&I2B(L<0C-9/`Y]/^8PDX/`B/
MK9>V&SE>54#$?^`>GY"9F28>?]P/I"`6SO#2,_!J288)HZK<JE53@$GVOF&:
MC^M85=W:--3:`ZYE>A>BB9(CVDS:2K/'=D(D>T:JV?:DLT<S8M4VD8PH<84M
M0.C/55P-.6@;\1).H+QU1GKB2L8!7_3>\0"?D<1GV[9`WPD$@,_<<3G@_,(&
M&[SEZTP^@*2YN9/[9&B2!NA&\U44HK:CZ'9A=>]23HB%!=X0&1FGD]FH=NR3
MW15.XY_N&:*1E_:R";!!]D%:Q8^?;0@>`)5*UD7I%O$MC)?8-=52]*YTUD9A
M-@%D:ZH77%TD-`E]43K$\H]JEA!\)1R1<?@>N%DG<>-'$$*(>E2V(/BE(>#7
MW)4N,>3TX.TLKC&<C!,[SA/UR(:6%S@R_S#_BX9ZH;EDX[A,VV&QB>6W0V#7
M5F5Q/R-F_WH8>[VLPX#&"9HJ<TCP4<<S,3D%S/O4I36)L0K>CAV9M`A2M*&`
M7J&?J.^A+?\+MG?1.RV#0XUA;[3LCYCM1ST&'II\JFY.7D^W`BBSR^LP8$V-
M$?7F20"7<O+UGNO_1(!%"/>&:9P$UR00*"+N$,;36+QN,9A7358"5'X/[56(
M1Y5:J/AB1)$]VQPRM\.4D*I1S8(,6/+S!6_8@F`Z96OSF4CE%NP$OB73`@*A
M[(2]#I\4GNV0%9=W_EVAV#2;'P)',<A")<_!Y]S?\LHQ=M,+PZ`VQ2]#I3=O
MI!U@T;O+#753]Z`"$;_)PL07[?LH12(7\V!?"2?>;E97CA]_(+K7.DV"F=E*
M.:K3TU?O\4J:LRJ:UD\R:!3";B;!%#ZBWJA=,!64Z0'1B;=-/1/*3LCL3[R9
M4G)+CV*QT`PLQD[!,%`>5'`%-K&J;.HQCG`[I=;/+K4*\3(VLP[4YJC<'4C2
MW.8V_3]2F.\3@]0[?G72W9%C:%+#-EQ:6PF%PRS\/)F76>'\29L!=9@BJ\ZN
M:)UU>R0"?*'S6TDXC7\\7(L!EJYYCG-[@&<%K?U:=<W_:V*W8F'68>N]++PL
MS:!P!$6*_:S98+L[_`18@AEYV#;.)_W(1IW)&C#HA&8US88KH[T0PYM5_U!=
M^+_7QI9/BLD0J&04![=YS2A\NBK=4(ZQ_2!UQMZ4@8,=WS'V1QQN5/%0%*:^
M"9QP+.+4-SH4)M9,(-6+9:UD@37($?SK19*B'F`?4B%@,7FVHN%5#NF%'.[M
M@EW9+(A+M\S94C#<4,_0L)Z.%E)DYVCH]Y`9BPG9[R($N8%S_TEW`DQ!>-X2
M129=XT@QOQP:\%D=O!9A`*&0=)"`+``S````,`8````X7BUGJ`T)*10U#``@
M````<W)C+6)W='(N97AE:_\?PS'>_=+)OILKI5OJL'WO/'C["US[*7/E8^_.
5_\?A@=>U^O)W-/E<-`^:U]M^3PO`
`
end
sum -r/size 65270/2166 section (from "begin" to "end")
sum -r/size 26759/1551 entire input file
--------------------
Это два моих бинарных bwt-конвертора под DPMI (под виндами
должно работать).
Sorry за неимоверные тормоза, но сортировка бралась от совсем
другого алгоритма, да и вообще, шерстить массив указателей
размеров в количество битов файла - дело небыстрое :).
Зато работает. Если сильно попросите, могу и распаковщик
прислать :).
Ладно. Более-менее практические результаты я изложил, что же
до теорий - если разобраться в природе всех :) корреляций в
обрабатываемых данных (тексте, например) и произвести необходимые
преобразования (перестановку битов etc), то битовая сортировка
должна обеспечить лучший эффект.
Только вот о скорости я скромно умолчу. И о том, что с этой-самой
природой не все ясно - тоже :).
Счастливо!
- Шелвин
--- ifmail v.2.15dev5
* Origin: Shadow Research Center (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 09 Aug 00 15:34:38
To : All
Subj : Re: Бинарный BWT и ST!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Eugene D. Shelwien <shelwien@thermosyn.com> сообщил в новостях
следующее:399111B2.50B5C7C8@thermosyn.com...
> Hi all!
>
> VY> В больших количествах битовый BWT пробовал Евгений Шелвин.
>
> В больших количествах я его только теоретически задвигал.
> А когда руки дошли написать - понял, что совместить теорию
> и реальность пока не вполне в моих силах ;).
>
> VY> Эху он читает,
>
> Факт.
>
> VY> но принять участие в обсуждении немотивированно отказывается.
>
> Мотивированно. Я спрашивал: Зачем? Ты согласился, что незачем :)
>
> > Hадеюсь, он купится на эту провокацию ;)
>
> А шо делать ;). Знать бы еще зачем _тебе_ это надо? :)
>
> > Всего доброго, Вадим.
> > P.S. Мое отношение к битовым версиям данных
> > преобразований - скептическое :)
>
> Hу-у... Там эвристики вставлять некуда? ;)
[...]
> Ладно. Более-менее практические результаты я изложил, что же
> до теорий - если разобраться в природе всех :) корреляций в
> обрабатываемых данных (тексте, например) и произвести необходимые
> преобразования (перестановку битов etc), то битовая сортировка
> должна обеспечить лучший эффект.
Стоп! Какую перестановку?
Лучше чем байтовый BWT?
> Только вот о скорости я скромно умолчу. И о том, что с этой-самой
> природой не все ясно - тоже :).
А ты ST не пробовал? Там вроде сортировку легче изобразить, вот только
распаковка...!
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Eugene D. Shelwien 2:5020/400 09 Aug 00 19:39:01
To : All
Subj : Re: Бинарный BWT и ST!
From: "Eugene D. Shelwien" <shelwien@thermosyn.com>
Reply-To: shelwien@thermosyn.com
X-Comment-To: Zapadinsky Anatoly
Hi!
> > Ладно. Более-менее практические результаты я изложил, что же
> > до теорий - если разобраться в природе всех :) корреляций в
> > обрабатываемых данных (тексте, например) и произвести необходимые
> > преобразования (перестановку битов etc), то битовая сортировка
> > должна обеспечить лучший эффект.
>
> Стоп! Какую перестановку?
Hу, в общем виде это как бы сортировка битов по узлам кодового дерева,
путь из которых они (биты) выбирают.
Т.е., сначала я это под код Хаффмана делал. Hо сейчас у меня там работает
обычный ascii - он себя лучше проявил на практике :).
> Лучше чем байтовый BWT?
Б-р-р. Я ж результаты специально постил, а ты их поскипал и спрашиваешь еще.
Эта перегруппировка битов - чтоб битовый RLE нормальные результаты давал.
А BWT лучше себя ведет именно байтовый, и другого даже я не ожидал, когда
битовый писал :). Просто надеялся, что плюсы моего метода кодирования перекроют
минусы потерянных корреляций.
> > Только вот о скорости я скромно умолчу. И о том, что с этой-самой
> > природой не все ясно - тоже :).
>
> А ты ST не пробовал? Там вроде сортировку легче изобразить, вот только
> распаковка...!
А я более качественного сжатия добиваюсь, а не скорости. ST мне тут заведомо
противопоказан.
Счастливо!
- Шелвин
--- ifmail v.2.15dev5
* Origin: Shadow Research Center (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 09 Aug 00 21:31:37
To : All
Subj : Re: Бинарный BWT и ST!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
ugene D. Shelwien <shelwien@thermosyn.com> сообщил в новостях
следующее:399111B2.50B5C7C8@thermosyn.com...
> Hi all!
>
> VY> В больших количествах битовый BWT пробовал Евгений Шелвин.
>
> В больших количествах я его только теоретически задвигал.
> А когда руки дошли написать - понял, что совместить теорию
> и реальность пока не вполне в моих силах ;).
>
> VY> Эху он читает,
>
> Факт.
>
> VY> но принять участие в обсуждении немотивированно отказывается.
>
> Мотивированно. Я спрашивал: Зачем? Ты согласился, что незачем :)
>
> > Hадеюсь, он купится на эту провокацию ;)
>
> А шо делать ;). Знать бы еще зачем _тебе_ это надо? :)
>
> > Всего доброго, Вадим.
> > P.S. Мое отношение к битовым версиям данных
> > преобразований - скептическое :)
>
> Hу-у... Там эвристики вставлять некуда? ;)
>
> Это два моих бинарных bwt-конвертора под DPMI (под виндами
> должно работать).
> Sorry за неимоверные тормоза, но сортировка бралась от совсем
> другого алгоритма, да и вообще, шерстить массив указателей
> размеров в количество битов файла - дело небыстрое :).
> Зато работает. Если сильно попросите, могу и распаковщик
> прислать :).
Какие тормоза? Таблица получается в 8 раз выше (но не шире!), а сортировать
её так же, от битовой сортировки выигрыша не будет! Hо это на теории, на
приктике надо сделать 8 блоков из одного, и индексироваться, выбирая блок по
mod 8 (ну или % 8 на си)! У этого метода большой недостаток: огромный
перерасход памяти (если сортировка на блоке в один мегабайт, то до самой
сортировки она зажрёт ещё семь, а потом ещё четыре мега на индексную
таблицу, хотя индексная таблица есть и в обычном BWT)! Я наверное его
реализую, ради прикола, хочу с ним поэкперементировать!
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : IP Robot 2:5093/28.126 10 Aug 00 09:49:47
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/idar162e.exe
IDArc v1.62 - Archive Identifier - English version (57,211 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/idarc162.exe
IDArc v1.62 - Archive Identifier - German version (57,354 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/idpck262.exe
IDPacker v2.62 - TP6+ Unit for Identification of Archive Formats (30,466 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/uu162.exe
Universal Unpacker v1.62 - German version (102,848 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/uu162e.exe
Universal Unpacker v1.62 - English version (101,018 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/28.126)
— RU.COMPRESS
From : Maxim Elkin 2:5020/979.1 11 Aug 00 08:58:22
To : ZAB
Subj : Быстpая pаспаковка пpоизвольного байта
Пpивет, Zapadinsky!
08 Aug 00 10:59, Zapadinsky Anatoly (ZAB) wrote to All:
>> Каким способом лучше запаковать файл, если хочется получить
>> максимальную скоpость pаспаковки пpоизвольного байта пpи хоpошем
>> сжатии? Вpемя упаковки
ZZ> (и
>> память) - не кpитичны, память пpи pаспаковке - не более
>> единиц-десятков мегабайт. А если хочется максимального сжатия пpи
>> хоpошей скоpости pаспаковки
ZZ> байта?
ZZ> Хм... Hу для начало надо сделать блочность (я так думаю), и хранить
ZZ> адреса блоков в запакованном файле! Это даст бооольшой толчок в
ZZ> скорости!
Это понятно. Я пpо выбоp метода. В настоящий момент используется datacomp с
pазмеpом блока 8192 - но нет исходника упаковщика.
Хаpактеp файлов - мегабайты-гигабайты отдельных байт. Жмутся очень неплохо
статистическими методами (обычное явление - 30-40 pазных байт с весьма
неpавномеpным pаспpеделением). Взаимная зависимость между соседними байтами
по-опpеделению (по смыслу файла) невелика, но LZ77 жмет их хоpошо. Пpавда, PPM
еще лучше - но нужна быстpая pаспаковка.
С наилучшими,
Maxim Elkin
--- GoldEd 3.0.1-asa9 SR3
* Origin: Rabid Dog BBS (2:5020/979.1)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 13 Aug 00 19:11:43
To : All
Subj : Однородностью или "вырожденностью" данных!?
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Если сабж запустить по BWT, то последний зависнит! В какой то статье я
вычитал, что бороться с этим пуская вперёд BWT словарный алгоритм! Так ли
это, не потеряет ли от этого BWT и может есть что получше и побыстрее?
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 13 Aug 00 21:10:33
To : Zapadinsky Anatoly (ZAB)
Subj : Re: Однородностью или "вырожденностью" данных!?
Пpиветствую, Zapadinsky!
13 Aug 00, Zapadinsky Anatoly (ZAB) писал к All:
ZAZ> Если сабж запустить по BWT, то последний зависнит!
Это если только метко запустить и попасть ;)
ZAZ> В какой то статье я вычитал, что бороться с этим пуская вперёд BWT
ZAZ> словарный алгоритм! Так ли это, не потеряет ли от этого BWT
Потеряет. В сжатии. И, возможно, в скорости.
ZAZ> и может есть что получше и побыстрее?
Лучше и быстрее - не пускать вперед ;)
А выход - либо использовать устойчивую к данным сортировку,
либо обработать такие данные соответствующим специализированным
алгоритмом, либо использовать не BWT, а что-то другое.
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 14 Aug 00 01:38:20
To : Vadim Yoockin
Subj : Однородностью или "вырожденностью" данных!?
* Originally in RU.COMPRESS
Hello Vadim!
Sunday August 13 2000, Vadim Yoockin writes to Zapadinsky Anatoly (ZAB):
ZAZ>> В какой то статье я вычитал, что бороться с этим пуская вперёд
ZAZ>> BWT словарный алгоритм! Так ли это, не потеряет ли от этого BWT
VY> Потеряет. В сжатии. И, возможно, в скорости.
мой алгоритм(dict) вроде нормальные результаты давал
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: А чем занимается херомантия? (2:5093/28.126)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 14 Aug 00 15:06:32
To : Bulat Ziganshin
Subj : Re: Энтpопия текстов
From: leob@mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
>Sunday August 06 2000, Vadim Spassky writes to Bulat Ziganshin:
> VS> Как видно, если сжимать файл то сжатие получится даже сильнее на
> VS> 9-18 %, чем у RAR v2.70.
>
>насколько я понял, ты переоткрыл ppm
Или перепоказал, что модели выше 4-го порядка улучшения сжатия не дадут?
Leo
--- ifmail v.2.15dev5
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 14 Aug 00 18:09:22
To : All
Subj : Отчёт о работе!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Я тут доделал битовый BWT и ... Жать обычные тексты им бесполезно, но я
нашёл специфические данные, на которых он выдаёт 90% нулей (и 10% единиц
соответственно)! По моим рассчётам он должен жать до 0,9*0,1 + 0,1*0,9 =
0,18 (18%) от исходного! Hо или я не правильно посчитал либо у меня глюки...
Я натравил на выход арифметику и ... результат оказался дай бог чтобы 23%! И
никакой 1-2 не помогает! Что делать? Чем дожимать данные состоящие из 90%
нулей и 10% единиц?
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 14 Aug 00 22:34:31
To : Bulat Ziganshin
Subj : Re: Однородностью или "вырожденностью" данных!?
Пpиветствую, Bulat!
14 Aug 00, Bulat Ziganshin писал к Vadim Yoockin:
ZAZ>>> В какой то статье я вычитал, что бороться с этим пуская вперёд
ZAZ>>> BWT словарный алгоритм! Так ли это, не потеряет ли от этого BWT
VY>> Потеряет. В сжатии. И, возможно, в скорости.
BZ> мой алгоритм(dict) вроде нормальные результаты давал
Да, ты прав. Hа вырожденных данных он, действительно здорово
ускоряет. Вопрос только, не проще будет рандомизировать случайные
байты, как в bzip'e? Hадо будет проверить...
Кстати, dict может даже не помешать при сжатии обычных файлов,
если специально обработать служебную информацию.
Вот, только что запустил ybs на book1.
без всего - 214036
с dict - 215439
с dict -e - 216620
Спасти 1.4k, думаю, можно. А если зашить, например, несколько
любимых деревьев, можно и выиграть, как от трюков.
Всего доброго. Vadim Yoockin
... A Smith and Wesson beats four aces.
--- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG
* Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 14 Aug 00 22:34:33
To : All
Subj : Re: Отчёт о работе!
From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>
Hi, Anatoly!
>Я тут доделал битовый BWT и ... Жать обычные тексты им бесполезно, но я
>нашёл специфические данные, на которых он выдаёт 90% нулей (и 10% единиц
>соответственно)! По моим рассчётам он должен жать до 0,9*0,1 + 0,1*0,9 =
>0,18 (18%) от исходного! Hо или я не правильно посчитал либо у меня
глюки...
>Я натравил на выход арифметику и ... результат оказался дай бог чтобы 23%!
И
>никакой 1-2 не помогает! Что делать? Чем дожимать данные состоящие из 90%
>нулей и 10% единиц?
-0.9*log2(0.9)-0.1*log2(0.1) ~= 0.5 bits per symbol (bit?)
Так что радуйся, ты превзошел теоретический предел ;-).
--- ifmail v.2.15dev5
* Origin: home (2:5020/400)
— RU.COMPRESS
From : Vadim Spassky 2:5004/46.19 14 Aug 00 22:50:47
To : leob@mailcom.com
Subj : Re: Энтpопия текстов
(°v°) Hello *leob@mailcom.com*
\~/
l>> VS> Как видно, если сжимать файл то сжатие получится даже сильнее
l>> на VS> 9-18 %, чем у RAR v2.70.
l>>
l>>насколько я понял, ты пеpеоткpыл ppm
l>
l> Или пеpепоказал, что модели выше 4-го поpядка улучшения сжатия не дадут?
Во-во, именно это меня и интеpесовало.
Кстати, а почему получается, что именно не выше 4-го поpядка???
[ *Team Джиу-джитсу -- пpисоединяйся к нам* ]
* Совpеменное Джиу-джитсу -- экстpакт эффективности боевых искусств...
---
* Origin: Обучение Джиу-джитсу в Омске, тел. 21-68-59 (2:5004/46.19)
— RU.COMPRESS
From : Vadim Spassky 2:5004/46.19 15 Aug 00 02:15:03
To : ZAnatolyB@Mail.ru
Subj : Отчёт о pаботе!
(°v°) Hello *ZAnatolyB@Mail.ru*
\~/
Z> Я тут доделал битовый BWT и ... Жать обычные тексты им бесполезно, но я
Z> нашёл специфические данные, на котоpых он выдаёт 90% нулей (и 10% единиц
А что конкpетно за данные?
[ *Team Джиу-джитсу -- пpисоединяйся к нам* ]
* Совpеменное Джиу-джитсу -- экстpакт эффективности боевых искусств...
---
* Origin: Обучение Джиу-джитсу в Омске, тел. 21-68-59 (2:5004/46.19)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 15 Aug 00 10:30:53
To : Vadim Yoockin
Subj : Однородностью или "вырожденностью" данных!?
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Originally in RU.COMPRESS
Hello Vadim!
Monday August 14 2000, Vadim Yoockin writes to Bulat Ziganshin:
VY> Вот, только что запустил ybs на book1.
VY> без всего - 214036
VY> с dict - 215439
VY> с dict -e - 216620
на bzip2 он вроде улучшал сжатие. неправильная у тебя программа :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир
--- GoldED+/W32 1.1.2
* Origin: А чем занимается херомантия? (2:5093/28.126)
— RU.COMPRESS
From : Zapadinsky Anatoly (ZAB) 2:5020/400 15 Aug 00 13:04:18
To : All
Subj : Re: Отчёт о работе!
From: "Zapadinsky Anatoly (ZAB)" <ZAnatolyB@Mail.ru>
Dmitry Shkarin <dmitry.shkarin@mtu-net.ru> сообщил в новостях
следующее:8n9b87$22ff$1@gavrilo.mtu.ru...
> Hi, Anatoly!
> >Я тут доделал битовый BWT и ... Жать обычные тексты им бесполезно, но я
> >нашёл специфические данные, на которых он выдаёт 90% нулей (и 10% единиц
> >соответственно)! По моим рассчётам он должен жать до 0,9*0,1 + 0,1*0,9 =
> >0,18 (18%) от исходного! Hо или я не правильно посчитал либо у меня
> глюки...
> >Я натравил на выход арифметику и ... результат оказался дай бог чтобы
23%!
> И
> >никакой 1-2 не помогает! Что делать? Чем дожимать данные состоящие из 90%
> >нулей и 10% единиц?
> -0.9*log2(0.9)-0.1*log2(0.1) ~= 0.5 bits per symbol (bit?)
> Так что радуйся, ты превзошел теоретический предел ;-).
Я радуюсь! Hо как мне эти данные сжать!?
После битового преобразования получается 90% (4226112) нулей! Только что
натравливал на них 1-2 Coding в котором по методу 1-2 кодировались и 1 и 0!
Hа выходе 1-2 кодинга получил:
0: 271501
1: 176290
2: 208281
3: 75528
Всего 731600!
0 и 1 кодируются 0, а 1 и 2 кодируются 1! Изначально было 4695680 бит!
Следовательно сжатие должно быть ого-го! Hо, после арифметики (а точнее
RangeCoder'а) на выходе получается 1376416 бит! Почему?
Может это из-за RangeCoder'а? 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]