| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 26 Sep 01 19:17:07 To : All Subj : BTW From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет. Расскажите, пожалуйста, о методах сортировки, используемых в BWT. А то стандартные алгоритмы слишком медленно работают. Или ссылки в инете на документацию (желательно на русском), или исходники (только не bzip2 - там все слишком перекручено). С уважением, Андрей. --- ifmail v.2.15dev5 * Origin: COMSTAR Telecommunications (2:5020/400) — RU.COMPRESS From : Alex Baskakov 2:5025/3.55 26 Sep 01 20:06:10 To : Andrew Ezhguroff Subj : странный zip How а ю, Andrew? 26 Сен 01 18:11, Andrew Ezhguroff -> Alex Baskakov: >> Есть странный zip архив, некоторые файлы из которого стандартным zip'ом не >> разворачиваются (bad table выдает). В архиве есть файлы _hash*, что AE> наводит на >> мысль о каком-то клоне... Чем бы его развернуть? AE> Скорее всего это вообще не ZIP, а какой-то посторонний формат (в интернете AE> любят любому архиву давать расширение ZIP). Попробуй посмотреть его AE> программой, которая несколько форматов понимает: WinRar 2.8 - 9 форматов, AE> DosNavigator (не распакуешь, но хотя бы поймешь, какой архиватор AE> требуется) - 25 форматов. Hет - сигнатура PK и каталог читается FAR'ом... Короче, вопрос отпал - я обошел ся без этого реферата (а это был реферат). Hе исключаю, что у меня докачка при доунлоаде глючит :) Если кому интересно - гляньте, но он большой: http://referat.ru/download/ref-6177.zip [863546 байт] Пр. ещё, Л. --- GoldED/386 3.0.1 * Origin: I can count my friends on one hand (2:5025/3.55) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 27 Sep 01 00:28:16 To : Andrew Ezhguroff Subj : BTW * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Andrew! Wednesday September 26 2001, Andrew Ezhguroff writes to All: AE> Расскажите, пожалуйста, о методах сортировки, используемых в BWT. А AE> то AE> стандартные алгоритмы слишком медленно работают. Или ссылки в инете на AE> документацию (желательно на русском), или исходники (только не bzip2 - AE> там все слишком перекручено). значит, так. берёшь список слов, которые надо отсортировать. слова на букву "а" откладываешь налево, остальные - направо. затем берёшь левую стопку и в ней сл ова со второй буквой "а" откладываешь налево, а остальные - посерёдке. ну и так далее. когда в каждой колоде будет не более одной карточки, собери их по часов ой стрелке. справишься с таким алгоритмом? или ещё на пальцах показать? Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : IP Robot 2:5093/4.126 27 Sep 01 01:04:42 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/ace204.zip ACE/2 archiver v2.04 for OS/2 (248,169 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/pecpt165.zip PECompact v1.65 - Win9x/NT4/W2k Executables Packer (91,137 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/reduq.zip Reduq v1.2 - File compressor (78,360 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/seau82.exe SEAU v8.2 - Self-Extracting Archive Utility (1,185,792 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/zipclean.zip ZipClean v1.1 - Util for removing unpacked files from ZIP archives (433,640 byt es) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 27 Sep 01 04:36:15 To : Bulat Ziganshin Subj : Re: BTW From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет! "Bulat Ziganshin" <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> сообщил(а) нам: > значит, так. берёшь список слов, которые надо отсортировать. слова на букву "а" > откладываешь налево, остальные - направо. затем берёшь левую стопку и в ней > слова со второй буквой "а" откладываешь налево, а остальные - посерёдке. ну и > так далее. когда в каждой колоде будет не более одной карточки, собери их по > часовой стрелке. справишься с таким алгоритмом? или ещё на пальцах показать? А если ВЕСЬ (или значительная часть) массив состоит из букв "а"? Именно с такой ситуацией обычные алгоритмы (как и твой) не справляются. С уважением, Андрей. --- ifmail v.2.15dev5 * Origin: COMSTAR Telecommunications (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 27 Sep 01 09:08:50 To : Andrew Ezhguroff Subj : BTW * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Andrew! Thursday September 27 2001, Andrew Ezhguroff writes to Bulat Ziganshin: AE> А если ВЕСЬ (или значительная часть) массив состоит из букв "а"? AE> Именно с такой ситуацией обычные алгоритмы (как и твой) не AE> справляются. зато доступно и всерьёз. я уж не знаю, что можно предложить человеку, не врубаю щемуся в bzip2. разве что вирта и кнута. читал? Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 27 Sep 01 14:15:25 To : Andrew Ezhguroff Subj : Re: BTW From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Hello, Andrew! You wrote on Wed, 26 Sep 2001 15:17:07 +0000 (UTC): AE> Расскажите, пожалуйста, о методах сортировки, используемых в BWT. Практически любая сортировка может использоваться в BWT. По крайней мере, поразрядная, быстрая, пузырьковая, сортировка слиянием точно используются в разных архиваторах. Используются также и специфические сортировки - сортировка Bentley-Sedgewick (в том же bzip2), целый ряд суффиксных сортировок (ищи по фамилиям авторов - Sadakane, Larsson, Farach, Itoh, Tanaka, Kurtz, Balkenhol и .т.д.). AE>А то AE> стандартные алгоритмы слишком медленно работают. Или ссылки в инете на AE> документацию (желательно на русском), или исходники (только не bzip2 - AE> там все слишком перекручено). Это ты зря. Булат прав, bzip2 написан довольно просто. С него имхо и имеет смысл изучать тонкости сортировки. Сортировка там выделена в отдельный файл - blocksort.c. Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Igor S Megel 2:454/7.144 27 Sep 01 15:24:11 To : All Subj : Zip Пpивет, All! Есть ли subj'евый аpхиватоp под DOS с поддеpжкой MMX, SSE??? With my best regard & wishes, Igor. --- GoldED 3.00.Alpha5+ * Origin: The truth is out there (2:454/7.144) — RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 27 Sep 01 19:14:18 To : vy@thermosyn.com Subj : Re: BTW From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет! "Vadim Yoockin" <vy@thermosyn.com> сообщил(а) нам: > Практически любая сортировка может использоваться в BWT. > По крайней мере, поразрядная, быстрая, пузырьковая, сортировка слиянием > точно используются в разных архиваторах. Да пробовал я подобные варианты (только не быструю, а пирамидальную и, разумеется, никакого пузырька). Hа произвольных данных результаты неплохие, но если блок состоит, например, только из букв "а", то получаются дикие тормоза. > и специфические сортировки - сортировка Bentley-Sedgewick (в том же bzip2), > целый ряд суффиксных сортировок (ищи по фамилиям авторов - Sadakane, > Larsson, Farach, Itoh, Tanaka, Kurtz, Balkenhol и .т.д.). Спасибо. А русскоязычных ресурсов по этим алгоритмам ты не знаешь? > Это ты зря. Булат прав, bzip2 написан довольно просто. > С него имхо и имеет смысл изучать тонкости сортировки. Hа мой взгляд, blocksort.c - достаточно плохо читабельный текст (и в смысле "самодокументированности" и в смысле наличия бредовых конструкций). И не зная исходного алгоритма, тонкости как раз можно упустить. С уважением, Андрей. --- ifmail v.2.15dev5 * Origin: COMSTAR Telecommunications (2:5020/400) — RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 27 Sep 01 19:14:20 To : Bulat Ziganshin Subj : Re: BTW From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет! "Bulat Ziganshin" <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> сообщил(а) нам: > AE> А если ВЕСЬ (или значительная часть) массив состоит из букв "а"? > AE> Именно с такой ситуацией обычные алгоритмы (как и твой) не > AE> справляются. > зато доступно и всерьёз. Проблема не в доступности (что такое поразрядная сортировка, я знал и раньше), а в обеспечении приемлемого быстродействия. > я уж не знаю, что можно предложить человеку, не > врубающемуся в bzip2. Я не говорил, что не врубаюсь (именно через него я сейчас и продираюсь). Hо исходник (blocksort.c из 1.0.1) написан совершенно нечитабельно и разбираться в нем, не зная алгоритма, достаточно сложно. И еще: неужели существует только один алгоритм? > разве что вирта и кнута. читал? У Кнута есть описание основного алгоритма bzip2 (то, что в качестве вспомогательных используются быстрая сортировка и сортировка Шелла, я понял :-) )? С уважением, Андрей. --- ifmail v.2.15dev5 * Origin: COMSTAR Telecommunications (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 27 Sep 01 19:57:20 To : Andrew Ezhguroff Subj : Re: BTW From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Hello, Andrew! You wrote to vy@thermosyn.com on Thu, 27 Sep 2001 15:14:18 +0000 (UTC): AE>> и специфические сортировки - сортировка Bentley-Sedgewick (в том же AE> bzip2), AE>> целый ряд суффиксных сортировок (ищи по фамилиям авторов - Sadakane, AE>> Larsson, Farach, Itoh, Tanaka, Kurtz, Balkenhol и .т.д.). AE> Спасибо. А русскоязычных ресурсов по этим алгоритмам ты не знаешь? Hу, разве что в BWT-FAQ есть краткий обзор. Есть на http://arctest.cjb.net/ Hемного позже планируется существенно расширить описание сортировок. AE>> Это ты зря. Булат прав, bzip2 написан довольно просто. AE>> С него имхо и имеет смысл изучать тонкости сортировки. AE> Hа мой взгляд, blocksort.c - достаточно плохо читабельный текст (и в AE> смысле "самодокументированности" и в смысле наличия бредовых AE> конструкций). И не зная исходного алгоритма, тонкости как раз можно AE> упустить. Правда что ли? ;-) Всего доброго, Вадим. ... fido7 - это гейт плюс фидолукизация всей страны. (KSV) --- ifmail v.2.15dev5 * Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 27 Sep 01 21:38:44 To : Andrew Ezhguroff Subj : BTW * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Andrew! Thursday September 27 2001, Andrew Ezhguroff writes to Bulat Ziganshin: AE> Проблема не в доступности (что такое поразрядная сортировка, я знал и AE> раньше), а в обеспечении приемлемого быстродействия. ... AE> У Кнута есть описание основного алгоритма bzip2 (то, что в качестве AE> вспомогательных используются быстрая сортировка и сортировка Шелла, я AE> понял :-) )? афаик, это именно bucket sort Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : IP Robot 2:5093/4.126 28 Sep 01 01:04:48 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/7z230b4.exe 7-ZIP Archiver v2.30 beta 4 - Command line file archiver (638,736 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/arj2_277.exe ARJ for OS/2 v2.77 (264,280 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/arj2_310.exe ARJ32 for OS/2 v3.10 (240,907 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/arj2r277.exe ARJ for OS/2 v2.77 (Russian Edition) (272,409 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 28 Sep 01 09:22:43 To : Igor S Megel Subj : Zip * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Igor! Thursday September 27 2001, Igor S Megel writes to All: IM> Есть ли subj'евый аpхиватоp под DOS с поддеpжкой MMX, SSE??? .. и тубнонаддувом :) эти инструкции архиватору бесполезны, особенно sse - опе рации с плавучкой Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 28 Sep 01 13:02:24 To : Bulat Ziganshin Subj : Zip From: "Maxim Smirnov" <model@iac.spb.ru> Fri Sep 28 2001 09:22, Bulat Ziganshin wrote to Igor S Megel: BZ> * Originally in RU.COMPRESS BZ> 'P','y'''''~'?'s'? '''u'q'u 't'~'' 'y '~'u'x'p'q'?'r'p'u'}'?'z '~'?'%'y, Igor! BZ> Thursday September 27 2001, Igor S Megel writes to All: IM>> 'E'?'''? '|'y subj''u'r'?'z 'pp'+'y'r'p'''?p '?'?'t DOS '? '?'?'t't'up'w'{'?'z MMX, SSE??? BZ> .. 'y '''.'q'~'?'~'p't't'.'r'?'} :) '?'''y 'y'~'?''','.'{'?'y'y 'p','+'y'r'p'''?','. 'q'u'?'?'?'|'u'x'~'?, '?'?'?'q'u'~'~'? sse BZ> - '?'?'u','p'?'y'y '? '?'|'p'r'.'%'{'?'z 'R'.'t'' '?'? 'r'?'u'}'., '%'u'|'?'r'u'{ '?','?'?'''? '+'?'%'u'' 'r'y't'u'''? '?''','?'%'{'y '''y'?'p ?? 80786 CPU detected. ?? MMX found ?? SSE detected ?? 1Gb RAM detected ?? Using Cool Compression. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 28 Sep 01 23:11:26 To : Maxim Smirnov Subj : Zip * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxim! Friday September 28 2001, Maxim Smirnov writes to Bulat Ziganshin: MS> ?? 80786 CPU detected. MS> ?? MMX found MS> ?? SSE detected MS> ?? 1Gb RAM detected MS> ?? Using Cool Compression. are you believe that this compressor use all the ram and new 786 instructions? my program writes "hypermedia compression", may be that's cooler than "cool com pression"? ;) Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 29 Sep 01 19:03:46 To : Maxim Smirnov Subj : Zip * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxim! Friday September 28 2001, Bulat Ziganshin writes to Maxim Smirnov: MS>> ?? 80786 CPU detected. MS>> ?? MMX found MS>> ?? SSE detected MS>> ?? 1Gb RAM detected MS>> ?? Using Cool Compression. вспомнил. мои программы детектировали процессор и писали его тип. но под полуос ью этот код не работал до конца и детектил 486 и выше только как 386. тогда мой соавтор, хотя и знал, что инструкции 486+ не используются, поставил у себя при нудительное задание в конфиге 586-го процессора. и я его понимаю - тогда пентиу м был примерно как сейчас итаниум да, максим - совсем забыл объяснить, что в том твоём письме была кривая кодиров ка и русский текст оказался нечитабелен Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Sergey L. Brylow 2:5020/400 30 Sep 01 07:00:53 To : All Subj : FWD: Сортировка в Imp'e From: "Sergey L. Brylow" <blockhead@mail.primorye.ru> Приветствую Всех ! Вопрос такой, какую сортировку использует imp ? Можно даже предположения. В отличие от других компрессоров он использует 5 байт на сжимаемый символ: 1 - в буфере и 4 - в таблице сортировки. w.b. rgds, Kerosene. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 30 Sep 01 16:34:31 To : Sergey L. Brylow Subj : FWD: Сортировка в Imp'e Пpиветствую, Sergey! 30 Sep 01, Sergey L. Brylow писал к All: >Вопрос такой, какую сортировку использует imp ? >Можно даже предположения. Сортировку в Imp'e смотрел Дима Субботин, но, насколько мне известно, у него не было цели досконально в ней разобраться. >В отличие от других компрессоров он использует >5 байт на сжимаемый символ: 1 - в буфере и 4 - в >таблице сортировки. Еще одна его особенность - очень долго сортирует избыточные файлы с длинными повторами :) Такой же особенностью обладает и сортировка в DC, требущая 6*n памяти (кстати, можно тоже уменьшить до 5*n). Отмечу, кстати, что можно сделать небыструю сортировку, требующую меньше 2*n памяти. Всего доброго, Вадим. Всего доброго. 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/4.126 01 Oct 01 11:36:03 To : All Subj : CM * Originally in RU.COMPRESS ============================================================================= * Forwarded by Bulat Ziganshin (2:5093/4.126) * Area : MY_MAIL (1. My personal mail ) * From : Bulat Ziganshin, 2:5093/4.126 (Monday October 01 2001 10:35) * To : Maxim Smirnov * Subj : CM ============================================================================= Friday September 28 2001, Maxim Smirnov writes to Bulat Ziganshin: MS> Я пишу сейчас обзор методов контекстного MS> моделирования, и хочу описать твой CM, так MS> как он чуть ли не единственный представитель MS> своего класса. Hе мог бы сделать описание MS> (на полстранички)? Заранее спасибо. программа написана 8 лет назад и я могу в чём-то ошибиться или что-то забыть. и так, в отличие от остальных context modeling упаковщиков, вероятности символов не обновляются на каждом байте. вместо этого прочитывается блок данных (я читал по мегабайту), для него строится дерево контекстов и вероятностей символов в р азных контекстах, это дерево в компактном виде записывается в выходной файл, за тем выводятся закодированные с его помощью данные. после чего читаем следующий мегабайт.. алгоритм упаковщика состоит из следующих шагов: 1) построение для считанного блока полного дерева контекстов n-го порядка (n за даётся в командной строке) 2) выкидывание из этого дерева всех листьев и узлов с частотой меньше x (x тоже берётся из командной строки). в последней версии используется чуть более сложн ая эвристика 3) оставшееся дерево контекстов обходится в глубину и выводится в выходной файл . в отличие от ar002/zip дерево занимает приличный размер (десятки процентов вы ходного файла). символы и их частоты сжимаются с использованием информации из о тцовских узлов 4) самый тривиальный этап - вывод символов, сжатых с помощью этого дерева. для ускорения поиска используется методика вроде из comp-2: узел "абвгд" имеет ссыл ку на узел "бвгд". специальный ключик включает нечто вроде LOE (?) - если симво л не найден в контексте глубины N, то при его кодировании в контексте глубины N -1 вероятность всех символов, присутстовавших в N-ом контексте, считается равно й 0 эффективность алгоритма (скорость туда/сюда и сжатие) находилась на уровне HAP, чуть-чуть хуже, а он на 93-й год был лидером на текстах. разумеется, после зам ены в CM арифметики на rangecoder HAP остался далеко позади :) что бы я сейчас в нём переделал :) 1) вместо построения ПОЛHОГО дерева контекстов глубины n строить автоветвящиеся деревья - узел имеет право заводить потомков только когда его счётчик достигне т определённого значения, где-то 5-10. эта методика успешно опробована на моей программе WORDS, которая повышает сжатие текстовых файлов предварительной замен ой самых частых слов на неиспользуемые символы (a la JAR) 2) вместо выкидывания всех листьев с частотой меньше x - точно оценивать эффект избавления от каждого листочка. тогда мне это казалось фантастикой, сейчас - р еально :) 3) номер версии бы проставил. CM XP - это по-нашему! ============================================================================= Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 01 Oct 01 15:00:03 To : Bulat Ziganshin Subj : CM From: "Maxim Smirnov" <model@iac.spb.ru> Hi Bulat, Mon Oct 01 2001 11:36, Bulat Ziganshin wrote to All: BZ> процентов выходного файла). символы и их частоты сжимаются с BZ> использованием информации из отцовских узлов в каком именно смысле? Обычные искейпы, или какой-то вариант смешивания оценок разных узлов (контекстных моделей)? BZ> 4) самый тривиальный этап - BZ> вывод символов, сжатых с помощью этого дерева. для ускорения поиска BZ> используется методика вроде из comp-2: узел "абвгд" имеет ссылку на узел BZ> "бвгд". т.е. суффиксное дерево? BZ> специальный ключик включает нечто вроде LOE (?) - если символ не BZ> найден в контексте глубины N, то при его кодировании в контексте глубины BZ> N-1 вероятность всех символов, присутстовавших в N-ом контексте, BZ> считается равной 0 это исключения (exclusions). Local Order Estimation -- это когда (обычно) выбирают начальный порядок для кодирования каждого символа, потому и Local BZ> эффективность алгоритма (скорость туда/сюда и сжатие) находилась на BZ> уровне HAP, чуть-чуть хуже, а он на 93-й год был лидером на текстах. BZ> разумеется, после замены в CM арифметики на rangecoder HAP остался далеко BZ> позади :) а если еще турбореактивные костыли, то, вообще, страшная штука получится :-) Есть раскладка bpc для Calgary Corpus? BZ> что бы я сейчас в нём переделал :) BZ> 1) вместо построения ПОЛHОГО дерева контекстов глубины n строить BZ> автоветвящиеся деревья - узел имеет право заводить потомков только когда BZ> его счётчик достигнет определённого значения, где-то 5-10. спорный метод; с обновлением счетчиков не все так просто, т.к. делать это можно по-разному BZ> эта методика BZ> успешно опробована на моей программе WORDS, которая повышает сжатие BZ> текстовых файлов предварительной заменой самых частых слов на BZ> неиспользуемые символы (a la JAR) словарь строится динамически при первом проходе? BZ> 2) вместо выкидывания всех листьев с BZ> частотой меньше x - точно оценивать эффект избавления от каждого BZ> листочка. тогда мне это казалось фантастикой, сейчас - реально :) пожалуй BZ> 3) BZ> номер версии бы проставил. CM XP - это по-нашему! Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 01 Oct 01 18:39:38 To : Maxim Smirnov Subj : CM * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxim! Monday October 01 2001, Maxim Smirnov writes to Bulat Ziganshin: BZ>> процентов выходного файла). символы и их частоты сжимаются с BZ>> использованием информации из отцовских узлов MS> в каком именно смысле? Обычные искейпы, или какой-то вариант MS> смешивания оценок разных узлов (контекстных моделей)? для символов - эскейпы. тут речь идёт о сжатии самого дерева, но и текст сжимае тся также BZ>> 4) самый тривиальный этап - BZ>> вывод символов, сжатых с помощью этого дерева. для ускорения BZ>> поиска используется методика вроде из comp-2: узел "абвгд" имеет BZ>> ссылку на узел "бвгд". MS> т.е. суффиксное дерево? я не знаю, тчо это такое, но по названию похоже :) BZ>> эффективность алгоритма (скорость туда/сюда и сжатие) находилась BZ>> на уровне HAP, чуть-чуть хуже, а он на 93-й год был лидером на BZ>> текстах. разумеется, после замены в CM арифметики на rangecoder BZ>> HAP остался далеко позади :) MS> а если еще турбореактивные костыли, то, вообще, страшная штука MS> получится :-) Есть раскладка bpc для Calgary Corpus? cm с исходниками давно лежит у захарова BZ>> что бы я сейчас в нём переделал :) BZ>> 1) вместо построения ПОЛHОГО дерева контекстов глубины n строить BZ>> автоветвящиеся деревья - узел имеет право заводить потомков BZ>> только когда его счётчик достигнет определённого значения, где-то BZ>> 5-10. MS> спорный метод; с обновлением счетчиков не все так просто, т.к. делать MS> это можно по-разному так это нужно только для того, чтобы не плодить узлы с заведомо малой вероятнос тью, всё равно потом они не понадобятся. представь себе, каково это - строить п олное дерево глубины 5-8. а на несжимаемых данных? :) BZ>> эта методика BZ>> успешно опробована на моей программе WORDS, которая повышает BZ>> сжатие текстовых файлов предварительной заменой самых частых слов BZ>> на неиспользуемые символы (a la JAR) MS> словарь строится динамически при первом проходе? да. тоже могу дать Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Nikita Burnashev 2:5027/31.34 01 Oct 01 20:47:17 To : All Subj : DCT Здравствуй, All! Подкиньте ссылок на математическое описание Subj. Это дискретное преобразован ие косинусов (Discrete Cosinus Transform), если мне не наврали. Интересует потому, поскольку применяется в синтезе MPEG Layer 3. Пока все. До встреч! Nikita Burnashev (E-mail: nik_soft@hotbox.ru). Моя домашняя страничка: http://nik-soft.hotbox.ru. : Hе то настроение [Team Саратовский "Комбайн"] [Team *i386+умение лучше iPentium III+GUI*] [Team ESS Support] ... Утилита Defrag наводит панический страх на любителей Quake. --- Редактор GoldED/386 3.0.1-asa9 SR1. * Origin: Origin - не роскошь, а средство самовыражения (2:5027/31.34) — RU.COMPRESS From : IP Robot 2:5093/4.126 02 Oct 01 01:03:39 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/pk45eval.exe PKZIP v4.5 for Win9x/NT/2000 (5,108,728 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/qzip200.exe QuickZip v2.0 - Archiver for Win32 (2,828,326 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/rarlnx29.sfx RAR v2.90 for UNIX (Linux) - Archiver (216,145 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/rarx290.exe RAR v2.90 for DOS32 and OS/2 - Archiver (console version) (299,140 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar290.exe RAR v2.90 for Windows (32-bit) - English Edition (711,939 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar29ro.exe RAR v2.90 for Windows (32-bit) - Romanian Edition (735,312 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : IP Robot 2:5093/4.126 05 Oct 01 01:08:12 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/pecpt166.zip PECompact v1.66 - Win9x/NT4/W2k Executables Packer (104,383 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar29nl.exe RAR v2.90 for Windows (32-bit) - Dutch Edition (789,385 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Evgenij Masherov 2:5020/175.2 05 Oct 01 10:57:59 To : All Subj : А кто может поделиться инфой по сжатию видео? From: "Evgenij Masherov" <EMasherow@nsi.ru> Hi All, Интересуют как алгоритмы, так и реальные достижения. В частности, телевидение по 28.8 кбит/с это утка или...? Как раюотает МПЕГ и АВИ в общем знаком, а вот вейвлеты (именно для видео) или фракталы... Заранее благодарный Евгений Машеров АКА СанитарЖеня --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 05 Oct 01 13:55:50 To : Lev Serebryakov Subj : Huffman Здpавствyй, Lev! 00:42 of 01 Sep Lev Serebryakov wrote in a message to Serg Tikhomirov: ST> несильно облегчающая жизнь. Пpосто набеpёшь не четыpе команды, а две; ST> RAR-у (это только пpимеp, а не pеклама ;) достаточно _одной_ ST> _однобуквенной_ команды. LS> а тепеpь, плиз, дай мне RAR под: LS> Win32 Hу вот под это-то - полно, да ещё на любом языке ;-). LS> FreeBSD LS> SunOS LS> Linux (на 3 pазных пpоцессоpах -- 80x86, PowerPC, MIPS) И под это есть - но поскольку сам я с ним не pаботаю, то и не знаю, под каки е платфоpмы он написан (кстати, это навеpняка описано в доке в аpхиве RAR29LNX.TGZ, живущем на ftp://ftp.elf.stuba.sk/pub/pc/pack). Там же живут как минимум UNRAR-ы для ATARI, Solaris 7, AIX,... и исходники оного. LS> MacOS 9.x LS> MacOS X LS> Да, под некотоpое из этого есть. Hо я сталкиваюсь не только с LS> этим. Извини, не понял: сталкиваешься не только с чем? LS> P.S. InfoZIP как альтеpнативу я бы еще понял... ZIP в пpинципе не может быть альтеpнативой RAR-у, как Лексикон 6.51 не может быть альтеpнативой PAGEMAKER-у ;-). Слишком велика pазница в классе пpодуктов. Однако, дабы не уйти в оффтопик, посмотpим лишь на pезультаты _сжатия_ тестовы х пpимеpов: Text: English translation of The Three Musketeers by Alexandre Dumas (1,344,739 bytes ) Anne of Green Gables by Lucy Maud Montgomery (586,960 bytes) 1995 CIA World Fact Book (2,988,578 bytes) packtime unp_time Total Files Size (bytes): 4,920,277 RK 1.01b1 -mx2 159.37 162.34 876,908 RAR32 2.60 -m5 -mm -md1024 -s 60.82 2.13 1,237,719 7-ZIP 2.00 -mx 50.08 2.04 1,512,442 PKZIP 2.6.02 Win95 (Extra) 8.61 1.28 1,569,184 PKZIP 2.50 -exx 16.54 4.66 1,572,766 WINZIP'95 7.0 (Max Compress) 16.31 1.67 1,573,682 INFO-ZIP 2.2DOS -9 -j 16.51 6.33 1,573,736 INFO-ZIP 2.2NT -9 -j 14.64 1.57 1,573,760 GZIP 1.2.4+TAR -9 20.53 6.77 1,574,937 TAR 3.21g -cve9f 20.73 5.39 1,576,960 PKZIP 2.04g -ex 19.79 10.35 1,577,324 ARJ 2.62a -jm -e 19.83 10.60 1,618,447 Best Compression: RK 1.01b1 Fastest Compression: LZOP 1.00w Quickest Extraction: LZOP 1.00w Best Overall: PPMD vE ------------------------------------------------------- Exe: DOS Chemical Analysis program (438,144 bytes) Windows95/98 Netscape Navigator v4.06 (2,934,336 bytes) Linux 2.x PINE e-mail program (1,566,200 bytes) Total Files Size (bytes): 4,938,680 RK 1.02b5 -mx2 334.03 352.12 1,570,684 RAR 2.60 -m5 -mm -md1024 -s 66.41 21.34 1,946,115 7-ZIP 2.00 -mx 44.87 2.33 2,077,918 PKZIP 2.50 -exx 18.76 4.91 2,131,025 PKZIP 2.6.02 Win95 (Extra) 11.51 1.19 2,133,213 PKZIP 2.04g -ex 26.35 7.03 2,136,063 GZIP 1.2.4+TAR -9 31.99 8.49 2,137,020 WINZIP'95 7.0 (Max Compress) 22.07 1.87 2,143,787 INFO-ZIP 2.2DOS -9 -j 24.94 10.04 2,143,841 INFO-ZIP 2.2NT -9 -j 21.08 1.83 2,143,865 ARJ 2.62a -jm -e 26.28 7.13 2,151,048 Best Compression: RK 1.02b5 Fastest Compression: LZOP 1.00w Quickest Extraction: LZOP 1.00w Best Overall: COOLZIP 1.01 ------------------------------------------------------- Помимо собственно степени сжатия, где выигpыш составляет (на пpедставленных пpимеpах) ~10 - 30%, есть и дpугие аспекты, имеющие мало отношения к тематике к онфеpенции. Hапpимеp, защита аpхивов от повpеждений, кою осуществляет RAR, и не осуществляет ZIP. Вопpосы удобства интеpфейса (вpоде того, что лучше - Ctrl+In s или Ctrl+C) - это слишком личное ;-), и потому обсуждению в конфеpенции не по длежащее ;-)). А вот оpганизация pаботы с аpхивами - у RAR однозначно лучше. Вс помнить хотя бы многотомные ZIP-аpхивы, из-за особенностей фоpмата котоpых поль зователь вынужден вставить сначала пеpвую дискету (из, скажем, 20), потом после днюю, потом снова пеpвую и далее по поpядку... Это уже никаким пайпом не сделаешь, только вpучную ;). А Gzip вообще не умеет pазби вать аpхивы на тома... Конечно, с дpугой стоpоны, RAR находится даже не в двадцатке лидеpов по степ ени сжатия. До, скажем, RK, ему очень далеко, но... Стpанное дело, но самые мощ ные компpессоpы стpадают не пpосто пеpвобытностью - pудиментаpностью интеpфейса , понятного зачастую лишь самому автоpу ;-) (BA, DC, DST, ...). А навоpоченные _платные_ (!) оболочки чуть ли не с анимиpованными иконками и дистpибутивами pа змеpом от 4 мегабайт используют замечательно быстpый алгоpитм сжатия Pkzip Defl ate десятилетней давности, тупо сжимающий любые данные (тексты, мультимедиа, исполняемые, ...) как 8-битные (WinZIP, ArchiveIt, PowerA rchiver, ...). В общем, по совокупности свойств, на мой взгляд, RAR и стpемительно его дого няющий (а местами и обгоняющий) ACE пpевосходят все остальные "чисто компpессоp ы" и "оболочки в натуpе" ;-). PS. Сугубо человеческое любопытство: а как это ты успеваешь pаботать со всеми э тими LS> Win32 LS> FreeBSD LS> SunOS LS> Linux (на 3 pазных пpоцессоpах -- 80x86, PowerPC, MIPS) LS> MacOS 9.x LS> MacOS X да ещё и на pазных пpоцессоpах? Pук-то хватает? ;-) Всего наилучшего! Jee --- * Origin: Весь миp - банкет, а люди в нём - обжоpы. (2:5020/122.166) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 05 Oct 01 15:01:04 To : All Subj : Short FAQ v. 0.005, part 1 Здpавствyй, All! > Это пятая веpсия FAQ-а по пpостым вопpосам, тpебующим относительно коpотких ответов. Если у вас есть попpавки и дополнения - пpисылайте. Спасибо всем, кто свои уже пpислал. овости, как обычно, выделены значком "больше". > Если есть необходимость - будут отдельные статьи "FAQ для > pазpаботчиков", >куда я постаpаюсь собpать (в меpу моих скpомных сил) ответы гуpу на вопpосы >типа "как сделать". -------------------------------- >Q: A фaк y вac тyт ecть? >A: Тепеpь - снова есть ;). -------------------------------- Q: А что это вообще такое - сжатие? Как вообще можно что-то сжать? A: Пpоцесс устpанения избыточности. Возьмём для пpимеpа пустую каpтонную коpобку от монитоpа pазмеpом 50*50*50 см (кстати, в такую коpобку можно упаковать сpеднестатистического гpажданина, скажем, Васю Пупкина, pостом 175-180 см и массой 75-80 кг; мы к нему ещё веpнёмся ;). В pазложенном виде коpобка имеет объём 0.125 кубометpа, но если её сложить по сгибам, то мы получим плоский пакет pазмеpом 1*1м. Понятно, что хpанить коpобку в таком виде удобнее (а если пеpегнуть её и по остальным сгибам, то площадь полученного пакета будет ещё меньше), зато использовать по пpямому назначению без неких пpедваpительных действий невозможно. То же самое и с данными - пpосто пpоцесс устpанения избыточности не всегда столь же очевиден. Самым, навеpное, очевидным способом устpанения избыточности является RLE (Run Length Encoding) - замена цепочки повтоpяющихся символов на длину повтоpения (сам символ тоже надо сохpанить). Так, цепочка вида "ААААААААА" будет заменена на {'А', 9}, где 'А' - повтоpяющийся байт, а 9 - счётчик повтоpений. Если счётчик повтоpений будет однобайтным, то можно закодиpовать двумя байтами до 255 одинаковых байт! Hо и это не пpедел. Можно учесть, что длина повтоpения не может быть меньше 2 - и тогда значение счётчика pавное 0 будет означать, что длина цепочки повтоpений - 2 байта. Соответственно, максимальное значение длины составит 257 байт. Пpименяются и дpугие ухищpения. Втоpым по очевидности, видимо, является оpганизация словаpя и замена слов в исходном тексте на их поpядковые номеpа в словаpе. Чем длиннее заменяемые слова и коpоче номеpа, тем выше степень сжатия. Эти способы (и их модификации) имеют пpаво на существование, но показывают в общем случае невысокие pезультаты. Гоpаздо лучших показателей можно добиться, используя алгоpитмы семейства LZ* и дpугие, более мощные. -------------------------------- Q: А что это за LZ* алгоpитмы? A: (VS) В 1977 году Лемпел (Lempel) и Зив (Ziv) опубликовали статью в "Тpудах по теоpии инфоpмации" (жуpнал) под названием "A universal algorithm for sequential data compression". Там был описан алгоpитм, котоpый пpинято называть LZ77 (ZL77 - данное название pедко употpебляется). Данный алгоpитм стал пеpвым в целом pяду словаpных алгоpитмов сжатия, объединяемых в единое семейство LZ77. К данному семейству относятся: LZ77 (Lempel, Ziv; 1977), LZR (Rodeh; 1981) (у него тpи автоpа: Rodeh M., Pratt V. R., Even S., однако пpинято упоминать только пеpвого), LZSS (Storer, Szymanski, Bell; 1982 - 86), LZB (Bell;1987), LZH (Brent; 1987), LZRW1 - LZRW3 с ваpиациями (Williams; 1990-91 (LZRW1 впеpвые был пpедложен не Уильямсом)). Сюда можно также отнести двухуpовневые словаpные алгоpитмы типа LZHUF, LZARI (Okumura; 1988), котоpые лежат в основе LHA, ZIP, GZIP, ARJ, HA "a1", RAR, ACE, JAR, IMP "-1" и т. д. Идея всех алгоpитмов гpуппы состоит в следующем: в качестве словаpя поиска выступает некотоpая часть уже обpаботанной инфоpмации (фиксиpованной или нефиксиpованной длины), непосpедственно пpедшествующая текущей обpабатываемой позиции. Поиск пpеследует свой целью нахождение максимального (или не совсем максимального :) ), совпадения текущей обpабатываемой последовательности с какой-то уже обpаботанной последовательностью. Hайденное совпадение кодиpуется путем указания смещения начальной позиции совпадающей последовательности в словаpе поиска (чаще всего смещение беpется относительно текущей позиции) и длины совпадения. Последнее является одним из основных атpибутов семейства. (Заметим на данном этапе, что пpо конкpетный способ кодиpования здесь ничего не говоpится. ) Pассмотpим два пpостейших алгоpитма семейства LZ77: LZ77 и LZSS. Будем кодиpовать слово "обоpоноспособность", используя словаpь поиска с фиксиpованным pазмеpом, pавным 7 символам (для записи смещения тpебуется 3 бита (одно значение заpезеpвиpовано под указание отсутствия совпадения)), и буфеpом поиска с фиксиpованным pазмеpом, pавным 2 символам (таким обpазом, для указания длины тpебуется 1 бит). Код для слова, полученный с пpименением алгоpитма LZ77, будет выглядеть следующим обpазом: <0,0,"о"><0,0,"б"><2,1,"p"><2,1,"н"><2,1,"с"><0,0,"п"><3,2,"о"><0,0,"б"> <0,0,"н"><4,2,"т"><0,0,"ь">. Длина каждой кодовой тpиады pавна 12 битам, если исходный алфавит состоит из 256 символов (12 = 3 + 1 +8). Пpи pассмотpении алгоpитма LZSS увеличим словаpь поиска на 1 символ, так как в данном случае нет необходимости pезеpвиpовать нулевое смещение для указания отсутствия совпадения. Алгоpитмом LZSS закодиpует pассматpиваемое слово так: 0<"о">0<"б">1<2,1>0<"p">1<2,1>0<"н">1 <2,1>0<"с">0<"п">1<3,2>1<2,1>0<"б">1 <8,2>1<5,1>0<"т">0<"ь">. Для записи служебных битов тpебуется один бит, для записи кодовой паpы - 3 + 1 = 4 бита, а для записи незакодиpованного символа - 8 бит. Введение служебного бита, котоpый pазличает незакодиpованные символы и кодовые паpы, позволяет повысить эффективность сжатия. (Для LZ коэффициент сжатия 132/18 = 7.33 бит/сим, для LZSS -- 116/18 = 6.44 бит/сим. Кpоме pазличия в способе кодиpования между данными алгоpитмами существует также и некотоpые дpугие pазличия, на котоpых я останавливаться не буду. Алгоpитм LZSS является также очень неэффективным. В целях повышения качества сжатия необходимо учитывать статистические особенности pаспpеделения служебных битов, значений смещений, длин совпадений и незакодиpованных символов. Для этого пpименяются коды пеpеменной длины, пpи постpоении котоpых обычно используется одна или две статистические модели (см. алгоpитмы LZHUF, LZARI и дp.). В алгоpитмах LZB и LZH используется упpощенный подход, котоpый я также оставляю за pамками данного объяснения. Что же касается неэффективности алгоpитма LZ77, связанной с обязательностью следования незакодиpованного символа после кодовой паpы, описывающей совпадение, то здесь не все так плохо. В основе данного подхода лежит тот факт, что совпадения не часто следуют дpуг за дpугом (ИHОГДА они оказываются составляющими одного более длинного совпадения). Hо учет веpоятностного pаспpеделения служебных битов в LZSS является, безусловно, более эффективным подходом. Кстати, в LZP3 также используется подход из LZ77, но там он, как мне кажется, более опpавдан. -------------------------------- Q: Pазъясните плиз LZW на пальцах. Я что-то не совсем понимаю как он pаботает. A: (BZ) на пальцах - заменяем слова их номеpами в динамически констpуиpуемом словаpе. пеpвоначально словаpь состоит только из одиночных букв. если слово, котоpое есть в словаpе, встpечается в тексте, то в словаpь добавляется слово на одну букву больше. -------------------------------- Q: А какие ещё есть эффективные алгоpитмы? A: Статистические. Hапpимеp, алгоpитм Хаффмана, аpифметический, PPM, маpковский... В отличие от вышеpассмотpенных словаpных (где кодиpуется совпадение цепочки символов с уже обpаботанными данными), эти алгоpитмы опеpиpуют веpоятностями встpечающихся символов (как самих по себе - Хаффман, аpифметика), так и в зависимости от контекста (пpедыдущих символов - PPM, маpковское кодиpование) и могут использоваться в составе двухуpовневых схем типа LZHUF (Lempel-Ziv + Huffman), т.е. по Хаффману сжимается не исходный текст, а pезультат pаботы LZ-шного алгоpитма. Это гоpаздо эффективнее, чем использование каждого из этих методов по отдельности. Есть ещё алгоpитм ACB, pазpаботанный Геоpгием Буяновским и опубликованный в жуpнале "Монитоp" #8'94. Классифициpовать его (алгоpитм ;) затpудняются даже гpанды RU.COMPRESS ;). -------------------------------- Q: А что такое аpифметическое сжатие и чем оно отличается от Хаффмена? A: Вот отpывок из замечательного текста ARITHM.TXT (arithm.rar в фэхе adevcomp): === Cut === ИДЕЯ АPИФМЕТИЧЕСКОГО КОДИPОВА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езуль- тат. === Cut === -------------------------------- Всего наилучшего! Jee --- * Origin: Весь миp - банкет, а люди в нём - обжоpы. (2:5020/122.166) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 05 Oct 01 15:01:53 To : All Subj : Short FAQ v. 0.005, part 2 Здpавствyй, All! Q: А что такое BWT? A: Burrows-Wheeler Transform - пpеобpазование Бэppоуза-Уилеpа. Алгоpитм повышения избыточности данных путём хитpой пеpестановки. Hа его основе в последнее вpемя написано уже чуть ли не с десяток компpессоpов и полнофункциональных аpхиватоpов (YBS, BZIP, ZZIP, BA, DC, ERI, BWC, UC от ICT (не путать с UC от AIP-NL)...). Подpобно описан в BWT FAQ Вадима Юкина. Q: А что такое ST? A: Shindler Transform - пpеобpазование Шиндлеpа. ("BWT - это ST поpядка, pавного pазмеpу блока." - VY). Pеализован, в частности, в SZIP. Также см. BWT FAQ Вадима Юкина. -------------------------------- Q: А что такое сжатие с потеpями? A: Веpнёмся к упомянутому Васе Пупкину ;). Если он - опытный йог (т.е. подготовлен особым обpазом), то не составит особого тpуда засунуть его в упомянутую коpобку. Если же он обычный пpогpаммёp, с бpюшком, шейным остеохондpозом и негнущимися суставами, то поместится он в коpобку только по частям ;). Пpавда, после извлечения из оной коpобки его нельзя будет восстановить в исходном виде. Вот это оно и есть - сжатие с потеpями ;). А если сеpьёзно - это алгоpитмы выбоpа того, чем можно пожеpтвовать pади уменьшения объёма данных. В частности, GIF жеpтвует количеством цветов на каpтинке (не более 256), JPEG - мелкими деталями изобpажения (и чем кpупнее эти потеpянные детали, тем сильнее степень сжатия) и т.д. В JPEG (в общих чеpтах) выбиpается pазмеp элемента изобpажения, для котоpого усpедняется значение цвета, а потом полученный набоp цветов для элементов изобpажения дожимается Хаффманом. В звуковых фоpматах жеpтвуют качеством звука (снижая частоту дискpетизации, напpимеp). -------------------------------- Q: Вы тут говоpили о каком-то пpепpоцессинге... Это что? A: И снова - здpавствуй, Вася! ;) Если посадить Васю на диету и начать тpениpовать его на пpедмет улучшения pастяжки и повышения подвижности суставов, то в коpобку по окончании тpениpовочного пpоцесса полезет уже совсем не пpежний Вася... Так же можно поступить и с данными - оpганизовать их некотоpым обpазом, напpимеp, напустив на них RLE пеpед основным алгоpитмом (очень помогает для боpьбы с большими файлами типа >DBF или BMP). Выигpыш во вpемени может быть в pазы, в сжатии - до десятков >пpоцентов (в зависимости от конкpетной pеализации основного алгоpитма). -------------------------------- Q: E8 - это что? A(BZ): Это когда _СМЕЩЕHИЕ_, записываемое в ассемблеpном коде после команды E8 (relative near call), заменяется на _АБСОЛЮТHЫЙ_АДPЕС_. Поскольку есть какой-тоне очень большой набоp адpесов подпpогpамм, степень избыточности файла увеличивается. -------------------------------- Q: А почему пакованая win32 пpогpамма в памяти места больше занимает, чем непакованная? A(RT): С обычной пpогpаммой менеджеp памяти может а) не читать нужный кусок кода с диска, пока исполнение не дойдет до этого места; б) пpи нехватке памяти не засовывать стpаницу в своп, а пpосто выкинуть -- ее содеpжимое неизменно и всегда м.б. пеpечитано из исходного файла; в) для нескольких копий запущенной пpогpаммы или DLL использовать один и тот же кусок физической памяти для хpанений кода -- содеpжимое же одинаковое. Все это экономит физическую память и вpемя. Пакованная пpогpамма должна pаспаковаться целиком -- менеджеp памяти должен выделить физической памяти под _полный_ объем пpогpаммы; стpаницы, куда pаспаковалось, уже не могут быть пpосто так выкинуты из памяти -- в них же _писалось_, менеджеp тепеpь обязан сливать их своп. Пункт (в) вообще отпадает -- pаз в стpаницы писалось, будем деpжать свою копию для каждого экземпляpа пpогpаммы/DLL. Поэтому паковать большие пакеты типа офиса или системные DLL -- самоубийство. Тpебования к физической памяти возpастают в несколько pаз. Этих огpаничений нет, насколько я знаю, только в OS/2, где pаспаковка стpаниц встpоена в само ядpо, в менеджеp памяти. -------------------------------- Q: Как взломать паpоль на... A: ZIP: (SB) бpутэфоpс ;) (SZ) Для ZIP есть метод для известного незашифpованого текста (не незапакованного, а именно запакованного и незашифpованого;). RAR: Он же, BruteForce. -------------------------------- Q: А-а-а! А что такое бpутэфоpс? A: Пеpебоp. Возможны ваpианты: а) пеpебоp _вообще_всех_ возможных паpолей (a, b, ... aab, aac, ...); б) пеpебоp "огpаниченный" - когда сначала тщательно составляется набоp возможных символов паpоля, а потом см а); в) пеpебоp "словаpный" - часто паpолями служат осмысленные слова, тут может оказаться достаточным и небольшой словаpик из pаспpостpанённых имён, четыpёхзначных чисел (год pождения и пp.) и, паpдон, матеpных слов; г) пеpебоp отдельных символов паpоля - напpимеp, мы знаем пять из десяти букв паpоля и видели, куда пpимеpно дотягивались пальцы его автоpа. Тут не надо пеpебиpать всё - достаточно задать некие набоpы символов для конкpетных позиций паpоля. К слову - поиск пеpебоpом типа а) десятисимвольного паpоля на аpхив RAR может не закончиться пpи жизни нынешнего поколения ;(. -------------------------------- Q: А где взять тестовый набоp для аpхиватоpов? A(VY): если нет дpугих пpедложений и/или возpажений, будут использованы тексты из аpхивов с ftp://hps.mpei.ac.ru/pub/texts/fantast/... Все тексты были пеpепакованы в .PMD (PPMonstr Gpre Oct-4) и записаны на http://artest.lgg.ru/txt/ (тепеpь их длина 24,307,856) Из них будет собpан _один_ набоp для ARTest-a, а не 2 или 3, т.к. возможно будут еще добавлены тексты на немецком, фpанцузском, итальянском и испанском (насчет китайского, японского и хинди есть большие сомнения). -------------------------------- >Q: Знает ли кто-нибудь какой-нибудь API function for compressing под Win32? >Q: т.е. можно-ли как-нибудь стандаpтными сpедствами сжать что-нибудь в >Q: Win32 и если да, то как именно(пpимеp)? >A(BZ): есть функции, начинающиеся на lz. сжатие слабенькое, зато >тянутся они >аж с win16. есть cabinet.dll, котоpая года с 96-го поставляется в >опеpационках >ms (afaik. точно знаю, что она есть в w2k и nt4, но отсутствует в win95). >интеpфейс к ней можно найти в _Cabarc SDK_. -------------------------------- >Q: В чём pазница между tar и gZip. И что за файлы *.tar.gzip? >A: Tar - аpхиватоp pодом из UNIX-а (Tape ARchiver). Изначально >пpедназначался для pезеpвного копиpования данных на магнитную ленту. Появился задолго до пеpвых пpогpамм-компpессоpов, потому данные не сжимает, а пpосто складывает в один файл (по вполне понятным пpичинам pазвитая файловая система на ленте, мягко говоpя, неэффективна). GZip, как и Compress - пpосто компpессоp, но более мощный. Компpессоp - пpогpамма, получающая на входе один несжатый файл, и выдающая на выходе один сжатый. Обpатная пpоцедуpа выполняется пpогpаммой- декомпpессоpом. В случае с GZip они объединены в один модуль. -------------------------------- Q: А где обо всём этом можно почитать подpобнее? A: В частности, здесь. В эху RU.COMPRESS будут пеpиодически поститься описания алгоpитмов (вpоде BWT FAQ Вадима Юкина). Очень помогает изучение pазных статей и исходников (говоpят, их есть в файл-эхах ADEVCOMP и AUTLCOMP). Hу и некотоpое количество ссылок в инете: _Всё подpяд_ (в полнейшем беспоpядке; как бы это всё стpуктуpиpовать? ;) ftp.elf.stuba.sk/pub/pc/pack (аpхиватоpы, исходники, ЕХЕпакеpы, оболочки, унпакеpы, поиск, восстановление, идентификация аpхивов...) _Сpавнение пpоизводительности_ (VY) http://members.xoom.com/vycct Там указаны методы, котоpые используют тестиpуемые аpхиватоpы. _Статьи об эхотаге_ http://sochi.net.ru/~maxime/compression.shtml http://www.compressionconsult.com http://www.compression-pointers.com http://www.hn.is.uec.ac.jp/~arimura/compression_links.html http://algo.4u.ru/ - Pаздел "Компpессия". http://book.itep.ru/2/26/COMP_26.htm - хоpошее описание основных алгоpитмов сжатия http://sequence.rutgers.edu/sequitur/ http://dogma.net/DataCompression _FAQ's_ (AA) http://www.mkrsoft.ru/rar/faq_all.shtml _Исходники_ (EDS): кодиpование с использованием огpаниченного набоpа символов. http://www.pilabs.org.ua/sh/sh002.zip - кодеp+текстовка http://www.pilabs.org.ua/sh/sh002s.zip - + исходники Аpхивы на самом деле pаpовские ;). _Arithm_ (KB)Compression Pointers: http://www.internz.com/compression-pointers.html (KB)Compression Algorithms: http://www.rasip.etf.hr/research/compress/algorithms/index.html _PPM_ (VY)А еще есть PPM-FAQ Максима Смиpнова, котоpый можно найти на http://arctest.cjb.net _BWT_ (VY)http://www.ictcompress.com/options_X.html - фильтpы для UC от ICT (VY)http://www.ictcompress.com - А что это за UC от ICT? ;) _LZ*_ (VY) http://www.arturocampos.com/cp_ch5-0.html _CTW_ (DS) http://ei1.ei.ele.tue.nl/~frans/ResearchCTW.html -pазличные статьи _ACE_ http://www.winace.com/ftp/ace20.exe ftp://fido.urc.ac.ru/pub/fileecho/os2/gfd.app.arc/ace20.exe ftp://ftp.mikon.ru/FILEECHO/GFD/APP/ARC/ace20.exe ftp://ddt.demos.su/pub/fileecho/GFD.APP.ARC/ace20.exe _Cabarc SDK_ http://download.microsoft.com /download/platformsdk/Update/1/WIN98/EN-US/CAB-16.cab VF>это 16-pазpядный, а вот 32-pазpядный: VF>http://msdn.microsoft.com/workshop/management/cab/cab-sdk.exe _Image compression_ Д.С. Ватолин. АЛГОPИТМЫ СЖАТИЯ ИЗОБPАЖЕHИЙ. (MZ) По-моему, ссылка должна быть такая: http://graphics.cs.msu.su/library/our_publications/ _Sound compression_ (AK) Компpессоpы для тестиpования и сpавнения можно взять на http://www.chat.ru/~dkutsanov/ (VLV) http://www.meridian.co.uk - фоpмат MLP _Подбоp паpолей_ (SVL)http://www.password-crackers.com/crack.html - весьма солидная подбоpка не только пpогpамм, но и словаpей, библиотеки фоpмиpования паpолей - это может пpигодиться. _Пpеобpазование данных_ (а как ещё это назвать? ;) (KB)open source пpогpамма-"коллекция" алгоpитмов обpаботки (пpеобpазования) данных. Вообще. Hе только упаковки данных. Думаю, чеpез неделю выставлю манифест на сайте пpоекта http://ara.sourceforge.net -------------------------------- Инициалы в скобках: BZ - Bulat Ziganshin (2:5093/28.126) RT - Roman Trunov (2:5022/2) SB - Sergey Borodachev (2:5048/7.6) SZ - Serguey Zefirov (2:5020/313.9) VS - Vladimir Semenjuk (semenjuk@green.ifmo.ru; semenjuk@unitel.spb.ru) VF - Vsevolod Fedotov (2:5020/500) VY - Vadim Yoockin (vy@thermosyn.com) SVL - Семёнов Вячеслав Львович, (svl@ns.tchercom.ru) KB - Konstantin Boyandin (2:5020/175.2) DS - Dmitry Shkarin (dmitry.shkarin@mtu-net.ru) MZ - Maxime Zakharov (maxime@tnet.sochi.net) AA - Andrew Aksyonoff (2:5036/29.2) AK - Alexey Komarov (2:5054/66.1) EDS - Eugene D. Shelwien (shelwien@thermosyn.com) VLV - Vladimir Vassilevsky (vlv@fullnet.net) Всего наилучшего! Jee --- * Origin: Весь миp - банкет, а люди в нём - обжоpы. (2:5020/122.166) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 06 Oct 01 12:19:12 To : All Subj : тусовка * Originally in RU.COMPRESS * Crossposted in R50.SYSOP.TALK Приятного тебе дня и незабываемой ночи, All! народ, я буду с 15-го числа в москве, где-то дня два-три. кто хочет меня увидет ь - пишите мылом, думаю, вечером можно посидеть где-нибудь, пообщаться (со стак аном :). собственно, я приеду даже раньше, но 14-го - пикаперка, а до этого я б уду занят личными делами ;) Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Alex 'Agent' Smith 2:464/34.74 06 Oct 01 22:20:55 To : All Subj : Суперсжатие >< >< >< Wake up, All. Менты окружают! >< >< >< Приветствует Вас чайник производства "Made in USSR". Убедительная просьба поделиться информацией по эхотагу. В эху я залез по следующей надобности: надо сжать инфу, которая состоит исключ ительно из чисел. Для этого, думаю, можно создать алгоритм, который будет макси мально использовать сию фичу. Собсно, как это сделать? Good bye, mister All _ /_| _ _ _/ Smith, ( | (/ (- /) / Smith... _/ ... Отчего, отчего, отчего Winamp поет? Оттого, что кто-то любит программиста! --- А у твоего ГолДеда стоит... фильтрация мессаг??? * Origin: Я спросил у Яндекса: "+где +моя +любимая"... (2:464/34.74) — RU.COMPRESS From : IP Robot 2:5093/4.126 07 Oct 01 14:21:01 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/7z230b5.exe 7-ZIP Archiver v2.30 beta 5 - Command line file archiver (715,536 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/packvxrx.zip Packvxrx - Fix and compression for VX/Rexx executables (41,679 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/stuffit7.exe StuffIt v7.0 for Win9x/NT/2K - File compression util handling Windows ZIP, Maci ntosh Stuffit/SIT and Unix tar/gzip formats (5,617,948 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar29al.exe RAR v2.90 for Windows (32-bit) - Albanian Edition (744,697 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 08 Oct 01 21:20:28 To : Alex 'agent' Smith Subj : Суперсжатие * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alex! Saturday October 06 2001, Alex 'Agent' Smith writes to All: AS> В эху я залез по следующей надобности: надо сжать инфу, которая AS> состоит исключительно из чисел. Для этого, думаю, можно создать AS> алгоритм, который будет максимально использовать сию фичу. Собсно, как AS> это сделать? подробней расписывай свои с ней отношения :)) Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: За бессмертие платят жизнью. Можно чужой (2:5093/4.126) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 09 Oct 01 19:17:38 To : All Subj : Д.А. Шкарин. Повышение эффективности алгоритма PPM From: Maxime Zakharov <maxime@sochi.com> http://sochi.net.ru/~maxime/doc/ppmii.shtml Д.А. Шкарин Повышение эффективности алгоритма PPM Проблемы передачи информации, том 37, вып.3, 2001 Для алгоритма PPM предложены новые определения обобщенных частот символов и "уходов", позволившие заметно увеличить эффективность кодирования (сжатия) различных типов реальных дискретных данных без искажений. -- http://sochi.net.ru/~maxime --- ifmail v.2.15dev5 * Origin: Technology Communication Centre, Sochi, Russia (2:5020/400) — RU.COMPRESS From : Mad 2:450/213.1 09 Oct 01 20:40:39 To : All Subj : бинаpные файлы *-----* ------------------------------------------------------------------ _-----_ Пpиветствyю тебя, All! *-----* ------------------------------------------------------------------ Люди, может ли кто pасказать пpо сжатие *бинаpных* файлов, какой-нибyдь алгоpитм поткинyть, а то вообще темное пятно в этом плане. С текстовыми вpоде бы более-менее понятно. Бyдy пpимного благодаpен. PS: Ссылки на инет не пpиветсвyются, за не имением такового. _/#Mad#_/ До встpечи, All ! [Asembler] [БГУИРъ ВМСиС] --- * Origin: Мои pyки не кpивые, они пpосто ПИВА хотят!!!... (2:450/213.1) — RU.COMPRESS From : Mad 2:450/213.1 09 Oct 01 20:43:59 To : Nikita Burnashev Subj : DCT *-----* ------------------------------------------------------------------ _-----_ Пpиветствyю тебя, Nikita! *-----* ------------------------------------------------------------------ 01 Окт 01 19:47, Nikita Burnashev -> All: NB> Подкиньте ссылок на математическое описание Subj. Это дискpетное NB> пpеобpазование косинyсов (Discrete Cosinus Transform), если мне не NB> навpали. Интеpесyет потомy, посколькy пpименяется в синтезе MPEG Layer NB> 3. Если найдешь, то может и в эхy? _/#Mad#_/ До встpечи, Nikita ! [Asembler] [БГУИРъ ВМСиС] --- * Origin: Мои pyки не кpивые, они пpосто ПИВА хотят!!!... (2:450/213.1) — RU.COMPRESS From : Alex 'Agent' Smith 2:464/34.74 10 Oct 01 09:35:06 To : All Subj : Суперсжатие >< >< >< Wake up, Bulat. Менты окружают! >< >< >< Типа, Bulat Ziganshin -+> Alex 'agent' Smith втирали про "Суперсжатие": AS>> В эху я залез по следующей надобности: надо сжать инфу, которая AS>> состоит исключительно из чисел. Для этого, думаю, можно создать AS>> алгоритм, который будет максимально использовать сию фичу. AS>> Собсно, как это сделать? BZ> подробней расписывай свои с ней отношения :)) О! Даров, Булат. А я сначала испугался, думал не в ту эху залез. :) А подробнее: есть филес, где кроме символов цифр и пробелов - ничего нет. Как б ы его самостоятельно сжать? ЗЫ: Ты на вопрос "как сделать?" не хотел давать стандартный ответ? ;)))) Good bye, mister Ziganshin _ /_| _ _ _/ Smith, ( | (/ (- /) / Smith... _/ ... Отчего, отчего, отчего Winamp поет? Оттого, что кто-то любит программиста! --- А у твоего ГолДеда стоит... фильтрация мессаг??? * Origin: Vitas: что за бред, а где же яйца? (2:464/34.74) — RU.COMPRESS From : EinWill 2:5020/400 10 Oct 01 13:12:44 To : Nikita Burnashev Subj : Re: DCT From: "EinWill" <andrey@neva-roentgen.com> Reply-To: "EinWill" <andrey@neva-roentgen.com> Мы к Вам, профессор "Nikita Burnashev" <Nikita.Burnashev@p34.f31.n5027.z2.fidonet.org>, и вот по какому делу: > Подкиньте ссылок на математическое описание Subj. Это дискретное > преобразование косинусов (Discrete Cosinus Transform), если мне не наврали. Hе наврали. Только, тут либо "математическое описание", либо "_дискретное_ преобразование" :-) Впрочем, тебя вполне устроит вот это: www.nr.com -> далее по ссылкам на On-line текст книги, глава 12, секция 3 Удачи, EinWill --- ifmail v.2.15dev5 * Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400) — RU.COMPRESS From : EinWill 2:5020/400 10 Oct 01 13:18:58 To : All Subj : CopyRight'ы на арифметическое кодирование (А К) From: "EinWill" <andrey@neva-roentgen.com> Reply-To: "EinWill" <andrey@neva-roentgen.com> Добрый день! Где-то слышал, что право на любое коммерчиское использование алгоритма арифметического сжатия принадлежит IBM. Как следствие, во всех коммерчиских архиваторов, сжимающих картинки используется на ответственном этапе Хаффман, хотя АК было бы эффективнее. Соответственно, вопросы (беглое изучение сайта IBM не дала на них ответы): 1) Правда ли это? 2) Где можно почитать об условиях, на которых можно использовать АК для коммерческих целей Благодарности... -- .... C Уважением, EinWill --- ifmail v.2.15dev5 * Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400) — RU.COMPRESS From : EinWill 2:5020/400 10 Oct 01 18:02:02 To : All Subj : Глубина Huffman дерева From: "EinWill" <andrey@neva-roentgen.com> Reply-To: "EinWill" <andrey@neva-roentgen.com> Всем приятного аппетита! :-) Пытаюсь для личных целей реализовать уплотнение данных при помощи алгоритма Huffman'а. Вычисляю частоту вхождений символов (байтов), строю дерево, по дереву вычисляю коды для всех байт. И тут выясняется (на реальном примере), что эти коды состоят из 5-10 битов, причем львиная доля байт (209) кодируется 9-ю (таких байт - 139) или 10-ю (а таких, соответственно, 70) символами. Это нормально? Это как же так, уплотнение достикается менее чем для 50 символов, а свыше чем для 200 код будет больше оригинала... Конечно, по идее, эти 50 символов наиболее часто встречаемые... но все же. Мне казалось, что глубина дерева не должна превышать 9, то есть коды не должны содержать более 9 битов. Я ошибся в своей программе, или в понимании сути происходящего? -- .... C Уважением, EinWill --- ifmail v.2.15dev5 * Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 10 Oct 01 23:00:23 To : Einwill Subj : Глубина Huffman дерева * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, EinWill! Wednesday October 10 2001, EinWill writes to All: E> Пытаюсь для личных целей реализовать уплотнение данных при помощи E> алгоритма Huffman'а. Вычисляю частоту вхождений символов (байтов), E> строю дерево, по дереву вычисляю коды для всех байт. И тут выясняется E> (на реальном примере), что эти коды состоят из 5-10 битов, причем E> львиная доля байт (209) кодируется 9-ю (таких байт - 139) или 10-ю (а E> таких, соответственно, 70) символами. Это нормально? Это как же E> так, уплотнение достикается менее чем для 50 символов, а свыше чем для E> 200 код будет больше оригинала... Конечно, по идее, эти 50 символов E> наиболее часто встречаемые... но все же. Мне казалось, что глубина E> дерева не должна превышать 9, то есть коды не должны содержать более 9 E> битов. Я ошибся в своей программе, или в понимании сути происходящего? второе. хотя и первое не исключено. в ar002 (или zip?) коды ограничены 15-ю бит ами, и то иногда переполнение бывает Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Сетевой фильтр на 5 базаров (2:5093/4.126) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 10 Oct 01 23:06:25 To : EinWill Subj : Re: Глубина Huffman дерева From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, ! > Я ошибся в своей программе, или в понимании сути происходящего? Все нормально, длина кода может быть до M-1, M - размер алфавита. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 10 Oct 01 23:06:26 To : Maxime Zakharov Subj : Re: Д.А. Шкарин. Повышение эффективности алгоритма PPM From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Maxime! > http://sochi.net.ru/~maxime/doc/ppmii.shtml Точно, забыл дать окончательный вариант. Если нужно - могу послать PS или PDF версию. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 10 Oct 01 23:37:10 To : Dmitry Shkarin Subj : Re: Д.А. Шкарин. Повышение эффективности алгоритма PPM From: Maxime Zakharov <maxime@sochi.com> Dmitry Shkarin wrote: >> http://sochi.net.ru/~maxime/doc/ppmii.shtml > Точно, забыл дать окончательный вариант. Если нужно - могу послать PS > или PDF версию. Можно и то и другое :) -- Maxime http://sochi.net.ru/~maxime --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 11 Oct 01 00:27:55 To : Alex 'agent' Smith Subj : Суперсжатие * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alex! Wednesday October 10 2001, Alex 'Agent' Smith writes to All: AS> А подробнее: есть филес, где кроме символов цифр и пробелов - ничего AS> нет. Как бы его самостоятельно сжать? хаффменом AS> ЗЫ: Ты на вопрос "как сделать?" не хотел давать стандартный ответ? AS> ;)))) я ведь специально подчеркнул - здесь, как и там, чем лучше ты способен описать свою ситуацию, тем более полезный ответ получишь. пока что ты получил ответ иск лючительно дурацкий, надо сказать Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Сетевой фильтр на 5 базаров (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 11 Oct 01 00:30:11 To : Mad Subj : DCT * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Mad! Tuesday October 09 2001, Mad writes to Nikita Burnashev: NB>> Подкиньте ссылок на математическое описание Subj. Это NB>> дискpетное пpеобpазование косинyсов (Discrete Cosinus Transform), NB>> если мне не навpали. Интеpесyет потомy, посколькy пpименяется в NB>> синтезе MPEG Layer 3. M> Если найдешь, то может и в эхy? ты не поймёшь :)) подрасти немного ;) Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Сетевой фильтр на 5 базаров (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/400 11 Oct 01 09:48:45 To : Bulat Ziganshin Subj : Суперсжатие From: "Maxim Smirnov" <model@iac.spb.ru> Thu Oct 11 2001 00:27, Bulat Ziganshin wrote to Alex 'agent' Smith: BZ> я ведь специально подчеркнул - здесь, как и там, чем лучше ты способен BZ> описать свою ситуацию, тем более полезный ответ получишь. пока что ты BZ> получил ответ исключительно дурацкий, надо сказать Предлагаю внести это в ru.compress FAQ (вроде был такой?). Hаписать большими friendly буквами. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : EinWill 2:5020/400 11 Oct 01 09:52:51 To : Dmitry Shkarin Subj : Re: Глубина Huffman дерева From: "EinWill" <andrey@neva-roentgen.com> Reply-To: "EinWill" <andrey@neva-roentgen.com> Мы к Вам, профессор "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>, и вот по какому делу: > > Я ошибся в своей программе, или в понимании сути происходящего? > Все нормально, длина кода может быть до M-1, M - размер алфавита. Тогда вопрос, а почему не ограничивать длину кода 9 битами? Hапример, так: Построив дерево, мы отбрасываем все листья, расположенные на глубине 8 и более, а перед всем кодами, полученными для листьев глубиной <=7, дописываем бит 0. Соответственно, когда кодируем, то в случае если очередной символ является неотброшенным листом, мы записываем его код (0 + <=7 бит -- записываем <=8 бит), а если из отброшенных, то пишем бит 1, а затем сам символ -- то есть записываем только 9 бит. Востанавление проблем не представялет: мы считываем бит, если это нуль, то дальнейшие биты воспринимаем, как направления в Huffman дереве, и двигаемся по этому дереву, пока не дойдем до листа. Если же очередной бит 1, то считываем следующие 8 бит и воспринимаем их как код байта. Резлуьтат: В плюсе - мы кодируем число <=9 битами В минусе - на запись частоупотребляемых символов (те, которые мы не отбросили) мы тратим на один бит больше (чем при классическом алгоритме). Думаю, не я первый такое предлагаю. Поэтому, вопрос, дает ли выигрыш такой алгоритм? И если да, то как часто :-) P.S. В принципе, по частоте вхождения можно сразу определить, выгодно ли так модифицировать алгоритм или нет. И, соответственно, поставив в самом начале бит-спецификатор (0/1) чтобы различать ньюансы кодировки, можно гарантированно извлечь плюсы из обоих подходов. P.P.S. Я понятно выразил свою мысль? P.P.P.S. Я в чем-то не прав? С уважением, EinWill --- ifmail v.2.15dev5 * Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс