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