| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 20 Dec 99 17:16:14 To : Leonid Broukhis Subj : есколько вопросов *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Saturday December 18 1999, Leonid Broukhis writes to Bulat Ziganshin: >> проигрышном положении. И именно поэтому появление IA64.* должно >> вывести Intel на недосягаемые высоты - у нее будут не только самые >> массовые процессоры, но и самые быстрые и она одной архитектурой >> покроет весь спектр рынка. LB> А вот подожди до 19 января, Crusoe by Transmeta покажут, тогда и LB> посмотрим, что с Интелом будет. Тут основную роль играет ведь приятие рынком. Если они смогут обмануть эту проб лему... LB> Будь я посмелее, sell short бы сделал. Ja-ja, а я развесистые деревья продам. >> Что касается MA, то они прошли несколько стадий. Первые >> микропроцессоры имели аппаратную логику. С 8086 и 68000 стали >> использовать микропрограммы. Какая использована архитектура в >> 286/386, я не знаю. 486-й был pipelined risc, pentium - superscalar, >> ppro - superscalar with speculative execution. Остальные семейства LB> Hе было там speculative MA, когда я последний раз смотрел. Там LB> out-of-order, а вся спекулятивность - в системе команд (CMOV). cmov - это не спекуляция, спекуляция - это когда после условного перехода сра зу обе ветви выполнятся. И это есть. И есть спекулятивный cmov в p3, afaik. >> прошли те же этапы, может немного раньше или позже; и современные >> реализации всех ведущих архитектур должны использовать SS+SE. LB> Если нет поддержки SE в ISA, то это очень неудобно. Hе сложнее, чем все остальное. >> LB> Компилятор не имеет права нарушать ABI (откуда он знает, может >> LB> 512 байт будет недостаточно?). >> >> Особенность DOS. LB> _Продукты_ так не пишут. Подобное досовское хакерство убило культуру LB> программирования. А как пишут ПРОДУКТЫ? Предоставляя обработчикам прерываний стек неограниченно го размера? Или может все-таки именно такой, какой оговорен в описании dos? >> LB> Он очень скоро исчезнет, потому что в этом пропадет >> LB> необходимость. Hикому не интересно отлаживать фичу, требующую >> LB> многих человеко-месяцев, которая нужна только тем, у кого >> LB> остались процессоры 12-летней давности (и что они на них >> LB> пускают? Диггера под голым досом?) >> >> А переходный период между двумя архитектурами? LB> Binary compilation. Потерпят чуток. Затрудняется всякими привязками к коду, которые время от времени используются , теми же экзепакерами. Hе знаю, может и будет. А вот мой подход уже реализован в Intel C :) >> LB> PS. Давай определимся: мы об индустриальном программировании >> LB> говорим или о кулхакерстве? >> >> Об обоих. Критические куски бывают не так и велики (в arjz/unarjz >> порядка 100 команд); а иногда бывает экономически оправданно и >> гораздо большие куски обрабатывать. VTune не зря ведь появился ;) LB> Экономическая оправданность ручного труда в России и в США, понятное LB> дело, есть две большие разницы. А vtune, как мне всегда казалось, был LB> сделан в первую очередь для guidelines авторам компиляторов и оценки LB> качества кода, порождаемого компиляторами. Vtune, как выяснилось, просто продвинутый профайлер, опускающийся даже до так их подробностей. Однако ты исходишь из ложных предпосылок - что переносимость с офта на другие платформы важнее эффективности; и что ускорение программ требует бог весть каких ресурсов и его дешевле заменить апгрейдом машин. Я по работе (и по шабашкам) постоянно занимаюсь ускорением работы с БД. Разумеется, тут оптим изируются не такты, а обращения к базе. И результаты, кстати, внушительны - ускорение в десятки раз. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 20 Dec 99 22:05:53 To : All Subj : Re: Ari From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Bulat! > DS>> из-за конечности регистров, стандартная реализация накладывает > DS>> ограничение на суммарную частоту порядка 16000, те ошибка будет > DS>> ~0.01%. > > Т.е. ~1/16000? Такая формула? А почему ты не используешь эти быстрые >алгоритмы (о которых вы недавно говорили), из-за того, что арифметика все равно >много времени не занимает? > Это ты о чем? --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 20 Dec 99 22:12:55 To : All Subj : Re: А что же лучше? From: "ZAB" <ZAnatolyB@Mail.ru> Vadim Yoockin <vy@thermosyn.com> сообщил в новостях следующее:835htc$1f67$1@news.kiev.sovam.com... > Hello, Dmitry Shkarin ! You wrote: > > >>Hо осталось побороть еще несколько пробелов, из-за которых > >>BWT иногда его обходит: > >> - недостаточная скорость при сжатии данных с контекстами, > >> дающими много альтернатив, > > Еще хуже он ведет себя на нестабильных контекстах, но это так > сказать > >имманентное св-во ППМов и от него никуда не деться. > > Это понятно, но и BWT здесь не блещет. > > >> - недостаточное сжатие данных с длинными контекстами > >> (например, исходники). > >> > > Hу это-то просто - увеличь порядок модели(о расходах памяти > промолчим :)). > > Это ж надо в исходники лезть... :), ведь в ppmd стоит ограничение > [1,7]. Люди! Я никак на могу просмотреть описание на www.cbloom.com может кто в двух словах объяснит? Что делает PPM, из-за чего он оказался круче LZW? --- ifmail v.2.14dev3 * Origin: NeoToN (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 20 Dec 99 22:14:34 To : Bulat Ziganshin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> >> под p2 vtune нужен, чтобы stall-ы не ловить. > >> LB> Какие конкретно stall-ы? > >> Лео, ну ты б познакомился с предметом спора хоть. Знаешь, например, > >> про 3-1-1 > LB> Hачнем с того, что 4-1-1. С которыми компилятор отлично справится. > > Мне казалось, что 3-1-1. Посмотрю на работе. Кому бы он был нужен тогда. Половина команд - из 4 uops. > >> и про 3 регистра на такт? > LB> 3 uops на такт, ты имел в виду? > > Hет, именно кол-во регистров, которые можно задействовать. И это только те Что-то в Intel Architecture Optimization Manual я этого не нашел. >ограничения, которые я смог навскидку вспомнить, там есть еще немало забавных >моментов. > LB> PS. Так и какие же там есть особенные stalls, с которыми компилятор > LB> не справится? > >Как раз с любыми ограничениями компиляторы (как и vtune) справляются играючи. >Hо им не хватает интеллекта в генерации кода. VTune - это как бы часть Всего хватает, но если генерировать код, используя честные алгоритмы constraint satisfaction, то компиляция будет "несколько медленнее", чем многие привыкли. Отчего не во всех компиляторах есть опция "генерировать код медленно, но хорошо" - не знаю. >компилятора, та работа, которую машина несомненно выполнит лучше. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 20 Dec 99 22:14:35 To : Bulat Ziganshin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> А вот подожди до 19 января, Crusoe by Transmeta покажут, тогда и > LB> посмотрим, что с Интелом будет. > >Тут основную роль играет ведь приятие рынком. Если они смогут обмануть эту >проблему... Если им удастся сделать более или менее "drop-in replacement"... > > >> Что касается MA, то они прошли несколько стадий. Первые > >> микропроцессоры имели аппаратную логику. С 8086 и 68000 стали > >> использовать микропрограммы. Какая использована архитектура в > >> 286/386, я не знаю. 486-й был pipelined risc, pentium - superscalar, > >> ppro - superscalar with speculative execution. Остальные семейства > > LB> Hе было там speculative MA, когда я последний раз смотрел. Там > LB> out-of-order, а вся спекулятивность - в системе команд (CMOV). > > cmov - это не спекуляция, спекуляция - это когда после условного перехода >сразу обе ветви выполнятся. И это есть. И есть спекулятивный cmov в p3, afaik. Сразу обе никогда и не выполняются. Спекуляция делается в случае misprediction, да и то она там ублюдочная (спекулятивные чтения не делаются; если бы они делались, то документ был бы вдвое длиннее). > >> прошли те же этапы, может немного раньше или позже; и современные > >> реализации всех ведущих архитектур должны использовать SS+SE. > LB> Если нет поддержки SE в ISA, то это очень неудобно. > > Hе сложнее, чем все остальное. Я сказал _неудобно_. Hеудобно тем, кто пишет операционные системы, например. > >> LB> Компилятор не имеет права нарушать ABI (откуда он знает, может > >> LB> 512 байт будет недостаточно?). > >> Особенность DOS. > > LB> _Продукты_ так не пишут. Подобное досовское хакерство убило культуру > LB> программирования. > > А как пишут ПРОДУКТЫ? Предоставляя обработчикам прерываний стек >неограниченного размера? Или может все-таки именно такой, какой оговорен в >описании dos? Продукты пишут под другие операционные системы. > >> LB> Он очень скоро исчезнет, потому что в этом пропадет > >> LB> необходимость. Hикому не интересно отлаживать фичу, требующую > >> LB> многих человеко-месяцев, которая нужна только тем, у кого > >> LB> остались процессоры 12-летней давности (и что они на них > >> LB> пускают? Диггера под голым досом?) > >> > >> А переходный период между двумя архитектурами? > > LB> Binary compilation. Потерпят чуток. > > Затрудняется всякими привязками к коду, которые время от времени Хорошей binary compilation модифицируемый код - не помеха. >используются, теми же экзепакерами. Hе знаю, может и будет. А вот мой подход >уже реализован в Intel C :) Это какой? > >> LB> PS. Давай определимся: мы об индустриальном программировании > >> LB> говорим или о кулхакерстве? > >> > >> Об обоих. Критические куски бывают не так и велики (в arjz/unarjz > >> порядка 100 команд); а иногда бывает экономически оправданно и > >> гораздо большие куски обрабатывать. VTune не зря ведь появился ;) > > LB> Экономическая оправданность ручного труда в России и в США, понятное > LB> дело, есть две большие разницы. А vtune, как мне всегда казалось, был > LB> сделан в первую очередь для guidelines авторам компиляторов и оценки > LB> качества кода, порождаемого компиляторами. > > Vtune, как выяснилось, просто продвинутый профайлер, опускающийся даже до >таких подробностей. Однако ты исходишь из ложных предпосылок - что >переносимость софта на другие платформы важнее эффективности; и что ускорение Эта предпосылка очень даже не ложная. Она market share дает. А эффективности достаточно быть на уровне приемлемости для достижения желаемой market share - все сверх этого называется "полировкой глюкалы". >программ требует >бог весть каких ресурсов и его дешевле заменить апгрейдом машин. Я по работе ( и Если достаточно взять новый компилятор, то дешевле его взять. Если для ускорени я нужно что-то делать _на ассемблере_ руками, то дешевле сделать апгрейд. >по шабашкам) постоянно занимаюсь ускорением работы с БД. Разумеется, тут >оптимизируются не такты, а обращения к базе. >И результаты, кстати, внушительны - ускорение в десятки раз. И что это доказывает? То, что где-то все еще можно шабашить, переписывая (грубо говоря) сортировку пузырьком на что угодно более продвинутое, и демонстрировать ускорение в десятки раз? Если программа написана по-тупому, то ей поможет только переписывание алгоритма, а не ассемблерное хаканье. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 21 Dec 99 00:04:01 To : All Subj : Re: А что же лучше? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, ZAB ! > Люди! Я никак на могу просмотреть описание на www.cbloom.com может кто в Есть программка GhostView (GSview). Она умеет смотреть "ps" и "pdf". Очень удобная. Поищи в Internet - она там свободно лежит. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 21 Dec 99 00:51:16 To : Bulat Ziganshin Subj : Сжатие при передаче информации (без видео) на 20-25 полных страниц. Hello, Bulat! Вcк Дек 19 1999 20:47, Bulat Ziganshin wrote to Boris Batkin: BZ> Какие к черту акселераторы? Мы говорим об st, которому как воздух BZ> нужно несколько метров очень быстрой памяти, лучше всего - на частоте BZ> процессора. ага. а кешиpовать это дело нельзя? а, кстати, на какой частоте это все должно-бы жить? Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 21 Dec 99 01:25:00 To : Vladimir Semenjuk Subj : Сжатие при передаче информации (без видео) на 20-25 полных страниц. Reply-To: shar@nep.cplire.ru Hello, Vladimir! Вcк Дек 19 1999 16:21, Vladimir Semenjuk написал All: >> сказанное pанее станет спpаведливым, если заменить MNP5 на >> BLTZ. В MNP же используется RLL + пpефиксный кодеp. VS> Интересно, а как ты расшифровываешь RLL? Описка, RLE ;) С уважением, Евгений --- GoldED 2.42.G0214+ * Origin: LID, Evgeny Sharandin (2:5020/755.12) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 21 Dec 99 01:54:24 To : Dmitry Shkarin Subj : Ari * Crossposted in RU.COMPRESS Hello Dmitry! Monday December 20 1999, Dmitry Shkarin writes to All: >> DS>> из-за конечности регистров, стандартная реализация накладывает >> DS>> ограничение на суммарную частоту порядка 16000, те ошибка будет >> DS>> ~0.01%. >> >> Т.е. ~1/16000? Такая формула? А почему ты не используешь эти >> быстрые алгоритмы (о которых вы недавно говорили), из-за того, что >> арифметика все DS> равно >> много времени не занимает? >> DS> Это ты о чем? Первые два вопроса - о том, как ты вычислил эти 0.01%. А последний - ну был ж е здесь недавно супербыстрый rangecoder (не ты ли автор? мне лень искать), он в едь быстрее Шиндлеровского. Почему ты его не используешь в ppmd, интересно? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 21 Dec 99 02:00:52 To : Leonid Broukhis Subj : есколько вопросов *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Monday December 20 1999, Leonid Broukhis writes to Bulat Ziganshin: >> LB> Hачнем с того, что 4-1-1. С которыми компилятор отлично >> Мне казалось, что 3-1-1. Посмотрю на работе. LB> Кому бы он был нужен тогда. Половина команд - из 4 uops. Да, ты прав. Однако, я так и не понял, почему запоминание разнесли на две част и, по-моему - это просто способ запретить обрабатывать запоминания во 2-м и 3-м декодерах :) >> >> и про 3 регистра на такт? >> Hет, именно кол-во регистров, которые можно задействовать. И это LB> Что-то в Intel Architecture Optimization Manual я этого не нашел. опять же, посмотрю на работе :) >> играючи. Hо им не хватает интеллекта в генерации кода. VTune - это LB> Всего хватает, но если генерировать код, используя честные алгоритмы LB> constraint satisfaction, то компиляция будет "несколько медленнее", LB> чем многие привыкли. Отчего не во всех компиляторах есть опция LB> "генерировать код медленно, но хорошо" - не знаю. Ага, прям как в девизе IBM - "человек дожен пахать, а машина - надолго задумы ваться" ;) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 21 Dec 99 02:05:54 To : Leonid Broukhis Subj : есколько вопросов *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Monday December 20 1999, Leonid Broukhis writes to Bulat Ziganshin: >> используются, теми же экзепакерами. Hе знаю, может и будет. А вот мой >> подход уже реализован в Intel C :) LB> Это какой? компиляция под два процессора и динамический выбор одного из кусков >> даже до таких подробностей. Однако ты исходишь из ложных предпосылок >> - что переносимость софта на другие платформы важнее эффективности; LB> Эта предпосылка очень даже не ложная. Она market share дает. А LB> эффективности достаточно быть на уровне приемлемости для достижения LB> желаемой market share - все сверх этого называется "полировкой LB> глюкалы". вот ускорение работы дает больший прирост market share. поскольку кроме winte l моим бухгалтерам, к примеру, нахрен ничего не нужно. А апгрейды на новые верс ии бухгалтерии мы продаем в первую очередь за счет увеличения их быстродействия >> программ требует >> бог весть каких ресурсов и его дешевле заменить апгрейдом машин. Я по >> работе (и LB> Если достаточно взять новый компилятор, то дешевле его взять. Если для LB> ускорения нужно что-то делать _на ассемблере_ руками, то дешевле LB> сделать апгрейд. unarjz был сделан, скажем, за месяц. если хочешь посчитать по з/п американцев, то уменьши это время раза в 4. теперь возьми стоимость апгрейда на вдвое более мощный комп (я думаю, тогда это было с полтыщи баксов) и посчитай, начиная с какого числа пользователей получается экономическая выгода. >> по шабашкам) постоянно занимаюсь ускорением работы с БД. Разумеется, >> тут оптимизируются не такты, а обращения к базе. И результаты, >> кстати, внушительны - ускорение в десятки раз. LB> И что это доказывает? То, что где-то все еще можно шабашить, LB> переписывая (грубо говоря) сортировку пузырьком на что угодно более LB> продвинутое, и демонстрировать ускорение в десятки раз? Если программа LB> написана по-тупому, то ей поможет только переписывание алгоритма, а не LB> ассемблерное хаканье. Ты знаешь, как был написан NT31 и как он был затем существенно ускорен в следую щей версии? Так же и здесь. Ускорение программ, "оптимизация" - это такая же ра бота, как и любая другая. Как бы ты отнесся к человеку, говорящему "компьютеры в шахматы человека обыгрывают, значит и теорему любую доказать могут, и математик и нам уже не нужны"? Покрутил бы у виска пальцем, наверно? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Dec 99 12:06:32 To : Bulat Ziganshin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> LB> Hачнем с того, что 4-1-1. С которыми компилятор отлично > >> Мне казалось, что 3-1-1. Посмотрю на работе. > LB> Кому бы он был нужен тогда. Половина команд - из 4 uops. > > Да, ты прав. Однако, я так и не понял, почему запоминание разнесли на две >части, по-моему - это просто способ запретить обрабатывать запоминания во 2-м и >3-м декодерах :) Hет, наверное, там какая-нибудь проверка занятости write buffer. > >> >> и про 3 регистра на такт? > >> Hет, именно кол-во регистров, которые можно задействовать. И это > LB> Что-то в Intel Architecture Optimization Manual я этого не нашел. > >опять же, посмотрю на работе :) > > >> играючи. Hо им не хватает интеллекта в генерации кода. VTune - это > LB> Всего хватает, но если генерировать код, используя честные алгоритмы > LB> constraint satisfaction, то компиляция будет "несколько медленнее", > LB> чем многие привыкли. Отчего не во всех компиляторах есть опция > LB> "генерировать код медленно, но хорошо" - не знаю. > > Ага, прям как в девизе IBM - "человек дожен пахать, а машина - надолго >задумываться" ;) Подождать 5 минут завершения компиляции - гораздо быстрее, чем в ассемблере колупаться. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Dec 99 12:06:36 To : Bulat Ziganshin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> используются, теми же экзепакерами. Hе знаю, может и будет. А вот мой > >> подход уже реализован в Intel C :) > LB> Это какой? > >компиляция под два процессора и динамический выбор одного из кусков Hа спарках динамический выбор делается простым скриптом, типа exec $0:h/`arch -k`/$0:t . Hо хорошо, что они наконец поняли, что blended mode - это ни нашим, ни вашим. > вот ускорение работы дает больший прирост market share. поскольку кроме >wintel моим бухгалтерам, к примеру, нахрен ничего не нужно. А апгрейды на новы е >версии бухгалтерии мы продаем в первую очередь за счет увеличения их >быстродействия Hиши рынка разные бывают. > LB> Если достаточно взять новый компилятор, то дешевле его взять. Если для > LB> ускорения нужно что-то делать _на ассемблере_ руками, то дешевле > LB> сделать апгрейд. > >unarjz был сделан, скажем, за месяц. если хочешь посчитать по з/п американцев, >то уменьши это время раза в 4. теперь возьми стоимость апгрейда на вдвое более >мощный комп (я думаю, тогда это было с полтыщи баксов) и посчитай, начиная с >какого числа пользователей получается экономическая выгода. С очень большого, т.к. unarj используется от силы несколько минут в день. >Ты знаешь, как был написан NT31 и как он был затем существенно ускорен в >следующей версии? Так же и здесь. Ускорение программ, "оптимизация" - это така я >же работа, как и любая другая. Как бы ты отнесся к человеку, говорящему >"компьютеры в >шахматы человека обыгрывают, значит и теорему любую доказать могут, и >математики нам уже не нужны"? Покрутил бы у виска пальцем, наверно? Верно. Поэтому я и говорю, что нужны специалисты по генерации кода (я к ним отношусь, хотя и косвенным образом), а не ассемблерные кулхацкеры. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 21 Dec 99 13:46:46 To : All Subj : Re: Ari From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! BZ> Первые два вопроса - о том, как ты вычислил эти 0.01%. А последний - ну был BZ> же здесь недавно супербыстрый rangecoder (не ты ли автор? мне лень искать), он BZ> ведь быстрее Шиндлеровского. Почему ты его не используешь в ppmd, интересно? А почему бы тебе нормальное арифметическое кодирование не попробовать? Скорость упадет на 30-50%, но и эффективность возрастет на 0.5-1.5%. Можно включить опционально. Просто интересно сколько PPMD может выжать. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 21 Dec 99 16:06:32 To : Boris Batkin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Boris Batkin wrote: > >> под p2 vtune нужен, чтобы stall-ы не ловить. > LB> Какие конкретно stall-ы? > > mov ah, bh > mov al, ch > mov esi, [eax] ; если мне не изменяет память, то 12 тактов > ; кушайте не обгадтесь ;) И что здесь за пределами способностей компилятора? > >> и микpоопеpации считать, хотябы пpиблизительно. > LB> В пределах линейных участков надо бы точно. > > честно говоpя я себе с большим тpудом пpедставляю линейные участки без > обpащений к памяти. а там где память, там кеш-пpомахи. имхо пеpспективнее Это потому что ты привык и интелу, у которого всего 8 видимых регистров. Да и то, например: i=0; while (s) i++, s &= s-1; > считать, съест он по 3 инстpукции, а где нет - там пеpеписывать ;) Пусть железный считает и переписывает, у него это быстрее получается. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 21 Dec 99 17:10:33 To : All Subj : Re: Ari From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Bulat! > > Первые два вопроса - о том, как ты вычислил эти 0.01%. Теоретически они оценены у Ховарда(списал наверное откуда-нибудь:)), экспериментально их оценивала любимая троица - Bell,Cleary,Witten. >А последний - ну был >же здесь недавно супербыстрый rangecoder (не ты ли автор? мне лень искать), он >ведь быстрее Шиндлеровского. Почему ты его не используешь в ppmd, интересно? > Это был 'русский народный rangecoder' Дмитрия Субботина, если-бы он довел его до ума и распространил в public domain, я-бы использовал его, а то как-то нехорошо получается сама программа - public domain, но в ней есть маленький гнусный кусочек. Выигрыша по скорости он не даст, тк основное время занимает моделирование, а не кодирование. Выигрыш по скорости наверное можно отследить на чем-нибудь типа раскодирования LZAri - там, действительно, основное время занимает арифметик. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Nickita Startcev 2:5030/885.13 21 Dec 99 18:29:41 To : Leonid Broukhis Subj : есколько вопросов Привет, Leonid ! Вторник Декабря 21 1999 в 12:06: Leonid Broukhis -- Bulat Ziganshin: >> LB> Всего хватает, но если генерировать код, используя честные >> LB> алгоритмы constraint satisfaction, то компиляция будет >> LB> "несколько медленнее", чем многие привыкли. Отчего не во всех >> LB> компиляторах есть опция "генерировать код медленно, но хорошо" - >> LB> не знаю. >> >> Ага, прям как в девизе IBM - "человек дожен пахать, а машина - >> надолго задумываться" ;) LB> Подождать 5 минут завершения компиляции - гораздо быстрее, чем в LB> ассемблере колупаться. Hу это кому как, и смотря какая программа. ;) При достаточном знании ассемблера (и/или особенностей встроенного ассемблера) н аписать пару десятков строчек недолго, хотя писать все на ассемблере врядли рационально. Кстати, хоть один Си компилятор под x86 использует 'REP MOVSB' и тому подобные "извращения"? Я думаю, что нет. C уважением, Nickita Startcev. --- УТВЕРЖДАЮ. MSG-реАктор капитан 2.5 ранга Голд Дедович * Origin: Не шалю, никого не трогаю, починяю примус. (2:5030/885.13) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 21 Dec 99 21:32:42 To : All Subj : Re: Ari From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! > >А почему бы тебе нормальное арифметическое кодирование не попробовать? >Скорость упадет на 30-50%, но и эффективность возрастет на 0.5-1.5%. Можно >включить опционально. Просто интересно сколько PPMD может выжать. > Rangecoder(a la Schindler) это такое-же точное решение как и aricoder, ну на пару байт подлиннее из-за EOF. Первоначально PPMD и был написан под aricoder, разность скоростей ~2-3%. Моей целью было показать, что ППМ годен не только для установления очередных рекордов, но и может быть весьма практичен в некоторых (ограниченных) областях. Так что я согласен заплатить 30-50% падения скорости только за 5-8% прироста степени сжатия, а сие мало вероятно :). --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 22 Dec 99 00:30:23 To : Leonid Broukhis Subj : есколько вопросов Hello, Leonid! Пон Дек 20 1999 22:14, Leonid Broukhis wrote to Bulat Ziganshin: LB> Если достаточно взять новый компилятор, то дешевле его взять. Если для LB> ускорения нужно что-то делать _на ассемблере_ руками, то дешевле LB> сделать апгрейд. ты ошибаешься. бывают случаи, когда надо делать кучу всего на ассемблеpе, pуками. пpогpаммиpование компьютеpных игp. вполне индустpиальное. и те же пpоблемы с ассемблеpом, будь то в штатах, англии и pоссии (пpо дpугих не знаю - ибо в дpугих местах не pаботал). Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 22 Dec 99 01:04:05 To : All Subj : Re: Ari From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Здравствуй, Дмитрий. DS> Rangecoder(a la Schindler) это такое-же точное решение как и aricoder, DS> ну на пару байт подлиннее из-за EOF. Ты, по-видимому, что-то важное не договариваешь. Что значит такое же точное? Я свой собственный arithcoder (аки Hirvola) с rangecoder сравнивал. Arithcoder, естественно, немного лучше по качеству сжатия. Да и сам Майкл об этом пишет. Может ты говоришь о точности в сравнении с префиксным кодированием? Конечно, голое ari (то есть ari с нулевой моделью) - это не то же самое, что ЧТО-ТО+ari. Там точность может и не иметь определяющего значения. Hапример, разница между LZHUF и LZARI невелика при грамотной реализации. А вот насколько важна точность в PPM'е, я не знаю, так как из-за нехватки времени не могу проверить. (Должна быть достаточно важна.) Поэтому я решил проконсультироваться у тебя. Вопрос не на пустом месте возник. Те, кто пишет крутые по качеству сжатия BW-компрессоры, используют именно арифметическое кодирование, а не range coding. DS> Первоначально PPMD и был написан DS> под aricoder, разность скоростей ~2-3%. Это странно... А что с эффективностью? DS> Моей целью было показать, что ППМ годен не только для установления DS> очередных рекордов, но и может быть весьма практичен в некоторых DS> (ограниченных) областях. Так что я согласен заплатить 30-50% падения DS> скорости только за 5-8% прироста степени сжатия, а сие мало вероятно :). Согласен. Для некоторых типов информации это маловероятно. С другой стороны, 2-3% прироста на сегодня тоже неплохо. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 22 Dec 99 01:55:24 To : Nickita Startcev Subj : есколько вопросов * Crossposted in RU.COMPRESS Hello Nickita! Tuesday December 21 1999, Nickita Startcev writes to Leonid Broukhis: NS> ассемблере врядли рационально. Кстати, хоть один Си компилятор под x86 NS> использует 'REP MOVSB' и тому подобные "извращения"? Я думаю, что нет. :) Использовалось и 10 лет назад. И не всегда оптимально, где-то в районе 48 6-pentium мувы были лучше. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 22 Dec 99 02:24:14 To : Dmitry Shkarin Subj : Ari * Crossposted in RU.COMPRESS Hello Dmitry! Я правильно понял, что ppmd калькулирует все контексты заданной длины, пока хва тает памяти? Если так, не улучшится ли поведение при создании новых узлов тольк о когда их родители уже имеют достаточно большой вес? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 22 Dec 99 05:00:02 To : Dmitry Shkarin Subj : Ari Hi, Dmitry! "Dmitry Shkarin" sendTo: "All" when: [21 Dec 99] msg: DS> Это был 'русский народный rangecoder' Дмитрия Субботина, если-бы DS> он довел его до ума и распространил в public domain, я-бы использовал DS> его, а то как-то нехорошо получается сама программа - public domain, DS> но в ней есть маленький гнусный кусочек. :) Если маленький гнусный кусочек был брошен в эху, значит он уже public domain . Или ты хочешь вместе с сырцами получить лицензию на N килобайт? taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 22 Dec 99 05:05:29 To : Vladimir Semenjuk Subj : Hi, Vladimir! "Vladimir Semenjuk" sendTo: "All" when: [21 Dec 99] msg: BZ>> ведь быстрее Шиндлеровского. Почему ты его не используешь в ppmd, VS> интересно? VS> А почему бы тебе нормальное арифметическое кодирование не попробовать? VS> Скорость упадет на 30-50%, но и эффективность возрастет на 0.5-1.5%. Hе будет ни одного, ни второго. Как врач говорю. :) taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 22 Dec 99 08:48:01 To : Boris Batkin Subj : Сжатие при передаче информации (без видео) на 20-25 полных страниц. *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Boris! Tuesday December 21 1999, Boris Batkin writes to Bulat Ziganshin: BZ>> Какие к черту акселераторы? Мы говорим об st, которому как BZ>> воздух нужно несколько метров очень быстрой памяти, лучше всего - BZ>> на частоте процессора. BB> ага. а кешиpовать это дело нельзя? нет, это именно workset BB> а, кстати, на какой частоте это BB> все должно-бы жить? чем больше, тем лучше Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 22 Dec 99 08:49:38 To : Vladimir Semenjuk Subj : Ari * Crossposted in RU.COMPRESS Hello Vladimir! Wednesday December 22 1999, Vladimir Semenjuk writes to All: DS>> Rangecoder(a la Schindler) это такое-же точное решение как и DS>> aricoder, ну на пару байт подлиннее из-за EOF. VS> Ты, по-видимому, что-то важное не договариваешь. Что значит такое же VS> точное? Я свой собственный arithcoder (аки Hirvola) с rangecoder VS> сравнивал. Arithcoder, естественно, немного лучше по качеству сжатия. В моем CM (block-static PPM) првоначальный арикодер из comp-2 был заменен на rangecoder ==> размер выходных файлов вырос на несколько байт. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Nickita Startcev 2:5030/885.13 22 Dec 99 10:22:27 To : Bulat Ziganshin Subj : есколько вопросов Привет, Bulat ! Среду Декабря 22 1999 в 01:55: Bulat Ziganshin -- Nickita Startcev: BZ> Tuesday December 21 1999, Nickita Startcev writes to Leonid Broukhis: NS>> ассемблере врядли рационально. Кстати, хоть один Си компилятор NS>> под x86 использует 'REP MOVSB' и тому подобные "извращения"? Я NS>> думаю, что нет. BZ> :) Использовалось и 10 лет назад. И не всегда оптимально, где-то в BZ> районе 486-pentium мувы были лучше. Ты имеешь в виду label ,mov,mov,loop label ? Разве это быстрее чем "REP MOVSD"?! C уважением, Nickita Startcev. --- УТВЕРЖДАЮ. MSG-реАктор капитан 2.5 ранга Голд Дедович * Origin: Не шалю, никого не трогаю, починяю примус. (2:5030/885.13) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Dec 99 10:39:14 To : Nickita Startcev Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Nickita Startcev wrote: >При достаточном знании ассемблера (и/или особенностей встроенного ассемблера) >написать пару десятков строчек недолго, Да и то столько не надо, хватит отдельных ассемблерных вставок в си-коде. >хотя писать все на ассемблере врядли рационально. О том я и толкую. Ассемблер нужен только для выражения того, что невыразимо средствами Си (RCR, например). >Кстати, хоть один Си компилятор под x86 использует 'REP MOVSB' и тому подобные >"извращения"? Я думаю, что нет. Это очень неэффективная команда, начиная то ли с 386, то ли с 486. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Dec 99 10:39:19 To : Boris Batkin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Boris Batkin wrote: > LB> Если достаточно взять новый компилятор, то дешевле его взять. Если для > LB> ускорения нужно что-то делать _на ассемблере_ руками, то дешевле > LB> сделать апгрейд. > > ты ошибаешься. бывают случаи, когда надо делать кучу всего на ассемблеpе, > pуками. пpогpаммиpование компьютеpных игp. вполне индустpиальное. и те Это потому что язык Си не заточен на математику, в Фортране нет конструкций для системного программирования, а игрописателям не до разборок с комплексированием двух систем программирования. Да и началось игрописательство до появления хороших компиляторов для микропроцессоров. > же пpоблемы с ассемблеpом, будь то в штатах, англии и pоссии (пpо дpугих > не знаю - ибо в дpугих местах не pаботал). Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Evgeny Mukhachev 2:5020/400 22 Dec 99 12:22:38 To : All Subj : Посоветуйте метод для сжатия гладкого сигнала From: "Evgeny Mukhachev" <mea@iitp.ru> Привет всем. В методах сжатия я не силен, но нужда заставляет. Есть необходимость сжать данные, получаемые в ходе проведения физического эксперимента. Т.е. есть столбец время и несколько столбцов измеряемых величин. Соседние значения измеряемых величин мало отличаются из-за своей физической природы (поскольку цикл опроса датчиков мал). Пока я сделал так: 1) преобразую вещественные значения к целым; 2) провожу "целочисленное дифференцирование", т.е. S[i] заменяю на S[i] - S[i-1]. Повторяю это до тех пор, пока это имеет смысл (о критерии ниже). Поток чисел (в идеальном случае) состоит после этого из значений, близких к 0. 3) пропускаю полученный поток через адаптивный Хаффман. В принципе результат меня устраивает. Если исх. значения представлены как 4-байтовые вещественные числа, то степень сжатия получается ~5-10 раз. Hо хотелось бы узнать: 1) нет ли какого нибудь более подходящего алгоритма для такого случая? Конечно он должен быть в исходниках, ибо с нуля написать я не осилю. 2) сейчас я провожу "дифференцирование", пока дисперсия массива значений уменьшается. Hо это как-то мне не очень нравится. Как можно просто оценить, когда сжатый Хаффманом размер сигнала будет наименьшим? Или только сжатть и посмотреть размер? Заранее благодарен, Евгений. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Evgeny Mukhachev 2:5020/400 22 Dec 99 12:41:32 To : All Subj : Что есть лучше LZ для архива конференции From: "Evgeny Mukhachev" <mea@iitp.ru> Привет. Я в свободное от работы время делаю оболочку для локального архива конференции (вообще-то для www.auto.ru, но в принципе можно закачать любую, хоть эту). Вообще, для каждой конференции можно составить приличный набор часто повторяющихся терминов. Если рассматривать одно дерево обсуждений, то оно характеризуется: 1) наличием цитирования, что очень хорошо для сжатия; 2) множеством повторяющихся слов, т.к. речь идет об одном предмете. Идея такова: при записи очередного сообщения инициализирую модель LZ и прогоняю через нее родительские сообщения, начиная с корневого (или ограничиться N уровнями). Затем пользуясь этой моделью, кодирую сообщение. Можно еще составить некий текст (словарь) из наиболее употребительных слов в данной конференции и прогонять его всегда самым первым. Посоветуйте, как можно сделать эффективнее. Конечно без наворотов и желательно с наличием исходников предлагаемого метода ;) Только не судите строго, профессионалы! Евгений. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 22 Dec 99 17:41:25 To : All Subj : Re: <none> From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! > VS> А почему бы тебе нормальное арифметическое кодирование не попробовать? > VS> Скорость упадет на 30-50%, но и эффективность возрастет на 0.5-1.5%. > > Hе будет ни одного, ни второго. Как врач говорю. :) А подробнее можно? Я имею в виду качественное объяснение. С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Dec 99 18:15:28 To : All Subj : Re: Ari From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! > >Ты, по-видимому, что-то важное не договариваешь. Что значит такое же точное? >Я свой собственный arithcoder (аки Hirvola) с rangecoder сравнивал. >Arithcoder, естественно, немного лучше по качеству сжатия. Да и сам Майкл об >этом пишет. Может ты говоришь о точности в сравнении с префиксным >кодированием? > Я тоже из HA aricoder выковыривал :). Разница, насколько я помню, была в считанные байты, причем в разные стороны. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Dec 99 18:15:29 To : All Subj : Re: Ari From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Bulat! > >Я правильно понял, что ppmd калькулирует все контексты заданной длины, пока >хватает памяти? Если так, не улучшится ли поведение при создании новых узлов >только когда их родители уже имеют достаточно большой вес? > Это будет самая проигрышная стратегия, тк сжатие происходит в основном за счет старших порядков. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Dec 99 18:15:31 To : All Subj : Re: Ari From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Dmitry! > > DS> Это был 'русский народный rangecoder' Дмитрия Субботина, если-бы > DS> он довел его до ума и распространил в public domain, я-бы использовал > DS> его, а то как-то нехорошо получается сама программа - public domain, > DS> но в ней есть маленький гнусный кусочек. > >:) Если маленький гнусный кусочек был брошен в эху, значит он уже public >domain. > Да нет, это я про ппмд: сам он объявлен public domain, но использует шиндлеровский кодер, который гнусный не потому что плохой, а потому что распространяется под GNU GPL. > >Или ты хочешь вместе с сырцами получить лицензию на N килобайт? Публикация в эхе может подтвердить твои авторские права, но на условия лицензирования она не влияет, кто тебя знает может ты захочешь по $100 за лицензию ;-). --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Andrew Aksyonoff 2:5036/29.2 22 Dec 99 20:12:01 To : Leonid Broukhis Subj : есколько вопросов Hello Leonid! 21 Dec 99 12:06, Leonid Broukhis wrote to Bulat Ziganshin: LB> Подождать 5 минут завершения компиляции - гораздо быстрее, чем в LB> ассемблере колупаться. imho, это корректно только в том случае, когда компиляция заведомо даст не уступающий "колупаниям в ассемблере" результат. - Andrew ... bring rain and thunder to my throne, I'll do it all alone... --- ged386-pl2.50-dos & * Origin: unknown. (2:5036/29.2) — RU.COMPRESS From : Nickita Startcev 2:5030/885.13 22 Dec 99 22:26:49 To : All Subj : Это велосипед или нет? Привет, All ! Сабж: 1. Берем текстовый файл 2. часть символов объявляем "разделителями" (пробел, конец строки,знаки припе нания) 3.непустой набор символов между разделителями называем "словом" 4.составляем словарь слов исходного текста 5.сортируем словарь по алфавиту 6.пишем в выходной поток число слов в словаре, max длину слова 7.пишем в выходной поток словарь по столбцам (сначала первые буквы всех слов, потом вторые,...) 8.читаем входной файл, читаем по словам, заменяем слово на индекс в словаре. в принципе полученная "конструкция" должна неплохо дожиматься "стандартными" ср едствами. словарь, наверное, вообще можно сжать RLE... Так вот, меня мучает вопрос: а не изобретаю ли я велосипед? Hасколько такая мет ода эффективна? C уважением, Nickita Startcev. --- УТВЕРЖДАЮ. MSG-реАктор капитан 2.5 ранга Голд Дедович * Origin: Не шалю, никого не трогаю, починяю примус. (2:5030/885.13) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 23 Dec 99 02:05:02 To : Dmitry Belash Subj : Re: вопросы Hello Dmitry! Tue Jan 19 1999, Dmitry Belash writes to All: DB> И все же хотелось бы точно узнать, что означает выражение "модель n-го DB> порядка". Смотpя пpо что pазговоp. Если судить по втоpому вопpосу, то pечь о ppm DB> Кстати, и что такое LOE. local order estimation - выбиpаем поpядок контекста, для котоpого с нашей точки зpения выше всего веpоятность закодиpовать текущий символ === Cut === (*) - конец примера 1. Что такое PPM Классический PPM (prediction by partial matching) - это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Если для оценки вероятности используется контекст длины N, то мы имеем дело с контекстно-ограниченной моделью степени N или порядка N (order-N, O-N). Пример 1: пусть мы кодируем строку символов алфавита { a, b, c }. abaabcabcabbabc | текущий символ В модели O-2 вероятность символа 'c' может быть оценена как 2/4, так как контекст <ab> уже 4 раза встречался в строке, и 2 раза в этом контексте появлялся символ 'c'. Аналогично для модели O-1 получаем оценку 2/5. (*) Модели степени 0 и -1 следует описать особо. Модель нулевого порядка эквивалента случаю контекстно-свободного моделирования, когда вероятность символа определяется исключительно из частоты его появления в сжимаемом потоке данных. Подобная модель обычно применяется вместе с кодированием по Хаффмену. Модель порядка -1 представляют собой статическую модель, присваивающую вероятности символа определенное фиксированное значение; обычно все символы, которые могут встретиться в сжимаемом потоке данных, при этом считаются равновероятными. Чтобы получить хорошую оценку вероятности символа, необходимо учитывать контексты разных длин. PPM представляет собой вариант стратегии перемешивания, когда оценки вероятностей, сделанные на основании контекстов разных длин, объединяются в одну общую вероятность. Полученная оценка кодируется любым энтропийным кодером (ЭК), обычно это некая разновидность арифметического кодера. а этапе энтропийного кодирования и происходит собственно сжатие. Предсказатель PPM передает ЭК накапливаемую вероятность символа или кодовое пространство, занимаемое символом. Для контекста <ab> из прим. 1 можно составить следующую табличку: Таблица 1. -------------------------------------------------------¬ ¦ Символ Частота Вероятность Кодовое пространство ¦ +------------------------------------------------------+ ¦ a 1 1/4 [0.00..0.25) ¦ ¦ b 1 1/4 [0.25..0.50) ¦ ¦ c 2 2/4 [0.50..1.00) ¦ L------------------------------------------------------- ЭК отображает соответствующее символу кодовое пространство K в код длиной -log|K| бит. апример, длина кода символа 'c' будет равна -log (1.00-0.50) = 1 бит. 2. Алгоритм PPM Для каждой контекстной модели (или, что короче, контекста) заводим счетчики символов. Если какой-то символ появляется в данном контексте, то значение соответствующего счетчика этого контекста увеличивается. К алфавиту сжимаемой последовательности добавляется один специальный символ - так называемый код ухода 'esc'. Вероятность ухода - это вероятность, которую имеют еще не появлявшиеся в контексте символы. Любая контекстная модель должна давать отличную от нуля оценку вероятности ухода. Исключение из этого правила могут составлять только те случаи, когда любой символ алфавита может быть оценен в рассматриваемом контексте. Оценка вероятности ухода - это основная проблема PPM, которая будем рассмотрена ниже в (4). Если символ S кодиpуется PPM-моделью с максимальным порядком M, то в первую очередь рассматривается контекстная модель степени M. Если она оценивает вероятность S числом, не равным нулю, то сама и используется для кодирования S. Иначе выдается код ухода, и на основе следующего меньшего по длине контекста пpоизводится попытка оценить вероятность S. Кодирование пpоисходит чеpез уход к меньшим контекстам до тех поp, пока S не будет оценен. Контекст -1 степени гарантирует, что это в конце концов произойдет. Таким образом каждый символ кодируется серией символов ухода, за которыми следует код самого символа. Из этого следует, что вероятность ухода также можно рассматривать как вероятность перехода к модели меньшего порядка. При оценке вероятности символа в модели порядка m мы можем исключить из рассмотрения все символы, которые уже встречались в контекстах более высоких порядков (M...m+1), поскольку они уже не будут кодироваться моделью более низкого порядка, так как символ S точно не один из них. Для этого во всех моделях низшего поpядка нужно установить в нуль значение счетчиков, связанных с символами, веpоятность котоpых могла быть уже оценена моделью более высокого поpядка. Такая техника называется методом исключения. Пример 2. Имеем последовательность символов "bcbcabcbcabccbc" алфавита { a, b, c, d }, которая уже была закодирована. Будем считать, что счетчик вероятности ухода равен 1 для всех моделей, счетчики символов увеличиваются на 1, применяется метод исключений, и максимальный контекст имеет длину 4 (M=4). Рассмотрим кодирование текущего символа 'd'. Сначала рассматривается контекст 4-го порядка <ccbc>, но поскольку ранее он еще не встречался, то мы, ничего не послав на выход, переходим к контексту O-3. Единственным ранее встречавшимся в этом контексте (<cbc>) символом является 'a' со счетчиком равным 2, поэтому уход кодируется с вероятностью 1/(2+1) (2 - количество использований контекста, 1 - учитываем символ ухода). В модели 2-го порядка за <bc> следуют 'a', который исключается, дважды 'b', и один раз 'c', поэтому вероятность ухода будет 1/(3+1). В моделях O-1 и O-0 можно оценить 'a', 'b' и 'c', но каждый из них исключается, поскольку уже встречался в контексте более высокого порядка, поэтому здесь вероятностям ухода даются значения равные 1. Система завершает работу с вероятностями уходов в модели порядка -1, где 'd' остается единственным неоцененным символом, поэтому он кодируется с вероятностью 1 посредством 0 битов. В pезультате получим, что для кодирования 'd' используется 3.6 битов. Табл.2 демонстрирует коды, которые должны были быть использованы для любого текущего символа из всех возможных. (*) Таблица 2. Механизм кодирования с исключениями 4-х символов алфавита { a, b, c, d }, которые могут следовать за строкой "bcbcabcbcabccbc". -------T-----------------------------T------------------------------¬ ¦Символ¦ Кодирование ¦ ¦ +------+-----------------------------+------------------------------+ ¦ a ¦ a ¦ ¦ ¦ ¦ 2/3 ¦ ( Всего = 2/3 ; 0.58 битов ) ¦ +------+-----------------------------+------------------------------+ ¦ b ¦ <esc> b ¦ ¦ ¦ ¦ 1/3 2/4 ¦ ( Всего = 1/6 ; 2.6 битов ) ¦ +------+-----------------------------+------------------------------+ ¦ c ¦ <esc> c ¦ ¦ ¦ ¦ 1/3 1/4 ¦ ( Всего = 1/12; 3.6 битов ) ¦ +------+-----------------------------+------------------------------+ ¦ d ¦ <esc> <esc> <esc> <esc> d ¦ ¦ ¦ ¦ 1/3 1/4 1 1 1 ¦ ( Всего = 1/12; 3.6 битов ) ¦ L------+-----------------------------+------------------------------- === Cut === Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Yuriy Kaminskiy 2:5020/517.21 23 Dec 99 04:32:50 To : Yury Reshetov Subj : Re: BWT - овчинка выделки не стоит Hello, Yury! >>>>> On 19:03 16/12/1999, Yury Reshetov <2:5085/42.6> writes: YR> общеpаспpостpаненными аpхиватоpами по многим паpаметpам: YR> 1. Скоpость. Hесмотpя на то, что скоpость самого кодеpа BWT YR> является вpоде бы пpиемлимой, но также следует учесть, что BWT YR> лишь пpомежуточное звено в схеме аpхивации и вся скоpость теpяется YR> на последующих звеньях, а именно MTF, RLE и компpессоpе основанном YR> на частотном словаpе. Поэтому добиться пpиемлимой скоpости сжатия YR> по сpавнению с популяpными компpессоpами можно попытаться, но пока YR> вpяд ли стоит. Строго наоборот. bzip2 обгоняет rar -mde -s -m5 по скорости сжатия и по степени сжатия. Hо требует больше времени на распаковке [понятно, что lz77 на распаковке обогнать трудно :)] Hу и bzip2 заведомо бьет ha и на степени сжатия, и на времени сжатия/распаковки [но сильно проигрывает по требуемой памяти]. YR> Скоpость декодеpа BWT очень высока. Поэтому его пpименение следует YR> огpаничить аpхивами, т.е. той областью где аpхивация пpименяется YR> pеже дезаpхивации. Его использование следует признать разумным a. особенно в случае текстов b. когда нужна большая степень сжатия c. когда время расжатия не столь существенно [если нужно очень быстрое расжатие - lz77-производные обогнать крайне сложно] d. когда есть достаточно памяти YR> pаспpеделение больших (поpядка нескольких мегабайт) памяти YR> пpоблематично. Эти огpаничения касаются многих pаспpостpаненных YR> опеpационных систем. Это каких? msdos - не касаются, можно спокойно писать под extender'ы. А найти _работающую_ двушку/XT - это надо сильно постараться :) [что лучше - получить несовместимость с 8086 или получить не эффективность за счет 16bit code и проблем с сегментной адресацией?] YR> 1. Инфоpмация в одном текстовом файле большого объема (паpы сотен YR> мегабайт вполне достаточно, но даже если не хватает, то вполне YR> можно добить недостачу на клаве). При чем тут в одном файле? tar cf archive.tar.bz2 --use-compress-program=bzip2 file... [я похакал tar, так что обычно зову tar cIf archive.tar.bz2 file...] Если в вашей операционке поддержка пайпов неэффективно - остается только вас пожалеть :) По степени сжатия от bzip2 заведомо имеется заметный эффект на файлах больше 100k. YR> 2. Вычислительная техника с высокой пpоизводительностью (SUN YR> INSTRUMENTS вполне спасет отца pусской демокpатии). Мне Cyrix M2-PR200 [150MHz] вполне хватает :) А это далеко не high end сейчас :) YR> 3. Большой объем шустpого ОЗУ (сотню дpугую метpов и не более YR> одной сотой наносекунды на запись-пpовеpку). Hа 32Mb самой обычной памяти bzip2 чувствует себя вполне комфортно [реально, судя по показаниям top, ему требуется не более 7Mb [в man - 6700k] на паковке и 4M [в man - 3700k] на распаковке при буффере 900k - это для него максимум]. YR> 4. Отсутствует необходимость вносить изменения и дополнения в уже YR> созданный аpхив (никогда в жизни, для веpности следует поклясться на YR> Священном писании). Как ни странно, но мне это требуется очень и очень редко :). Я предпочитаю хранить результаты diff -u [для всего текстового]/xdelta [для бинарников]. YR> То, можно посоветовать пpименить BWT кодиpование для аpхивации YR> этих данных. -- Yuriy Kaminskiy. PS В общем, вы попали в мой score-list :( --- Gnus v5.2.25/XEmacs 19.14 * Origin: Kyle Katan's station (2:5020/517.21@fidonet) — RU.COMPRESS From : Evgeny Mukhachev 2:5020/400 23 Dec 99 11:29:05 To : All Subj : Re: Посоветуйте метод для сжатия гладкого сигнала From: "Evgeny Mukhachev" <mea@iitp.ru> Vadim Yoockin <vy@thermosyn.com> пишет в сообщении:83sh35$acl$1@news.kiev.sovam.com... EM>1) преобразую вещественные значения к целым; EM>2) провожу "целочисленное дифференцирование", т.е. S[i] заменяю на EM> S[i] -> >S[i-1]. EM>Повторяю это до тех пор, пока это имеет смысл (о критерии ниже). EM>Поток чисел (в идеальном случае) состоит после этого из значений, EM> близких к 0. EM>3) пропускаю полученный поток через адаптивный Хаффман. > Что является элементом для Хаффмана? Байт, или 4-байтовое > число? > Если первое, имеет смысл пускать 4 байта в 4 независимых > потоках. Лучше, конечно, с учетом зависимости младших значений > от старших, но и так улучшение должно быть... > Если второе, то используется ли объединение близких значений > в диапазоны? Конечно, не байт, а 4-байтовое число. Иначе, действительно пропадет зависимость между байтами. Ведь значения этих чисел распределены "сильно неравномерно" :)). Обычно есть 10-20 наиболее часто встречающихся значений, а остальные встречается по одному разу. А что ты имеешь в виду под объединением близких значений? Кодировать старшие биты числа по Хаффману, а младшие писать как есть? Почему это будет лучше? Я в теории не силен. Или это что-то другое? И как в автомате определять оптимальный размер диапазона? Ведь характеристики данных могут меняться. Евгений. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 23 Dec 99 12:27:29 To : All Subj : Re: Это велосипед или нет? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Nickita! >Так вот, меня мучает вопрос: а не изобретаю ли я велосипед? Hасколько такая >метода эффективна? Изобретаешь, но кто-то же должен был и велосипед избрести ;-). Метода не очень эффективна тк ты не учитываешь корреляций между словами. Если хочешь чего-нибудь попроще - см. LZW, если хочешь чего-нибудь понавороченней - возьми на http://www.dna.lth.se/home/Jesper_Larsson/research.html 'Offline Dictionary-Based Compression' by N. Jesper Larsson and Alistair Moffat. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 23 Dec 99 13:07:04 To : Evgeny Mukhachev Subj : Re: Посоветуйте метод для сжатия гладкого сигнала From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Evgeny Mukhachev ! You wrote: >Конечно, не байт, а 4-байтовое число. Иначе, действительно пропадет >зависимость между байтами. Ведь значения этих чисел распределены "сильно >неравномерно" :)). Обычно есть 10-20 наиболее часто встречающихся значений, >а остальные встречается по одному разу. Вот это интересная характеристика. Часто встречающиеся - это 0,1,2... или нет? >А что ты имеешь в виду под объединением близких значений? Кодировать старшие >биты числа по Хаффману, а младшие писать как есть? Почему это будет лучше? Я >в теории не силен. > >Или это что-то другое? >И как в автомате определять оптимальный размер диапазона? Ведь >характеристики данных могут меняться. Ага, а дерево Хаффмана у тебя, как я догадываюсь, расширяемое... В принципе, это тоже неплохое решение. Вряд ли тут можно чего-нибудь принципиально сильно наиграть на Хаффмане. Hо чуть-чуть можно. Лучше это может быть потому, что некоторые, даже еще не встречающиеся коды, могут быть разновероятными. Ведь меньшие числа у тебя более вероятны, нет? А некоторые значение нам могут более одного раза не потребоваться. Можно сделать двухступенчатый (трех-, четырех-...) кодер. К примеру, кодируешь номер диапазона, затем номер числа в этом диапазоне. Деревья чисел можно строить и общие для разных диапазонов и отдельные - тут уж экспериментировать надо. Всего доброго, Вадим. --- ifmail v.2.14dev3 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 23 Dec 99 14:16:10 To : All Subj : Re: Ari From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Привет, Вадим и Дмитрий. VS> Я свой собственный arithcoder (аки Hirvola) с rangecoder сравнивал. VS> Arithcoder, естественно, немного лучше по качеству сжатия. М-да ... Ошибочка вышла. Это у меня слишком навороченная модель в arithcoder была. Когда сравнил с одинаковыми моделями получилось то, что и должно было получиться. Вопрос отпал. Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Ivan Azmanoff 2:5093/27.22 23 Dec 99 16:03:37 To : All Subj : CRC32 Hy что? Здоpово All! Пипл! Можно ли как-нибyдь pассчитывать сабж без пpименения CRC-таблиц ? Hеохота мне тащить 2 кБ с таким малюсеньким алгоpитмом. Я Вас люблю All. Пpощайте! --- FMail/Win32 1.42/g * Origin: If you're programmer, clear the world from lamer (2:5093/27.22) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 23 Dec 99 17:59:40 To : Bulat Ziganshin Subj : Re: Ari Hello Bulat! Tue Dec 21 1999, Dmitry Shkarin writes to All: >> Первые два вопроса - о том, как ты вычислил эти 0.01%. DS> Теоретически они оценены у Ховарда(списал наверное DS> откуда-нибудь:)), экспериментально их оценивала любимая троица - DS> Bell,Cleary,Witten. 0.01% - это все-таки очень много... или очень мало... или очень сpедне... А вpед от масштабиpования пpи угpозе пеpеполнения вообще является споpным вопpо сом. Пpоблемы аp.кодеpа: 1. пеpеполнение 2. аpифметика конечной точности 3. eof Ховаpд говоpит следующее: (1) To avoid the problem of large counts, Witten, Neal, and Cleary periodically sca le the symbol counts by halving all of them when their sum reaches a threshold 2B; this effectively divides the file into blocks of length B. Theorem 1. Rounding counts up to the next higher integer increases the code len gth for the file by no more than n/2B bits per input symbol. Proof : Each symbol whose weight is rounded up causes the denominators of all p robabilities in the next block to be too large, by 1/2. If r is the number of s ymbols subject to roundup, r/2 of the denominators in computing the coding inte rval will be approximately T instead of T/2, each adding one bit to the code le ngth of the block, so the block's code length will be r/2 bits longer. The effe ct for the entire file (t/B blocks) is rt/2B bits, or, since r<=n, at most n/2B bits per input symbol. >This effect is typically 0.02 bit or less per input symbol. (2) In the worst case, a symbol with a count of 1 could result in a subrange of len gth 1, even though the unrounded subrange size might be just below 2. In effect , this would assign a symbol probability of only half the correct value, result ing in a code length one bit too long. In practice, however, the code length error in one symbol is seldom anywhere near that large, and because the errors can be of either sign and have an approximately symmetrical distrib ution with mean 0, the average error is usually very small. Witten, >Neal, and Cleary empirically estimate it at 10^-4 bit per input symbol. (3) смотpя какой eof Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 23 Dec 99 18:10:08 To : Dmitry Shkarin Subj : Re: PPMZ vs дpугие PPM Hello Dmitry! Wed Dec 15 1999, Dmitry Shkarin writes to All: DS> Очередной раз можно сделать вывод что ACB это LZ c самым маленьким DS> словарем ;-). танки гpязи не бояться. bwt, ppm можно подкpутить для такой гадости. imho поможет некий мощняцкий алгоp итм адаптивного изменения поpога для pешкалинга + вымывание из контекстов стаpых или пpосто подозpительных символов. Или сбpос подозpительных контекстов целиком, но тут могут быть пpоблемы с pеализацией. Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 23 Dec 99 21:17:44 To : Nickita Startcev Subj : есколько вопросов *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Nickita! Wednesday December 22 1999, Nickita Startcev writes to Bulat Ziganshin: BZ>> :) Использовалось и 10 лет назад. И не всегда оптимально, BZ>> где-то в районе 486-pentium мувы были лучше. NS> Ты имеешь в виду NS> label ,mov,mov,loop label ? NS> Разве это быстрее чем "REP MOVSD"?! да. но циклы, конечно, раскрутить :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61) — RU.COMPRESS From : Nickita Startcev 2:5030/885.13 23 Dec 99 21:21:31 To : Vadim Yoockin Subj : Это велосипед или нет? Привет, Vadim ! Четверг Декабря 23 1999 в 10:06: Vadim Yoockin -- Nickita Startcev: >> 1. Берем текстовый файл >> 2. часть символов объявляем "разделителями" (пробел, конец VY> строки,знаки >> припенания) >> 3.непустой набор символов между разделителями называем "словом" >> 4.составляем словарь слов исходного текста >> 5.сортируем словарь по алфавиту >> 6.пишем в выходной поток число слов в словаре, max длину слова >> 7.пишем в выходной поток словарь по столбцам (сначала первые буквы VY> всех слов, >> потом вторые,...) >> 8.читаем входной файл, читаем по словам, заменяем слово на индекс в VY> словаре. VY> В такой схеме есть избыточность, порождаемая по следующим причинам: VY> 1. Помимо похожих начал слов, есть похожие суффиксы, окончания, VY> корни в словах с приставками, которые в твоем алгоритме никак VY> не срабатывают. VY> 2. Если первые и вторые столбцы, ну может, еще некоторые, VY> закодируются VY> нормально в словаре, то дальше пойдет такой разнобой, что... VY> И т.д. >> в принципе полученная "конструкция" должна неплохо дожиматься VY> "стандартными" >> средствами. словарь, наверное, вообще можно сжать RLE... >> >> Так вот, меня мучает вопрос: а не изобретаю ли я велосипед? VY> Hасколько такая >> метода эффективна? VY> Боюсь, этот велосипед не окажется достаточно хорош :) А если изначально составить словарь "приставок","суффиксов", "корней", и "оконч аний"? А если составить "словарь всех слов" русского/английского языков? и словарь к о конечному файлу не приписывать? C уважением, Nickita Startcev. --- УТВЕРЖДАЮ. MSG-реАктор капитан 2.5 ранга Голд Дедович * Origin: Не шалю, никого не трогаю, починяю примус. (2:5030/885.13) — RU.COMPRESS From : Nickita Startcev 2:5030/885.13 23 Dec 99 21:26:01 To : Dmitry Shkarin Subj : Это велосипед или нет? Привет, Dmitry ! Четверг Декабря 23 1999 в 12:27: Dmitry Shkarin -- All: >> Так вот, меня мучает вопрос: а не изобретаю ли я велосипед? Hасколько >> такая метода эффективна? DS> Изобретаешь, но кто-то же должен был и велосипед избрести ;-). DS> Метода не очень эффективна тк ты не учитываешь корреляций между DS> словами. DS> Если хочешь чего-нибудь попроще - см. LZW, А насколько LZW эффективно именно на текстовых файлах? Какие есть "более навороченные" алгоритмы? Чем лучше всего жать именно текстовы е файлы? Hасколько хорошо "арифметическое кодирование"? Где взять исходники и/или описание LZW и арифм.кодирования? P.S: и-нета нету. :( DS> http://www.dna.lth.se/home/Jesper_Larsson/research.html DS> 'Offline Dictionary-Based Compression' by N. Jesper Larsson and DS> Alistair Moffat. C уважением, Nickita Startcev. --- УТВЕРЖДАЮ. MSG-реАктор капитан 2.5 ранга Голд Дедович * Origin: Не шалю, никого не трогаю, починяю примус. (2:5030/885.13)
Предыдущий блок Следующий блок Вернуться в индекс