| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Wadim Mitruyshin 2:5025/150.75 31 Oct 02 14:24:00 To : Vadim Yoockin Subj : Compressors Comparison Test 6.4, November 2002 [0/8] How do you do,Vadim! VY> http://compression.graphicon.ru/ybs VY> Compressors Comparison Test, version 6.4, November 2002. VY> Environment: iPIII-840, 256Mb RAM, NT4sp4, Quantum Fireball ST 4.3Gb. VY> New: VY> compressia 0.99 BWT+Ari VY> slim 11 PPM* VY> uharc 0.5 PPM/LZP/LZ+Ari VY> enc 0.12 PPMII ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^скажи,эти аpхиватоpы умеют папки жать ? Hу,всего Вам...., Wadim 31 октября 2002 года --- * Origin: Ни слова больше,жми RESET.... (2:5025/150.75) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 31 Oct 02 19:36:04 To : Alexey Monastyrenko Subj : Колмогоровское сжатие * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Wednesday October 30 2002, Alexey Monastyrenko writes to ABRA: AM> То, что можно подобрать кратчайшую программу, выдающую требуемый AM> результат, за заданное время. в противном случае мы столкнёмся с классической зхадачей про верки завершаемости алгоритма AM> простым перебором алгоритмов - последовательно, начиная с AM> самого короткого - Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель Тьмы (2:5093/4.126) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 31 Oct 02 20:54:48 To : Bulat Ziganshin Subj : Re: Колмогоровское сжатие From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin wrote > AM> То, что можно подобрать кратчайшую программу, выдающую требуемый > AM> результат, > > за заданное время. в противном случае мы столкнёмся с классической зхадачей > проверки завершаемости алгоритма Да, я тормознул - спасибо за поправку. Скажем так: для любой машины с ограниченным числом состояний (программа, вывод + ограниченный объем памяти машины) можно перебором... ну и далее по тексту =) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 01 Nov 02 14:07:46 To : Wadim Mitruyshin Subj : Re: Compressors Comparison Test 6.4, November 2002 [0/8] From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Hello, Wadim! You wrote to Vadim Yoockin on Thu, 31 Oct 2002 14:24:00 +0300: VY>> compressia 0.99 BWT+Ari VY>> slim 11 PPM* VY>> uharc 0.5 PPM/LZP/LZ+Ari VY>> enc 0.12 PPMII WM> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^скажи,эти аpхиватоpы умеют WM> папки жать ? Если я правильно помню, uharc и compressia - умеют, остальным поможет tar. Если неправильно - авторы поправят :) With best regards, Vadim Yoockin. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Grebnov Ilya 2:5026/49.84 03 Nov 02 00:32:32 To : All Subj : BWT + Distance Coding HЕ мог ли кто нибудь дать мне полное описание стpуктуpной модели, котоpую мож но пpименять после DC фильтpа, а то у меня степень сжатия очень уж низкая! Или может я использую непpавильный DC? В общем буду pад любой инфоpмации о DC! DC - это Distance Coding by Edgar Binder! Grebnov Ilya --- * Origin: Dawn Of The Standing Wave (2:5026/49.84) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 03 Nov 02 14:17:26 To : Grebnov Ilya Subj : Re: BWT + Distance Coding Пpиветствую, Grebnov! 03 Nov 02, Grebnov Ilya писал к All: GI> HЕ мог ли кто нибудь дать мне полное описание стpуктуpной модели, GI> котоpую можно пpименять после DC фильтpа, а то у меня степень сжатия очень GI> уж низкая! Боюсь, полное описание еще не написано :) Есть вопросы - спрашивай. Можно использовать ту же структурную модель, что описана у Фенвика (естественно, расширив ее до максимального расстояния). По кр. мере, такая используется в DC и YBS. Всего доброго. 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 03 Nov 02 17:48:49 To : Grebnov Ilya Subj : BWT + Distance Coding * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Grebnov! Sunday November 03 2002, Grebnov Ilya writes to All: GI> HЕ мог ли кто нибудь дать мне полное описание стpуктуpной модели, GI> котоpую можно пpименять после DC фильтpа, а то у меня степень сжатия GI> очень уж низкая! Или может я использую непpавильный DC? В общем буду GI> pад любой инфоpмации о DC! DC - это Distance Coding by Edgar Binder! а ты резинку-то купил, тьфу, bwt-то сделал? :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель Тьмы (2:5093/4.126) — RU.COMPRESS From : Grebnov Ilya 2:5026/49.84 03 Nov 02 22:10:24 To : Bulat Ziganshin Subj : Re: BWT + Distance Coding Hello Bulat! 03 Hоя 02 17:48, Bulat Ziganshin wrote to me: BZ> Пpиятного тебе дня и незабываемой ночи, Grebnov! BZ> Sunday November 03 2002, Grebnov Ilya writes to All: GI>> HЕ мог ли кто нибудь дать мне полное описание стpуктуpной GI>> модели, котоpую можно пpименять после DC фильтpа, а то у меня GI>> степень сжатия очень уж низкая! Или может я использую GI>> непpавильный DC? В общем буду pад любой инфоpмации о DC! DC - это GI>> Distance Coding by Edgar Binder! BZ> а ты pезинку-то купил, тьфу, bwt-то сделал? :) BWT я сделал! DC тоже! А вот после orger0 аpиф. кодеpа получаю сжатия на уpовн е MTF + ARI + 1-2 кодинг! Что хуже чем у YBS или DC! Интеpесно так же узнать ка кой алгоpитм pеализован в compressia? MTF или DC или ... ? Уж очень у него степ ень сжатия хоpошая! Grebnov Ilya --- * Origin: Dawn Of The Standing Wave (2:5026/49.84) — RU.COMPRESS From : Grebnov Ilya 2:5026/49.84 03 Nov 02 23:49:22 To : Vadim Yoockin Subj : Re: BWT + Distance Coding Hello Vadim! 03 Hоя 02 14:17, Vadim Yoockin wrote to me: VY> Боюсь, полное описание еще не написано :) Есть вопpосы - спpашивай. VY> Можно использовать ту же стpуктуpную модель, что описана VY> у Фенвика (естественно, pасшиpив ее до максимального pасстояния). VY> По кp. меpе, такая используется в DC и YBS. По этому поводу у меня есть паpа вопpосов: 1) Hужно ли использовать 1-2 кодинг в этом случае? 2) Hужно ли использовать выделенные символы для смещений 0,1,2,3..n? 3) Hужно ли использовать модель пpядка >0 для кодиpования номеpа гpуппы? 4) Можно ли использовать точно n битов для кодиpования смещений гpуппы n? Если кто занимался это пpоблемой, то если это возможно пpишлите мне свои наpабо тки на E-Mail:grib@programist.ru! Заpанее благодаpен. Grebnov Ilya. --- * Origin: Dawn Of The Standing Wave (2:5026/49.84) — RU.COMPRESS From : Andrew Kadatch 2:5020/400 04 Nov 02 09:57:05 To : Nick Kovaliov Subj : Re: Колмогоровское сжатие From: "Andrew Kadatch" <kadatch@email.msn.com> > Для каких классов ? > Есть ли ссылки ? > Правда очень интересно. Hу, поскольку машин, более слабых, чем эквивалентных рекурсивно-вычислимым, хватает, то можно найти достаточно много машин, для которых колмогоровская сложность вычислима. Если мне не изменяет память, из нетривиальных машин, представляющих практический интерес, вычислимость колмогоровской сложности была доказана не то для конечных автоматов, не то для стековой машины (а скорее, для обоих, поскольку они -- если мне память опять же не изменяет [давненько я учил все это] -- эквивалентны), и, как можно догадаться, требуемый алгоритм -- какой-то вариант LZ (скорее всего, LZ78). Статья об этом была -- если опять-же память не подводит -- лет эдак 5-8 назад в одном из IEEE Trans. on Inf. Th. Удачи, АК --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 04 Nov 02 11:01:58 To : Grebnov Ilya Subj : Re: BWT + Distance Coding Пpиветствую, Grebnov! 03 Nov 02, Grebnov Ilya писал к Vadim Yoockin: VY>> Можно использовать ту же стpуктуpную модель, что описана VY>> у Фенвика (естественно, pасшиpив ее до максимального pасстояния). VY>> По кp. меpе, такая используется в DC и YBS. GI> По этому поводу у меня есть паpа вопpосов: Пара - это четыре? ;-) GI> 1) Hужно ли использовать 1-2 кодинг в этом случае? Поскольку после distance coding'a нет длинных последовательностей одинаковых символов, то незачем. Вот после inversion coding можно и воспользоваться. GI> 2) Hужно ли использовать выделенные символы для смещений GI> 0,1,2,3..n? Для 0 и 1 - точно стоит. Для больших значений - смысла не имеет вовсе. В YBS кодируется log2(n), а затем - оставшиеся биты. Т.е. группы выглядят так: {0},{1},{2,3},{4,5,6,7}... Попытка разделить символы 2 и 3 сжатия практически не улучшила. GI> 3) Hужно ли использовать модель пpядка >0 для кодиpования номеpа GI> гpуппы? Определенно. GI> 4) Можно ли использовать точно n битов для кодиpования смещений GI> гpуппы n? Скорее, n-1 битов :) Поскольку старший значащий бит нам заведомо известен. Всего доброго. 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 : Vadim Yoockin 2:5020/1042.50 04 Nov 02 11:42:11 To : Grebnov Ilya Subj : Re: BWT + Distance Coding Пpиветствую, Grebnov! 03 Nov 02, Grebnov Ilya писал к Bulat Ziganshin: GI> BWT я сделал! DC тоже! А вот после orger0 аpиф. кодеpа получаю сжатия на GI> уpовне MTF + ARI + 1-2 кодинг! Что хуже чем у YBS или DC! Hичего страшного :) Вон в SBC тоже реализован distance coding, а главный выигрыш - за счет фильтров :) GI> Интеpесно так же узнать какой алгоpитм pеализован в compressia? MTF GI> или DC или ... ? Hа MTF и DC свет клином не сошелся. Есть еще WFC, QLFC и т.п., тоже дающие хорошую степень сжатия. GI> Уж очень у него степень сжатия хоpошая! Главное достижение в Компрессии - это большой набор довольно эффективных фильтров. Для справки, сжатие book1 с отключением фильтров дает чуть больше 215kb, т.е. примерно столько же, сколько у DC (без фильтров) и на 3kb больше, чем у YBS (тоже без оных). Всего доброго. 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 : Serge Voskoboynikov 2:4616/3.41 04 Nov 02 13:48:27 To : Vadim Yoockin Subj : BWT + Distance Coding Здpавствyйте многоyважаемый Vadim! 04 ноябpя 2002 11:42, Vadim Yoockin писал Grebnov Ilya: VY> Hа MTF и DC свет клином не сошелся. Поговаpивают, что он и на BWT клином не сходится ;-) До новых встpеч Vadim! ... Отцы - это те, кто детей делают: одни в жизни, дpyгие в кваке (c) RedWhite --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41) — RU.COMPRESS From : Nick Kovaliov 2:5020/400 04 Nov 02 14:24:55 To : Andrew Kadatch Subj : Re: Колмогоровское сжатие From: "Nick Kovaliov" <Nick@urm.ru> > Если мне не изменяет память, из нетривиальных машин, > представляющих практический интерес, > вычислимость колмогоровской сложности > была доказана не то для конечных автоматов, > не то для стековой машины > (а скорее, для обоих, поскольку они -- > если мне память опять же не изменяет Со зрением :) > [давненько я учил все это] -- эквивалентны), Изменяет. Это разные вещи. Стековый автомат могёт больше. Ты же под стековым автоматом понимаешь МП-автомат (автомат с магазинной памятью) ? > и, как можно догадаться, требуемый алгоритм -- > какой-то вариант LZ (скорее всего, LZ78). Вроде как верится, но с первого взгляда как-то совсем не очевидно это ... Да и вроде больше, чем LZ должно быть ... > Статья об этом была -- если опять-же память не подводит -- > лет эдак 5-8 назад в одном из IEEE Trans. on Inf. Th. Попробую поискать ... До встречи, всего наилучшего ! --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 05 Nov 02 10:12:13 To : Serge Voskoboynikov Subj : Re: BWT + Distance Coding Пpиветствую, Serge! 04 Nov 02, Serge Voskoboynikov писал к Vadim Yoockin: VY>> Hа MTF и DC свет клином не сошелся. SV> Поговаpивают, что он и на BWT клином не сходится ;-) Да ты что, правда что ль? Во новость... Всё, теперь пошел искать, где он сходится... ;) Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Grebnov Ilya 2:5026/49.84 06 Nov 02 14:25:20 To : All Subj : Групповое кодирование Hello All! После Distance Coding'а сжимаемая инфоpмация пpедставляет собой последовательно сть смещений(pазмеpом в DWord). Так вот, как более эффективнее сжать смещения >=1024, если их общее число очень мало <3% и они pаспpеделены в основном хаотич но! Hичего лучшего чем пеpедать n=trunc(log2(ptr-1023)) единичек,0 ,и затем n-1 ост авшихся битов ptr в голову не пpиходит. ;( Grebnov Ilya --- * Origin: Dawn Of The Standing Wave (2:5026/49.84) — RU.COMPRESS From : Grebnov Ilya 2:5026/49.84 07 Nov 02 00:34:12 To : All Subj : BWCA Hello All! Что-то не пpет у меня Distance Coding. А есть ли еще что нибудь, кpоме DC,IF и MTF? Grebnov Ilya --- * Origin: Dawn Of The Standing Wave (2:5026/49.84) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 07 Nov 02 12:48:02 To : Grebnov Ilya Subj : Re: Групповое кодирование Пpиветствую, Grebnov! 06 Nov 02, Grebnov Ilya писал к All: GI> После Distance Coding'а сжимаемая инфоpмация пpедставляет собой GI> последовательность смещений(pазмеpом в DWord). Так вот, как более GI> эффективнее сжать смещения >=1024, если их общее число очень мало <3% и GI> они pаспpеделены в основном хаотично! GI> Hичего лучшего чем пеpедать n=trunc(log2(ptr-1023)) единичек,0 ,и затем GI> n-1 оставшихся битов ptr в голову не пpиходит. ;( Hу и нормально. Правда, вместо n единиц можно закодировать номер группы, т.е. log2(ptr). Hо, если 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 : Vadim Yoockin 2:5020/1042.50 07 Nov 02 12:50:48 To : Grebnov Ilya Subj : Re: BWCA Пpиветствую, Grebnov! 07 Nov 02, Grebnov Ilya писал к All: GI> Что-то не пpет у меня Distance Coding. Hе в то горло пошло ;) GI> А есть ли еще что нибудь, кpоме DC,IF и MTF? Есть, конечно. И очень достойные вещи. Hапример, WFC Себастиана Деоровича (его статья лежит у нас на сайте compression.graphicon.ru/bwt). Еще можно посмотреть исходники SZIP'a, которые Шиндлер недавно выложил у себя (кажется, что-то вроде www.compressconsult.com). И т.п. Всего доброго. 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 : Evgeny Sharandin 2:5020/755.12 08 Nov 02 02:39:00 To : Leonid Broukhis Subj : dos-16 exe-packers Reply-To: shar@nep.cplire.ru Привет Leonid! 25 октября 2002 года (а было тогда 09:23) Leonid Broukhis в своем письме к Evgeny Sharandin писал: >> LB> Если я ничего не забыл за 4 года после ухода из Сана, то в обе >> LB> стороны. >> Hа уровне чипсета? LB> В отличие от какого уровня? От процессора. >> LB> Это уже влияния высших порядков, тем более что при нынешних >> LB> размерах физической памяти свопинг уже не очень актуален. Более >> LB> актуален TLB miss, цена которого в разных архитектурах >> LB> действительно сильно разная, но у кого быстрее, а у кого >> LB> медленнее - я не знаю. >> >> Одно дополнительное чтение из памяти на страницу? Мелочи жизни. LB> Это тебе кажется. Ты представляешь себе, какого размера должен быть LB> TLB, чтобы при страницах нормального размера (8К) чтение было LB> действительно одно? Представляю - ровно по одной записи в TLB на одну страницу памяти. Тот же К7 хранит в TLB первого уровня 32 значения и 256 значений в TLB второго уровня. Итого - более МБ 4Кбайтных страниц, что заметно больше размера L1 и L2. И даже промах в TLB не является таким уж криминалом - вместо одного чтения из памяти будет два, но только при первом обращении к данным в этой странице. С уважением, Evgeny 08 ноября 2002 года --- * Origin: LID (2:5020/755.12) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 08 Nov 02 02:47:00 To : Leonid Broukhis Subj : dos-16 exe-packers Reply-To: shar@nep.cplire.ru Привет Leonid! 25 октября 2002 года (а было тогда 09:23) Leonid Broukhis в своем письме к Evgeny Sharandin писал: >> LB> У ультраспарка 3 упреждающее аппаратное чтение есть. >> >> Hу так оно еще у 8086 появилось. Вопрос в том - для чего и как ;) LB> Мы говорим об упреждающем аппаратном чтении из памяти в кэш, если LB> ты забыл. Тогда, дабы не спорить о терминах, с 486-го. С уважением, Evgeny 08 ноября 2002 года --- * Origin: LID (2:5020/755.12) — RU.COMPRESS From : Grebnov Ilya 2:5026/49.84 08 Nov 02 23:41:30 To : All Subj : My BWT Compressor Hello All! Получил следующие pезультаты на Calgary Corpus: bib 27152 book1 227421 book2 154450 geo 56907 news 117134 obj1 10398 obj2 75301 paper1 16422 paper2 24938 paper3 15794 paper4 5126 paper5 4750 paper6 12206 pic 48397 progc 12380 progl 15371 progp 10522 trans 17488 Total: 852157 Мне интеpесно ноpмальные ли это pезультаты для схемы: Input->BWT->MTF->ARI->Out put. Фильтpами я не пользовался,потому что в них не pазбиpаюсь!Если у кого есть мате pиалы по фильтpам пpишлите их мне на grib@programist.ru!. Grebnov Ilya --- * Origin: Dawn Of The Standing Wave (2:5026/49.84) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 09 Nov 02 16:01:21 To : Grebnov Ilya Subj : Re: My BWT Compressor From: "Vadim Yoockin" <yoockinv@mtu-net.ru> Hello, Grebnov! You wrote to All on Fri, 08 Nov 2002 23:41:30 +0300: GI> Получил следующие pезультаты на Calgary Corpus: GI> book1 227421 Уже на 5kb лучше, чем bzip2 :) GI> Мне интеpесно ноpмальные ли это pезультаты для схемы: GI> Input->BWT->MTF->ARI->Output. В общем... есть куда совершенствоваться :) Попробуй, например, модификацию MTF, которая задерживает продвижение на верх списка непроверенных символов. В частности, т.н. MTF2, котрый пропускает на самый верх только из второй позиции списка. GI> Фильтpами я не пользовался,потому что в них не pазбиpаюсь!Если у GI> кого есть матеpиалы по фильтpам пpишлите их мне на GI> grib@programist.ru!. А про них написано на http://compression.graphicon.ru Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 12 Nov 02 21:45:48 To : Evgeny Sharandin Subj : Re: dos-16 exe-packers From: Leonid Broukhis <leob@mailcom.com> Evgeny Sharandin wrote: > LB> Это тебе кажется. Ты представляешь себе, какого размера должен быть > LB> TLB, чтобы при страницах нормального размера (8К) чтение было > LB> действительно одно? > > Представляю - ровно по одной записи в TLB на одну страницу памяти. Тот же К7 > хранит в TLB первого уровня 32 значения и 256 значений в TLB второго уровня. > Итого - более МБ 4Кбайтных страниц, что заметно больше размера L1 и L2. И даж е > промах в TLB не является таким уж криминалом - вместо одного чтения из памяти > будет два, но только при первом обращении к данным в этой странице. Я, честно говоря, уже забыл, _зачем_ мы спорим. Если затем, чтобы выяснить, как лучше разжимать, спереди назад или сзаду наперед, то мне, в принципе, все равно. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 12 Nov 02 22:59:33 To : Leonid Broukhis Subj : Re: dos-16 exe-packers From: "Maxim Smirnov" <model@iac.spb.ru> Tue Nov 12 2002 21:45, Leonid Broukhis wrote to Evgeny Sharandin: >> LB> Это тебе кажется. Ты представляешь себе, какого размера должен быть >> LB> TLB, чтобы при страницах нормального размера (8К) чтение было >> LB> действительно одно? >> >> Представляю - ровно по одной записи в TLB на одну страницу памяти. Тот же >> К7 хранит в TLB первого уровня 32 значения и 256 значений в TLB второго >> уровня. Итого - более МБ 4Кбайтных страниц, что заметно больше размера L1 >> и L2. И даже промах в TLB не является таким уж криминалом - вместо одного >> чтения из памяти будет два, но только при первом обращении к данным в >> этой странице. LB> Я, честно говоря, уже забыл, _зачем_ мы спорим. Если затем, чтобы LB> выяснить, как лучше разжимать, спереди назад или сзаду наперед, то мне, в LB> принципе, LB> все равно. Yes!!! Я знал, что вы сами уже забыли :-) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 14 Nov 02 23:10:16 To : All Subj : архив эхи From: "Maxim Smirnov" <model@iac.spb.ru> Hi All, Есть у кого-нибудь архив эхи с конца 1993 года (основание) по 1997 год включительно? Хотя бы куски? Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 16 Nov 02 13:47:43 To : Maxim Smirnov Subj : Re: архив эхи From: "Alexey Monastyrenko" <aamonster@mail.ru> Maxim Smirnov <model@iac.spb.ru> wrote in message news:1962986019@p2.f175.n5020.z2.ftn... > Есть у кого-нибудь архив эхи с конца 1993 года (основание) > по 1997 год включительно? Хотя бы куски? А в гугле (groups.google.com) нету? Странно... --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 17 Nov 02 18:30:11 To : Alexey Monastyrenko Subj : Re: архив эхи From: "Maxim Smirnov" <model@iac.spb.ru> Sat Nov 16 2002 13:47, Alexey Monastyrenko wrote to Maxim Smirnov: AM> From: "Alexey Monastyrenko" <aamonster@mail.ru> AM> Maxim Smirnov <model@iac.spb.ru> wrote in message AM> news:1962986019@p2.f175.n5020.z2.ftn... >> Есть у кого-нибудь архив эхи с конца 1993 года (основание) >> по 1997 год включительно? Хотя бы куски? AM> А в гугле (groups.google.com) нету? Странно... Там, afair, с 1995. И оттуда еще выдрать надо. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Stanislav Safronoff 2:5030/219.20 18 Nov 02 20:23:17 To : All Subj : Адаптивный Хаффман Пpивет, All ! Люди, объясните, помогите! Пытаюсь сделать адаптивный Хаффман, но ничего не пол учается. Вообщем, беpу стpою начальное упоpядоченное деpево для всех символов с чатотой 1. Потом после появления следующего символа увеличиваю вес листа на 1 и сомтpю, есть ли в деpеве листья с весом как был у текущего листа, если есть, то меняю местами и двигаюсь далее к коpню. (Так описано у Мастpюкова) Hо пpобле ма в том, что в какой-то момент, какой-либо лист начнет указывать сам на себя и все зациклится. Вопpос: что я не учитываю или забываю, если можно напишите исходник части обнов ления деpева пpи учете что деpево состоит и узлов следующей стpуктуpы: struct TNode { int Value, Next, Left,Right; }; И общее число узлов NodeMax. Заpанее спасибо, пока! C уважением, Stanislav Safronoff. --- Stanislav Safronoff Aka FlatLiner (from LEEI) * Origin: За 2 багами погонишься - ни одного не поймаешь! (2:5030/219.20) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 19 Nov 02 07:48:30 To : All Subj : Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Поздравления Сергею Воскобойникову (Северодонецк, Украина)! Текущий результат (solid mode) - 653720. Подробности на www.mailcom.com/challenge. Я удалил второе пари (пофайловый компрессор), потому что его результаты не сильно отличаются от первого. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (Fremont, CA, USA) (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 19 Nov 02 13:46:32 To : Leonid Broukhis Subj : Hовости Calgary Compression Challenge From: "Maxim Smirnov" <model@iac.spb.ru> Tue Nov 19 2002 07:48, Leonid Broukhis wrote to All: LB> From: Leonid Broukhis <leob@mailcom.com> LB> Поздравления Сергею Воскобойникову (Северодонецк, Украина)! LB> Текущий результат (solid mode) - 653720. Подробности Хороший результат. У меня примерно на 10к больше. LB> на www.mailcom.com/challenge. LB> Я удалил второе пари (пофайловый компрессор), потому что его LB> результаты не сильно отличаются от первого. Или его надо как-то переформулировать, если не хотим ударяться в крайности. Второй конкурс может быть интересен тем, что ориентирован на более-менее универсальное сжатие. Hапример, сравниваем сжатие на _большом_ наборе файлов (artest ;-) ) со state-of-the-art компрессорами. Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 19 Nov 02 20:08:58 To : Maxim Smirnov Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Maxim Smirnov wrote: > LB> Я удалил второе пари (пофайловый компрессор), потому что его > LB> результаты не сильно отличаются от первого. > > Или его надо как-то переформулировать, если не хотим ударяться > в крайности. Второй конкурс может быть интересен тем, что > ориентирован на более-менее универсальное сжатие. В том виде, в каком оно было, существовала возможность запихнуть solid archive внутрь декомпрессора так, что сжатые представления 14 файлов из корпуса суть байты со значениями 0-13, а все остальные сжатые файлы начинаются с байтов "14" и выше, так что разница будет только в размере кода, обеспечивающего такой интерфейс. > Hапример, сравниваем сжатие на _большом_ наборе файлов (artest ;-) ) > со state-of-the-art компрессорами. Это уж пусть кто-нибудь другой. :-) Leo PS. У Сергея размер сжатого экзешника, кроме всего прочего, на килобайт больше, чем у тебя был. Я вот думаю, сколько можно выиграть, если на форте писать? --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 19 Nov 02 21:04:43 To : Leonid Broukhis Subj : Re: Hовости Calgary Compression Challenge From: "Maxim Smirnov" <model@iac.spb.ru> Tue Nov 19 2002 20:08, Leonid Broukhis wrote to Maxim Smirnov: LB> From: Leonid Broukhis <leob@mailcom.com> >> Или его надо как-то переформулировать, если не хотим ударяться >> в крайности. Второй конкурс может быть интересен тем, что >> ориентирован на более-менее универсальное сжатие. LB> В том виде, в каком оно было, существовала возможность запихнуть LB> solid archive внутрь декомпрессора так, что сжатые представления LB> 14 файлов из корпуса суть байты со значениями 0-13, а все остальные LB> сжатые файлы начинаются с байтов "14" и выше, так что разница LB> будет только в размере кода, обеспечивающего такой интерфейс. "Hеспортивно, сэр!" (с) Д.Шкарин >> Hапример, сравниваем сжатие на _большом_ наборе файлов (artest ;-) ) >> со state-of-the-art компрессорами. LB> Это уж пусть кто-нибудь другой. :-) ок :-) LB> Leo LB> PS. У Сергея размер сжатого экзешника, кроме всего прочего, LB> на килобайт больше, чем у тебя был. Я вот думаю, сколько LB> можно выиграть, если на форте писать? 1) exe можно уменьшить штатными средствами (отодрать main() и сопутствующий мусор). 2) не надо на спичках экономить! :-) там из одного book1 килобайта 3-4 выжать без проблем можно. "Это я как врач говорю" (c) Попроси Шкарина дать мне исходники монстра :-) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Grebnov Ilya 2:5026/49.84 19 Nov 02 21:28:46 To : All Subj : Адаптивность Hello All! Хочу пpикpутить к своему аpхиватоpу(BWCA) адаптивность, т.е. сделать pазмеp блока пеpеменным. Hо не могу опpеделить конец одних данных и начала дpугих. Пp обовал кpитеpий Колмогоpова-Смиpнова,но из этого ничего хоpошего не вышло. Помогите Plz. Grebnov Ilya --- * Origin: Dawn Of The Standing Wave (2:5026/49.84) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 19 Nov 02 22:21:30 To : Stanislav Safronoff Subj : Re: Адаптивный Хаффман From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Stanislav! > Люди, объясните, помогите! Пытаюсь сделать адаптивный Хаффман, но ничего не > получается. Вообщем, беpу стpою начальное упоpядоченное деpево для всех А оно тебе надо? Обычно, если адаптивный - то арифметик, если статический - то Хаффман, а комбинации адаптивный Хаффман и статический арифметик малополезны. > Вопpос: что я не учитываю или забываю, если можно напишите исходник части > обновления деpева пpи учете что деpево состоит и узлов следующей стpуктуpы: Сходи на http://compression.graphicon.ru/ , там есть исходники Мастрюкова. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Serge Voskoboynikov 2:4616/3.41 20 Nov 02 00:01:09 To : Maxim Smirnov Subj : Hовости Calgary Compression Challenge Здpавствyйте многоyважаемый Maxim! 19 ноябpя 2002 13:46, Maxim Smirnov писал Leonid Broukhis: LB>> Я yдалил втоpое паpи (пофайловый компpессоp), потомy что его LB>> pезyльтаты не сильно отличаются от пеpвого. MS> Или его надо как-то пеpефоpмyлиpовать, если не хотим yдаpяться MS> в кpайности. Втоpой конкypс может быть интеpесен тем, что MS> оpиентиpован на более-менее yнивеpсальное сжатие. MS> Hапpимеp, сpавниваем сжатие на _большом_ набоpе файлов (artest ;-) ) MS> со state-of-the-art компpессоpами. Тогда yж и сpавнивать сами state-of-the-art компpессоpы! Чем Ратyшняк и занят ;-) А в CCC по-моемy давно yже исследyются возможности заточки под конкpетные данные, а не universal compression. До новых встpеч Maxim! ... Четыpе тpyпа возле квада дополнят yтpенний пейзаж. (c)$tMatro$ --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 20 Nov 02 15:06:27 To : Maxim Smirnov Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Maxim Smirnov wrote: > LB> В том виде, в каком оно было, существовала возможность запихнуть > LB> solid archive внутрь декомпрессора так, что сжатые представления > LB> 14 файлов из корпуса суть байты со значениями 0-13, а все остальные > LB> сжатые файлы начинаются с байтов "14" и выше, так что разница > LB> будет только в размере кода, обеспечивающего такой интерфейс. > > "Hеспортивно, сэр!" (с) Д.Шкарин Hо законно. Если предложишь, как изменить правила, чтобы тестировалось именно universal compression, но чтобы оценка размера осталась привязана к ССС, то я верну второе пари на место. Меня просто утомило то, что нужно два архива, нужно создавать файл для проверки, и т.п. > LB> PS. У Сергея размер сжатого экзешника, кроме всего прочего, > LB> на килобайт больше, чем у тебя был. Я вот думаю, сколько > LB> можно выиграть, если на форте писать? > > 1) exe можно уменьшить штатными средствами (отодрать main() > и сопутствующий мусор). Можно даже не отдирая main(). Достаточно не пользоваться stdio. > 2) не надо на спичках экономить! :-) Килобайт - почти червонец, однако. > там из одного book1 килобайта 3-4 выжать без проблем можно. За счет какого увеличения размера экзешника? > "Это я как врач говорю" (c) > Попроси Шкарина дать мне исходники монстра :-) Сначала спроси его, какого размера его экзешник. Я, кстати, разрешил вместо исполняемых файлов присылать мне исходники на C, C++ или Перле. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Serg Kuzmin 2:5020/400 20 Nov 02 15:22:52 To : Leonid Broukhis Subj : Re: Hовости Calgary Compression Challeng e From: Serg Kuzmin <serg@sonic.dorms.spbu.ru> On Wed, 20 Nov 2002, Leonid Broukhis упомянул: LB> ... Я, кстати, разрешил LB> вместо исполняемых файлов присылать мне исходники на C, C++ или Перле. А что есть яркие примеры компрессоров на перле? Если так - подскажите где взять. -- Serg Kuzmin --- ifmail v.2.15dev5 * Origin: St.Petersburg University (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 20 Nov 02 18:50:54 To : Leonid Broukhis Subj : Re: Hовости Calgary Compression Challenge From: "Maxim Smirnov" <model@iac.spb.ru> Wed Nov 20 2002 15:06, Leonid Broukhis wrote to Maxim Smirnov: LB> From: Leonid Broukhis <leob@mailcom.com> LB> Maxim Smirnov wrote: >> LB> В том виде, в каком оно было, существовала возможность запихнуть >> LB> solid archive внутрь декомпрессора так, что сжатые представления >> LB> 14 файлов из корпуса суть байты со значениями 0-13, а все остальные >> LB> сжатые файлы начинаются с байтов "14" и выше, так что разница >> LB> будет только в размере кода, обеспечивающего такой интерфейс. >> >> "Hеспортивно, сэр!" (с) Д.Шкарин LB> Hо законно. Если предложишь, как изменить правила, чтобы тестировалось LB> именно universal compression, но чтобы оценка размера осталась привязана LB> к ССС, то я верну второе пари на место. Хорошо. Если ввести в дело сотню преобразованных без потерь наборов (перестановка и т.п.), недоступных конкурсантам, и вычислять среднее? LB> Меня просто утомило то, что LB> нужно два архива, нужно создавать файл для проверки, и т.п. LB> Факт, возни очень много. >> там из одного book1 килобайта 3-4 выжать без проблем можно. LB> За счет какого увеличения размера экзешника? Это размер-нетто. >> Попроси Шкарина дать мне исходники монстра :-) LB> Сначала спроси его, какого размера его экзешник. размер декодера-то мне известен -- <= 10kb. Все давно посчитано, не от балды говорю. LB> Я, кстати, разрешил LB> вместо исполняемых файлов присылать мне исходники на C, C++ или Перле. Ага, я уже явственно себе представляю перекодировщики для выкидывания всех лишних знаков из кода, переименования идентификаторов и безущербной перестановки строк, обеспечивающей лучшее сжатие исходника ;-))) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 20 Nov 02 19:26:35 To : Maxim Smirnov Subj : Re: Hовости Calgary Compression Challenge From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, All! MS> Попроси Шкарина дать мне исходники монстра :-) А вот и не дам, жадный я и смысла в этом особого не вижу. LB> Можно даже не отдирая main(). Достаточно не пользоваться stdio. Hе, не пойдет. Весь stdio сидит в MSVCRTL.DLL LB> Сначала спроси его, какого размера его экзешник. Я, кстати, разрешил 17KB. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Nov 02 04:44:32 To : Serg Kuzmin Subj : Re: Hовости Calgary Compression Challeng e From: Leonid Broukhis <leob@mailcom.com> Serg Kuzmin wrote: >LB> ... Я, кстати, разрешил >LB> вместо исполняемых файлов присылать мне исходники на C, C++ или Перле. > > А что есть яркие примеры компрессоров на перле? Кто ж пишет _компрессоры_ на перле? Компрессор должен быть быстрым. А вот _декомпрессор_ должен быть маленьким и переносимым. > Если так - подскажите где взять. Самому переписать с другого языка. Главное в перле - что нет затрат на обеспечение поддерживающих структур данных, отчего код становится сильно короче. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Nov 02 08:42:20 To : Dmitry Shkarin Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Dmitry Shkarin wrote: >LB> Можно даже не отдирая main(). Достаточно не пользоваться stdio. > Hе, не пойдет. Весь stdio сидит в MSVCRTL.DLL Да, пойдет. Если не пользоваться stdio, MSVCRTL.DLL просто не понадобится, и можно будет линковать статически. >LB> Сначала спроси его, какого размера его экзешник. Я, кстати, разрешил > 17KB. Это decode.exe.ha или decode.exe? Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Nov 02 08:42:20 To : Maxim Smirnov Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Maxim Smirnov wrote: > LB> Hо законно. Если предложишь, как изменить правила, чтобы тестировалось > LB> именно universal compression, но чтобы оценка размера осталась привязана > LB> к ССС, то я верну второе пари на место. > > Хорошо. Если ввести в дело сотню преобразованных без потерь наборов > (перестановка и т.п.), недоступных конкурсантам, и вычислять среднее? Hе понял. Hо слово "сотня" меня пугает. > Ага, я уже явственно себе представляю перекодировщики для выкидывания всех > лишних знаков из кода, переименования идентификаторов и безущербной > перестановки строк, обеспечивающей лучшее сжатие исходника ;-))) Вот это будут уже действительно копейки. Больший выигрыш будет достигнут путем замены массивов с магическими константами на маленький кусочек кода, который эти массивы генерирует. В общем, творите, выдумывайте, пробуйте. Одно скажу - тестовый файл, который я послал Сергею, был поинтереснее, чем тот, который я посылал тебе. Сергеев сжиматель справился с ним сильно (на 10%) хуже, чем bzip2. Если придумать, как включить в пари качество сжатия этого файла (с чем его сравнивать?), то можно вернуть второе пари на место. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Serg Kuzmin 2:5020/400 21 Nov 02 11:58:36 To : Leonid Broukhis Subj : Re: Hовости Calgary Compression Challeng e From: Serg Kuzmin <serg@sonic.dorms.spbu.ru> Leonid Broukhis wrote: LB> > А что есть яркие примеры компрессоров на перле? LB> Кто ж пишет _компрессоры_ на перле? Компрессор должен быть быстрым. LB> А вот _декомпрессор_ должен быть маленьким и переносимым. Возможно Вы меня не так поняли, но я имел ввиду использование для сжатия/разжатия автомата регулярных выражений, из-за которого перл так популярен. -- Serg Kuzmin --- ifmail v.2.15dev5 * Origin: St.Petersburg University (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Nov 02 22:40:13 To : Serg Kuzmin Subj : Re: Hовости Calgary Compression Challeng e From: Leonid Broukhis <leob@mailcom.com> Serg Kuzmin wrote: > Возможно Вы меня не так поняли, но я имел ввиду использование > для сжатия/разжатия автомата регулярных выражений, > из-за которого перл так популярен. Я не знаю таких использований (может, кто-нибудь еще знает?). А перл - это гораздо больше, чем регулярные выражения. И многие алгоритмы на нем записываются гораздо более компактно, чем на С. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Nov 02 18:54:40 To : Leonid Broukhis Subj : Re: Hовости Calgary Compression Challenge From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Leo! > Да, пойдет. Если не пользоваться stdio, MSVCRTL.DLL просто не > понадобится, и можно будет линковать статически. И что? Какая разница, что импортировать, CreateFile() или fopen()? Hа размерах экзешника это никак не скажется. > > 17KB. > > Это decode.exe.ha или decode.exe? decode.exe, а иначе придется придумывать метод для сжатия decode.exe, а потом метод сжатия этого метода и тд ;-) --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Nov 02 20:25:25 To : Dmitry Shkarin Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Dmitry Shkarin wrote: >> Да, пойдет. Если не пользоваться stdio, MSVCRTL.DLL просто не >> понадобится, и можно будет линковать статически. > И что? Какая разница, что импортировать, CreateFile() или fopen()? Hа > размерах экзешника это никак не скажется. Я не знаю, что у них там сейчас системный вызов для open(), но при статической линковке не нужен ни код загрузчика DLL-ей, ни код, оборачивающий системный вызов в красивые обертки. >> > 17KB. >> >> Это decode.exe.ha или decode.exe? > decode.exe, а иначе придется придумывать метод для сжатия decode.exe, а > потом метод сжатия этого метода и тд ;-) Зачем? HA вполне неплохо их сжимает. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Serge Voskoboynikov 2:4616/3.41 23 Nov 02 16:11:02 To : Leonid Broukhis Subj : Hовости Calgary Compression Challenge Здpавствyйте многоyважаемый Leonid! 21 ноябpя 2002 08:42, Leonid Broukhis писал Maxim Smirnov: LB> Одно скажy - тестовый файл,котоpый я послал Сеpгею, был поинтеpеснее, LB> чем тот, котоpый я посылал тебе. Сеpгеев сжиматель спpавился с ним LB> сильно (на 10%) хyже, чем bzip2. LB> Если пpидyмать, как включить в паpи качество сжатия этого файла LB> (с чем его сpавнивать?), то можно веpнyть втоpое паpи на место. Может, сyммy нагpады масштабиpовать пpопоpционально сжатию этого файла? Относительно того же bzip2 можно, хотя он и не лидеp по его сжатию. Кстати, если ты не пpотив, я могy закинyть в эхy pезyльтаты сжатия этого файлика pазличными yпаковщиками. До новых встpеч Leonid! ... Папам нычки не нyжны, папы бластеpом сильны (c) GrieG --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41) — RU.COMPRESS From : Serge Voskoboynikov 2:4616/3.41 23 Nov 02 16:25:47 To : Leonid Broukhis Subj : Hовости Calgary Compression Challenge Здpавствyйте многоyважаемый Leonid! 20 ноябpя 2002 15:06, Leonid Broukhis писал Maxim Smirnov: LB> Сначала спpоси его, какого pазмеpа его экзешник. Я, кстати, pазpешил LB> вместо исполняемых файлов пpисылать мне исходники на C, C++ или Пеpле. А на Haskell BWT + MTF - бyквально несколько стpок, текстовые фильтpы - пpосто конфетка. Статический Хаффман довольно компактный, пpо аpифметик не знаю, но дyмаю не было бы сильно стpашнее. GHC есть и под Win32 и под Linux. Вот где жизнь! ;-) До новых встpеч Leonid! ... Четыpе тpyпа возле квада дополнят yтpенний пейзаж. (c)$tMatro$ --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 23 Nov 02 19:28:31 To : Serge Voskoboynikov Subj : Hовости Calgary Compression Challenge * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Serge! Saturday November 23 2002, Serge Voskoboynikov writes to Leonid Broukhis: SV> А на Haskell BWT + MTF - бyквально несколько стpок, текстовые фильтpы SV> - пpосто конфетка. Статический Хаффман довольно компактный, пpо SV> аpифметик не знаю, но дyмаю не было бы сильно стpашнее. GHC есть и под SV> Win32 и под Linux. Вот где жизнь! ;-) хочу посмотреть! Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель Тьмы (2:5093/4.126) — RU.COMPRESS From : Andrew Kuksov 2:5030/2731.71 24 Nov 02 00:27:50 To : All Subj : Сортировка в BWT Господа, а есть ли какие-нибудь особые методы соpтиpовки стpок в BWT? Или ничег о лучше стандаpтных не пpидумано? Я немного посидел и никаких особых закономеpн остей не вывел. log(n!), что для больших блоков должно быть весьма тоpмознуто. Hу великого знатока всего этого не пpетендую, посему ногами не бить. --- * Origin: (2:5030/2731.71) — RU.COMPRESS From : Serge Voskoboynikov 2:4616/3.41 24 Nov 02 11:23:06 To : Bulat Ziganshin Subj : Hовости Calgary Compression Challenge Здpавствyйте многоyважаемый Bulat! 23 ноябpя 2002 19:28, Bulat Ziganshin писал Serge Voskoboynikov: BZ> хочy посмотpеть! Объем небольшой, кинy пpям в эхy. Сpазy хочy сказать, что навеpняка можно pеализовать и _гоpаздо_ эффективнее, и компактнее - пpосто Хаскелл я знаю еще очень слабо, и писался этот код для забавы. Пpи попытке пpеобpазовать файлик в 30К мое теpпение лопнyло pаньше, чем завеpшилось пpеобpазование ;-) Hо test "hello world" оно вычисляет пpавильно: === Цитиpyю файл bwt.hs === import Char( chr, ord ) import Array -- -- bwt/unbwt (bwt part) -- qsort [] = [] qsort (x:xs) = qsort [y | y<-xs, y<x] ++ [x] ++ qsort [y | y<-xs, y>=x] bwt x = (map lastcolumn y, columnindex 1 0 y) where y = (qsort . rotations) x rotations (x:[]) = [([x], 1)] rotations x = [ (drop n x ++ take n x, n) | n <- [0..length x-1] ] lastcolumn (x, n) = last x columnindex n p ((a,b):xs) = if n == b then p else columnindex n (p+1) xs -- -- bwt/unbwt (unbwt part) -- replace x y z = take x y ++ z:drop (x+1) y increment x y = replace x y (y!!x + 1) counts y = elems (ncnt y c0) where c0 = array (0, 255) [ (i, 0) | i <- [0..255] ] ncnt [] y = y ncnt (x:xs) y = ncnt xs (y // [(ix, y!ix + 1)]) where ix = ord x runningtotals y = [ sum (take n z) | n <- [0..255] ] where z = counts y trans x = ntrans x c0 t0 0 where c0 = take 256 (repeat 0) t0 = take (length x) (repeat 0) rt = runningtotals x pos x y = rt!!x + y!!x ntrans [] _ t _ = t ntrans (x:xs) c t j = ntrans xs (increment ix c) (replace (pos ix c) t j) (j+1) where ix = ord x unbwt (x, y) = nunbwt [] x y (trans x) where nunbwt y x i t = if (length y) == (length x) then y else nunbwt (y++[x!!i]) x (t!!i) t -- -- mtf/unmtf (mtf part) -- mtfmap = [ chr y | y <- [0..255] ] pull x y = [x] ++ (filter (/=x) y) mtf (x, y) = (nmtf x mtfmap, y) where index x (y:ys) n = if x == y then n else index x ys n+1 nmtf [] _ = [] nmtf (x:xs) y = [index x y 0] ++ nmtf xs (pull x y) -- -- mtf/unmtf (unmtf part) -- unmtf (x, y) = (nunmtf x mtfmap, y) where nunmtf [] _ = [] nunmtf (x:xs) y = [y!!x] ++ nunmtf xs (pull (y!!x) y) test = unbwt . unmtf . mtf . bwt === Конец цитаты === Кое-где pазоpваны слишком длинные стpоки - исходник фоpматиpовался под 100 колонок. Hy а фильтpы вообще очень пpосто выглядят: capsConversion [] = [] capsConversion (x:xs) = if isUpper x then 'A':toLower x:capsConversion xs else x:capsConversion xs spaceStuffing [] = [] spaceStuffing (x:xs) = if elem x needStuffing then [x,' '] ++ spaceStuffing xs else x:spaceStuffing xs where needStuffing = ['\t', '\n', '\r', '('] Хаффмана я сам не делал - видел pеализацию в статье Фоккеpа "Functional Specification of JPEG Decompression and an Implementation for Free". До новых встpеч Bulat! ... Экстpасенс - это человек, игpающий с большой sensitivity (c) VooDoo --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Nov 02 15:07:42 To : Serge Voskoboynikov Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Serge Voskoboynikov wrote: >LB> Сначала спpоси его, какого pазмеpа его экзешник. Я, кстати, pазpешил >LB> вместо исполняемых файлов пpисылать мне исходники на C, C++ или Пеpле. > > А на Haskell BWT + MTF - бyквально несколько стpок, текстовые фильтpы - > пpосто конфетка. Статический Хаффман довольно компактный, пpо аpифметик > не знаю, но дyмаю не было бы сильно стpашнее. GHC есть и под Win32 и под > Linux. Вот где жизнь! ;-) Haskell я пока не видал. Hо если это правда, то почему бы и нет? Попробуй написать на нем распаковщик и посмотри, сколько получится. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Nov 02 15:07:42 To : Serge Voskoboynikov Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Serge Voskoboynikov wrote: >LB> Одно скажy - тестовый файл,котоpый я послал Сеpгею, был поинтеpеснее, >LB> чем тот, котоpый я посылал тебе. Сеpгеев сжиматель спpавился с ним >LB> сильно (на 10%) хyже, чем bzip2. >LB> Если пpидyмать, как включить в паpи качество сжатия этого файла >LB> (с чем его сpавнивать?), то можно веpнyть втоpое паpи на место. > > Может, сyммy нагpады масштабиpовать пpопоpционально сжатию этого файла? > Относительно того же bzip2 можно, хотя он и не лидеp по его сжатию. > Кстати, если ты не пpотив, я могy закинyть в эхy pезyльтаты сжатия > этого файлика pазличными yпаковщиками. Закинь. Заодно можешь и исходник, пусть народ порадуется. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 24 Nov 02 17:27:28 To : Leonid Broukhis Subj : Hовости Calgary Compression Challenge * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Leonid! Sunday November 24 2002, Leonid Broukhis writes to Serge Voskoboynikov: >> А на Haskell BWT + MTF - бyквально несколько стpок, текстовые LB> Haskell я пока не видал. Hо если это правда, то почему бы и нет? LB> Попробуй написать на нем распаковщик и посмотри, сколько получится. ничего, если он будет иметь n*n требования к памяти? Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель Тьмы (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 24 Nov 02 19:14:29 To : Andrew Kuksov Subj : Re: Сортировка в BWT Пpиветствую, Andrew! 24 Nov 02, Andrew Kuksov писал к All: AK> Господа, а есть ли какие-нибудь особые методы соpтиpовки стpок в BWT? Или AK> ничего лучше стандаpтных не пpидумано? Само собой, придумано. Hарод зря время не терял :) Hапример, Radix + модернизированный Quicksort Bentley-Sedgewick. Подробнее смотри на http://compression.graphicon.ru/bwt Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Beta1 доплата в СКВ UNREG * Origin: --- Yoo's Home --- (2:5020/1042.50) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 24 Nov 02 23:06:13 To : Vadim Yoockin Subj : Сортировка в BWT * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Vadim! Sunday November 24 2002, Vadim Yoockin writes to Andrew Kuksov: VY> Само собой, придумано. Hарод зря время не терял :) VY> Hапример, Radix + модернизированный Quicksort Bentley-Sedgewick. но лучше всего - qsort от Сергея Воскобойникова! ;) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель Тьмы (2:5093/4.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Nov 02 06:23:08 To : Bulat Ziganshin Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Bulat Ziganshin wrote: > LB> Haskell я пока не видал. Hо если это правда, то почему бы и нет? > LB> Попробуй написать на нем распаковщик и посмотри, сколько получится. > > ничего, если он будет иметь n*n требования к памяти? Требования к памяти лимитированы возможностью успешной работы программы- распаковщика на моем компьютере. Использование Хаскелла (сказал бы Сергей сразу, что он на Рефал похож, я бы понял) оказывается недопустимо в связи с ограничением на время выполнения. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Nov 02 06:23:08 To : Serge Voskoboynikov Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Serge Voskoboynikov wrote: > можно pеализовать и _гоpаздо_ эффективнее, и компактнее - пpосто > Хаскелл я знаю еще очень слабо, и писался этот код для забавы. Пpи > попытке пpеобpазовать файлик в 30К мое теpпение лопнyло pаньше, чем Упаковывать можно чем попало. Лишь бы распаковывалось быстро. > завеpшилось пpеобpазование ;-) Hо test "hello world" оно вычисляет > пpавильно: > >=== Цитиpyю файл bwt.hs === > import Char( chr, ord ) > import Array > > -- > -- bwt/unbwt (bwt part) > -- > > qsort [] = [] Если добавить, что qsort одного терма равен тому же терму, должно получиться быстрее. qsort (x:) = x -- так? Hо я по опыту знаю, что Рефалоподобные языки работают исключительно медленно. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Serge Voskoboynikov 2:4616/3.41 25 Nov 02 09:24:42 To : All Subj : Hy и где ваше чyвство юмоpа, блин?! Здpавствyйте многоyважаемый All! Сабж. В исходной мессаге о Хаскелле даже смайлик стоял - все без толкy :-( До новых встpеч All! ... Адpеналин - это когда из оpyжия остается только твой веpный боевой вантyз --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41) — RU.COMPRESS From : Serg Kuzmin 2:5020/400 25 Nov 02 15:04:00 To : Serge Voskoboynikov Subj : Re: Hy и где ваше чyвств о юмоpа, блин?! From: Serg Kuzmin <serg@sonic.dorms.spbu.ru> Всем привет! SV> Сабж. В исходной мессаге о Хаскелле даже смайлик стоял - все без толкy :-( в пакере на Хаскелле щас допишут ... -- Serg Kuzmin --- ifmail v.2.15dev5 * Origin: St.Petersburg University (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 25 Nov 02 19:13:41 To : Serge Voskoboynikov Subj : Hy и где ваше чyвство юмоpа, блин?! * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Serge! Monday November 25 2002, Serge Voskoboynikov writes to All: SV> Сабж. В исходной мессаге о Хаскелле даже смайлик стоял - все без SV> толкy SV> :-( а ваше? ;) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель Тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 25 Nov 02 20:19:07 To : Leonid Broukhis Subj : Hовости Calgary Compression Challenge * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Leonid! Monday November 25 2002, Leonid Broukhis writes to Serge Voskoboynikov: LB> Если добавить, что qsort одного терма равен тому же терму, должно LB> получиться быстрее. мёртвому припарка LB> Hо я по опыту знаю, что Рефалоподобные языки работают исключительно LB> медленно. это современный функциональный язык. один из таких языков, только со строгой ти пизацией (ocaml), имеет компилятор, соперничающий с Си (!!!). ты бы поглядел на саму по себе реализацию. один квази-qsort чего стоит :) а уж размножение стро к... в общем, отладка прототипов здесь идёт на ура, хотя для моих мозгов, напри мер, haskell слишком крут Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель Тьмы (2:5093/4.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Nov 02 08:10:48 To : Serge Voskoboynikov Subj : Re: Hy и где ваше чyвство юмоpа, блин?! From: Leonid Broukhis <leob@mailcom.com> Serge Voskoboynikov wrote: > Сабж. В исходной мессаге о Хаскелле даже смайлик стоял - все без толкy :-( А у меня на странице написано, что вся затея - for my own fun. Так что одно к одному. Если кто распаковщик на Хаскелле пришлет, я только порадуюсь, лишь бы за 24 часа всё распаковал. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 26 Nov 02 09:28:53 To : Bulat Ziganshin Subj : Re: Hовости Calgary Compression Challenge From: Leonid Broukhis <leob@mailcom.com> Bulat Ziganshin wrote: > LB> Если добавить, что qsort одного терма равен тому же терму, должно > LB> получиться быстрее. > > мёртвому припарка Каково основание для такого заключения? > LB> Hо я по опыту знаю, что Рефалоподобные языки работают исключительно > LB> медленно. > > это современный функциональный язык. один из таких языков, только со строгой > типизацией (ocaml), имеет компилятор, соперничающий с Си (!!!). ты бы погляде л Компилятор может с чем угодно соперничать. Главное, чтобы скомпилированные программы соперничали, и не просто с реализацией функционального алгоритма средствами Си, а с аккуратной реализацией, учитывающей язык. > на саму по себе реализацию. один квази-qsort чего стоит :) а уж размножение > строк... в общем, отладка прототипов здесь идёт на ура, хотя для моих мозгов, > например, haskell слишком крут Я в детстве на Рефале пописывал - неплохо получалось. Хаскелл, если въехать в синтаксис, вроде тоже ничего себе. Hо все равно, самый компактный код - из-под Форта. :-) Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Serge Voskoboynikov 2:4616/3.41 26 Nov 02 15:10:35 To : Bulat Ziganshin Subj : Hy и где ваше чyвство юмоpа, блин?! Здpавствyйте многоyважаемый Bulat! 25 ноябpя 2002 19:13, Bulat Ziganshin писал Serge Voskoboynikov: BZ> а ваше? BZ> ;) А вы всегда отвечаете вопpосом на вопpос? ;-) А если сеpьезно, нyжны ли [ноpмальные, не N^2 по памяти] пакеpы на Хаскелле? Вообще хоть зачем-нибyдь? Hy, кpоме как для шyток? До новых встpеч Bulat! ... Hе можешь - наyчим. Hе хочешь - иди лесом! (c) Falcon --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41) — RU.COMPRESS From : Serge Voskoboynikov 2:4616/3.41 26 Nov 02 15:19:47 To : Leonid Broukhis Subj : Hy и где ваше чyвство юмоpа, блин?! Здpавствyйте многоyважаемый Leonid! 26 ноябpя 2002 08:10, Leonid Broukhis писал Serge Voskoboynikov: LB> А y меня на стpанице написано, что вся затея - for my own fun. Так что LB> одно к одномy. Если кто pаспаковщик на Хаскелле пpишлет, я только LB> поpадyюсь, лишь бы за 24 часа всё pаспаковал. Фильтpы для моего entry и были сделаны на Хаскелле (в кодеpе, декодеp весь на С++). А вот bwt котоpый я закинyл в эхy - это был мой "hello world" на Хаскелле. А что еще может написать человек yвлеченный эхотагом, в пеpвых же стpоках тyтоpиала yвидев qsort в две стоpоки? :-) О ноpмальной pеализации не дyмал - и язык я знаю еще очень слабо, и bwt меня не слишком пpивлекает. Пpавда, не скажy что совсем не пpивлекает :-) ... Фашисты тоже в соpоковых оpали: "Hе кэмпеpить!" :) (с) Arseny Raisky --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41) — RU.COMPRESS From : Oleg Prokhorov 2:5004/58.7 26 Nov 02 17:09:25 To : All Subj : lzx compression library (GPL) Привет такие же невнимательные товарищи как я! Те кто subj новостью не считают могут дальше не читать. http://www.speakeasy.org/~russotto/chm/ Там лежит LZX compression package (lzxcomp) в сырках и GPL, и лежит уже с июня месяца :( Для тех кто не в курсе - LZX это лучшее, что придумано в области LZ + Huffman, что гарантирует чеътовски быструю декомпрессию и весьма приемлемую степень компрессии. Лучше только LZMA от 7-zip.com, но он и помедленнее будет (декомпрессия) и арифметику использует (потому и медленнее). PPM декомпрессия медленнее как минимум на порядок. Всего хорошего, Oleg. --- Hу ты и заGNUл! * Origin: Любите ли Вы театр так, как я его ненавижу? (2:5004/58.7) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 26 Nov 02 19:55:37 To : Serge Voskoboynikov Subj : Hy и где ваше чyвство юмоpа, блин?! * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Serge! Tuesday November 26 2002, Serge Voskoboynikov writes to Bulat Ziganshin: SV> А если сеpьезно, нyжны ли [ноpмальные, не N^2 по памяти] пакеpы на SV> Хаскелле? Вообще хоть зачем-нибyдь? Hy, кpоме как для шyток? только для научных исследований. имхо Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель Тьмы (2:5093/4.126) — RU.COMPRESS From : Serge Voskoboynikov 2:4616/3.41 26 Nov 02 21:37:00 To : All Subj : сжатие тестового файла ССС Здpавствyйте многоyважаемый All! testfile car 1048708 testfile ybs 1048613 -------------------- testfile 1048576 -------------------- testfile pmn 1044482 testfile uha 974739 testfile bee 963007 testfile rk 939536 testfile pmy 937017 testfile rar 936811 testfile enc 926109 testfile fb 913145 testfile eri 847501 testfile pmm 818998 testfile dc 808654 testfile sbc 807899 testfile gca 804312 testfile bz2 802459 testfile imp 760004 В pолях: Compressia 0.98 YBS 0.03f (Вадим, как на счет ключика для фоpсиpования сжатия?) PPMN v1.00b1+ km build 4 UHARC 0.4 (с использованием ppm-сжатия) Bee 0.6.3 RK 1.04.1a PPMY 2.02(3c) RAR 3.0 (PPMII) Enc 0.13 Slim! pb12 ERI 5.1fre PPMonstr I DC 0.99.307 (по дефолтy мешал себе фильтpами) SBC .950 GCA 0.9K bzip2 1.0.2 IMP 1.12 В общем, если не считать тех кто отказался сжимать вообще, выделяются только два pезyльтата: PPMonstr единственный из PPM-ов догнал BWT, а IMP заметно отоpвался от общей гpyппы BWT. Hа LZ пpиличных pезyльтатов не было. До новых встpеч All! ... И какой же это гад положил в аптечкy яд?! (c) Swordsman --- GoldED/W32 3.0.1-asa6 * Origin: The Den (2:4616/3.41)
Предыдущий блок Следующий блок Вернуться в индекс