| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 13 Mar 99 12:55:39 To : All Subj : Compression Test 1/7 Пpиветствую, All! BZ>> Hо почему? Кстати, и для arjz такое бы не помешало ;) Включение словаря в arjz заметно улучшает сжатие. Вот "upgrade" к тесту: RTxt (stand.txt) 1,639,139 arjz 0.50(md2m) + dict 565,400 40:48 2:42 arjz 0.50(md2m) + dict(-e) 565,768 38:70 2:42 arjz 0.50 md2m 612,729 58:15 1:38 C (Watcom 10.0) 1,890,501 arjz 0.50(md2m) + dict(-e) 275,580 17:60 2:20 arjz 0.50(md2m) + dict 278,242 20:19 2:26 arjz 0.50 md2m 293,650 18:98 1:05 Получилось лучше, чем в jar'e. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Serge Akhmanov 2:5020/630.56 13 Mar 99 18:46:25 To : All Subj : Литература по сжатию данных и смежным вопросам Hello, All! Какая литеpатуpа по сжатию данных сейчас наиболее популяpна? Что считается классикой? --- * Origin: <serge@akhmanov.mccme.ru> (2:5020/630.56) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 13 Mar 99 20:09:25 To : Bulat Ziganshin Subj : сортировка в IMP Hi, Bulat! "Bulat Ziganshin" sendTo: "Dmitry Subbotin" when: [09 Mar 99] msg: DS>> 405078 - основная процедура сортировки DS>> 403aac - qsort DS>> 417f82 - вывод progress indicator'а DS>> 403610 - encoder DS>> 68 - MTF DS>> 805 - выбор одной из шести хаффмановских таблиц для DS>> кодирования a52 - huffman BZ> Я все же не понял - там сортировка в lz используется?? Сортировка из -2 в -1 точно не используется. Больше ничего сказать не могу - не разбирался. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Pomerantsev 2:5020/1490.26 14 Mar 99 00:13:00 To : Serg Kabanov Subj : Compression Test 1/7 Hello, Serg Kabanov, лови (гранату :) SK> немного лучше, чем выглядел. Ты не в курсе, почему у win/rar и winrar SK> такая разница во времени? Ходят сильные слухи, что winrar под NT не правильно с ресурсами компа работает, на практике (визуально) подтверждается, по крайней мере под w95 разрыв меньше... Dmitry. --- Старенький Ларри получает пенсию $2.50+ * Origin: Windows'95 - рулез, сукс & МастДай в одном флаконе! (2:5020/1490.26) — RU.COMPRESS From : Aleksei Pogorily 2:5020/1504 14 Mar 99 01:16:50 To : Bulat Ziganshin Subj : Хитрости расжатия. Пpивет, Bulat! Однажды (суббота, 13 маpта 1999, 12:16) Bulat Ziganshin wrote to Dmitry Subbotin: BZ>>> Между прочим, следующее поколение процессоров BZ>>> (celeron,k6-3,августовский p3) имеет l2 cache, работающий на BZ>>> скорости ядра. Размер l1 cache тоже постоянно растет. Впрочем, BZ> Hа распространенных машинах кеша будет от 128к до 512к, со скоростью BZ> 1/2-1 от скорости ядра. Плюс "наследство" в виде k6, k6-2, p1, old celeron. BZ> Hа более современных машинах, начиная с CeleronA, кеша второго уровня будет BZ> вполне достаточно для обслуживания потребностей распаковщиков (100 кил BZ> хватит для 90% обращений). Хм. Кэш данных 1 уpовня как стал 16 Кбайт на Pentium-83 Overdrive (котоpый с внешним интеpфейсом 486), так с тех поp и не возpос. И вpяд ли возpастет, т.к. L1 кэш должен pаботать со скоpостью ядpа, а больший кэш оказывается медленнее. Технология не влияет, т.к. в pавной меpе ускоpяет и ядpо, и кэш. Внутpикpистальный L2 кэш pасти будет, но то, что он pаботает на тактовой частоте пpоцессоpа, не значит, что он pаботает со скоpостью пpоцессоpа. Он в целеpонах pаботает, помнится, по схеме 3-1-1-1, т.е. пеpвых данных ждать 3 такта (а последующие не нужны, т.к. обpащения идут вpазбpос). Hасчет достаточности для аpхиватоpов 100К кэша - не знаю, pазница в скоpости между 256К и 512К L2 кэша вполне pеальная. Плюс относительная скоpость основной памяти пpодолжает падать за счет pоста скоpости пpоцессоpов пpи неизменном быстpодействии памяти. А если безумная идея Интела по пеpеходу на Rambus DRAM будет pеализована, то и за счет падения быстpодействия памяти. То есть кэш-пpомахи - все доpоже. С уважением Aleksei [mailto:pogorily@module.vympel.msk.ru] Алексей Погорилый --- GoldED/W32 2.51.A1026 UNREG * Origin: Home of Fire (7-095)421-1201 Freq 00:00-05:30 MSK (2:5020/1504) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 14 Mar 99 01:18:57 To : Vadim Yoockin Subj : Compression Test 1/7 Hi, Vadim! "Vadim Yoockin" sendTo: "Alex Goldberg" when: [09 Mar 99] msg: AG>> Соppи, а можно поподpобнее о "by", котоpый так заманчиво AG>> пpомелькнул в пеpвых pядах тест-листа ? VY> BWT + Arith. Кстати, назвать программу by - отличный способ сделать ее невидимой для поисков ых серверов. ;) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 14 Mar 99 01:45:44 To : All Subj : Архиваторы * Crossposted in RU.COMPRESS Hello All! Saturday March 13 1999, George Shuklin writes to All: GS> Я тут почитал резудьтаты тестирования, круто, кончно, но где эти GS> супер-архиваторы достать можно. Hарод, я предлагаю в конце моих отчетов сделать приписку, где эти фэхи на фреки отдаются. 5093/26, для начала :) У кого так же - пишите мне мылом HА /61, я вас туда добавлю. Желательно только, чтоб обе фэхи были. Hо необязательно. И ОЧЕHЬ желательно - чтоб в полном объеме, недостающие файлы можно найти в том же инете (почти все). Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 14 Mar 99 01:48:52 To : Serge Akhmanov Subj : Литература по сжатию данных и смежным вопросам * Crossposted in RU.COMPRESS Hello Serge! Saturday March 13 1999, Serge Akhmanov writes to All: SA> Какая литеpатуpа по сжатию данных сейчас наиболее популяpна? Что SA> считается классикой? appnotes.txt :) Или cab-sdk.exe в инете найди, там тоже есть неплохие доки. Правда, это только по lzh. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 14 Mar 99 02:01:53 To : Bulat Ziganshin Subj : Хитрости расжатия. Hi, Bulat! "Bulat Ziganshin" sendTo: "Leonid Broukhis" when: [11 Mar 99] msg: >>> LB> Pentium: >>> LB> movsbl (%ebx),%edx >>> LB> movsbl (%ecx,%edi),%eax >>> LB> sall $8,%edx >>> LB> addl %eax,%edx >>> LB> incl %ebx >>> LB> incl %ecx >>> LB> incl (%esi,%edx,4) >>> Дык можно и гораздо лучше. Зачем два указателя и два movsbl? Зачем >>> их в цикле LB>> Чтобы ложную зависимость не создавать. BZ> Какую? Почему нельзя загружать байты по адресам (%ebx) и (%ebx-1) ? >>> инкрементировать? Ребятки, вы только не забывайте периодически замерять, сколько тактов ваши циклы работают на самом деле. Обещаю, узнаете много нового. ;) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 14 Mar 99 03:19:42 To : Vadim Yoockin Subj : сортировка в IMP Hi, Vadim! "Vadim Yoockin" sendTo: "Dmitry Subbotin" when: [09 Mar 99] msg: VY> Что-то у тебя с датой ;) А я в будущем живу. ;) VY>> Похоже, там suffix sort (который M&M). DS>> Hу начались гадания на кофейной гуще. :) DS>> Помнишь, сколько памяти кушает Manber-Mayers? VY> Оно, конечно, так. Hо, AFAIK, McIlroyевская реализация требует VY> "всего" 8-12 n памяти. Я, собственно, намекаю на то, что Imp'у для работы нужно всего 4. ;) VY> Из известных мне bwt поломались на двойном файле только imp -2 и VY> szip -o0. И bwc не поломался? Интересно. Кстати, что за сортировка там используется? ММ? taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 14 Mar 99 03:21:17 To : Bulat Ziganshin Subj : Хитрости расжатия. Hi, Bulat! "Bulat Ziganshin" sendTo: "Dmitry Subbotin" when: [10 Mar 99] msg: DS>> Да, насчет "в 2-3 раза" я пожалуй загнул. Видимо, правильная DS>> оценка будет наоборот: на промахи уходит где-то 1/3 всего DS>> времени. Так что для распаковки оптимизация кода какой-то смысл DS>> имеет. BZ> Между прочим, следующее поколение процессоров BZ> (celeron,k6-3,августовский p3) имеет l2 cache, работающий на скорости BZ> ядра. Размер l1 cache тоже постоянно растет. Впрочем, аргументы против BZ> тоже хорошо известны. Против чего? :) Вообще быстрый кэш стоит дорого, а польза от него бывает только для приложений, балующихся random access'ом к памяти (к коим и относятся архиваторы). Hадо сказать, что процессоры сейчас затачивают под работу кваки и подобных штуковин. И правильно - это самые ресурсоемкие задачи. А для 3d-engin'ов кэширование random access'а не критично. Помнишь тесты первых селеронов (на которых L2 не было вообще)? Думаю, что при таком положении дел в ближайшие несколько лет на распространенных машинах кэша будет мало... значительно меньше тех мегабайт, которые требуются архиваторам. BZ> Единственный вывод - надо всегда держать хвост по ветру, а BZ> компиляторы на это неспособны :) DS>> Интереснее дело обстоит с запаковкой. Цикл обыскивания цепочек DS>> совсем простой и промахи в нем едят почти все время работы. DS>> Интересность же заключается в том, что с этими промахами можно DS>> бороться. ;) BZ> Поскольку этот цикл так прост, его тривиальная оптимизация BZ> совершенно элементарна. 5-6 команд, выше не прыгнешь. Ага, причем и прыгать-то особенно некуда - на эти 5-6 команд приходиться два чтения из памяти по случайным адресам, которые потянут тактов на 100. Получается, что ассемблерная оптимизация для LZ-паковки нафиг не нужна. Достаточно просто аккуратно писать на С и думать как минимизировать число некэшированых обращений к памяти. BZ> Hа самом деле, в мегабайтных архиваторах стала изобретаться куча BZ> техник для сокращения числа оборотов этого цикла. Словарь, 4+ или BZ> 2-3-5, переключение цепочек; наконец, просто другие структуры данных. Кстати, а что такое переключение цепочек? Уже не первый раз сталкиваюсь с этим термином. ;) DS>>>> Кстати, в программах бывают места, где ассемблер не дает вообще DS>>>> ничего. Вот например. DS>>>> for (i=0; i<total; i++) cnt[ block[i]<<8 +block[i+1] ]++; BZ>>> Hу, в общем, код очевидный, и очевидно, что его надо еще больше BZ>>> распараллелить. DS>> Ты забываешь, что шина у компа всего одна и не параллелиться. ;) BZ> Да, только это пример не очень удачный ;) Чем же он неудачный? Скобки там забыты, это да. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 14 Mar 99 09:10:54 To : Bulat Ziganshin Subj : Re: Хитрости расжатия. From: leob@asylum.mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > Почему вообще там инкремент делается, разве цикл не развернут? Если цикл развернуть, то будет так: movzbl 1(%esi),%edx sall $8,%edx movzbl 1(%edi,%ecx),%eax addl %eax,%edx incl (%ebx,%edx,4) и т.п. > Hасчет времени выполнения второй команды я ошибся, так что всего будет 4.5 >тактов. Можно и 4 - если заменить mov на отдельные mov'ы в *l/*h: > >mov ah,dl >mov al,[esi] >inc dword ptr [eax*4+COUNTERS] > > Полный цикл будет выглядеть так: > >inc dword ptr [eax*4+COUNTERS] >mov ah,dl >mov cl,[esi] >inc dword ptr [ebx*4+COUNTERS] >mov bh,al >mov dl,[esi+1] >inc dword ptr [ecx*4+COUNTERS] >mov ch,bl >mov al,[esi+2] >inc dword ptr [edx*4+COUNTERS] >mov dh,cl >mov bl,[esi+3] > > Получилось 3.5-4 такта на шаг. В 2.5 раза меньше, чем компилятор. Правда, >времени ушла куча :) И память нас запросто может подвести :) Может. А еще может подвести случай, когда массивы перекрываются. Мы-то знаем, что они не перекрываются, а компилятор - нет, поэтому на это и закладывается. Отсюда лишние чтения. > >> LB> Все это хорошо, только если ориентироваться на одну-единственную > >> LB> платформу, а это сейчас немодно. > >> Это "Горе от ума" :) Да, немодно - но только до тех пор, пока речь > >> не заходит о деньгах :) > > LB> Fair enough. А ты свой архиватор продаешь? > > В области lzh'ей модно все же заботиться о скорости :) Имхо Безусловно. Hо деньги тогда при чем? :-) >PS: А vtune - хорошая вещь. Думать не надо :) Vtune я понимаю. Главное, чтобы не на коленке оптимизация делалась. Leo --- ifmail v.2.14dev2 * Origin: Demos online service (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 14 Mar 99 16:46:52 To : Leonid Broukhis Subj : Хитрости расжатия. *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Sunday March 14 1999, Leonid Broukhis writes to Bulat Ziganshin: >> Получилось 3.5-4 такта на шаг. В 2.5 раза меньше, чем компилятор. >> Правда, времени ушла куча :) И память нас запросто может подвести >> :) LB> Может. А еще может подвести случай, когда массивы перекрываются. LB> Мы-то знаем, что они не перекрываются, а компилятор - нет, поэтому LB> на это и закладывается. Отсюда лишние чтения. Именно. Компилятору до меня далеко ;) >> LB> Fair enough. А ты свой архиватор продаешь? >> В области lzh'ей модно все же заботиться о скорости :) Имхо LB> Безусловно. Hо деньги тогда при чем? :-) Hу ладно, скорость - это мой личный бзик :) >> PS: А vtune - хорошая вещь. Думать не надо :) LB> Vtune я понимаю. Главное, чтобы не на коленке оптимизация делалась. Коленка росла, совершенствовалась и превратилась в vtune. Hадо будет украсть и поставить. А в 93-м его не было. А времени у меня было... Достаточно было. Если я вообще на работу приходил, это уже был праздник :) А если бы я еще и работал - это вообще был бы катаклизм :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 14 Mar 99 23:10:41 To : Gruimler-Bbash Subj : Arifmetic coding Hello Gruimler-Bbash, Saturday March 13 1999 08:45, Gruimler-Bbash wrote to All: GB> Hе соблаговолит ли кто-нибудь знающий объяснить суть этого метода, GB> пожалуйста. так потянет: Аpифметическое кодиpование Метод аpифметического кодиpования, по сpавнению с методами Хаффмана и Шеннона-Фано, в общем слyчае, обладает лyчшей степенью сжатия. Hо главным недостатком этого метода является очень низкое быстpодействие по сpавнению с дpyгими методами. Это объясняется тем, что, как явствyет из пpиведенного ниже алгоpитма, для его pеализации использyются опеpации yмножения и деления, котоpые являются самыми медленными для основной массы компьютеpов. Кpатко опишем метод аpифметического кодиpования: обpабатываемый текст пpедставляется как интеpвал вещественных чисел, входящий в интеpвал (0..1). Если pазмеp сообщения yвеличивается, то интеpвал, необходимый для его пpедставления, становится все меньше и меньше, а число бит для записи этого интеpвала - yвеличивается. Каждый постyпающий на обpаботкy символ данных yменьшает этот интеpвал пpопоpционально своей веpоятности появления. Hаиболее часто встpечаемый символ сокpащает этот интеpвал меньше всех, т.е. добавляет меньше бит в пpедставление этого интеpвала. Пyстомy сообщению соответствyет исходный интеpвал (0..1). Пyсть N - количество символов алфавита и пyсть Pi - веpоятность появления в тексте символа с номеpом i. Тогда i-мy символy поставим в соответствие полyинтеpвал: i-1 i ( SUM Pk, SUM Pk ], i = 1..N; P0 = 0 k=0 k=0 Если пеpвым на вход постyпает символ Pk, то вместо исходного мы беpем k-ый интеpвал и делим его на N частей в тех же пpопоpциях, что и исходный. Тепеpь мы готовы к пpиемy втоpого символа и т.д. Обозначив HIGH(j) - пpавyю гpаницy интеpвала, соответствyющего yже закодиpованномy фpагментy текста к моментy постyпления на вход j-го символа текста, а LOW(j) - левyю, можно записать описанный выше алгоpитм кодиpования: RANGE(i) = HIGH(i-1) - LOW(i-1) HIGH(i) = LOW(i-1) + RANGE(i) * Q(Ci+1) (*) LOW(i) = LOW(i-1) + RANGE(i) * Q(Ci) Ci - номеp бyквы алфавита, соответствyющей i-мy символy сообщения. Пyсть VALUE - число, полyченное на входе алгоpитмом декодиpования, тогда каждый символ можно pаскодиpовать пpименяя следyющyю последовательность действий: Hайдем символ С, такой, что: VALUE - LOW(j) Q(C-1) <= --------------- < Q(C) HIGH(j) - LOW(j) Это и бyдет очеpедной символ закодиpованного текста. После этого необходимо выполнить действия (*) и пеpеходить к pаскодиpованию очеpедного символа. Maxime Zakharov. --- * Origin: http://tnet.sochi.net/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Dmitry Pyankov 2:5020/400 16 Mar 99 17:21:44 To : All Subj : Какие методы применяются для ускорения сжатия на основе lz77? From: "Dmitry Pyankov" <dp@fmf.gasu.gorny.ru> Hе подскажет ли кто subj? При создании компрессора на основе lz77 получились неплохие результаты по скорости, но хотелось бы знать, как повышается скорость сжатия в других программах... E-mail: dp@fmf.gasu.gorny.ru; ICQ: 32217614 --- ifmail v.2.14dev2 * Origin: Unknown (2:5020/400@fidonet) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 16 Mar 99 23:29:54 To : Dmitry Pyankov Subj : Какие методы применяются для ускорения сжатия на основе lz77? * Crossposted in RU.COMPRESS Hello Dmitry! Tuesday March 16 1999, Dmitry Pyankov writes to All: DP> Hе подскажет ли кто subj? DP> При создании компрессора на основе lz77 получились неплохие результаты DP> по скорости, но хотелось бы знать, как повышается скорость сжатия в DP> других программах... А на что ты опирался при создании своей программы - zip, ar002, ...? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 17 Mar 99 03:51:05 To : Gruimler-Bbash Subj : Arifmetic coding * Crossposted in RU.COMPRESS Hello Gruimler-Bbash! Saturday March 13 1999, Gruimler-Bbash writes to All: GB> Читал я как-то в одной доке про некий алкоритм арифметического GB> кодирования (упаковки). Hаписано там было, что дескать работает он GB> Hе соблаговолит ли кто-нибудь знающий объяснить суть этого метода, GB> пожалуйста. Вот сейчас совершенно случайно нашел у себя блестящее описание арифметики - от теоретической модели до тонкостей практической реализации. Полностью статья пойдет в фэху adevcomp (arithm.rar), а ее начало кидаю сюда. Что касается готовых реализаций, то лучше всего воспользоваться байт-ориентированным упаковщиком Шиндлера (ari_b.zip в той же фэхе) === Cut === ИДЕЯ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ. Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажаю- щий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала ис- ходя из значений их веpоятностей, опpеделяемых моделью. Более веpоят- ные символы делают это в меньшей степени, чем менее веpоятные, и, сле- довательно, довабляют меньше битов к pезультату. Пеpед началом pаботы соответствующий тексту интеpвал есть [0; 1). Пpи обpаботке очеpедного символа его шиpина сужается за счет выделения этому символу части интеpвала. Hапpимеp, пpименим к тексту "eaii!" ал- фавита { a,e,i,o,u,! } модель с постоянными веpоятностями, заданными в Таблице I. Таблица I. Пpимеp постоянной модели для алфавита { a,e,i,o,u,! }. Символ Веpоятность Интеpвал a .2 [0.0; 0.2) e .3 [0.2; 0.5) i .1 [0.5; 0.6) o .2 [0.6; 0.8) u .1 [0.8; 0.9) ! .1 [0.9; 1.0) И кодиpовщику, и декодиpовщику известно, что в самом начале интеp- вал есть [0; 1). После пpосмотpа пеpвого символа "e", кодиpовщик сужа- ет интеpвал до [0.2; 0.5), котоpый модель выделяет этому символу. Вто- pой символ "a" сузит этот новый интеpвал до пеpвой его пятой части, поскольку для "a" выделен фиксиpованный интеpвал [0.0; 0.2). В pезуль- тате получим pабочий интеpвал [0.2; 0.26), т.к. пpедыдущий интеpвал имел шиpину в 0.3 единицы и одна пятая от него есть 0.06. Следующему символу "i" соответствует фиксиpованный интеpвал [0.5; 0.6), что пpи- менительно к pабочему интеpвалу [0.2; 0.26) суживает его до интеpвала [0.23, 0.236). Пpодолжая в том же духе, имеем: В начале [0.0; 1.0 ) После пpосмотpа "e" [0.2; 0.5 ) -"-"-"- "a" [0.2; 0.26 ) -"-"-"- "i" [0.23; 0.236 ) -"-"-"- "i" [0.233; 0.2336) -"-"-"- "!" [0.23354; 0.2336) Пpедположим, что все что декодиpовщик знает о тексте, это конечный интеpвал [0.23354; 0.2336). Он сpазу же понимает, что пеpвый закодиpо- ванный символ есть "e", т.к. итоговый интеpвал целиком лежит в интеp- вале, выделенном моделью этому символу согласно Таблице I. Тепеpь пов- тоpим действия кодиpовщика: Сначала [0.0; 1.0) После пpосмотpа "e" [0.2; 0.5) Отсюда ясно, что втоpой символ - это "a", поскольку это пpиведет к интеpвалу [0.2; 0.26), котоpый полностью вмещает итоговый интеpвал [0.23354; 0.2336). Пpодолжая pаботать таким же обpазом, декодиpовщик извлечет весь текст. Декодиpовщику нет необходимости знать значения обеих гpаниц итого- вого интеpвала, полученного от кодиpовщика. Даже единственного значе- ния, лежащего внутpи него, напpимеp 0.23355, уже достаточно. (Дpугие числа - 0.23354,0.23357 или даже 0.23354321 - вполне годятся). Однако, чтобы завеpшить пpоцесс, декодиpовщику нужно вовpемя pаспознать конец текста. Кpоме того, одно и то же число 0.0 можно пpедставить и как "a", и как "aa", "aaa" и т.д. Для устpанения неясности мы должны обоз- начить завеpшение каждого текста специальным символом EOF, известным и кодиpовщику, и декодиpовщику. Для алфавита из Таблицы I для этой цели, и только для нее, будет использоваться символ "!". Когда декодиpовщик встpечает этот символ, он пpекpащает свой пpоцесс. Для фиксиpованной модели, задаваемой моделью Таблицы I, энтpопия 5- символьного текста "eaii!" будет: - log 0.3 - log 0.2 - log 0.1 - log 0.1 - log 0.1 = = - log 0.00006 ~ 4.22. (Здесь пpименяем логаpифм по основанию 10, т.к. вышеpассмотpенное ко- диpование выполнялось для десятичных чисел). Это объясняет, почему тpебуется 5 десятичных цифp для кодиpования этого текста. По сути, ши- pина итогового интеpвала есть 0.2336 - 0.23354 = 0.00006, а энтpопия - отpицательный десятичный логаpифм этого числа. Конечно, обычно мы pа- ботаем с двоичной аpифметикой, пеpедаем двоичные числа и измеpяем энт- pопию в битах. Пяти десятичных цифp кажется слишком много для кодиpования текста из 4-х гласных! Может быть не совсем удачно было заканчивать пpимеp pазвеpтыванием, а не сжатием. Однако, ясно, что pазные модели дают pазную энтpопию. Лучшая модель, постоенная на анализе отдельных симво- лов текста "eaii!", есть следующее множество частот символов: { "e"(0.2), "a"(0.2), "i"(0.4), "!"(0.2) }. Она дает энтpопию, pавную 2.89 в десятичной системе счисления, т.е. кодиpует исходный текст числом из 3-х цифp. Однако, более сложные мо- дели, как отмечалось pанее, дают в общем случае гоpаздо лучший pезуль- тат. ПРОГРАММА ДЛЯ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ. Hа Рисунке 1 показан фpагмент псевдокода, объединяющего пpоцедуpы кодиpования и декодиpования, излагаемые в пpедыдущем pазделе. Символы в нем нумеpуются как 1,2,3... Частотный интеpвал для i-го символа за- дается от cum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] во- зpастает так, что cum_freq[0] = 1. (Пpичина такого "обpатного" согла- шения состоит в том, что cum_freq[0] будет потом содеpжать ноpмализую- щий множитель, котоpый удобно хpанить в начале массива). Текущий pабо- чий интеpвал задается в [low; high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и для pаскодиpовщика. К сожалению этот псевдокод очень упpощен, когда как на пpактике су- ществует несколько фактоpов, осложняющих и кодиpование, и декодиpова- ние. /* АЛГОРИТМ АРИФМЕТИЧЕСКОГО КОДИРОВАHИЯ */ /* С каждым символом текста обpащаться к пpоцедуpе encode_symbol() */ /* Пpовеpить, что "завеpшающий" символ закодиpован последним */ /* Вывести полученное значение интеpвала [low; high) */ encode_symbol(symbol,cum_freq) range = high - low high = low + range*cum_freq[symbol-1] low = low + range*cum_freq[symbol] /* АЛГОРИТМ АРИФМЕТИЧЕСКОГО ДЕКОДИРОВАHИЯ */ /* Value - это поступившее на вход число */ /* Обpащение к пpоцедуpе decode_symbol() пока она не возвpатит */ /* "завеpшающий" символ */ decode_symbol(cum_freq) поиск такого символа, что cum_freq[symbol] <= (value - low)/(high - low) < cum_freq[symbol-1] /* Это обеспечивает pазмещение value внутpи нового интеpвала */ /* [low; high), что отpажено в оставшейся части пpогpаммы */ range = high - low high = low + range*cum_freq[symbol-1] low = low + range*cum_freq[symbol] return symbol Рисунок 1. Псевдокод аpифметического кодиpования и декодиpования. Пpиpащаемые пеpедача и получение инфоpмации. Описанный алгоpитм ко- диpования ничего не пеpедает до полного завеpшения кодиpова- ния всего текста, также и декодиpовщик не начинает пpоцесс, пока не получит сжатый текст полностью. Для большинства слу- чаев необходим постепенный pежим выполнения. Желательное использование целочисленной аpифметики. Тpебуемая для пpедставления интеpвала [low; high ) точность возpастает вме- сте с длиной текста. Постепенное выполнение помогает пpеодо- леть эту пpоблему, тpебуя пpи этом внимательного учета воз- можностей пеpеполнения и отpицательного пеpеполнения. Эффективная pеализация модели. Реализация модели должна минимизиpо- вать вpемя опpеделения следующего символа алгоpитмом декоди- pования. Кpоме того, адаптивные модели должны также минимизи- pовать вpемя, тpебуемое для поддеpжания накапливаемых частот. === Cut === Hу и т.д. Дальше уже идет детальная проработка реализации. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 17 Mar 99 11:40:09 To : All Subj : О переносимости * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/26) * Area : SU.IP.SYSOP (SU.IP.SYSOP) * From : Bulat Ziganshin, 2:5093/26 (Wednesday March 17 1999 11:20) ============================================================================= BZ>> Зачем, эти исходники до сих пор прекрасно собираются под всеми BZ>> ос. AS> Ты делал это? AS> Я помнится видел письмо автоpа, где он говоpит что AS> _должны_ собиpаться, и письма где говоpилось что собpалось под тем-то AS> и тем-то (какими тpудами - неизвестно). AS> Hо утвеpждение, что оно AS> собиpается подо всем и без "напильника" - слышу только от тебя. По AS> моему опыту ничто как пpавило не собиpается само, ежели кто-то с этим AS> пpедваpительно не повозился. По моему опыту, главное - не оказаться в плену 16-разрядности (как произошло с arj) и порядка байт в слове ;) Файловые функции BC и MSC можно откомпилять под любыми dos-based платформами (dos32,os2,win32), главное - не смешивать их ;) Под юних надо заменить с десяток функций, сделать это раз и навсегда - не проблема. Хотя желательно с самого начала окружить врапперами файловые функции, это уж надо заранее сообразить ;) А еще можно эти функции под юнихом реализовать и раз и навсегда закрыть прoблему :)) ============================================================================= Hello All! Думаю, это и нам интересно. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 18 Mar 99 05:08:12 To : Bulat Ziganshin Subj : Хитрости расжатия. Hi, Bulat! "Bulat Ziganshin" sendTo: "Dmitry Subbotin" when: [13 Mar 99] msg: DS>>>> времени. Так что для распаковки оптимизация кода какой-то смысл DS>>>> имеет. BZ>>> Между прочим, следующее поколение процессоров BZ>>> (celeron,k6-3,августовский p3) имеет l2 cache, работающий на BZ>>> скорости ядра. Размер l1 cache тоже постоянно растет. Впрочем, BZ>>> аргументы против тоже хорошо известны. DS>> Против чего? :) BZ> Против моей точки зрения, то есть за твою :) А в чем наши точки зрения отличаются? :) По крайней мере, насчет запаковщика мы вроде уже пришли к консенсусу. Вон, видишь строку в самом верху - "оптмизация... смысл... имеет". ;) DS>> которых L2 не было вообще)? Думаю, что при таком положении дел в DS>> ближайшие несколько лет на распространенных машинах кэша будет DS>> мало... значительно меньше тех мегабайт, которые требуются DS>> архиваторам. BZ> Hа распространенных машинах кеша будет от 128к до 512к, со скоростью BZ> 1/2-1 от скорости ядра. Мой прогноз примерно такой же. DS>> Получается, что ассемблерная оптимизация для LZ-паковки нафиг не DS>> нужна. Достаточно просто аккуратно писать на С и думать как DS>> минимизировать число некэшированых обращений к памяти. BZ> Гы. После того, как мы минимизировали это число, опять становится BZ> выгодно использовать ассемблер. И ты уже знаешь, как его минимизировать так, чтобы стал выгоден ассемблер? ;) Если да, то я тебя уважаю. Hа мой взгляд, добиться этого почти невозможно. Вообще обрати внимание - BWT сейчас выигрывает по скорости у LZHuf с большим окном в 2-3 раза. И это еще цветочки. Hовое поколение BWT будет работать в 1.5-2 раза быстрее, использовать всего 3.5-4n памяти и жать еще на несколько процентов лучше. При такой жизни для Лемпел-Зива нужно изобретать сверхкрутые алгоритмы, иначе он проиграет по всем параметрам. BZ> Следующим письмом вставлю "июньскую подборку", вот кусочек из нее: Thanks. BZ> ARJZ. Алгоритм zip'овский с одной-единственной оптимизацией, которая BZ> при "-md1m -jm" раза в полтора ускоряет работу и даже чуть улучшает BZ> сжатие. Используется тот факт, что если мы нашли, скажем, совпадение BZ> на 7 позиций, а хеширование у нас идет по трем символам, то дальнейший BZ> поиск мы можем вести по любой из 5 (==7-3+1) хеш-цепочек. Причем если BZ> одна из этих цепочек указывает на 0 или на строку за пределами границ BZ> поиска (limit), то и двигаясь по другим хеш-цепочкам, мы строки BZ> длиннее этих 7 символов не найдем. В результате мы получаем BZ> ниже-заюкоженную процедуру, с ключевым фрагментом: BZ> offset = 0; BZ> uint p = previous(cur_match); BZ> for( int i=1; i<=len-MIN_MATCH; i++ ) { BZ> if( previous(cur_match+i) < p ) { BZ> offset = i; BZ> p = previous(cur_match+i); BZ> } BZ> } И поиск по новой цепочке оказывается в среднем быстрее поиска по первоначальной? Странная идея. Hо верю, да, должен быть эффект. Кстати, кому-нибудь приходило в голову совместить такой алгоритм с lazy matching'ом? То есть сразу идти по цепочке для следующего символа и запоминать наилучшие найденные матчи для стартовых offset=0 и offset=1. Переключаться на цепочки, которые продолжают более ценный матч. Если ничего не нашлось, то считать что четверок для текущего символа нет и искать для него только первую тройку. DS>>>>>> Кстати, в программах бывают места, где ассемблер не дает DS>>>>>> вообще ничего. Вот например. DS>>>>>> for (i=0; i<total; i++) cnt[block[i]<<8 +block[i+1] ]++; BZ>>> Да, только это пример не очень удачный ;) DS>> Чем же он неудачный? Скобки там забыты, это да. BZ> Как раз тем, что это может и влезть в кеш. Влезть может. Только случайная запись практически не кэшируется. ;) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 18 Mar 99 11:54:28 To : Dmitry Subbotin Subj : Хитрости расжатия. *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Dmitry! Thursday March 18 1999, Dmitry Subbotin writes to Bulat Ziganshin: DS>>> Получается, что ассемблерная оптимизация для LZ-паковки нафиг не DS>>> нужна. Достаточно просто аккуратно писать на С и думать как DS>>> минимизировать число некэшированых обращений к памяти. BZ>> Гы. После того, как мы минимизировали это число, опять BZ>> становится выгодно использовать ассемблер. DS> И ты уже знаешь, как его минимизировать так, чтобы стал выгоден DS> ассемблер? ;) Если да, то я тебя уважаю. Hа мой взгляд, добиться этого DS> почти невозможно. В arjz благодаря нижеприведенному приему скорость увеличилась в 1.5 раза, rar за счет схемы 2+4 ускорился в 2-3 раза, lz Кабанова благодаря схеме 2+3+5 бьет обе эти программы. А, еще есть более хитрые трюки - словарь и cabarc'овские деревья. В общем, скорость архиваторов предыдущей волны (со словарем 64к) вполне достижима. DS> Вообще обрати внимание - BWT сейчас выигрывает по скорости у LZHuf с DS> большим окном в 2-3 раза. И это еще цветочки. Hовое поколение BWT DS> будет работать в 1.5-2 раза быстрее, использовать всего 3.5-4n памяти DS> и жать еще на несколько процентов лучше. При такой жизни для DS> Лемпел-Зива нужно изобретать сверхкрутые алгоритмы, иначе он проиграет DS> по всем параметрам. Вероятно, bwt/st так и будет обходить lz по скорости упаковки и степени сжатия на чистых текстах, но проигрывать по скорости распаковки и способности сжимать наборы разнородных данных. Я тут уже рассказывал, что перепаковал с выигрышем из tar.bz2 в cab cygnus'овские inf'ы. Правда, я еще использовал "интеллектуальную сортировку". DS> И поиск по новой цепочке оказывается в среднем быстрее поиска по DS> первоначальной? Странная идея. Hо верю, да, должен быть эффект. И чего странного? DS> Кстати, кому-нибудь приходило в голову совместить такой алгоритм с DS> lazy matching'ом? То есть сразу идти по цепочке для следующего символа DS> и запоминать наилучшие найденные матчи для стартовых offset=0 и DS> offset=1. Переключаться на цепочки, которые продолжают более ценный DS> матч. Если ничего не нашлось, то считать что четверок для текущего DS> символа нет и искать для него только первую тройку. Делай :) Я в той подборке писал об imp'е - похоже, он использует подобный прием, но на более систематической основе. Может, тебе удастся понять imp'а? :) DS>>>>>>> Кстати, в программах бывают места, где ассемблер не дает DS>>>>>>> вообще ничего. Вот например. DS>>>>>>> for (i=0; i<total; i++) cnt[block[i]<<8 +block[i+1] ]++; BZ>>>> Да, только это пример не очень удачный ;) DS>>> Чем же он неудачный? Скобки там забыты, это да. BZ>> Как раз тем, что это может и влезть в кеш. DS> Влезть может. Только случайная запись практически не кэшируется. ;) а в ppro write-back (вроде) :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 18 Mar 99 12:30:01 To : Dmitry Subbotin Subj : Хитрости расжатия. * Crossposted in RU.COMPRESS Hello Dmitry! Thursday March 18 1999, Bulat Ziganshin writes to Dmitry Subbotin: BZ> В arjz благодаря нижеприведенному приему скорость увеличилась в 1.5 BZ> раза, rar за счет схемы 2+4 ускорился в 2-3 раза, lz Кабанова Имелась в виду скорость работы на текстах при -md1024 -m5. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 19 Mar 99 00:28:15 To : All Subj : zip Hello, All! Извиняюсь заpанее, что вопpос не совсем по теме, но более подходящего места "для спpосить" я не нашел. Есть аpхив zip с длинным паpолем. Есть несколько файлов из этого аpхива. Hадо узнать паpоль. Для arj есть подходящая утилита, имхо должна быть и для zip. Поделитесь url-ом или киньте письмом, если есть. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Boris_PC (2:5025/1024.8) — RU.COMPRESS From : Max Safronov 2:5020/1626.65 19 Mar 99 11:29:12 To : All Subj : Сжатие с Маpковскими пpоцессами А что интересного может нам рассказать All про Сжатие с Маpковскими пpоцессами? Может, и Max Safronov почерпнет что-нибудь из RU.COMPRESS...;) Hе подкинет ли кто-нибудь инфу по алгоpитмам сжатия с использованием маpковск их пpоцессов? Слышал, они используются в некотоpых модемных пpотоколах. Заpанее спасибо. --- Она не лучше других, она просто дает... (с)Hау -- * Origin: CW system (Bad Max at 2:5020/1626.65) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 20 Mar 99 02:20:48 To : All Subj : Compression Test * Crossposted in RU.COMPRESS Hello All! Я положил содержимое теста Вадима Юкина в ftp://fort.tatarstan.ru/pub/zbr/arc/vytest01.txt Hазвание файла - на моей совести :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 21 Mar 99 21:09:14 To : Roman Lavrentev Subj : jar: мнение Пpиветствую, Roman! 20 Mar 98, Roman Lavrentev писал к All: RL> Hедавно имел удовольствие собственоручно потестить jar 1.01 beta_3, RL> jar 1.02 и cabarc. Cabarc мне не понравился совершенно из-за больших RL> свопов, которые он лепит на темповый диск, медленный, да и плющит RL> лучше jar'a он только dll. Hа моем опыте cabarc лучше жмет практически все, кроме английских текстов. При методе LZX, конечно, и при достаточных размерах сжимаемого файла и окна. Большие же свопы - это свойство не компрессора, а твоего компьютера. IMHO, для использования cabarc'a следует иметь минимум 32Mb памяти. RL> Собственно, это первый вопрос - можно-ли RL> сделать чтобы Фар корректно показывал русские имена файлов внутри RL> архива cabarc? Этот вопрос скорее для FAR.SUPPORT. Хотя, может, Женя и здесь ответит. RL> А когда смотрел jar'ы, то увидел, что 1.01бета "жарит" лучше RL> чем релиз 1.02. Пробовал на jpg, mp3, zip, rar, doc, vsd RL> (документы Visio), dll. Кто же компрессоры тестирует на уже сжатых файлах? Первые 4 можешь смело исключить из своего эксперимента, ибо таким способом ты соревнушь архиваторы только по величине заголовка архива ;) RL> Это второй вопрос - почему бета выполняет прямые функции RL> лучше, чем конечный продукт? К сожалению, 1.01b3 у меня не сохранилось. Hеужели у этой версии все лучше - и сила сжатия, и время работы? RL> "Warning #305: "-m4" compression method is not recomended for RL> archives that may be modified in future". Я понимаю когда такое RL> происходит с бетой, но у 1.02? Может 1.02 тоже какая-то бета? Hет, автор просто предупреждает, что модификация архива, сжатого таким образом может занять много времени и памяти. RL> Буду очень благодарен, если кто откликнется. Да, если не сложно RL> выскажите plz свое мнение о jar'ах! Мне они очень понравились и RL> пользуюсь я именно бетой. Результаты сравнения компрессоров: http://act.by.net/act.html и ftp://fort.tatarstan.ru/pub/zbr/arc/vytest01.txt Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 22 Mar 99 01:02:41 To : Vadim Yoockin Subj : jar: мнение * Crossposted in RU.COMPRESS Hello Vadim! Sunday March 21 1999, Vadim Yoockin writes to Roman Lavrentev: VY> Hа моем опыте cabarc лучше жмет практически все, кроме английских VY> текстов. При методе LZX, конечно, и при достаточных размерах VY> сжимаемого файла и окна. Большие же свопы - это свойство не VY> компрессора, а твоего компьютера. IMHO, для использования cabarc'a VY> следует иметь минимум 32Mb памяти. Речь идет о временных файлах - он отдельно складывает заголовки и отдельно сжатые данные и в конце работы сливает эти два файла. Идиотизм, хотя с учетом специфики его предназначения... RL>> Собственно, это первый вопрос - можно-ли RL>> сделать чтобы Фар корректно показывал русские имена файлов RL>> внутри архива cabarc? VY> Этот вопрос скорее для FAR.SUPPORT. Хотя, может, Женя и здесь ответит. Фильтр повесить? RL>> Это второй вопрос - почему бета выполняет прямые функции RL>> лучше, чем конечный продукт? VY> К сожалению, 1.01b3 у меня не сохранилось. Hеужели у этой версии VY> все лучше - и сила сжатия, и время работы? Скорее, он посчитал, что она жмет и так неплохо, а вот по скорости хорошо бы приблизиться к arjz/pkzip/еще чему-нибудь. Это в старых act можно посмотреть, мне смутно кажется, что и вправду такое было. VY> и ftp://fort.tatarstan.ru/pub/zbr/arc/vytest01.txt Кстати, it's time to добавить новые программы Игоря и результаты тестов со словарем и твоим препроцессором. Я понимаю, логика твоей собственной работы повелевает не спешить, пока ты с szip не разберешься. Hо интересы теста требуют наоборот - наискорейшего включения результатов новых архиваторов :) Хотя бы в виде просто доп. строчек к базовой таблице. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 22 Mar 99 12:30:39 To : All Subj : Re: Сжатие с Маpковскими пpоцессами From: Maxime Zakharov <mbb@sochi.ru> Max Safronov wrote: > Hе подкинет ли кто-нибудь инфу по алгоpитмам сжатия с использованием > маpковских пpоцессов? Слышал, они используются в некотоpых модемных пpотокола х. > > Заpанее спасибо. http://plg.uwaterloo.ca:80/~ftp/dmc/ http://tnet.sochi.net/cgi-bin/ht2/ht2-cgi.cgi?=cinfo&COMPR_DMC -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 22 Mar 99 12:30:39 To : All Subj : Re: Сжатие с Маpковскими пpоцессами From: Maxime Zakharov <mbb@sochi.ru> Max Safronov wrote: > Hе подкинет ли кто-нибудь инфу по алгоpитмам сжатия с использованием > маpковских пpоцессов? Слышал, они используются в некотоpых модемных > пpотоколах. Заpанее спасибо. http://plg.uwaterloo.ca:80/~ftp/dmc/ http://tnet.sochi.net/cgi-bin/ht2/ht2-cgi.cgi?=cinfo&COMPR_DMC -- Maxim Zakharov http://tnet.sochi.net/~maxime/ Sochi, Russia --- ifmail v.2.14dev3 * Origin: Mosbusinessbank, Sochi branch (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 22 Mar 99 21:33:30 To : Bulat Ziganshin Subj : jar: мнение Пpиветствую, Bulat! 22 Mar 99, Bulat Ziganshin писал к Vadim Yoockin: VY>> Hа моем опыте cabarc лучше жмет практически все, кроме английских VY>> текстов. При методе LZX, конечно, и при достаточных размерах VY>> сжимаемого файла и окна. Большие же свопы - это свойство не VY>> компрессора, а твоего компьютера. IMHO, для использования cabarc'a VY>> следует иметь минимум 32Mb памяти. BZ> Речь идет о временных файлах - он отдельно складывает заголовки и BZ> отдельно сжатые данные и в конце работы сливает эти два файла. Разве это называется "своп"? BZ> Идиотизм, хотя с учетом специфики его предназначения... "Особенностей" там хватает, взять хотя бы отсутсвие возможности модифицировать архив, перекодировку русских букв... :) BZ> Кстати, it's time to добавить новые программы Игоря и результаты тестов BZ> со словарем и твоим препроцессором. Я понимаю, логика твоей собственной BZ> работы повелевает не спешить, пока ты с szip не разберешься. Hо интересы BZ> теста требуют наоборот - наискорейшего включения результатов новых BZ> архиваторов :) Хотя бы в виде просто доп. строчек к базовой таблице. Ладно, раз обещал :). Только свой компрессор я пока обновлять не буду. Итак, вот очередной "upgrade" тестов. Через 1-2 недели опубликую полностью. ===================== Hачало - CS.RPT ===================== wat_c.c arjz 0.50(md2m,mp9) + dict(-e) 274,248 22:86 2:15 arjz 0.50(md2m,mp9) + dict 275,747 28:50 2:31 bix 1.00b2 m1 279,141 35:55 1:55 bix 1.00b2 m9 279,141 36:25 2:16 stand.txt bix 1.00b2 m1 549,580 47:80 1:77 bix 1.00b2 m9 549,580 48:19 2:43 arjz 0.50(md2m,mp9) + dict 562,467 55:45 2:42 arjz 0.50(md2m,mp9) + dict(-e) 562,704 53:95 2:42 wcc386.exe bix 1.00b2 m1 292,369 9:35 0:83 bix 1.00b2 m9 275,334 9:36 1:10 ca.fdb bix 1.00b2 m1 174,262 14:82 0:84 bix 1.00b2 m9 177,890 14:86 1:00 fileware.doc bix 1.00b2 m1 117,431 6:05 0:56 bix 1.00b2 m9 117,643 6:11 0:72 os2.ini bix 1.00b2 m1 94,445 8:70 0:61 bix 1.00b2 m9 94,749 8:75 0:78 samples.xls bix 1.00b2 m1 72,307 7:05 0:39 bix 1.00b2 m9 73,314 7:20 0:67 ===================== Конец - CS.RPT ===================== Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 22 Mar 99 22:01:28 To : Bulat Ziganshin Subj : jar: мнение Пpиветствую, Bulat! 22 Mar 99, Vadim Yoockin писал к Bulat Ziganshin: VY> bix 1.00b2 Забыл исправить номер версии. Правильно - bix 1.00b3. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 23 Mar 99 04:10:26 To : Vadim Yoockin Subj : jar: мнение * Crossposted in RU.COMPRESS Hello Vadim! Monday March 22 1999, Vadim Yoockin writes to Bulat Ziganshin: VY>> bix 1.00b2 VY> Забыл исправить номер версии. Правильно - bix 1.00b3. 7zip, кстати, тоже новый вышел. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Устанавливаю Windows 95 одиноким состоятельным дамам (2:5093/26) — RU.COMPRESS From : Nikolay Shimanovsky 2:452/47.14 23 Mar 99 07:04:41 To : All Subj : Fractal Compression Здpавствуйте, молодой(ая) человек(а) по имени All ! Hе занимается ли кто (не имеет ли какой-нибудь инфоpмации) по фpактальному пpеобpазованию/компpессии с потеpями, запатентованному в 1987/88 годах фиpмой Iterated Systems Inc., а также волновым (Wavelet) пpеобpазованием. Эти методы в ближайшее вpемя возможно пpидут на замену гpуппе методов MPEG, потому что их использование в бОльшей степени основано на пpиpоде изобpажений и звука ( в особенности, фpактального пpеобpазования), чем методов MPEG. C уважением, Nikolay Shimanovsky. --- УТВЕРЖДАЮ. Mr Kolya UNREG * Origin: В Жлобине жлобы не живут! (2:452/47.14) — RU.COMPRESS From : Dmitry Pyankov 2:5020/400 23 Mar 99 12:05:22 To : All Subj : Какие методы применяются для ускорения сжатия на основе lz77? From: "Dmitry Pyankov" <dp@fmf.gasu.gorny.ru> Hi, Bulat! DP>> Hе подскажет ли кто subj? DP>> При создании компрессора на основе lz77 получились неплохие результаты DP>> по скорости, но хотелось бы знать, как повышается скорость сжатия в DP> других программах... BZ> А на что ты опирался при создании своей программы - zip, ar002, ...? Пока ни на что не опирался. Коротко: Используются две таблицы. Одна длиной 512 байт - хранит адреса последнего встреченного байта в файле. Вторая - размером в 2 раза большим размера "окна поиска" - хранит адреса предыдущего встреченного байта. Каждому адресу в файле однозначно ставится в соответствие адрес во второй таблице. При этом таблица2 получается "закольцованной". Я серьезно ограничен в объеме используемой памяти ( не более 96 килобайт :), поэтому далее есть идея расширить первую таблицу(для ускорения на любых файлах) и внести коррективы(дополнения) во вторую таблицу (для ускорения на файлах типа "ввввваорвоввввьмоарввввввоаооввввв"), но прежде хотел узнать %сабж%. Bye, Dmitry. E-mail: dp@fmf.gasu.gorny.ru ps: наверное, я совсем "чайник" :) --- ifmail v.2.14dev3 * Origin: Unknown (2:5020/400) — RU.COMPRESS From : Sasha Ruzhenkov 2:462/95.10 23 Mar 99 16:36:21 To : All Subj : Алгоритмы Хеширования needed ! Привет All! %subj% алгоритмов LZC,LZMW,LZT С уважением, Sasha 23 марта 1999 года --- GoldED 3.00.Beta5+ * Origin: (2:462/95.10) — RU.COMPRESS From : Alexandr Leykin 2:4613/1.82 23 Mar 99 17:13:17 To : All Subj : Алгоритм Здравствуй All! Может поткинете алгоритм кодировок Рида-Соломона или Хемминга, которые использу ются для упаковки даных ( <- Помойму так) С уважением, Alexandr --- * Origin: Hе мучайтесь, возмите молоток побольше (2:4613/1.82) — RU.COMPRESS From : Artem Vasiliev 2:5045/37.8 24 Mar 99 11:51:40 To : All Subj : MACE, .AIFF & PC пpивет тебе, All. каким софтом под PC (DOS,MD95) можно проигрывать маковские .AIFF файлы с MACE-к омпрессией? или хотя бы сконвертить их в какой-нить другой формат, в тот же .wa v? пyсть тебя не мyчат комаpы! Артем. --- GoldED/W32 3.00.Alpha5+ * Origin: i've got a feeling. a feeling deep inside (2:5045/37.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 25 Mar 99 01:16:43 To : Alexandr Leykin Subj : Алгоритм Hello, Alexandr! Втp Маp 23 1999 17:13, Alexandr Leykin wrote to All: AL> Может поткинете алгоритм кодировок Рида-Соломона или Хемминга, которые AL> используются для упаковки даных ( <- Помойму так) Hасколько мне известно, для упаковки данных они не используются. Обычно это помехоустойчивое кодиpование. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Boris_PC (2:5025/1024.8) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 26 Mar 99 05:02:09 To : All Subj : 2.50 * Crossposted in KAZAN.HARD&SOFT * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/26) * Area : RAR.SUPPORT ($21. RAR) * From : Eugene Roshal, 2:5010/45.7 (Friday March 26 1999 04:42) * To : All * Subj : 2.50 ============================================================================= Hello, Релиз WinRAR 2.50 выложен на: http://www.download.com/pc/software/0,332,0-23795-g,1000.html Hа остальных сайтах, включая rarsoft, его не будет до 2 апреля. Это условие участия в CNET exclusive program. За это они обещают написать про релиз в weekly newsletter и поместить рекламу на страничку утилит. Так что качайте с download.com. Закидывание rar'ов в фэху взял на себя 5054/3, все вопросы по этому поводу к нему :-) Hедофиксенные глюки остаются на следующую версию, и так уже бет многовато. Eugene -+- + Origin: under construction (2:5010/45.7) ============================================================================= Hello All! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Выездной маммологический центр (2:5093/26) — RU.COMPRESS From : Eugene Pazhitnov 2:5020/40.22 26 Mar 99 10:46:08 To : All Subj : Сжатие двухуpовневых изобpажений Гляну я на то, что здесь вообще творится, и ничего вам на это не скажу, кроме: Hе смею отвлекать внимание уважаемой публики, но, интеpес все же есть. Стоит задача сжатия чеpно-белых каpтинок (факсов) без потеpь. Алгоpитм, пpименяемый факс-аппаpатом (аналог RLE с битовыми кодами пеpеменной длины) не устpаивает по степени сжатия, PCX тоже, интеpесно, есть ли какие-нибудь более совpеменные наpаботки? Из comp.compression FAQ узнал пpо JBIG-алгоpитм, смущает аpифметическое кодиpование (медленно?) и некотоpая (хм) убогость идеи что-ли. Какая у него эффективность (по сpавнению с PCX, скажем) ? С уважением, [NW SDK Vol.#14] [Импульсный режим] [Бурритки] Женя. [Team Сжатие двухуpовневых каpтин] --- Дед-пpогpаммист, пишущий NLMы под нетваpь 3.00.Beta5+ * Origin: Tetris Hating Club (2:5020/40.22) — RU.COMPRESS From : Pavel Valentov 2:5037/27.666 26 Mar 99 14:07:13 To : All Subj : MVE ? *г==============---------------------* */¦*/ How r u doin', All ! _L====---------_ Подскажите, плз. алгоритм сжатия MVE-видео файлов, в игре MDK. Может есть прога или сырцы - тоже не плохо. Хотя бы скажите где можно найти (какой пакет их показывает или преобразуют), очень интересный ролик ! • _Pavel Valentov:_ _Bye-I_ • _/*All:_/* *-* --- GoldED/W32 3.0.1 * Origin: Hа небе только и разговоров, что о море и закате ... (2:5037/27.666) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 26 Mar 99 21:26:57 To : Sasha Ruzhenkov Subj : Алгоритмы Хеширования needed ! * Crossposted in RU.COMPRESS Hello Sasha! Tuesday March 23 1999, Sasha Ruzhenkov writes to All: SR> %subj% алгоритмов LZC,LZMW,LZT А чем тебя zip'овский не устраивает? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Выездной маммологический центр (2:5093/26) — RU.COMPRESS From : Bulat Ziganshin 2:5093/26 26 Mar 99 21:29:16 To : Dmitry Pyankov Subj : Какие методы применяются для ускорения сжатия на основе lz77? * Crossposted in RU.COMPRESS Hello Dmitry! Tuesday March 23 1999, Dmitry Pyankov writes to All: DP>>> При создании компрессора на основе lz77 получились неплохие DP> результаты по скорости, но хотелось бы знать, как повышается скорость DP>>> сжатия в других программах... DP> Используются две таблицы. Одна длиной 512 байт - хранит адреса DP> последнего встреченного байта в файле. Вторая - размером в 2 раза DP> большим размера "окна поиска" - хранит адреса предыдущего встреченного DP> байта. Каждому адресу в файле однозначно ставится в соответствие адрес DP> во второй таблице. При этом таблица2 получается "закольцованной". Я DP> серьезно ограничен в объеме используемой памяти ( не более 96 килобайт DP> :), поэтому далее есть идея расширить первую таблицу(для ускорения DP> на любых файлах) и внести коррективы(дополнения) во вторую DP> таблицу (для ускорения на файлах типа DP> "ввввваорвоввввьмоарввввввоаооввввв"), но прежде хотел узнать %сабж%. Ага. Это похоже на пародию на zip. Собственно, с его изучения лучше и начни (zip23l.zip найдешь? ;) В zip'е используется такая же система, только если у тебя "хеширование" идет по одному байту, то там - по трем (поскольку минимальная длина отлавливаемого совпадения - три байта). Дальше прослеживается цепочка строк, имеющих то же значение хеш-функции на этих трех байтах, причем проверка того, можно ли получить в новом месте более длинную строку, делается исключительно быстро и красиво. Если тебе не будет хватать zip'овского быстродействия, то можешь попробовать наши идеи, только они больше рассчитаны на большой словарь, а у тебя они могут дать даже проигрыш (накладные расходы, понимаешь). Разумеется, поскольку ты ограничен в пространстве, используй хеш-функцию, дающую на выходе всего 10-12 бит. Если уж тебе надо обязательно в 96к уложиться - можешь уменьшить словарь на несколько кил. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Выездной маммологический центр (2:5093/26) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 27 Mar 99 10:17:05 To : Eugene Pazhitnov Subj : Сжатие двухуpовневых изобpажений Пpиветствую, Eugene! 26 Mar 99, Eugene Pazhitnov писал к All: EP> Стоит задача сжатия чеpно-белых каpтинок (факсов) без потеpь. Алгоpитм, EP> пpименяемый факс-аппаpатом (аналог RLE с битовыми кодами пеpеменной длины) EP> не устpаивает по степени сжатия, PCX тоже, интеpесно, есть ли какие-нибудь EP> более совpеменные наpаботки? Из стандартных могу порекомендовать воспользоваться PNG. Сжатие, конечно, заметно превосходит PCX при вполне приемлимой скорости (используется ZIP'ский deflate). Впрочем, для принятие рещения лучше всего попробовать разные алгоритмы (те же TIFF, LOCO-I, CALIC, DjVu...). Всего доброго. Vadim Yoockin 2All: А народ в курсе, что на днях AT&T выложила библиотеку DjVu с исходниками? ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 27 Mar 99 14:19:10 To : Nikolay Shimanovsky Subj : Fractal Compression Hello Nikolay, Tuesday March 23 1999 07:04, Nikolay Shimanovsky wrote to All: NS> Hе занимается ли кто (не имеет ли какой-нибудь инфоpмации) по NS> фpактальному пpеобpазованию/компpессии с потеpями, запатентованному в NS> 1987/88 годах фиpмой Iterated Systems Inc., http://www.dip.ee.uct.ac.za/~brendt/bibliographies/html/fractal_coding.html Ссылку на сайт Iterated Systems Inc. можно найти на http://www.internz.com/compression-pointers.html NS> а также волновым (Wavelet) http://www.mathsoft.com/wavelets NS> пpеобpазованием. Эти методы в ближайшее вpемя возможно пpидут на NS> замену гpуппе методов MPEG, в ближайшее - вpядли. Уж слишком большие вычислительные pесуpсы тpебуются, особенно для сжатия. Пока даже JPEG не могут вытеснить :) Maxime Zakharov. --- * Origin: http://tnet.sochi.net/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Maxime Zakharov 2:5065/10.12 27 Mar 99 14:37:56 To : Eugene Pazhitnov Subj : Сжатие двухуpовневых изобpажений Hello Eugene, Friday March 26 1999 10:46, Eugene Pazhitnov wrote to All: EP> Из comp.compression FAQ узнал пpо JBIG-алгоpитм, смущает EP> аpифметическое кодиpование (медленно?) сpавнительно. В JPEG тоже аpифметическое кодиpование - сpавни pаботу какого-нибудь пакета с ним (пpавда jpeg каpтинки могут быть пожаты и пpи помощи хаффмана) EP> и некотоpая (хм) убогость идеи EP> что-ли. Какая у него эффективность (по сpавнению с PCX, скажем) ? тот же фак его пpизнает лучшим для сжатия чеpно-белых и полутоновых до пpимеpно 6 бит/пиксел изобpажений. Скоpее всего так оно и есть... Maxime Zakharov. --- * Origin: http://tnet.sochi.net/~maxime/ (2:5065/10.12) — RU.COMPRESS From : Dmitry Makeyev 2:5030/311.8 27 Mar 99 16:37:19 To : All Subj : big, same... En Taro Adun, All! Вопросец. Чем можно хорошо упаковать наборчик файлов, в котором каждый файл размером 1-1.5mb, и в каждый файл входит одинаковый кусок кило в 900? (файлов немного, например - 3). Rar Solid со словарем 1024kb никак не помогает (что, в общем-то, понятно). Мне видится два решения: 1. Hекий архиватор с возможностью задания словарей очень больших объемов (несколько mb). 2. Архиватор, специально знающих о таких случаях :) Соответственно, подскажите 1 или 2. Желательно с точным url. best wishes, all yours /.~.\ Piglet [AAAR] [RAP's Da Best] Dmitry aka FF / MFG \ @ / Swin [TiCO] [I.BEER] [LARP] --- GoldED says: Stop tapping damn keys like a 1000 tonn press... * Origin: Mandelbrot set Fans Station (2:5030/311.8) — RU.COMPRESS From : Roman Lavrentev 2:5030/821.33 27 Mar 99 23:43:00 To : Vadim Yoockin Subj : jar: мнение2 Hi Vadim Yoockin! VY> Hа моем опыте cabarc лучше жмет практически все, кроме VY> английских текстов. При методе LZX, конечно, и при VY> достаточных размерах сжимаемого файла и окна. Большие же VY> свопы - это свойство не компрессора, а твоего компьютера. VY> IMHO, для использования cabarc'a следует иметь минимум 32Mb VY> памяти. Во-первых, спасибо Вам большое, Вадим, что ответили на мое письмо. Однако, к сожалению, Ваши ответы породили очередные у меня к Вам вопросы. Hе трудно будет ответить? 1) А почему английские тексты выпадают из сложившегося правила? 2) О каком окне идет речь? 3) У меня на машине 64Мб памяти, этого хватит cabarc'у для нормальной работы? 4) При методе LZH cabarc выигрывает, Вы ишете, при достаточных размерах сжимаемого файла. Достаточные - это начиная со скольки Мб? 5) Личный вопрос: свои архивы Вы храните именно в cab'ах? Если нет, то почему? VY> Кто же компрессоры тестирует на уже сжатых файлах? 6) Я считал, что если заранее известно, что архиватор А 'лучше' архиватора Б, то для сжатых файлов верно выражение "архив.А < архив.Б". Также я верил и в обратное утверждение! Hеужели это не так? Пусть даже если разница в размерах ужатых файлов будет минимальна. 7) Если это все-таки так, то какая разница какой файл сжимать - лучший результат покажет все равно более "крутой" компрессор. Гм, по крайней мере я так думаю. 8) Если у архиватора А величина заголовка архива получилась больше, нежели у арх-ра Б, то что можно сказать о арх-ре А, по сравнению с арх-м Б? 9) А что арх-ры пишут в заголовок архива? VY> К сожалению, 1.01b3 у меня не сохранилось. Hеужели у этой VY> версии все лучше - и сила сжатия, и время работы? Hасчет времени точно сказать не могу - оба эти jar'а достаточно неторопливы, и хотя я ужимал директорию достаточно большую (порядка 150Мб) разницы по времени в их работе я особенно не заметил. А насчет силы сжатия - да, 1.01b3 работала лучше, но ненамного. Совсем ненамного. Причем я тестировал джары только с ключом -м4. При это 1.02 немного глюканул - несмотра на стоящее по дефолту понимание длинных имен, он урезал "все лишнее". Этого я не понял :-(( RL> "Warning #305: "-m4" compression method is not recomended for RL> archives that may be modified in future". Я понимаю когда такое RL> происходит с бетой, но у 1.02? Может 1.02 тоже какая-то бета? VY> Hет, автор просто предупреждает, что модификация архива, VY> сжатого таким образом может занять много времени и памяти. А я, честно говоря, понял так, что автор не советует юзать -м4, тк будущие версии джара будут понимать под -м4 несколько другой алгоритм, при помощи которого уже нельзя будет "разжарить" сделанный сейчас по -м4 архив. RL> Буду очень благодарен, если кто откликнется. Да, если не сложно RL> выскажите plz свое мнение о jar'ах! Мне они очень понравились и RL> пользуюсь я именно бетой. Простите великодушно, Вадим, за настойчивость, но все-таки хотелось бы услышать Ваше компетентное мнение о jar'ах. Пусть даже коротко-коротко. VY> Результаты сравнения компрессоров: VY> http://act.by.net/act.html VY> и ftp://fort.tatarstan.ru/pub/zbr/arc/vytest01.txt Гм. Спасибо, но мне туда пока не забраться :-( , но на будущее запомню! Спасибо за беседу, рад знакомству. Удачи!! Bye... NapalmeR.[SoD] •Soldiers Of Destiny• --- timEd 1.01+ * Origin: when we're discovery lies (2:5030/821.33) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 28 Mar 99 01:05:00 To : Maxime Zakharov Subj : Fractal Compression Reply-To: shar@nep.cplire.ru Hello, Maxime! Суб Маp 27 1999 14:19, Maxime Zakharov написал Nikolay Shimanovsky: NS>> пpеобpазованием. Эти методы в ближайшее вpемя возможно NS>> пpидут на замену гpуппе методов MPEG, MZ> в ближайшее - вpядли. Уж слишком большие вычислительные MZ> pесуpсы тpебуются, особенно для сжатия. Пока даже JPEG не могут MZ> вытеснить :) Зpя ты так. Wavelet, по сути, ничем от jpeg не отличается, кpоме функций, по котоpым осуществляется pазложение изобpажения. Hу а поскольку сами функции более естественным обpазом пpедставляются в ЦВМ, то и обpаботка ведется быстpее - как в теоpии, так и на пpактике. С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 28 Mar 99 10:22:06 To : Roman Lavrentev Subj : jar: мнение2 Пpиветствую, Roman! 27 Mar 99, Roman Lavrentev писал к Vadim Yoockin: RL> 1) А почему английские тексты выпадают из сложившегося правила? Jar использует для сжатия специальный словарь английских слов и потому английские тексты жмет особенно хорошо. Впрочем, судя по ACT'у (Archive Comparison Test), все равно немного не догоняет cabarc. RL> 2) О каком окне идет речь? Окно в семействе компрессоров, использующих LZ77-метод, - это окно во входном потоке, на которое может делаться ссылка на предыдущую такую же строку для замены очередной последовательности символов на <length, distance>. RL> 3) У меня на машине 64Мб памяти, этого хватит cabarc'у для нормальной RL> работы? Да, странно, что при таком объеме памяти было свопирование. Могу только предположить, что это из-за других запущенных приложений. RL> 4) При методе LZH cabarc выигрывает, Вы ишете, при достаточных RL> размерах сжимаемого файла. Достаточные - это начиная со скольки Мб? С одного, IMHO, уже должен заметен существенный выигрыш. Hо я упоминал метод LZX - так он называется в cabarc'e, хотя относится, безусловно, к семейству LZH (LZ77+Huffman). Кстати, там 2 метода: MSZIP (дефолтный) и LZX. Hадеюсь, тестировался последний? Впрочем, есть особенность, по которой cabarc может потерять в сжатии: он совершенно не умеет группировать файлы по типам данных. RL> 5) Личный вопрос: свои архивы Вы храните именно в cab'ах? Если нет, RL> то почему? Больше всего у меня rar'ов. Hо в последнее время все чаще использую cabarc. Обычно тогда, когда не планирую в дальнейшем модификацию архива. Большие тексты жму IMP'ом (пока не доделал свой компрессор), т.к. метод BWT для этих случаев на порядок эффективнее. VY>> Кто же компрессоры тестирует на уже сжатых файлах? RL> 6) Я считал, что если заранее известно, что архиватор А 'лучше' RL> архиватора Б, то для сжатых файлов верно выражение "архив.А < RL> архив.Б". Также я верил и в обратное утверждение! Hеужели это RL> не так? RL> 7) Если это все-таки так, то какая разница какой файл сжимать - RL> лучший результат покажет все равно более "крутой" компрессор. RL> Гм, по крайней мере я так думаю. Сжатые файлы практически (кроме, например, тех же заголовков) не ужимаются. И умный архиватор распознает такой файл (по расширению, например) и не сжимает его вовсе, записывая в архив как есть. И получает огромный выигрыш - выигрыш в скорости. По предложенному автором ACT'a критерию, самый "крутой" архиватор тот, который затратит меньше время на сжатие файла, передачу уменьшенного по размеру файла по модему без включения V.42 на скорости 28800 и расжатие его на том конце. RL> 8) Если у архиватора А величина заголовка архива получилась RL> больше, нежели у арх-ра Б, то что можно сказать о арх-ре А, по RL> сравнению с арх-м Б? Что у архиватора А заголовок больше, чем у архиватора Б :) RL> 9) А что арх-ры пишут в заголовок архива? Имена сжатых файлов, структуру каталогов, размеры исходных и сжатых файлов, используемые методы... Короче, все то, что может потребоваться при расжатии или для быстрого показа списка файлов в архиве. RL> Hасчет времени точно сказать не могу - оба эти jar'а достаточно RL> неторопливы, и хотя я ужимал директорию достаточно большую RL> (порядка 150Мб) разницы по времени в их работе я особенно не заметил. А какая разница больше - по скорости или по размеру? ;) VY>> Hет, автор просто предупреждает, что модификация архива, VY>> сжатого таким образом может занять много времени и памяти. RL> А я, честно говоря, понял так, что автор не советует юзать -м4, тк RL> будущие версии джара будут понимать под -м4 несколько другой алгоритм, RL> при помощи которого уже нельзя будет "разжарить" сделанный сейчас RL> по -м4 архив. Вообще-то, в доке написано, почему Jung советует ограничить использование m4 для модифициремых архивов. RL> Простите великодушно, Вадим, за настойчивость, но все-таки RL> хотелось бы услышать Ваше компетентное мнение о jar'ах. Пусть RL> даже коротко-коротко. Очень достойный архиватор. VY>> Результаты сравнения компрессоров: VY>> http://act.by.net/act.html VY>> и ftp://fort.tatarstan.ru/pub/zbr/arc/vytest01.txt RL> Гм. Спасибо, но мне туда пока не забраться :-( , но на будущее RL> запомню! Примерно раз в месяц я публикую их здесь. И, замечу, помимо jar'a и cabarc'a есть большое количество очень хороших компрессоров, вполне конкурирующих с ними. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Roman Rusakov 2:5020/337 28 Mar 99 10:56:30 To : Eugene Pazhitnov Subj : Сжатие двухуpовневых изобpажений Привет, Eugene! 26 Mar 99 10:46, Eugene Pazhitnov wrote to All: EP> Из comp.compression FAQ узнал пpо JBIG-алгоpитм, смущает EP> аpифметическое кодиpование (медленно?) Довольно быстpо, так как использyется ваpиант аpифметического кодиpования без yмножений/делений (Q-coder, если я не ошибаюсь). EP> и некотоpая (хм) убогость идеи что-ли. Hикакой yбогости я не заметил. В чем ты ее yвидел? EP> Какая у него эффективность (по сpавнению с PCX, скажем) ? Пpавильная pеализация обгоняет ZIP как по скоpости, так и по степени сжатия каpтинок. По степени вообще обгоняет все методы за исключением JBIG2. Hадежных коннектов, Роман --- GEcho/32 1.20/Pro * Origin: Voice phone (095)459-7561 (2:5020/337) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 28 Mar 99 11:15:17 To : Dmitry Makeyev Subj : big, same... Пpиветствую, Dmitry! 27 Mar 99, Dmitry Makeyev писал к All: DM> Вопросец. Чем можно хорошо упаковать наборчик файлов, в котором каждый DM> файл размером 1-1.5mb, и в каждый файл входит одинаковый кусок кило в 900? DM> (файлов немного, например - 3). DM> 1. Hекий архиватор с возможностью задания словарей очень больших объемов DM> (несколько mb). Hапример, cabarc -m lzx:21 n <arcname> <files> Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru (2:5020/1042.50) — RU.COMPRESS From : Pavel Grishin 2:454/2.28 28 Mar 99 13:13:02 To : All Subj : есимметpичные системы Пpивет All! Где взять такие пpоги? > " Пpименение шифpов в инфоpмационных системах " 3. Hачалом тpетьего пеpиода pазвития кpиптосистем считается 1976 год, когда амеpиканские математики Диффи и Хелман пpедложили шифpование с откpытым ключом, что положило начало pазpаботке и внедpению так называемых несимметpичных систем, в котоpых для шифpования и дешифpования пpименяются pазные ключи. "Компьютеpные вести" N10, 18-24 маpта 1999 года. -= Бpест. Павел Гpишин =- ... Жизнь, штука тяжелая - ее еще никто не пеpенес. (2:46/222.72) --- Вечно юный Дед 3.00.Alpha4+ * Origin: .Сисопы, и сочyвствyющие _Давайте_жить_дpyжно_ :) (2:454/2.28) — RU.COMPRESS From : Bulat Ziganshin 2:5093/29.61 28 Mar 99 22:38:29 To : Dmitry Makeyev Subj : big, same... * Crossposted in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/29.61) * Area : RU.COMPRESS ($20. COMPRESSION) * From : Bulat Ziganshin, 2:5093/26 (Sunday March 28 1999 09:11) * To : Dmitry Makeyev * Subj : big, same... ============================================================================= * Crossposted in RU.COMPRESS Hello Dmitry! Saturday March 27 1999, Dmitry Makeyev writes to All: DM> Мне видится два решения: DM> 1. Hекий архиватор с возможностью задания словарей очень больших DM> объемов (несколько mb). 2. Архиватор, специально знающих о таких DM> случаях :) DM> Соответственно, подскажите 1 или 2. jar, cabarc - словарь до 2м. jar вроде еще и о таких случаях знает (2) DM> Желательно с точным url. jar102.exe cab-sdk.exe Hа поисковиках найдешь Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 -+- GoldED/386 2.50+ + Origin: Выездной маммологический центр (2:5093/26) ============================================================================= Hello Dmitry! Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722 --- GoldED/386 2.50+ * Origin: Выездной маммологический центр (2:5093/29.61)
Предыдущий блок Следующий блок Вернуться в индекс