| Предыдущий блок | Следующий блок | Вернуться в индекс |
— 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)
Предыдущий блок Следующий блок Вернуться в индекс