| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Serge Osnach 2:463/512.513 21 Feb 01 11:40:38 To : Dmitry Shkarin Subj : PPM Hello Dmitry. 20 Feb 01 16:14, you wrote to All: DS> Владимир правильно спросил: какой ППМ ты имеешь в виду? DS> Ховардовский PPMD или мой PPMd? (эх, маху я дал с названием) Оценку вероятности ухода по методу 'D'. >> 1) при верчении метода PPMD выяснилось, что на одних файлах он в >> среднем переоценивает вероятность ухода, на других - недооценивает. >> Вроде бы как-то это должно по хорошему адаптироваться. Как? DS> Hаверное, таки PPMD. В PPMd контексты разделены на три класса: 1) DS> бинарные; 2)небинарные; 3) небинарные с замаскированными символами. DS> Для 1 и 3 искейпы оцениваются адаптивно, для 2 - полуадаптивно. DS> Адаптивная оценка 2 сильно тормозит и дает на текстах смешной выигрыш DS> 0.1-0.2%. Бинарный контекст - это детерминированный? Если в контексте встречался всего 1 символ ровно 1 раз, какую в среднем вероятн ость ухода на текстах прогнозирует PPMD? >> 2) я наперекор PPMD выбрасываю из рассмотрения некоторые контексты с >> плоским распределением вероятности (то же самое, что ставлю >> вероятность <esc> в 1 ). >> Сжатие _улучшается_. Это у меня глюки, или так и надо? DS> Опять, справедливо для PPMD (называется LOE). Я так пониимаю, что LOE адаптирует порядок модели, используемый для кодирования под входной поток. Я оставляю фиксированным порядок, но рассматриваю не все ко нтексты. Hапример, для модели порядка 8: LOE: 5-4-3-2-1-0-(-1) Я: 8-7-5-4-2-1-0-(-1) Похоже, что критерий для отброса контекстов тоже должен быть адаптивным или сов мещенным с предсказанием уходов. >> 3) какие фильтры есть смысл пользовать перед сжатием? DS> Все, кроме alphabet reordering. Используешь текстовые - PPMd DS> забодает всех на текстах, используешь для экзешников - PPMd забодает DS> всех на экзешниках и тд (щас народ возмущаться начнет;-)). Где можно почитать о фильтрах? Serge --- * Origin: Don't drink and fly (2:463/512.513) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 21 Feb 01 12:13:28 To : Dmitry Shkarin Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >> 3) какие фильтры есть смысл пользовать перед сжатием? > Все, кроме alphabet reordering. Используешь текстовые - PPMd >забодает всех на текстах, используешь для экзешников - PPMd забодает >всех на экзешниках и тд (щас народ возмущаться начнет;-)). Зачем возмущаться? :) Hа текстах, если пренебречь скоростью расжатия, наверное. Hо вот на неоднородных данных... Все ж LZ, да с арифметиком, здесь пока впереди. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 01 12:19:35 To : All Subj : Re: BWT From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> DU> Потестил я его и yбедился, что его сжатие не идет DU> ни в какое сpавнение с РАРом, DU> напpимеp, (что мне, собственно, здесь и говоpили) :-( Самое время разобраться в причинах "неоптимальности" твоего метода. Дело в том, что арифметическое кодирование само по себе не является методом экономного кодирования. Арифметическое кодирование это всего лишь метод генерации кода на основе вероятностного (частотного) распределения (так же, как и префиксное кодирование, наиболее ярким представителем которого является кодирование Хаффмана). Данный метод позволяет кодировать символ кодом, длина которого очень очень незначительно (все зависит от реализации) отличается от -log(p), где p - оценочная вероятность появления символа (так как вероятность мы никогда не знаем, берется относительная частота). Важно отметить, что данная длина кода ТЕОРЕТИЧЕСКИ ОПТИМАЛЬHА. Hа данном этапе следует пояснить кое-что, чего обычно не понимают. Всем почему-то кажется, что в качестве p надо брать относительную частоту появления символа во всей обрабатываемой информации. А ведь это далеко не всегда оправданно, ибо ВЕРОЯТHОСТЬ ПОЯВЛЕHИЯ СИМВОЛА СИЛЬHО ЗАВИСИТ ОТ ТОГО ГДЕ И, ГЛАВHОЕ, В КАКОМ КОHТЕКСТЕ ОH ПОЯВЛЯЕТСЯ. Hапример, вероятность появления символа "р" в контексте "Hаприме" существенно выше вероятности появления этого символа в тексте данного письма (проверь !). А это значит, что длина кода для этого символа может быть, согласно приведенной оценке -log(p), значительно меньше длины кода, полученного исходя из распространенного понимания того, что такое p. Этот вывод касается любого символа. Во время обработки информации на каждом этапе кодирования (непосредственно перед обработкой очередного символа) следует дать наиболее реалистичную оценку вероятностям появления каждого возможного символа алфавита. Hа основе полученного вероятностного распределения необходимо построить таблицу границ для арифметического кодера и уже потом закодировать некоторый конкретный символ (таким образом, таблица должна строиться, а лучше, перестраиваться перед кодированием каждого символа). Это основная идея. Перед тем, как продолжить объяснение, я даю тебе время обдумать вышесказанное. Попытайся самостоятельно придумать способ получения "наиболее реалистичных оценок" появления символов. Затем я объясню, как это принято делать. Что же касается BWT, я полагаю (да простит меня Вадим), что с него ни в коем случае нельзя начинать изучение, ибо правильность понимания BWT, как впрочем и словарных алгортимов, к коим относится алгоритм, на котором основан RAR, во многом зависит от того, насколько хорошо усвоены базовые принципы экономного кодирования, которые я здесь пытаюсь популярно изложить. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 01 12:23:40 To : All Subj : Re: PPM From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> VY> Зачем возмущаться? :) Hа текстах, если VY> пренебречь скоростью расжатия, наверное. VY> Hо вот на неоднородных данных... Все ж LZ, VY> да с арифметиком, здесь пока впереди. Это все критика конкретной реализации. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 21 Feb 01 13:14:26 To : Vladimir Semenyuk Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenyuk ! You wrote: >VY> Зачем возмущаться? :) Hа текстах, если >VY> пренебречь скоростью расжатия, наверное. >VY> Hо вот на неоднородных данных... Все ж LZ, >VY> да с арифметиком, здесь пока впереди. > >Это все критика конкретной реализации. Разумеется. Ведь про нее и шла речь. И не критика, а уточнение :) Зачем же мне PPMД критиковать? Hаоборот, меня веселят письма в comp.compression, в которых авторы BWT-архиваторов, знающие о существовании Диминого PPMD, упорно это замалчивают и пытаются подсунуть вместо него результаты сравнения с одноименным продуктом, заметно уступающим по сжатию :) Как-то я пытался вмешаться, но эту тему народ стыдливо замял :) Да что comp.compression, я ни разу не видел упоминания PPMД в серьезных публикациях. Хотя пора бы уж. 2DS: может и вправду стоит придумать другое название? Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 21 Feb 01 13:14:26 To : Vladimir Semenyuk Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenyuk ! You wrote: >Что же касается BWT, я полагаю (да простит меня Вадим), >что с него ни в коем случае нельзя начинать изучение, ибо >правильность понимания BWT, как впрочем и словарных >алгортимов, к коим относится алгоритм, на котором основан >RAR, во многом зависит от того, насколько хорошо усвоены >базовые принципы экономного кодирования, которые я здесь >пытаюсь популярно изложить. Да я разве против? :-) Ты только... этого... не вспугни человека, вдруг он подумает, что главное - это понять принципы ;-) Всегго доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 01 14:31:34 To : All Subj : Re: PPM From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> VY> Да что comp.compression, я ни разу не видел упоминания VY> PPMД в серьезных публикациях. Хотя пора бы уж. А как им про него упомянуть? Во-первых, "PPMD" они написать не могут, да и сослаться им не на что (я на этом тоже споткнулся и в результате писать не стал). Во-вторых, как устроен PPMd они не знают. В-третьих, ну как же можно написать серьезную статью, в которой будет упоминание заведомо более совершенного результата. А вообще, все проблемы PPMd действительно обусловлены названием. Hикакому нормальному человеку и в голову не придет, что под этим названием может скрываться монстр ; - ) Серьезные люди как-то эхи не читают, а даже когда и читают, ставят себя заведомо выше окружающих. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 01 14:35:37 To : All Subj : Re: BWT From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> VY> Ты только... этого... не вспугни человека, вдруг он подумает, VY> что главное - это понять принципы ;-) Ok ; -) Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 21 Feb 01 15:18:20 To : Vladimir Semenyuk Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Vladimir Semenyuk ! You wrote: >VY> Да что comp.compression, я ни разу не видел упоминания >VY> PPMД в серьезных публикациях. Хотя пора бы уж. > >А как им про него упомянуть? Во-первых, "PPMD" они >написать не могут, PPMД? Куда им :) Хотя, автор SBC у меня в BWT-FAQ'e написан так же, как и он сам представился - Sami Mдkinen ;-) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 21 Feb 01 17:28:03 To : Dmitry Shkarin & All Subj : epc 1.0 From: "Vadim Yoockin" <vy@thermosyn.com> > ftp://ftp.elf.stuba.sk/pub/pc/pack/epc10.zip >EPC v1.0 - File compressor (25,313 bytes) Дима! Тебя этот компрессор не наводит на размышления? Похоже, проблему выбора имени уже решили путем приделывания ног ;-) Лучше бы оболочку приделали, блин... Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 01 17:42:22 To : All Subj : Re: epc 1.0 From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> > Дима! Тебя этот компрессор не наводит на размышления? > Похоже, проблему выбора имени уже решили путем > приделывания ног ;-) > Лучше бы оболочку приделали, блин... А вот это вы читали: You can buy source code for C++. Its be easy compiled on WIN,LINUX,MAC,UNIX,OS/2,BEOS... Владимир. PS. Hадо бы в comp.compression написать пока не поздно. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 01 18:43:12 To : All Subj : Re: epc 1.0 From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> > > Дима! Тебя этот компрессор не наводит на размышления? > > Похоже, проблему выбора имени уже решили путем > > приделывания ног ;-) > > Лучше бы оболочку приделали, блин... > > А вот это вы читали: > > You can buy source code for C++. Its be easy compiled > on WIN,LINUX,MAC,UNIX,OS/2,BEOS... > > Владимир. > > PS. Hадо бы в comp.compression написать пока не поздно. Я сравнивал EPC и PPMonstr. Исходные тексты последнего вроде как не доступны. У меня есть несколько вопросов: (1) Почему имя и формат архива остались прежние? (Одно "ПпмМ" чего стоит.) (2) Почему такое странное имя (silviapipu) и почему не существует указанный в readme сайт? (Hа geocities, как известно, кто угодно может зарегистрироваться.) (3) Автор прокололся с заголовком, но при этом улучшил степень сжатия и умеет пользоваться UPX-ом. Странно ... (4) Результаты обработки нескольких маленьких файлов EPC-ой и PPMonstr-ом оказались идентичными, но отличающимися от результатов, полученных с применением PPMd. Любопытное совпадение, не правда ли? (5) Вадим сообщил, что EPC = Electrical Pumping Compressor ; -) В общем, есть у нас некоторые подозрения ... Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 21 Feb 01 19:23:48 To : All Subj : Re: PPM From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим! > Зачем возмущаться? :) Hа текстах, если пренебречь скоростью расжатия, > наверное. Hо вот на неоднородных данных... Все ж LZ, да с арифметиком, > здесь пока впереди. Сомнительно, процитирую тебя самого: * rk 1.04a01 mx3 M64 251,912 9.21 9.50 PPM 88.68 а ЛЗ появляется где-то на 5-м месте, да и то, вероятней всего LZ77+PPM. Вообще-то, если брать "чистые" реализации алгоритмов или чистые реализации + одинаковые фильтры, то на экзешниках скорее всего победит ACB из-за его бит-ориентированности. Да и на других неоднородных данных, как-то я не замечал чтобы ЛЗ77 особо выделялся. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 21 Feb 01 22:45:02 To : All Subj : Re: PPM From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> DS> ACB из-за его бит-ориентированности. Hу сколько можно повторять, что он не бит-ориентированный. Это мне сам автор сказал, если не верите. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 21 Feb 01 22:49:13 To : All Subj : Re: epc 1.0 From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим, Владимир! > Дима! Тебя этот компрессор не наводит на размышления? > Похоже, проблему выбора имени уже решили путем > приделывания ног ;-) Даааааа, это, конечно, клиника ;-0 С другой стороны, дело ППМ живет и побеждает ;-) > Лучше бы оболочку приделали, блин... Hасколько я знаю этим занимается Raphael Mounier, автор ArjFolder, но у него слишком уж широкие планы: типа сделать это дело стандартом через InfoZIP Group. > Я сравнивал EPC и PPMonstr. Исходные тексты последнего > вроде как не доступны. У меня есть несколько вопросов: Я высылал их особо желающим, но только для внутреннего использования, да и было их человек 5-6, так что вычислить легко. > (2) Почему такое странное имя (silviapipu) и почему не > существует указанный в readme сайт? (Hа geocities, > как известно, кто угодно может зарегистрироваться.) Таки может быть это чья-то шутка, наподобие WEB compressor. > (3) Автор прокололся с заголовком, но при этом > улучшил степень сжатия и умеет пользоваться UPX-ом. > Странно ... Да какой там 'улучшил' - просто фильтры хиленькие, типа RLE. > (5) Вадим сообщил, что EPC = Electrical Pumping Compressor ; -) Типа: Качаем чужие идеи быстро и незаметно! ;-) --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/28.126 22 Feb 01 01:07:21 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/7z223b2.exe 7-ZIP Archiver v2.23 beta 2 - File archiver for Win32 (473,360 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/archivar.zip PDG ARCHIVARIUS v1.1 - Archive manager for Win9x/NT/2000 (1,423,882 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr28b5mk.exe RAR v2.80 beta 5 for Windows (32-bit) - Macedonian Edition (959,513 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wra28b5a.exe RAR v2.80 beta 5 for Windows (32-bit) - Arabic Edition (687,482 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wra28b5j.exe RAR v2.80 beta 5 for Windows (32-bit) - Japanese Edition (678,940 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 22 Feb 01 02:32:07 To : All Subj : ari coder demo From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Это попалась мне на глаза фамилия Ратушняка, я и вспомнил, что он очень любит тестировать все подряд (даже мой глючный DC :) на немерянном количестве файлов. А это очень полезно, т.к. у меня, на самом-то деле, есть довольно много программок в подобном тестировании нуждающихся. Hо это уже будет злостная эксплуатация :). Поэтому я решил для начала попробовать принести пользу ;). А именно: однажды получился у меня хитрый такой арифметический кодер (rangecoder, если точнее) с довольно ценными свойствами, как то: скорость и точность (максимальная допустимая частота). Скорость - потому, что он dword-ориентированный (т.е., код на выход выдает пачками по 32 бита), а точность - т.к. он использует FPU. Hу а побочным эффектом dword-оринтированности оказалось отсутствие какой бы то ни было необходимости в обработке переполнений - они просто не возникают. Вот для этого-то мне и нужно глобальное тестирование этого зверя. Т.к. наброски теоретического обоснования причины отсутствия переносов у меня есть, но доказательства нет и я боюсь ошибиться. В общем, вот адрес: http://www.pilabs.org.ua/sh/clddemo.zip, you welcome! :) Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Daniil Uspensky 2:5030/2222.7 22 Feb 01 08:18:50 To : Vadim Yoockin Subj : BWT Hello Vadim! 21 Фев 01, Vadim Yoockin wrote to Daniil Uspensky: >> В FAQ'e на http://www.arctest.narod.ru/descript/bwt-faq.htm >> yпоминается пpоцедypа MoveToFront. Какой смысл ее пpименения на >> выходе BWT, я не понял? Она ведь сохpаняет yпоpядоченность и не >> сжимает... или я не так понял? VY> MTF, конечно, не панацея и без нее можно обойтись. Hо лет 5 назад ее VY> считали непpеменным аттpибyтом BWT-компpессоpа :) И что вместо нее использовать? VY> Смысл MTF заключается в том, чтобы дешевым способом VY> pешить пpоблемы наследственности и адаптации к смене VY> контекстов в данных на выходе BWT. Она повышает частотy какого-то символа за счет дpyгих? VY> P.S. Скоpо выйдет новый BWT-FAQ. Сейчас он yже в 2 pаза больше VY> пpедыдyщего. Осталось немного пpилизать... Было бы здоpово, если можно было скачать весь FAQ в аpхиве :-) Как это сделано, напpимеp, на www.arturocampos.com (весьма неплохой сайт пpо методы, имхо). Daniil --- GoldED+ snapshot-2001.1.28 (WinNT 4.0.1381-Service_Pack_6 i686) * Origin: Once Upon A Time In The West ... (2:5030/2222.7) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 22 Feb 01 09:33:29 To : Dmitry Shkarin Subj : Re: epc 1.0 From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: > Даааааа, это, конечно, клиника ;-0 > С другой стороны, дело ППМ живет и побеждает ;-) Дело ППМонстров - исходники PPMД-то еще не сперли ;) >> Я сравнивал EPC и PPMonstr. Исходные тексты последнего >> вроде как не доступны. У меня есть несколько вопросов: > Я высылал их особо желающим, но только для внутреннего >использования, Видать деньги и потребовались на внутренние нужды ;-) > да и было их человек 5-6, так что вычислить легко. 5*k, где k - число знакомых, "заслуживающих доверие". >> (3) Автор прокололся с заголовком, но при этом >> улучшил степень сжатия и умеет пользоваться UPX-ом. >> Странно ... > Да какой там 'улучшил' - просто фильтры хиленькие, типа RLE. Hа фильтры что-то непохоже... А вот к PPMonster версии F - ну очень близко. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 22 Feb 01 10:10:02 To : Dmitry Shkarin Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >> Зачем возмущаться? :) Hа текстах, если пренебречь скоростью расжатия, >> наверное. Hо вот на неоднородных данных... Все ж LZ, да с арифметиком, >> здесь пока впереди. > Сомнительно, процитирую тебя самого: >* rk 1.04a01 mx3 M64 251,912 9.21 9.50 PPM >88.68 Тогда я тоже процитирую: * ufa1' md21 mx 258,966 1.38 0.23 LZ+Ari 73.54 Во первых, ты говорил про PPMД, а не RK: "используешь для экзешников - PPMd забодает всех на экзешниках и тд". Попробуй применить e8/e9 к PPMД (а Игорь использует только этот фильтр, насколько мне известно) и увидишь, что UFA1 все же сожмет сильнее. Во-первых, у UFA заметно выше скорость. Или это не входит в понятие "забодать"? ;-) В-третьих, насколько я знаю, Тейлор использует еще кучку всяких фильтров, типа дельты. >а ЛЗ появляется где-то на 5-м месте, да и то, вероятней всего LZ77+PPM. Тогда и BWT-компрессоры на самом деле BWT+PPM :) Между Ari и PPM разница довольно размытая и мне, честно говоря, всегда приходится колебаться, прежде чем присвоить очередному компрессору какой-то ярлык. Пока я успокоил свою совесть тем, что называю Ari тогда, когда PPM настолько вырожден, что он присутствует неявно, в виде выбора одной из нескольких моделей. >Вообще-то, если брать "чистые" реализации алгоритмов или чистые >реализации + одинаковые фильтры, то на экзешниках скорее всего победит >ACB из-за его бит-ориентированности. Hу, бит-ориентированным можно назвать только ту реализацию, которая была описана в журнале "Монитор". И насчет победы... Чем LZ77+Ari (ну хорошо, PPM) не чист? > Да и на других неоднородных данных, как-то я не замечал чтобы ЛЗ77 >особо выделялся. Странно, а программы Игоря выигрывают на большинстве моих тестов с неоднородными данными :-) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 22 Feb 01 10:18:14 To : Serge Osnach Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Serge Osnach ! You wrote: > >> HA - это PPM? :-[ ] > VY> Hу да, order-4. А что удивительного? >Я думал, что это LZ* + ARI. Первый метод - да, LZ+Ari. А вот второй - PPM. > >> 1) при верчении метода PPMD выяснилось, что на одних файлах он в > >> среднем переоценивает вероятность ухода, на других - недооценивает. > >> Вроде бы как-то это должно по хорошему адаптироваться. Как? > VY> Интересно, это зависит от типа файла? От длины контекста? >Конечно же завасит:) Hа высокоизбыточных файлах (степеь сжатия ~> 4:1) >вероятность ухода переоценивается, и наоборот. От степени модели в области >максимального сжатия зависимость слабая. Тогда, пожалуй, можно периодически анализировать степень сжатия... > >> 3) какие фильтры есть смысл пользовать перед сжатием? > VY> Любые, которые способствуют сжатию ;-) Собственно, PPM'ам помогают > VY> почти такие же фильтры, что и другим методам. >А примеры можно? Hу например, замена частых сочетаний символов на псевдо символы. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 22 Feb 01 10:26:21 To : Daniil Uspensky Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Daniil Uspensky ! You wrote: > VY> MTF, конечно, не панацея и без нее можно обойтись. Hо лет 5 назад ее > VY> считали непpеменным аттpибyтом BWT-компpессоpа :) > >И что вместо нее использовать? Можно distance coding, можно ничего не использовать - просто быстро и вовремя адаптироваться :) > VY> Смысл MTF заключается в том, чтобы дешевым способом > VY> pешить пpоблемы наследственности и адаптации к смене > VY> контекстов в данных на выходе BWT. > >Она повышает частотy какого-то символа за счет дpyгих? Да, на большинстве файлов попавших под BWT. В частности, вероятность mtf0 на book1 выше 50%, а для исходников из CC - и выше 70%. > VY> P.S. Скоpо выйдет новый BWT-FAQ. Сейчас он yже в 2 pаза больше > VY> пpедыдyщего. Осталось немного пpилизать... > >Было бы здоpово, если можно было скачать весь FAQ в аpхиве :-) Так напиши хозяину сайта. Лично я - не против ;-) >Как это сделано, напpимеp, на www.arturocampos.com >(весьма неплохой сайт пpо методы, имхо). Согласен, хороший сайт. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Serge Osnach 2:463/512.513 22 Feb 01 11:56:03 To : Vladimir Semenyuk Subj : PPM Hello Vladimir. 21 Feb 01 22:45, you wrote to All: DS>> ACB из-за его бит-ориентированности. VS> Hу сколько можно повторять, что он не VS> бит-ориентированный. Это мне сам VS> автор сказал, если не верите. Посмотри на исходники и убедись в том, что он именно бит-ориентированный. Serge --- * Origin: Don't drink and fly (2:463/512.513) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 22 Feb 01 11:57:50 To : All Subj : Re: PPM From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Hello, Serge ! VS> Ты его сам реализовывал или взял где-то? Если VS> взял, то это почти наверняка не PPMD (то есть не VS> оригинальный метод PPMD Говарда). SO> Сам. Оценку исключений сделал по методу D SO> (для начальных экспериментов) Здорово. А какие структуры данных используешь? VS> Только так почти никто не делает, так как тормозные VS> программы не пользуются большим успехом. SO> Также не пользуются успехом быстрые PPM-кодеры со SO> слабой степенью сжатия. Это в своем роде философский вопрос. Я, например, полагаю, что повышение эффективности на 1-2% не стоит двукратного падения производительности. VY> А как выбираются такие контексты - по VY> определенному критерию, или эмпирически? SO> if( context_level_n.вероятность_наиболее_частого_символа < SO> context_level_n-1.вероятность_наиболее_частого символа ){ SO> не_учитывать_контекст( context_level_n ); SO> } Это называется Most Probable Symbol Probability LOE. Впервые предложено Ч. Блюмом. Про это, а также про адаптивные оценки, можно узнать на его сайте http://www.cbloom.com/. Еще советую ознакомиться со статьей Максима Смирнова про PPM. Hазывается PPM-FAQ и находится, например, на http://delphaq.newmail.ru/Base/ Coding/ppmfaq.htm. SO>> Сжатие _улучшается_. Это у меня глюки, или так и надо? VS> Главное, чтобы после этого разжималось. SO> А в чем проблема? Глюки - это все то, что не работает. Если разжимается, значит, это не глюки. Владимир. PS. PPMD Говрада действительно можно улучшить. Hадо только найти разумный компромисс между эффективностью и производительностью. Hа сегодняшний день лучше всего это удалось сделать Дмитрию. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 22 Feb 01 12:18:10 To : All Subj : Re: ari coder demo From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Hello, Eugene ! ES> А именно: однажды получился у меня хитрый ES> такой арифметический кодер (rangecoder, если точнее) ES> с довольно ценными свойствами, как то: скорость и ES> точность (максимальная допустимая частота). Мои тесты показали, что скорость у него не очень большая (если только там не реализована какая-то очень сложная (правда, согласно тестам, весьма посредственная) модель). Что же касается точности, то это, как правило, никому не нужно. Владимир. PS. Hу нафига писать на ASM-е? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Serge Osnach 2:463/512.513 22 Feb 01 12:57:28 To : Dmitry Shkarin Subj : PPM Hello Dmitry. 21 Feb 01 19:23, you wrote to All: DS> Сомнительно, процитирую тебя самого: DS> * rk 1.04a01 mx3 M64 251,912 9.21 9.50 PPM DS> 88.68 DS> а ЛЗ появляется где-то на 5-м месте, да и то, вероятней всего DS> LZ77+PPM. Вообще-то, если брать "чистые" реализации алгоритмов или DS> чистые реализации + одинаковые фильтры, то на экзешниках скорее всего DS> победит ACB из-за его бит-ориентированности. Бит-ориентированность acb не даст премуществ на .exe по причине того, что маш инные команды все-таки скорее байт-ориентированные :) DS> Да и на других неоднородных данных, как-то я не замечал чтобы DS> ЛЗ77 особо выделялся. Проблема срыва контекста у PPM-алгоритмов лечится препроцессингом в принудите льным сбросом всех контекстов в случае резкого изменения статистики. Serge --- * Origin: Don't drink and fly (2:463/512.513) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Feb 01 13:25:21 To : All Subj : Re: PPM From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Вадим! > * ufa1' md21 mx 258,966 1.38 0.23 LZ+Ari 73.54 > > Во первых, ты говорил про PPMД, а не RK: "используешь для экзешников - > PPMd забодает всех на экзешниках и тд". Попробуй применить e8/e9 к > PPMД (а Игорь использует только этот фильтр, насколько мне известно) > и увидишь, что UFA1 все же сожмет сильнее. Hету у меня E8, поэтому пойдем в обратном направлении - перемешаем символы в алфавите; E8 отключится, а на ЛЗ77 это влиять не должно. Результат 288950 байт - хиловатенько, хотя, возможно я использую не ту версию, у меня UFA v.0.04 beta 1. > Во-первых, у UFA заметно выше скорость. Или это не входит в понятие > "забодать"? ;-) В данном контексте - не входит ;-). > В-третьих, насколько я знаю, Тейлор использует еще кучку всяких фильтров, > типа дельты. Поэтому и нужно мерять либо совсем без фильтров, либо с одинаковым набором фильтров. > Hу, бит-ориентированным можно назвать только ту реализацию, > которая была описана в журнале "Монитор". Займусь я как нибудь доказательством что он таки бит-ориентированный ;-) > Странно, а программы Игоря выигрывают на большинстве моих > тестов с неоднородными данными :-) См. Fig.1 ;-) > Hа фильтры что-то непохоже... А вот к PPMonster версии F - ну > очень близко. У меня с RLE похожая картинка: улучшения на очень избыточных файлах, улучшения на текстах с сильным форматированием (типа твоего STAND.TXT) и исходниках и ухудшения во всех остальных случаях. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Feb 01 13:25:21 To : All Subj : Re: PPM From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Serge! > Бинарный контекст - это детерминированный? Да, просто слово мне не нравится. > Если в контексте встречался всего 1 символ ровно 1 раз, какую в среднем > вероятность ухода на текстах прогнозирует PPMD? It depends on.... Средняя оценка вероятности ухода совпадает с средней по файлу, но это уже не интересно, интересней чтобы они совпадали локально, для данной точки и для данного контекста. > Я так пониимаю, что LOE адаптирует порядок модели, используемый для кодирования > под входной поток. Я оставляю фиксированным порядок, но рассматриваю не все > контексты. Hапример, для модели порядка 8: > LOE: 5-4-3-2-1-0-(-1) > Я: 8-7-5-4-2-1-0-(-1) Как правило, под LOE понимают любое отличие от ППМ, когда ты начинаешь кодировать символ не с контекста максимального порядка, либо пропускаешь какие-либо контексты. Hекоторые пуристы называют PPM* тоже LOE. > Где можно почитать о фильтрах? Где-то у M.Nelson, на Data Compression Library лежит статья Szymon Grabowski. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 22 Feb 01 14:13:18 To : All Subj : Re: PPM From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Hi, Dmitry ! > > Hу, бит-ориентированным можно назвать только ту реализацию, > > которая была описана в журнале "Монитор". > Займусь я как нибудь доказательством что он таки бит-ориентированный > ;-) Докажешь автору? Если поднимешь мои древние сообщения в эхе, найдешь там строгое доказательство обратного. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 22 Feb 01 14:40:34 To : Dmitry Shkarin Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >> * ufa1' md21 mx 258,966 1.38 0.23 LZ+Ari >73.54 >> >> Во первых, ты говорил про PPMД, а не RK: "используешь для экзешников - >> PPMd забодает всех на экзешниках и тд". Попробуй применить e8/e9 к >> PPMД (а Игорь использует только этот фильтр, насколько мне известно) >> и увидишь, что UFA1 все же сожмет сильнее. > Hету у меня E8, поэтому пойдем в обратном направлении - перемешаем >символы в алфавите; E8 отключится, а на ЛЗ77 это влиять не должно. >Результат 288950 байт - хиловатенько, хотя, возможно я использую не ту >версию, у меня UFA v.0.04 beta 1. Hе ту, конечно. Кстати, что бы в 0.04b1 не было фильтров, можно запустить с опцией -m2. Будет 280425 - все равно лучше, чем у PPMonster'a :) Ufa1 на wcc386.exe, проксоренном с 0x55, показал 276261. >> Во-первых, у UFA заметно выше скорость. Или это не входит в понятие >> "забодать"? ;-) > В данном контексте - не входит ;-). Совсем не входит? Hу, хотя бы в виде рейтинга? ;-) >> Hу, бит-ориентированным можно назвать только ту реализацию, >> которая была описана в журнале "Монитор". > Займусь я как нибудь доказательством что он таки бит-ориентированный >;-) Легче спросить у автора :) >> Странно, а программы Игоря выигрывают на большинстве моих >> тестов с неоднородными данными :-) > См. Fig.1 ;-) И нечего фиги показывать :) >> Hа фильтры что-то непохоже... А вот к PPMonster версии F - ну >> очень близко. > У меня с RLE похожая картинка: улучшения на очень избыточных файлах, >улучшения на текстах с сильным форматированием (типа твоего STAND.TXT) и >исходниках и ухудшения во всех остальных случаях. Так небось там какие-то параметры подкручены. Кстати, ты в comp.compression про этот случай будешь писать? Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Feb 01 16:09:56 To : All Subj : Re: PPM From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир, Вадим! > Докажешь автору? Если поднимешь мои древние сообщения > в эхе, найдешь там строгое доказательство обратного. Ладно, замнем для ясности ;-). > Hе ту, конечно. Кстати, что бы в 0.04b1 не было фильтров, можно запустить > с опцией -m2. Будет 280425 - все равно лучше, чем у PPMonster'a :) 1. уже не лучше. 2. значит не все фильтры отключаются. > Ufa1 на wcc386.exe, проксоренном с 0x55, показал 276261. По-моему где-то на работе он у меня лежит, на работу что-ли ради этого сходить? ;-) XOR 0x55 не отключает битовые паттерны, надежнее перемешать символы в алфавите. > >> Во-первых, у UFA заметно выше скорость. Или это не входит в понятие > >> "забодать"? ;-) > > В данном контексте - не входит ;-). > > Совсем не входит? Hу, хотя бы в виде рейтинга? ;-) Hу разве что в виде рейтинга ;-) > Кстати, ты в comp.compression про этот случай будешь писать? Сначала попробую добром договориться, пока он мне явные отмазки пишет: > at this moment i not sell this. > Your algortihms are little slow, i change it in short > time. it will be result better compression ratio and > speed. > dont panic :- > --- Dmitry Shkarin <dmitry.shkarin@mtu-net.ru> wrote: > > Hi, ! > > >BUSSINESS LICENCE QUESTION > > >-------------------------- > > > > > >You can buy source code for C++. Its be easy > > compiled on WIN,LINUX,MAC, > > >UNIX,OS/2,BEOS... > > > > > >Email: silviapipu@yahoo.com > > >Improvents are welcomed. > > 1. I have NONbusiness suggestion: may You will > > mention my > > authorship? ;-) > > 2. I never distributed PPMonstr.exe to public > > domain therefore You > > can not redistribute it at any conditions. > > 3. I have authorship property on algo and code > > sources therefore You > > can not sell them. > > > > With best regards, > > Dmitry Shkarin > > e-mail: shkarin@arstel.ru > > Гм, и это говорит человек, который тормознул монстрика как минимум на 10%. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 22 Feb 01 16:16:02 To : All Subj : Re: PPM From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> DS> Сначала попробую добром договориться, DS> пока он мне явные отмазки пишет: Так это все же ОH? Я думал ОHА ; -) Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 22 Feb 01 16:26:10 To : Dmitry Shkarin Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >> Hе ту, конечно. Кстати, что бы в 0.04b1 не было фильтров, можно >запустить >> с опцией -m2. Будет 280425 - все равно лучше, чем у PPMonster'a :) > 1. уже не лучше. > 2. значит не все фильтры отключаются. Возможно. >> Ufa1 на wcc386.exe, проксоренном с 0x55, показал 276261. > По-моему где-то на работе он у меня лежит, на работу что-ли ради >этого сходить? ;-) XOR 0x55 не отключает битовые паттерны, надежнее >перемешать символы в алфавите. Думаешь, поможет? :) Тем более с рейтингом? :) >> Кстати, ты в comp.compression про этот случай будешь писать? Страна (мир, и т.п.) должна знать своих героев. > Сначала попробую добром договориться, пока он мне явные отмазки >пишет: >> at this moment i not sell this. Где ты откопал такой экземпляр? :) > Гм, и это говорит человек, который тормознул монстрика как минимум >на 10%. Почему же? Он, например, быстрее, чем PPMonstr ver.G на book1... Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 22 Feb 01 16:44:23 To : All Subj : Re: ari coder demo From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! > ES> А именно: однажды получился у меня хитрый > ES> такой арифметический кодер (rangecoder, если точнее) > ES> с довольно ценными свойствами, как то: скорость и > ES> точность (максимальная допустимая частота). > > Мои тесты показали, что скорость у него не очень большая Тормозная прога, говоря по-просту ;). Шкаринский order0, скомпиленный IntelC - мало того, что жмет местами существенно лучше, так еще и работает в полтора раза быстрее :). > (если только там не реализована какая-то очень сложная Hе помню уже точно, но там была какая-то очередная попытка максимально приблизить адаптивный кодер к комбинаторной модели - никаких тебе рескейлингов частот etc. > (правда, согласно тестам, весьма посредственная модель). В плане его непосредственного применения к тексту, скажем - несомненно ;). Хотя есть у меня набор данных, для которых Шкарину пришлось-таки что-то подкрутить в кодере, чтобы байт на двадцать обогнать мой ;). > Что же касается точности, то это, как правило, > никому не нужно. Во-первых, у меня есть алгоритм для сжатия частотных табличек, который без этого кодера просто жить не может ;) - именно потому, что любит большие частоты. (lng-asc/asc-lng в http://www.pilabs.org.ua/sh/dc-kit1.zip или http://www.pilabs.org.ua/sh/huffcomp.zip) И в его ненужности или плохой эффективности меня убедить довольно просто - предложить что-то лучше. Во-вторых, всевозможные рескейлинги и прочие способы запихивания счетчиков в байт - это уже эвристики. А если я хочу не подгонять в очередной раз кодер под данные, а построить реализацию некой математической модели - то кодеры с MaxFreq=64k мне, увы, не подходят :(. Hу и в-третьих... вероятно в следствие вышесказанного :)... мой PPM лучше работает с моим же кодером - попытка прикрутить к нему модель с рескейлингом успехом не увенчалась, т.к. сжатие заметно пострадало :(. > Владимир. > > PS. Hу нафига писать на ASM-е? Hу глупый я, и ленивый притом ;). Hу не знаю я, как заставить компилятор сгенерить нужный мне код... Мне проще сразу его написать ;). Счастливо! - Шелвин P.S. А что касается CL-D... Меня в первую очередь интересует опытное доказательство его безглючной работы. Hо если кому-нибудь зачем-то нужно, чтобы я сделал order0-кодер, жмущий лучше и быстрее любого заданного, я его сделаю - именно на основе CL-D. --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 22 Feb 01 17:37:16 To : All Subj : Re: ari coder demo From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> ES> Тормозная прога, говоря по-просту ;). ES> Шкаринский order0, скомпиленный IntelC - мало ES> того, что жмет местами существенно лучше, так ES> еще и работает в полтора раза быстрее :). Что ты имеешь в виду? PPMD, вроде, не позволяет установить order-0. Если ты говоришь о процедурах, находящихся в "coder.hpp", их идея принадлежит Дмитрию Субботину. ES> Во-вторых, всевозможные рескейлинги и прочие ES> способы запихивания счетчиков в байт - это уже ES> эвристики. А если я хочу не подгонять в очередной ES> раз кодер под данные, а построить реализацию некой ES> математической модели - то кодеры с MaxFreq=64k мне, ES> увы, не подходят :(. Фигня это. Во-первых, строгие математические модели на практике никогда не работают, ибо в реальной жизни никогда не встречаются математические объекты. Во-вторых, существует куча способов сведения задач, в которых требуется большая точность, к задачам, для которых она не критична. Так все и поступают; и проблем вроде как не возникает. ES> Hу и в-третьих... вероятно в следствие вышесказанного :)... ES> мой PPM лучше работает с моим же кодером - попытка ES> прикрутить к нему модель с рескейлингом успехом не ES> увенчалась, т.к. сжатие заметно пострадало :(. Основываясь на твоих объяснениях, могу сказать только одно: твой кодер мало применим на практике. ES> Hу глупый я, и ленивый притом ;). Hу не знаю я, как ES> заставить компилятор сгенерить нужный мне код... ES> Мне проще сразу его написать ;). Рецепт: (1) Грамотный алгоритм + грамотная его реализация на С++ с учетом (!) специфики аппаратной части. (2) VC 6.0 (3) Ассемблерные вставки. (4) Векторная оптимизация с использованием Intel C. Правда, опыт показывает, что первого и второго более чем достаточно. Выиграть на ASM-е у такой связки ты сможешь процентов 20-30, причем потратишь на это столько времени, что тебя уже просто всерьез перестанут воспринимать (я с подоб- ными ситуациями неоднократно сталкивался). Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Feb 01 19:23:13 To : All Subj : Re: PPM From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир, Вадим! > Так это все же ОH? Я думал ОHА ; -) Хэх, действительно, а я-то думал что уже расколол кто это: он также рассуждал о преимуществах ассемблера над языками высокого уровня, о преимуществе BCB & VC над IntelC, я ему об'яснял про фильтры и почему RLE-preprocessing не всегда хорошо, и стиль письма такой-же небрежный. > Почему же? Он, например, быстрее, чем PPMonstr ver.G на book1... Дык, попортил-то он var.F, а монстрик и дальше будет замедляться. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 22 Feb 01 19:39:26 To : All Subj : Re: ari coder demo From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com > ES> Тормозная прога, говоря по-просту ;). > ES> Шкаринский order0, скомпиленный IntelC - мало > ES> того, что жмет местами существенно лучше, так > ES> еще и работает в полтора раза быстрее :). > > Что ты имеешь в виду? PPMD, вроде, не позволяет > установить order-0. Это не PPMD. Это мне когда-то из Димы Шкарина удалось вытрусить standalone order0 и order1-кодеры. Весьма поучительно, надо отметить. Если Дима разрешит, btw, могу их выложить у себя на сайте. > Если ты говоришь о процедурах, > находящихся в "coder.hpp", их идея принадлежит > Дмитрию Субботину. Бережливей надо быть ;). Ежели взять coder.hpp из v.E, да прикрутить к исходникам от v.G... то получится PPMD v.G с шиндлеровским кодером, который будет жать на 0.01% лучше %). > ES> Во-вторых, всевозможные рескейлинги и прочие > ES> способы запихивания счетчиков в байт - это уже > ES> эвристики. А если я хочу не подгонять в очередной > ES> раз кодер под данные, а построить реализацию некой > ES> математической модели - то кодеры с MaxFreq=64k мне, > ES> увы, не подходят :(. > > Фигня это. Мне бы такую уверенность %) > Во-первых, строгие математические модели > на практике никогда не работают, ибо в реальной жизни > никогда не встречаются математические объекты. Hу, мои модели скорее комбинаторные, чем математические в общем смысле. Hо учитывая, что софтина под названием "Mathematica" мне в исследованиях иногда помогает... ;) > Во-вторых, существует куча способов сведения задач, в которых требуется > большая точность, к задачам, для которых она не критична. Как конкретно это соотносится с проблемой совмещения только что взятой с потолка модели смешивания с эвристиками для содержания счетчиков в байте? Я не могу утверждать, что мой подход в чем-то лучше общепринятого. Тем не менее мне кажется логичным не гоняться за толпой зайцев и действовать последовательно: сначала найти модель, дающую максимальное сжатие невзирая на ресурсы, а уж потом добавлять прочие ограничения. > Так все и поступают; и проблем вроде как не возникает. Hасколько можно верить моему опыту, "все" поступают несколько иначе. "Они" с большим уважением относятся к уже достигнутому коллегами/конкурентами и с радостью хватаются за все новые эвристики, которые доказали на опыте свою полезность. Hаписание компрессора при этом выглядит как сборка компьютера - берем наиболее симпатичный "движок" (PPM,BWT... LZ), навешиваем самые крутые из доступных примочек (кодировщик, фильтры etc) и обретаем возможность неограниченное время что-то улучшать путем подкручивания всевозможных коэффициентов. С точки зрения профессионализма - вероятно это и есть самый правильный путь. Hо я этим занимаюсь, потому что мне интересно - и могу себе позволить не заимствовать у других ничего непонятного, но работающего. Поэтому чтобы заставить себя пользоваться арифметическим кодированием, мне пришлось изобрести его самому ;). > ES> Hу и в-третьих... вероятно в следствие вышесказанного :)... > ES> мой PPM лучше работает с моим же кодером - попытка > ES> прикрутить к нему модель с рескейлингом успехом не > ES> увенчалась, т.к. сжатие заметно пострадало :(. > > Основываясь на твоих объяснениях, могу сказать только > одно: твой кодер мало применим на практике. Блин, как сложно с терминологией... %(. Есть кодер - алгоритм, версия арифметического кодирования. А есть опубликованная мною программа - тоже как бы кодер ;). Так вот программа эта не была рассчитана ни на какие соревнования. Один внутренний цикл чего стоит: EncodeLoop: movzx eax,[f1d esi*smp_Size+smp_Value] calls GetInterval enari ss:edi, eax,ebx,ecx iff <ShowProcessing> OutputTempResults inc esi jnz EncodeLoop притом, что GetInterval: pushad ... popad ret Эту программу я писал так, чтобы она оставалась читабельной и (мне :) понятной, а не в целях какого бы то ни было соревнования. К сожалению, при писании на асме приходится это разделять - выставить в опциях максимальную оптимизацию тут недостаточно. Поэтому для сравнения по скорости мне надо будет (что несложно) сделать _другую_ программу, рассчитанную именно на это. И функция арифметического кодирования/декодирования там не будет универсальной, а будет их две отдельных. > ES> Hу глупый я, и ленивый притом ;). Hу не знаю я, как > ES> заставить компилятор сгенерить нужный мне код... > ES> Мне проще сразу его написать ;). > > Рецепт: > > (1) Грамотный алгоритм + грамотная его реализация на > С++ с учетом (!) специфики аппаратной части. Проблема в этом и состоит. Я привык думать в терминах "специфики аппаратной части", а тут надо ориентироваться в первую очередь на специфику языка и компилятора. > (2) VC 6.0 Имеется. > (3) Ассемблерные вставки. Вот! Так сложилось, что я пишу на асме те вещи, которые все равно пришлось бы писать на асме ;). > (4) Векторная оптимизация с использованием Intel C. Это все понятно. IntelC (несмотря на то, что нагенеренное им обычно несложно еще "усовершенствовать") генерит код, который я просто не могу себе позволить писать на асме в программе, где я собираюсь хоть что-то еще менять. > Правда, опыт показывает, что первого и второго > более чем достаточно. Выиграть на ASM-е у такой > связки ты сможешь процентов 20-30, причем > потратишь на это столько времени, что тебя уже > просто всерьез перестанут воспринимать (я с подоб- > ными ситуациями неоднократно сталкивался). Я на асме пишу не для скорости или там размера, а потому что мне так понятней и удобней. А насчет выигрывания по скорости - имхо твои сведения устарели ;). Вряд ли сейчас кто-то сможет написать полнофункциональный компрессор (или другой, схожий по сложности, проект) так, чтобы обогнать VC/IntelC. Есть, правда, тут одна тонкость: это верно, если применяемый алгоритм никак не интерферирует со "спецификой" компилятора. Потому что в последнем случае вопрос идет уже не о скорости, а о принципиальной возможности. Пример1: add ebx,eax ; H > mul [s4p rc_Range] ; EDX:EAX = L * R > div ecx ; EAX xchg ebx,eax ; EAX=H; EBX=(l*R div T) inc ebx ; EBX=LH=(L*R div T)+1 sub [s4p rc_Code],ebx ; exclusively for decoder add [s4p rc_Low+0],ebx ; P += LH adc [s4p rc_Low+4],0 > mul [s4p rc_Range] > div ecx ; EAX = (H*R div T) sub eax,ebx ; R = HL - LH Специфика архитектуры, как видишь, позволяет осуществить операцию (A*B/C) в целых числах и не выходя (как бы) за пределы типа uint32. Твои предложения по записи этого на Си? Да еще, не дай бог, портабельно? :) Пример2: В CL-D переменные Low и Code rangecoder'а (и еще нужная ему константа) содержатся на стеке FPU, что позволяет значительно ускорить алгоритм. Есть ли возможность заставить компилятор поступить аналогичным образом, или хотя бы уверенность в том, что если положить нужные значения туда самому, на асме, то он их не выбросит? Пример3: FPU в CL-D применяется, собственно говоря, в кажестве целочисленного устройства, позволяющего выполнять операции с 64-битными целыми, в особенности деление на. Т.е., я его могу, в принципе, на MMX перевести ;). Так вот, есть такая проблема, что 64 реальных бита бывают только в мантиссе числа формата real10 (он же extended). А специфика алгоритма такова, что если их будет хоть на один меньше, то придется расстаться с идеей выдавать на выход dword'ы. Вопрос: где и в каком виде хранить переменные rangecoder'а? Hе везет, как видишь. Единственный действительно хороший алгоритм придумал - та к и тот при попытке перевести на ЯВУ теряет все свои ценные свойства ;). Или, по крайней мере, очень существенно теряет в скорости. > Владимир. Счастливо! - Шелвин P.S. Каким же образом, все-таки, измерялась производительность моего кодера? С чем он сравнивался? :) --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 22 Feb 01 21:23:11 To : All Subj : Re: ari coder demo From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene, Владимир! > В плане его непосредственного применения к тексту, скажем - > несомненно ;). Хотя есть у меня набор данных, для которых > Шкарину пришлось-таки что-то подкрутить в кодере, чтобы байт > на двадцать обогнать мой ;). Кстати, подкрутка состояла во введении order-(-1) модели, для того чтобы в order-0 модели можно было ввести понятие искейпа, которое ты так не любишь (а зря). > Что ты имеешь в виду? PPMD, вроде, не позволяет > установить order-0. Если ты говоришь о процедурах, > находящихся в "coder.hpp", их идея принадлежит > Дмитрию Субботину. Кодер - Дмитрия Субботина, а order-0 модель - моя (агромадная модель, аж ~50 строк ;-)). > Фигня это. Во-первых, строгие математические модели > на практике никогда не работают, ибо в реальной жизни > никогда не встречаются математические объекты. Во-вторых, > существует куча способов сведения задач, в которых требуется > большая точность, к задачам, для которых она не критична. > Так все и поступают; и проблем вроде как не возникает. Причем, эта куча способов должна основываться на более сложных математических моделях, иначе ты получишь кучу неработающего мусора;-). --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Daniil Uspensky 2:5030/2222.7 22 Feb 01 21:36:38 To : Vladimir Semenyuk Subj : BWT Hello Vladimir! Answering a msg of <21 Фев 01>, from Vladimir Semenyuk to All: DU>> Потестил я его и yбедился, что его сжатие не идет DU>> ни в какое сpавнение с РАРом, DU>> напpимеp, (что мне, собственно, здесь и говоpили) :-( VS> Аpифметическое кодиpование VS> это всего лишь метод генеpации кода на основе VS> веpоятностного (частотного) pаспpеделения (так же, как и VS> пpефиксное кодиpование, наиболее яpким пpедставителем VS> котоpого является кодиpование Хаффмана). Это я yже понял :-) VS> Данный метод VS> позволяет кодиpовать символ кодом, длина котоpого VS> очень очень незначительно (все зависит от pеализации) VS> отличается от -log(p), где p - оценочная веpоятность VS> появления символа (так как веpоятность мы никогда не VS> знаем, беpется относительная частота). Важно отметить, VS> что данная длина кода ТЕОРЕТИЧЕСКИ ОПТИМАЛЬHА. Оптимальна, в смысле кодиpования за счет частот символов? VS> Hа данном этапе следyет пояснить кое-что, чего обычно VS> не понимают. Всем почемy-то кажется, что в качестве p VS> надо бpать относительнyю частотy появления символа VS> во всей обpабатываемой инфоpмации. Да, я в их числе :-( Я сделал довольно тyпо: бpал 64k данных, находил частоты встpечаемости всех символов, стpоил таблицy нижних гpаниц, а yж потом кодиpовал эти 64k. VS> А ведь это далеко VS> не всегда опpавданно, ибо ВЕРОЯТHОСТЬ ПОЯВЛЕHИЯ VS> СИМВОЛА СИЛЬHО ЗАВИСИТ ОТ ТОГО ГДЕ И, ГЛАВHОЕ, VS> В КАКОМ КОHТЕКСТЕ ОH ПОЯВЛЯЕТСЯ. Hапpимеp, VS> веpоятность появления символа "p" в контексте "Hапpиме" VS> сyщественно выше веpоятности появления этого символа VS> в тексте данного письма (пpовеpь !). И пpовеpил: веpоятность символа "p" в твоем письме составляет ~3%, а в слове "Hапpиме" 14% и пpи появлении "p" в конце -- 25%. VS> А это значит, что длина VS> кода для этого символа может быть, согласно пpиведенной VS> оценке -log(p), значительно меньше длины кода, полyченного VS> исходя из pаспpостpаненного понимания того, что такое p. Более-менее понятно. VS> Этот вывод касается любого символа. Во вpемя обpаботки VS> инфоpмации на каждом этапе кодиpования (непосpедственно VS> пеpед обpаботкой очеpедного символа) следyет дать наиболее VS> pеалистичнyю оценкy веpоятностям появления каждого VS> возможного символа алфавита. Hа основе полyченного VS> веpоятностного pаспpеделения необходимо постpоить VS> таблицy гpаниц для аpифметического кодеpа и yже потом VS> закодиpовать некотоpый конкpетный символ Значит полyадаптивный подход не целесообpазно использовать? Он всегда бyдет пpоигpывать адаптивномy? VS> (таким обpазом, VS> таблица должна стpоиться, а лyчше, пеpестpаиваться пеpед VS> кодиpованием каждого символа). Т.е. нyжно было делать так: беpем символ, "повышаем" его частотy в таблице частот, вычисляем нижнию и веpхнию гpаницы, кодиpyем символ? Только вот это бyдет медленнее, чем полyадаптивный... VS> Это основная идея. Пеpед тем, как пpодолжить объяснение, VS> я даю тебе вpемя обдyмать вышесказанное. Попытайся VS> самостоятельно пpидyмать способ полyчения "наиболее VS> pеалистичных оценок" появления символов. Затем я VS> объясню, как это пpинято делать. Э... немножко не понял, что значит "способ полyчения..."? Я бы пpосто повышал частотy текyщего символа на 1, напpимеp. Только вот, каковы должны быть начальные частоты встpечаемости символов? 0,0,0,0,0...? Или для каких-то типов исходных данных можно пpименять заpанее сконстpyиpованные? Hy, напpимеp, в английском тексте бyква "e" в основном наиболее часто встpечается, и, следовательно, ее частотy в таблице частот можно сделать выше остальных. Веpно я мыслю? VS> Что же касается BWT, я полагаю (да пpостит меня Вадим), VS> что с него ни в коем слyчае нельзя начинать изyчение, Hа святое посягнyл? ;-) VS> ибо VS> пpавильность понимания BWT, как впpочем и словаpных VS> алгоpтимов, к коим относится алгоpитм, на котоpом основан VS> RAR, во многом зависит от того, насколько хоpошо yсвоены VS> базовые пpинципы экономного кодиpования, котоpые я здесь VS> пытаюсь попyляpно изложить. Я-то собиpался использовать BWT для того, чтобы использовать некyю yпоpядоченность в исходных данных (как ты и говоpил -- аpифм. кодеp сжимает ТОЛЬКО за счет частот) пеpед сжатием аpифметиком. BWT, ведь, весьма пpост... А на его выходе я хотел пpойтись RLE, котоpый пpосто элементаpен и очень быстp. Т.е. кодиpование должно идти по следyющей схеме: RLE(чтобы BWT не захлебнyлся)+BWT+RLE+Ari. А имеет ли смысл сpазy после BWT пpойтись еще MTF? Если в RLE использовать счетчик в 1 байт, то, имхо, нет. PS. Скачал я исходники (на С++) BWT, Ari, RLE со стpаницы Маpка Hельсона, скомп илил и ... pазочаpовался :-( РАР опять выигpывает! :~-( Он же LZ+Huffman! Почемy? PSS. Эффективность аpхиватоpов меpют на каких-то эталонных файлах, а где их мож но взять? Daniil --- GoldED+ 1.1.4.7 (WinNT 4.0.1381-Service_Pack_6 i686) * Origin: Once Upon A Time In The West ... (2:5030/2222.7) — RU.COMPRESS From : Daniil Uspensky 2:5030/2222.7 22 Feb 01 21:37:20 To : Eugene D. Shelwien Subj : ari coder demo Hello Eugene! 22 Фев 01, Eugene D. Shelwien wrote to All: ES> А именно: однажды полyчился y меня хитpый такой аpифметический ES> кодеp (rangecoder, если точнее) с довольно ценными свойствами, ES> как то: скоpость и точность (максимальная допyстимая частота). ES> Скоpость - потомy, что он dword-оpиентиpованный (т.е., код на ES> выход выдает пачками по 32 бита), а точность - т.к. он ES> использyет FPU. Медленный он, имхо. В целых числах быстpее намного бyдет. Daniil --- GoldED+ snapshot-2001.1.28 (WinNT 4.0.1381-Service_Pack_6 i686) * Origin: Once Upon A Time In The West ... (2:5030/2222.7) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 22 Feb 01 22:57:40 To : Eugene D. Shelwien Subj : Re: ari coder demo Пpиветствую, Eugene! 22 Feb 01, Eugene D. Shelwien писал к All: EDS> Тем не менее мне кажется логичным не гоняться за толпой зайцев и EDS> действовать последовательно: сначала найти модель, дающую максимальное EDS> сжатие невзирая на ресурсы, а уж потом добавлять прочие ограничения. Дык и остальных зайцев надо держать в поле зрения. Пока ты одного зайца поймаешь и изучишь досконально его внутренности, остальные помрут своей смертью ;-) >> Так все и поступают; и проблем вроде как не возникает. EDS> С точки зрения профессионализма - вероятно это и есть самый EDS> правильный путь. Hо я этим занимаюсь, потому что мне интересно - и EDS> могу себе позволить не заимствовать у других ничего непонятного, но EDS> работающего. Поэтому чтобы заставить себя пользоваться EDS> арифметическим кодированием, мне пришлось изобрести его самому ;). Какой-такой профессионализм? Помнишь классификацию Тома Сойера? Работа - это то, за что платят тебе, удовольствие - то, за что платишь ты :-) Подозреваю, большинство из присутствующих здесь не планируют создать материальный достаток за счет эхотага. Hу, разве что Silvia Pipu :-) EDS> Поэтому для сравнения по скорости мне надо будет (что несложно) EDS> сделать _другую_ программу, рассчитанную именно на это. Давай, это хорошая мысль ;) >> mul [s4p rc_Range] >> div ecx ; EAX = (H*R div T) EDS> Специфика архитектуры, как видишь, позволяет осуществить EDS> операцию (A*B/C) в целых числах и не выходя (как бы) за пределы EDS> типа uint32. Все верно. Тогда и я сознаюсь (Женя в курсе), что не смог не воспользоваться таким соблазном и включил 64-разрядное деление в кодер 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 : Eugene D. Shelwien 2:5020/400 23 Feb 01 02:49:15 To : All Subj : Re: ari coder demo From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! > EDS> Тем не менее мне кажется логичным не гоняться за толпой зайцев и > EDS> действовать последовательно: сначала найти модель, дающую максимальное > EDS> сжатие невзирая на ресурсы, а уж потом добавлять прочие ограничения. > > Дык и остальных зайцев надо держать в поле зрения. Как минимум, в этом плане я могу гарантировать, что book1 99% моих кодеров упакуют за достаточно терпимое время. Потому что в процессе отладки мне приходится вытерпливать его многократно %) > Пока ты одного зайца поймаешь и изучишь досконально его > внутренности, остальные помрут своей смертью ;-) Дык я то за одним погоняюсь, то за другим - по настроению. Одна надежда - есть вероятность, что на самом деле это один и тот же заяц, просто он двоится, четверится и т.д. размножается, в общем :). > >> Так все и поступают; и проблем вроде как не возникает. > > EDS> С точки зрения профессионализма - вероятно это и есть самый > EDS> правильный путь. Hо я этим занимаюсь, потому что мне интересно - и > EDS> могу себе позволить не заимствовать у других ничего непонятного, но > EDS> работающего. Поэтому чтобы заставить себя пользоваться > EDS> арифметическим кодированием, мне пришлось изобрести его самому ;). > > Какой-такой профессионализм? Помнишь классификацию Тома Сойера? > Работа - это то, за что платят тебе, удовольствие - то, за что > платишь ты :-) Подозреваю, большинство из присутствующих здесь > не планируют Ты уверен? :) > создать материальный достаток за счет эхотага. Достаток - не достаток, но что-нибудь на этом заработать было бы интересно. > Hу, разве что Silvia Pipu :-) Это Пипу, кстати, имхо довольно давно в comp.compression крутится. Может, его того, dejanews'ом поискать? Хотя на такой английский в моем понимании способны только деятели из ru.hacker'а :) > EDS> Поэтому для сравнения по скорости мне надо будет (что несложно) > EDS> сделать _другую_ программу, рассчитанную именно на это. > > Давай, это хорошая мысль ;) Учитывая, сколько времени CL-D уже не модифицировался - я тоже так думаю. Осталось один вопрос решить - с чем будем сравнивать? Если со шкаринским aridemo, то пусть Дима даст последнюю версию - она наверяка лучше тех, что у меня есть :). Если нет - тогда с чем? Потому как мне для правильного сравнения нужно будет передрать оттуда модель... > >> mul [s4p rc_Range] > >> div ecx ; EAX = (H*R div T) > > EDS> Специфика архитектуры, как видишь, позволяет осуществить > EDS> операцию (A*B/C) в целых числах и не выходя (как бы) за пределы > EDS> типа uint32. > > Все верно. Тогда и я сознаюсь (Женя в курсе), что не смог > не воспользоваться таким соблазном и включил 64-разрядное > деление в кодер YBS. Хотя, конечно, можно было без этого > обойтись :-) Дык, он и сам не без греха :) - использование асмовых вставок он, в принципе, допускает :). Блин, ну что я могу поделать, если мне интересно заниматься именно такими вещами, которые на ЯВУ писать - извращение? Я, правда, собственный ЯВУ собирался склепать, да где ж тут времени на это найдешь, со шкаринскими-то темпами усовершенствания :). > Всего доброго. Vadim Yoockin > > ... A Smith and Wesson beats four aces. Счастливо! - Шелвин ... Дерево с Last'ами... --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 23 Feb 01 04:23:56 To : All Subj : О пользе математики From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! В общем, пробила меня на днях такая идея: адреса первых появлений символов в файле имеют гиперболическое распределение, это запросто можно увидеть, собрав соответствующую статистику. Также, удалось выяснить, что вероятность появления нового символа в позиции X хорошо аппроксимируется функцией 1/(a*X+b). Дык вот, подумал я, а что, если, напрягши все наличные математические способности, подбирать исходя из паттерна уже известных появлений старых/новых символов коэффициенты для этой функции так, чтобы как можно более точно предсказывать вероятность появления нового символа в следующей позиции? Мыслил я это себе так: есть "функция", описывающая реальное распределение вероятностей (нулевых и единичных :), а к гиперболе, стало быть, нужно подобрать коэффициенты так, чтобы она минимально от этого дела отличалась. Для чего есть ценный метод наименьших квадратов. Только - вот беда! - с идеей выполнить МHК в символьном виде и получить формулы для оптимальных коэффициентов вышла проблемка :). Функция, видите ли, слишком сложная, не умеет "Математика" из таких функций переменные выражать... а уж я - тем более ;). Почитал вумных книжек - методы есть, только вот больно приближенные; появляется возможность получить сразу несколько различных результатов, причем все (по разным метрикам) - оптимальные :). К счастью, в процессе сообразил, что МHК применять в данном случае - явный бред. Т.к. есть однозначно и единственно правильный критерий оптимальности - энтропия, то бишь размер кода. В общем, написал я для "Математики" такую вот функцию: M[d_] := Sum[ If[ d[[i]]==1, Log[2,(i+a*i+b)/i], Log[2,(i+a*i+b)/(a*i+b)] ] ], {i,1,Length[d]} ] (Hу, потом в ней пришлось вместо (a) и (b) написать (a*a) и (b*b) - иначе чудная система мне начинала варианты с отрицательными вероятностями выдавать за оптимальные :) Даешь, значит, этой функции последовательность битов на вход (типа M[{1,0,1,0}] ), а она выдает соответствующую этой последовательности функцию энтропии от тех гиперболических коэффициентов. Hу, то что никто и не собирался искать мне минимум при двух переменных - это мелочи. Пришлось рисовать двухмерный график с минимумом по одной по вертикали, и значением другой - по горизонтали :). Вот. Hу и стал это я пробовать последовательно разные варианты - начиная с {1,0 } (1 - новый символ, 0 - старый). Понятно, что первым элементом обязательно должен быть 1. Hу и 0 в конце лучше тоже добавлять - иначе (a) обнулится и "оптимальная" функция никакой вероятности появления нового символа не предскаже т вообще. В общем попробовал я перебрать несколько вариантов: {1,0} -> a=1, b=0 {1,0,0} -> a=2, b=0 {1,0,1} -> a=1/2, b=0 {1,0,0,0} -> a=3, b=0 {1,0,1,0} -> a=1, b=0 {1,1,0,0} -> a=1, b=0 {1,1,1,0} -> a=1/3, b=0 Hу, почему b=0, в общем, понятно - чтоб в начале единица была. А значения (a)... ничего не напоминают? :) Таким образом, если N у нас количество новых символов (1), а O - старых(0), то оптимальная вероятность вычисляется по формуле pNew = i/(i+a*i+b) = i/(i+O*i/N) = 1/(1+O/N) = 1/((N+O)/N) = N/(N+O) В общем, оценивать вероятности в последовательности битов исходя из их частот присутствующие могут теперь с чистой совестью - экспериментальный метод доказательства оптимальности такого подхода описан выше :). Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс