| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 11 Dec 99 01:28:33 To : All Subj : Re: BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Здравствуй, Дмитрий ! VS>(1) Hа ближнюю. При ссылочном кодировании нас не сильно волнует то, что VS>непосредственно предшествует кодируемой последовательности. В этом состоит VS>принципиальное различие. DS>Любой адаптивный кодер должен опираться на предысторию, иначе он не DS>будет адаптивным, в каком виде он эту предысторию хранит это его, кодера, DS>личное дело. Причем тут это высказваение я не понял. Я что против? Я совсем про другое говорю. VS> (2) Теперь по поводу PPM. Во-первых, классический PPM при ПОЛHОМ сбросе VS>статистики в лучшем случае превращается в простое копирование (модель VS>"-1"-го порядка). Если все время использовать модель нулевого порядка, то VS>это будет то, что формально называется адаптивным арифметическим VS>кодированием. DS> Хм, разговор шел о сбросе статистики после повторяющейся строки. Что-то мне начинает казаться, что под словом статистика мы понимаем совершенно разные вещи. VS>Во-вторых, идеология PPM предполагает предсказание всегда VS>одного символа, а не строки. В-третьих, в PPM-е используется вероятностная DS> См. Фенвика, что-то типа "Differential LZ compressor". Это я не догадался, что почти все методы сжатия называются PPM :) VS>В-третьих, в PPM-е используется вероятностная VS>оценка. Там ссылками и не пахнет. Поэтому PPM не может быть эквивалентен VS> LZ. DS> Всюду где я пишу PPM я подразумеваю контекстное моделирование - DS> лениво писать такое длинное словосочетание(я и дальше так делать DS>буду:)). PPM это частный случай, когда контекст строится из DS>непосредственно предшествующих символов. Я вот до этого письма думал, что контекст символа - это либо последовательность символов, которая ему непосредственно предшествует, либо последовательность символов, которая сразу за ним следует. А оказывается, что это только в PPM-е. А что же тогда в остальных методах? DS>Что тебе мешает наряду с закодированным в контексте символом DS> передавать и сам контекст? Такой подход нередко и используется, но вопрос то не про это. DS>Если слишком длинно и если контекст встречался в DS> тексте раньше, передай ссылку на него(LZ offset). Что слишком длинно? DS> Любые известные на сегодняшний день схемы, за исключением DMC, DS> являются неявным ППМ. В свою очередь ППМ является подмножеством DS> схем типа DMC. Под этими схемами ты имеешь в виду модели состояний или что? А вот c BW как быть? VS>Сходится, не сходится. Какая разница. Я, например, сильно разочарован VS>поведением классического PPM (не PPMZ) на малоизбыточной информации. VS>(А то, что произошло с PPMD при сжатии массива текстовой информации, куда VS>случайно затесался небольшой ZIP-архив, вообще трудно передать словами.) VS>Да, BW предназначен для той же информации, что и PPM. Однако на другой VS>информации (например, неоднородной или малоизбыточной) BW не VS>редко бьет PPM по качеству сжатия, а про скорость кодирования я вообще VS>промолчу. DS> Тот-же BA например умеет адаптивно выбирать размер блока, для ППМ это DS> аналогично сбросу статистики, но PPMD, будучи обучающей программой, таким DS> кунштюкам естественно не обучен. А знаешь, в методе Барроуза-Уилера не всегда следует что-то разбивать. Увеличение размера блока как правило ведет к повышению эффективности сжатия. Поэтому бить или не бить - это еще большой вопрос. VS>(1) Если говорить строго, то энтропия бывает только одна. Она совпадает с VS>тем, что ты называешь "order-0" только в случае отсутствия корреляции VS>между символами. Да и вообще в данном случае имеет смысл говорить VS>о количестве информации, а не об энтропии. DS>Если говорить строго, то энтропия текста имеет смысл только по DS>отношению к некоторой модели. Энтропия - это и есть энтропия. Она одна. Я умею считать энтропию для бесконечного источника за бесконечное время (в общем случае). Для информации конечного размера без знания порядка источника (порядков или статистических характеристик), ее породившего, определять понятие энтропии (количества информации) бессмысленно и некорректно. DS> PPMZ не является отдельной схемой, это просто PPM*+LOE+SEE. DS> ... DS>PPMZ который является конкретной реализацией(алгоритмом) схемы PPM*. Давай расставим все точки над "i". Я правильно понимаю, что между подходами к детерминированным контекстам в PPMZ и PPM* ты ставишь знак равенства. DS> Hу наверное, как-то он короткие детерменированные(лучше будет бинарные) DS> контексты использует ибо первоначально(после первого обновления) любой DS> контекст является бинарным. Мне кажется, что "бинарные" здесь не совсем слово подходящее. (Оно скорее для запутывания.) Каюсь, к PPMZ я пристрастен, тк PPMZv9.0 был > грубо подогнан к CC, а PPMZ2, может и хорош, но он не идет на моей машине А что такое "CC" ? 5 минут думал, но не понял. С уважением, Владимир. PS. Перед продолжением дискуссии хочу узнать твои определения (а) статистики (б) сброса статистики (в) кодера (кодировщика) (г) контекста (д) модели (е) PPM (ж) словарного метода (з) энтропии (и) контекстно-ориентированного кодирования. И еще хочу узнать, в чем по твоему мнению состоят основные отличия между ACB, классическим PPM-ом (PPMC, например) и ссылочными LZ (если они есть, конечно). Извини, но сначала надо договориться об определениях. Я по возможности стараюсь использовать те термины, которые приводятся в первоисточниках. Многие из них ты называешь по-своему, поэтому беседовать становится как-то бессмысленно. Возможно у нас позиции совпадают, а я об этом и не догадываюсь. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 11 Dec 99 01:52:53 To : Leonid Broukhis Subj : есколько вопросов * Crossposted in RU.COMPRESS Hello Leonid! Thursday December 09 1999, Leonid Broukhis writes to Vadim Yoockin: LB> PS. Hе имея в виду тебя конкретно, скажу: есть еще среди нас любители LB> Борландовских компиляторов, которые до сих пор думают, что качество LB> кода, порождаемое Борландом, есть лучшее, что бывает. exp откомпилирован bcc32i ;) 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 11 Dec 99 02:01:40 To : Vadim Yoockin Subj : соpтиpовка в BWT * Crossposted in RU.COMPRESS Hello Vadim! Friday December 10 1999, Vadim Yoockin writes to Boris Batkin: VY> Если конец года в банке не будет достаточно напряженным, VY> может, в январе доделаю ybs, наконец. Тссс... Hикто, кроме нас, наверно и не знает, что январь - это конец года :) 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 11 Dec 99 05:20:43 To : Bulat Ziganshin Subj : ARJZ Hi, Bulat! А как, если не секрет, сделан словарь в субже? Откровенно говоря, показываемые им результаты несколько удивляет. 8) taste you later, morf --- GoldED 2.50+ * Origin: Hеча на алгоритм пенять коли в голове мозги мало (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 11 Dec 99 05:23:59 To : Dmitry Shkarin Subj : BWT Hi, Dmitry! "Dmitry Shkarin" sendTo: "All" when: [09 Dec 99] msg: >> DS> Доказательство оптимальности или неоптимальности? Если >> DS> неоптимальности, то достаточно привести пример: order-0 >> DS> источник с неравномерным распределением, если оптимальности, >> DS> то оно опровергается примером. Вообще ты практически прав, но не надо забывать, что на выходе MTF может стоять напрмер PPM (так сейчас некоторые маньяки делают и, что интересно, получают не плохие результаты 8-). А еще есть такая штука как DMC. ;) taste you later, morf --- GoldED 2.50+ * Origin: Hеча на алгоритм пенять коли в голове мозги мало (2:5020/530.18) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Dec 99 10:34:56 To : Leonid Broukhis Subj : Re: есколько вопросов Пpиветствую, Leonid! 10 Dec 99, Leonid Broukhis писал к Vadim Yoockin: >> Лео, ты невнимателен. Сравни функциональность моего кода >> и откомпилированного тобой фрагмента. Я привел весь кусок. >> Внутренний цикл здесь начинается с for(j=0;j<256;j++). >> А внешний там еще был :) LB> Так компилятор за человека алгоритм переписывать действительно LB> не обязан. А находить индуктивные переменные и редуцировать их, LB> чтобы не было необходимости вводить временные указатели и засорять LB> программу - обязан. Я рад, что ты согласился с тем, что даже у "хорошего" компилятора ограниченные возможности :) К сожалению, обязанность также не всегда соответсвует действительности. Было бы, неплохо, если бы дела обстояли так, как ты говоришь... И, должен сказать, для PC компиляторы еще не самые худшие. Возможно, это из-за широкого рынка. Для той же AS400, несмотря на широкое распространение в последнее время, оптимизация оставляет желать лучшего. Кстати, меня тоже огорчила недостаточная эффективность кода, сгенеренная gcc (ну плохо он работает с 8-битными регистрами), в отличие от bcc32i. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Dec 99 10:57:00 To : Yury Reshetov Subj : Re: есколько вопросов Пpиветствую, Yury! 09 Dec 99, Yury Reshetov писал к Vadim Yoockin: VY>> IMHO MTF имеет смысл только на данных, содержащих VY>> много подряд идущих одинаковых символов. YR> Когда pазница между значениями соседних символов меньше YR> диапазона значений. Это слишком мягкое ограничение. Возможность хорошего сжатия MTF предоставляет только для нулевого ранга. Когда слишком большие веса получаю ранги старше первого, лучше сработает должным способом написанный адаптивный кодер. Впрочем, можно сказать, первое условие является достаточным, а твое - необходимым. Всего доброго. 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 : Leonid Broukhis 2:5020/400 11 Dec 99 11:32:41 To : Bulat Ziganshin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> PS. Hе имея в виду тебя конкретно, скажу: есть еще среди нас любители > LB> Борландовских компиляторов, которые до сих пор думают, что качество > LB> кода, порождаемое Борландом, есть лучшее, что бывает. > > exp откомпилирован bcc32i ;) А был бы у тебя, например, Solaris for Intel, вполне может быть, что ты бы откомпилировал им, и выбросил бы bcc на помойку. Кстати, покажи мне кусок кода, который bcc скомпилирует лучше, чем gcc (то, что компилировал я, было с ключом -mcpu=i686, так что не бойся, насчет U и V gcc знает). Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 11 Dec 99 17:31:52 To : All Subj : Re: А что же лучше? From: "ZAB" <ZAnatolyB@mail.ru> Привет! Vladimir Semenjuk <semenjuk@green.ifmo.ru> сообщил в новостях: > Hi, ZAB ! > > > Люди! Я почитал эту эху и чуть с ума не сошёл! Я думал, что самые высокие > > результаты по сжатию даёт LZW! А разве не так? Может скажете какой > алгоритм > > самый крутой (не по времени, а по степени сжатия)? > > Вопрос спорный. Чаще всего PPMZ2. > (Конституцию России PPMZ2 сжимает ровно в 2 раза лучше, чем LZW.) А он ещё не запатентован? Когда он появился? Где его взять, всмысле описание алгоритма или что-нибудь про принцип сжатия? > Чтобы получить полное представление о возможностях почти всех существующих > программ упаковки информации посети www.act.by.net или > www.shomonopoly.com\arctest. Посмотрел, но RK почему-то качаться не стал, его страница не открылась! --- ifmail v.2.14dev3 * Origin: Fidolook Express page http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 11 Dec 99 17:31:57 To : Dmitry Subbotin Subj : ARJZ * Crossposted in RU.COMPRESS Hello Dmitry! Saturday December 11 1999, Dmitry Subbotin writes to Bulat Ziganshin: DS> А как, если не секрет, сделан словарь в субже? DS> Откровенно говоря, показываемые им результаты несколько удивляет. 8) Ты про использование dict в тесте Вадима? 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 11 Dec 99 17:32:57 To : Leonid Broukhis Subj : есколько вопросов * Crossposted in RU.COMPRESS Hello Leonid! Saturday December 11 1999, Leonid Broukhis writes to Bulat Ziganshin: >> exp откомпилирован bcc32i ;) LB> А был бы у тебя, например, Solaris for Intel, вполне может быть, что LB> ты бы откомпилировал им, и выбросил бы bcc на помойку. он PE делает? LB> Кстати, покажи LB> мне кусок кода, который bcc скомпилирует лучше, чем gcc (то, что LB> компилировал я, было с ключом -mcpu=i686, так что не бойся, насчет U и LB> V gcc знает). bzip2 устроит? Согласно тем же тестам Вадима. Хотя не факт, в 0.9.5 улучшен вво д-вывод и у меня тоже. Возможно, мой исходный код просто оказался чуть лучше. А bcc32i - это интеловский компилятор :)) С фреймворком от Борланда. Что чер товски удобно, особенно для старых программ. В принципе, мы с Вадимом пришли вр оде к выводу, что из watcom, visual, intel, gnu в разных ситуациях могут побеждать разные компиляторы. Вот борланд, конечно, не жилец. Хотя об u/v даже он давным-давно знает. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 11 Dec 99 18:37:26 To : All Subj : Re: А что же лучше? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, ZAB ! ZAB> Может скажете какой алгоритм ZAB> самый крутой (не по времени, а по степени сжатия)? VS> Вопрос спорный. Чаще всего PPMZ2. VS> (Конституцию России PPMZ2 сжимает ровно в 2 раза лучше, чем LZW.) ZAB> А он ещё не запатентован? Когда он появился? Где его взять, всмысле описание ZAB> алгоритма или что-нибудь про принцип сжатия? Алгоритм PPMZ существует уже несколько лет. PPMZ2 появился в этом году. www.cbloom.com - домашний сайт автора (Чарльз Блюм). Там про PPMZ много написано. Ищи "ppmz.ps" - это описание. VS> Чтобы получить полное представление о возможностях почти всех существующих VS> программ упаковки информации посети www.act.by.net или VS> www.shomonopoly.com\arctest. ZAB> Посмотрел, но RK почему-то качаться не стал, его страница не открылась! Бывает. Зайди на ftp://ftp.elf.stuba.sk/pub/pc/pack/ Там лежат почти все архиваторы, которые были задействованы в тестах. С уважением, Владимир. PS. PPMZ, кстати, и в RK используется. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 11 Dec 99 18:41:10 To : Leonid Broukhis Subj : есколько вопросов * Crossposted in RU.COMPRESS Hello Leonid! Thursday December 09 1999, Leonid Broukhis writes to Vadim Yoockin: >> Хотя я использую не Borland, а gcc, но должен сказать, код, >> генерирумый интеловским Борландом (или борландовским >> Интелом) очень неплох. LB> Знаю, как он был неплох... То-то я всем пользователям Freeze на PC LB> рекомендовал MS. bcc32i появился лет 5 назад, вряд ли тогда freeze был актуален. Ты, вероятно, говоришь еще о 16-разрядных компиляторах, когда интела на рынке не было. LB> Так вот, обязан, и еще как. Погоди пару-тройку лет, начнутся LB> VLIW-процессоры, тут я на тебя посмотрю, кто чью работу делать не LB> обязан. Да хотя бы на iMAC с PowerPC посмотреть: в нем система команд LB> - не чета тому, что выросло из 8080. Тот же суперскаляр, что и в пентиум/пентиумпро. Если ты уверен, что компилято р может конкурировать с человеком, покажи такой, который догадается использоват ь POP для чтения из входного буфера :) А для vliw писать программы даже проще, чем для суперскаляра :) Кстати, хочешь тест - посмотри скорость упаковки и скорость вычисления CRC в zip. Там есть ассемблерные и сишные варианты обеих процедур. А еще можно сравни ть скорость распаковки pkzip25 и unzip. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 11 Dec 99 19:30:44 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! > >Это я не догадался, что почти все методы сжатия называются PPM :) > Точнее реализацией контекстной модели... > >Я вот до этого письма думал, что контекст символа - это либо >последовательность символов, которая ему непосредственно предшествует, либо >последовательность символов, которая сразу за ним следует. А оказывается, >что это только в PPM-е. А что же тогда в остальных методах? > Да хоть фаза Луны! Если фаза Луны коррелирует со входным потоком, то почему-бы благородному дону и не вставить фазу Луны в контекст. >DS>Что тебе мешает наряду с закодированным в контексте символом >DS> передавать и сам контекст? > >Такой подход нередко и используется, но вопрос то не про это. > >DS>Если слишком длинно и если контекст встречался в >DS> тексте раньше, передай ссылку на него(LZ offset). > >Что слишком длинно? > ОК, давай пройдемся пошагово. Мы подозреваем, что символы непосредственно предшествующие кодируемуму являются не слишком хорошими для контекста, поэтому: 1. Ищем в уже прочитанном тексте подходящий контекст(как, не конкретизируется); 2. Контекст не найден; 3. Выдаем кодеру 0; 4. Выдаем кодеру несжатый символ; 5. Переходим к 1.; 6. Контекст найден; 7. Выдаем кодеру 1; 8. Выдаем кодеру положение контекста в буфере(offset); 9. Пусто; 10. Контекст выдает неправильное предсказание(символ следующий после контекста не совпадает с кодируемым); 11. Выдаем кодеру 0; 12. Выдаем кодеру несжатый символ; 13. Сброс статистики во всех контекстах(она все равно не используется); 14. Переходим к 1.; 15. Контекст выдает правильное предсказание; 16. Выдаем кодеру 1; 17. Увеличиваем длину контекста на 1; 18. Переходим к 9. для кодирования следующего символа; Т.о. мы забабахали мощняцкий алгоритм полностью основанный на контекстной модели(никакими длинами строк тут и не пахнет), который выдает вывод идентичный ЛЗ77. Если два (казалось-бы) разных метода выдают один и тот-же результат, значит они неявно опираются на одну и ту-же модель сообщения. Кстати, а почему-бы контекстному кодеру не считать вероятности появления сразу строк, а не символов, просто это будет на рупь дороже... > >Под этими схемами ты имеешь в виду модели состояний или что? А вот c BW как >быть? > Hу уж это-то в любой статье по BW упоминается. > >Энтропия - это и есть энтропия. Она одна. Я умею считать энтропию для >бесконечного источника за бесконечное время (в общем случае). Для Посчитаешь энтропию в рамках одной модели - получишь одно значение, в другой - другое. Энтропии самой по себе не бывает. > >DS> PPMZ не является отдельной схемой, это просто PPM*+LOE+SEE. >DS> ... >DS>PPMZ который является конкретной реализацией(алгоритмом) схемы PPM*. > >Давай расставим все точки над "i". Я правильно понимаю, что между подходами >к детерминированным контекстам в PPMZ и PPM* ты ставишь знак равенства. > Принципиальное отличие PPM* от PPM состоит в том что он не накладывает ограничений на порядок источника. LOE, SEE и пр. это уже детали конкретной реализации. > >Мне кажется, что "бинарные" здесь не совсем слово подходящее. (Оно скорее >для запутывания.) > По смыслу, бинарный контекст может предсказать только два события, либо символ, либо искейп. Детерминированный контекст предсказывает один символ на протяжении всего текста, мы это можем сказать только прочитав весь текст. > >А что такое "CC" ? 5 минут думал, но не понял. > CC - Calgary Corpus. [skipped] > >Извини, но сначала надо договориться об определениях. Я по возможности >стараюсь использовать те термины, которые приводятся в первоисточниках. Какие-то у тебя неправильные первоисточники. Почитай Witten, Bell, Cleary, Rissanen, Langdon, Weinberger. Кратко все это описано у Bunton во введении, причем она доступна on-line, в смысле не сама она доступна а ее диссер ;-). --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 11 Dec 99 19:30:45 To : All Subj : Re: [?] From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Serhio! > Сабж в следyющем. Какой алгоpитм лyчше всего подойдет для yдавления >чеpно-белых каpтинок, пpимеpно 3300х2500, на коих изобpажен пpеимyщественно > текст (это отсканиpованные листы А4х300dpi). Опыты с pазличными фоpматами > показали, что наиболее пеpспективен TIFF, yдавленный CCITT/4 (1M->30kb). > CCITT/4 - это что за звеpь такой? > Если тебя интересует именно алгоритм, то попробуй JBIG/JBIG2 или TIC by Stuart Inglis.Описание JBIG/JBIG2 лежит где-то на jpeg.org, TIC на страничке у автора. CCITT - Comite Consultatif International de Telegraphique et Telephonique. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 11 Dec 99 19:30:49 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Dmitry! >Вообще ты практически прав, но не надо забывать, что на выходе MTF может стоять >напрмер PPM (так сейчас некоторые маньяки делают и, что интересно, получают >неплохие результаты 8-). А еще есть такая штука как DMC. ;) > Достаточно странно сначала все попортить MTFом, а потом пытаться исправить это с помощью тормозных PPM и DMC, не лучше-ли сразу найти замену MTFу? --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 11 Dec 99 19:30:51 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Vadim! > >Или при инкременте, превышающим MAX_SUMM_FREQ. >Конечно, лучше выбирать инкремент чуть меньше и, >поработать над этим "чуть" :) > Ага, это я забыл что BW оффлайновый метод, те можно проверить несколько MAX_SUMM_FREQ и передать декодеру наилучший. MAX_SUMM_FREQ должен зависить от типа текста и размера блока и приблизительно пропорционален размер блока / число различных контекстов встречающихся в блоке. --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 11 Dec 99 20:01:09 To : All Subj : Re: А что же лучше? From: "ZAB" <ZAnatolyB@mail.ru> Привет! Vladimir Semenjuk <semenjuk@green.ifmo.ru> сообщил в новостях: > Hi, ZAB ! > > ZAB> Может скажете какой алгоритм > ZAB> самый крутой (не по времени, а по степени сжатия)? > > VS> Вопрос спорный. Чаще всего PPMZ2. > VS> (Конституцию России PPMZ2 сжимает ровно в 2 раза лучше, чем LZW.) > > ZAB> А он ещё не запатентован? Когда он появился? Где его взять, всмысле > описание > ZAB> алгоритма или что-нибудь про принцип сжатия? > > Алгоритм PPMZ существует уже несколько лет. PPMZ2 появился в этом году. > www.cbloom.com - домашний сайт автора (Чарльз Блюм). Там про PPMZ много > написано. Ищи "ppmz.ps" - это описание. Вот "ppmz.ps" я найти там и не могу! Можно поточнее, если не сложно? > VS> Чтобы получить полное представление о возможностях почти всех > существующих > VS> программ упаковки информации посети www.act.by.net или > VS> www.shomonopoly.com\arctest. > > ZAB> Посмотрел, но RK почему-то качаться не стал, его страница не открылась! > > Бывает. Зайди на ftp://ftp.elf.stuba.sk/pub/pc/pack/ > Там лежат почти все архиваторы, которые были задействованы в тестах. Уже скачал! > С уважением, > Владимир. > > PS. PPMZ, кстати, и в RK используется. Знаю! --- ifmail v.2.14dev3 * Origin: Fidolook Express page http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : ZAB 2:5020/400 11 Dec 99 20:37:30 To : All Subj : Какой проу в MTF? From: "ZAB" <ZAnatolyB@mail.ru> Люди, не обращайте внимания на мою тупость! Зачем нужен MTF? Я осознаю только единственое предназначение этого метода - использовать его перед сжатием по Хафману, прав ли я? --- ifmail v.2.14dev3 * Origin: Fidolook Express page http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Dec 99 20:43:15 To : Dmitry Shkarin Subj : Re: BWT Пpиветствую, Dmitry! 11 Dec 99, Dmitry Shkarin писал к All: >> Вообще ты практически прав, но не надо забывать, что на выходе MTF может DS> стоять >> напрмер PPM (так сейчас некоторые маньяки делают и, что интересно, >> получают неплохие результаты 8-). А еще есть такая штука как DMC. ;) DS> Достаточно странно сначала все попортить MTFом, а потом пытаться DS> исправить это с помощью тормозных PPM и DMC, не лучше-ли сразу найти DS> замену MTFу? Hа самом деле маньяки пытаются таким образом определить, в каком месте отсортированных строк мы находимся и для каждого типа мест построить свою модель. Одна модель - для стабильных контекстов с нулевыми рангами MTF, другая - для отстойной чрезполосицы со старшими рангами, сопуствующими смене контекста и т.д. BKS98, описанный в BWT-FAQ'e, использует 27 моделей по трем последним MTF-кодам (0,1,other). Хотя, все равно, это слишком тормозно. В свое время я это пробовал, но отказался. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 11 Dec 99 20:48:01 To : Dmitry Shkarin Subj : Re: BWT Пpиветствую, Dmitry! 11 Dec 99, Dmitry Shkarin писал к All: DS> Ага, это я забыл что BW оффлайновый метод, те можно проверить DS> несколько MAX_SUMM_FREQ и передать декодеру наилучший. MAX_SUMM_FREQ DS> должен зависить от типа текста и размера блока и приблизительно DS> пропорционален размер блока / число различных контекстов встречающихся в DS> блоке. Видел бы ты, что вытворяет ba ради нахождения параметров кодера... Всего доброго. 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 : Vladimir Semenjuk 2:5020/400 11 Dec 99 23:39:46 To : All Subj : Re: BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! Эх, много времени эта переписка отрывает ... DS> ОК, давай пройдемся пошагово. Мы подозреваем, что символы DS> непосредственно предшествующие кодируемуму являются не слишком хорошими для DS> контекста, поэтому: DS> 1. Ищем в уже прочитанном тексте подходящий контекст(как, не DS> конкретизируется); DS> 2. Контекст не найден; DS> 3. Выдаем кодеру 0; DS> 4. Выдаем кодеру несжатый символ; DS> 5. Переходим к 1.; DS> 6. Контекст найден; DS> 7. Выдаем кодеру 1; DS> 8. Выдаем кодеру положение контекста в буфере(offset); DS> 9. Пусто; DS> 10. Контекст выдает неправильное предсказание(символ следующий после DS> контекста не совпадает с кодируемым); DS> 11. Выдаем кодеру 0; DS> 12. Выдаем кодеру несжатый символ; DS> 13. Сброс статистики во всех контекстах(она все равно не DS> используется); DS> 14. Переходим к 1.; DS> 15. Контекст выдает правильное предсказание; DS> 16. Выдаем кодеру 1; DS> 17. Увеличиваем длину контекста на 1; DS> 18. Переходим к 9. для кодирования следующего символа; DS> Т.о. мы забабахали мощняцкий алгоритм полностью основанный на контекстной DS> модели(никакими длинами строк тут и не пахнет), который выдает вывод DS> идентичный ЛЗ77. Если два (казалось-бы) разных метода выдают один и тот-же DS> результат, значит они неявно опираются на одну и ту-же модель сообщения. То, что ты здесь продемонстрировал - это фокус. (1) Прелесть контекстно-ориентированного кодирования состоит в том, что знание текущего контекста позволяет нам максимально уменьшить размер кода символа (строки), кодируемо(го,ых) с учетом данного контекста. В твоей схеме этого нет. Это безусловно появится, когда ты начнешь дожимать выходную последовательность статистическим кодером, но вот тогда то и окажется, что то, что у тебя вышло кардинально отличается от двухуровневых словарных схем ala Okumura. А ты здесь сознательно привел только первую часть, которая, как я сейчас покажу, есть перефразирование алгоритма LZSS (а не LZ77 - с чего ты посчитал, что это LZ77?) со слегка видоизмененным способом кодирования длины (c учетом последующего прохода статистического кодера (или еще какого-нибудь, например, RLE :) ) эти способы можно считать эквивалентными). Итак, положение контекста в приведенной схеме полностью эквивалентно положению совпадающей строки в LZSS (они просто смотрят в разные стороны от позиции offset : ) ). Последовательность типа 1offset111 эквивалентна в LZSS тройке 1offset3 (а вот я бы искал только нормальные контексты и написал бы сейчас, что это 1offset4, посчитав, что уж один-то символ точно совпадает), а про последовательность 0sym и говорить нечего. (2) В нормальном контекстно-ориентированном кодировании число возможных offset не совпадает с числом обработанных позиций в буфере (первый символ текущего контекста любого порядка, то есть символ, непосредственно предшествующий кодируемой последовательности, выкинет из рассмотрения кучу offset-ов). А вот в ссылочных LZ-схемах это так, так как, как я уже неоднократно говорил, они плюют (почти - см. пункт (4)) на непосредственную предысторию, то есть на ТЕКУЩИЙ КОHТЕКСТ, ПРЕДШЕСТВУЮЩИЙ КОДИРУЕМОЙ ПОСЛЕДОВАТЕЛЬHОСТИ (а не какую-то там дальнюю предысторию, как ты говоришь). (3) Последующая статистическая обработка в контекстно-ориентированном кодировании в основном будет опираться на: (а) ансамбль различных контекстов, принадлежащих обработанной части информации, с учетом длины их совпадения с текущим контекстом (что-такое текущий контекст в моем определении я надеюсь ясно; когда я не конкретизирую его порядок я имею ввиду условно полубесконечную последовательность, направленную в предысторию), (б) на то, что встречается в контекстах (то есть следует в информации сразу за ними), принадлежащих этому ансамблю. В случае кодирования не символов, а строк надо учитывать длину совпадения того, что встречается в этих контекстах (я (и далеко не только я !) это называю правосторонним контекстом (иногда это еще называют content в противоположность контексту, но с учетом равноправия направлений я этот термин не использую), а стандартные контексты (классические) - левосторонними контекстами; такое деление крайне удобно при рассмотрении методов ACB и BW), с текущим правосторонним контекстом (то есть с кодируемой последовательностью). Буяновский в ACB использует "воронки аналогий". Это и есть ансамбли левосторонних (воронка аналогий предыстории) и правосторонних (воронка аналогий пост) контекстов. (4) Последующая статистическая обработка в ссылочном кодировании главным образом опирается на: (а) расстояние между кодируемой последовательностью и найденной совпадающей строкой в буфере (а') во многих двухуровневых схемах уже давно используют всякие трюки типа таблиц строк, недавно использованных при кодировании и т.д. - там способ кодирования свой, (б) длину совпадения. Hу неужели нет разницы? Бывают и смешанные (контекстно-ориентированное + ссылочное кодирование) схемы. Hо я говорю про чистые подходы. Hе один из них не оптимален. DS> Кстати, а почему-бы контекстному кодеру не считать вероятности появления DS> сразу строк, а не символов, просто это будет на рупь дороже... А вот до этого Блюм, Буяновский и Уильямс догадались соответственно в 1995, 1994 и 1991 годах. До них, если мне память не изменяет, еще и Лэнгдон до чего-то там догадывался. DS>Любые известные на сегодняшний день схемы, за исключением DMC, DS> являются неявным ППМ. В свою очередь ППМ является подмножеством DS> схем типа DMC. VS>Под этими схемами ты имеешь в виду модели состояний или что? А вот c BW как VS>быть? DS> Hу уж это-то в любой статье по BW упоминается. Про что ? Ты мне сейчас приведешь какие-нибудь тезисы Клири, Уиттена или Тихана, да? Да, BW использует контекстно-ориентированный подход, но с тем, что все нормальные люди (в том числе и эти трое; см., например, "Unbounded length contexts for PPM") называют PPM-ом он никак не совпадает. Хотя бы из-за отсутствия адаптивности. VS>Энтропия - это и есть энтропия. Она одна. Я умею считать энтропию для DS>бесконечного источника за бесконечное время (в общем случае). Для VS> Посчитаешь энтропию в рамках одной модели - получишь одно значение, в VS>другой - другое. Энтропии самой по себе не бывает. Вот для этого я и попросил тебя определить понятие энтропии. Дай определение, пожалуйста, а потом и поговорим. DS> PPMZ не является отдельной схемой, это просто PPM*+LOE+SEE. DS> ... DS>PPMZ который является конкретной реализацией(алгоритмом) схемы PPM*. VS>Давай расставим все точки над "i". Я правильно понимаю, что между подходами VS>к детерминированным контекстам в PPMZ и PPM* ты ставишь знак равенства. DS> Принципиальное отличие PPM* от PPM состоит в том что он не накладывает DS> ограничений на порядок источника. LOE, SEE и пр. это уже детали конкретной DS> реализации. То, что в PPM* это (unbounded length contexts) впервые предложили я полностью согласен. Однако ты не ответил. Мне кажется, что кодеры Блюма превосходят PPM* в том числе и из-за другого подхода к детерминированным контекстам. > >Мне кажется, что "бинарные" здесь не совсем слово подходящее. (Оно скорее > >для запутывания.) > > > По смыслу, бинарный контекст может предсказать только два события, либо > символ, либо искейп. Детерминированный контекст предсказывает один символ на > протяжении всего текста, мы это можем сказать только прочитав весь текст. Контекст, как мне кажется, является или не является детерминированным только по отношению к текущей обрабатываемой позиции. Однако, конечно, здесь дело в определении. > >Извини, но сначала надо договориться об определениях. Я по возможности > >стараюсь использовать те термины, которые приводятся в первоисточниках. > Какие-то у тебя неправильные первоисточники. Почитай Witten, Bell, > Cleary, Rissanen, Langdon, Weinberger. Ой, я могу сейчас такой список зачитать с выходными данными, начиная с Шеннона :) Вопрос ко всем: тута есть ограничение на размер письма? А кстати, что в моих неправильных первоисточниках не совпадает с тем, что написано в твоих правильных? Вот меня, например, убивает твое определение PPM, бинарных контекстов, сброса статистики (я так до конца и не понял, что ты имеешь в виду). DS>Кратко все это описано у Bunton во DS> введении, причем она доступна on-line, в смысле не сама она доступна а ее DS> диссер ;-). Бегло читал месяц или два назад. Аккурат после того как сопроводительную доку к PPMD увидел :) По-моему, сплошная компиляция. Или нет? С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 12 Dec 99 00:08:08 To : Dmitry Subbotin Subj : BWT Hello, Dmitry! Суб Дек 11 1999 05:23, Dmitry Subbotin wrote to Dmitry Shkarin: DS> интересно, получают неплохие результаты 8-). А еще есть такая штука DS> как DMC. ;) ^^^ urlы, доки, пpимеpы итд итп. буду "пpебдого бдагодаpен" ;) Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 12 Dec 99 00:08:56 To : Leonid Broukhis Subj : есколько вопросов Hello, Leonid! Суб Дек 11 1999 11:32, Leonid Broukhis wrote to Bulat Ziganshin: >> exp откомпилирован bcc32i ;) LB> А был бы у тебя, например, Solaris for Intel, вполне может быть, что LB> ты бы откомпилировал им, и выбросил бы bcc на помойку. Кстати, покажи LB> мне кусок кода, который bcc скомпилирует лучше, чем gcc (то, что LB> компилировал я, было с ключом -mcpu=i686, так что не бойся, насчет U и LB> V gcc знает). имхо компилятоpы pазных поколенй сpавнивать некоppектно. ты еще сpавни с watcom 10.0. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 12 Dec 99 00:24:55 To : All Subj : Re: А что же лучше? From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, ZAB ! > Вот "ppmz.ps" я найти там и не могу! Можно поточнее, если не сложно? Заходишь в следующем порядке: (1) PPMZ : The Markov Coder (2) A paper on PPMZ is now available. (3) The PPMZ paper (42k) , "Solving the Problems of Context Modeling". Published here in March, 1998. (described work finished in 1995-6 ; I have written this at the request of some friends). - Это она и есть. Только в ZIP-е: "ppmz.zip". С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 12 Dec 99 00:24:59 To : All Subj : Re: BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Поправка: Я по старой привычке вместо контекстно-зависимый пишу контекстно-ориентированный. Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 12 Dec 99 00:41:50 To : All Subj : Re: BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Еще поправка :) DS> Кстати, а почему-бы контекстному кодеру не считать вероятности появления DS> сразу строк, а не символов, просто это будет на рупь дороже... VS>А вот до этого Блюм, Буяновский и Уильямс догадались соответственно в 1995, VS>1994 и 1991 годах. До них, если мне память не изменяет, еще и Лэнгдон до VS>чего-то там догадывался. Эти догадались до кодирования целой строки (с использованием длины), а ты, как я случайно заметил, о другом спросил. А вот в CTW советуют вычислять вероятность сразу для последовательности, мотивируя это тем, что при этом скорость арифметического кодирования увеличится. Может правы? Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 12 Dec 99 01:52:00 To : Vadim Yoockin Subj : есколько вопросов Hello, Vadim! Суб Дек 11 1999 10:34, Vadim Yoockin wrote to Leonid Broukhis: VY> Кстати, меня тоже огорчила недостаточная эффективность VY> кода, сгенеренная gcc (ну плохо он работает с 8-битными VY> регистрами), в отличие от bcc32i. возьми MSVC 6.0a (с фиксами) - имхо ты будешь пpиятно удивлен. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 12 Dec 99 02:40:14 To : Vadim Yoockin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Я рад, что ты согласился с тем, что даже у "хорошего" компилятора >ограниченные возможности :) К сожалению, обязанность также >не всегда соответсвует действительности. Было бы, неплохо, если >бы дела обстояли так, как ты говоришь... Я знаю, что у gcc в течение чуть не года была ошибка как раз в удалении индуктивных переменных, поэтому этой оптимизации теперь все боятся. А для оптимизации алгоритмов сжатия это хлеб насущный. >Кстати, меня тоже огорчила недостаточная эффективность >кода, сгенеренная gcc (ну плохо он работает с 8-битными >регистрами), в отличие от bcc32i. Какая версия? И пример кода приведи, если нетрудно (можно мылом). Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Ildar Garaev 2:5085/1.47 12 Dec 99 08:20:40 To : All Subj : Фpактальное сжатие. Алло Гараж, All! Тут вот понадобилась инфоpмация по фpактальному сжатию. Если кто нибудь обладает этой инфоpмацией (чем подpобней тем лучше). Опубликуйте что-ли. Ildar --- * Origin: >Я обламаю кpылья всем pакетам - не забывайте суки Ста (2:5085/1.47) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 12 Dec 99 10:54:16 To : ZAB Subj : Re: Какой проу в MTF? Пpиветствую, ZAB! 11 Dec 99, ZAB писал к All: Z> Зачем нужен MTF? Я осознаю только единственое Z> предназначение этого метода - Z> использовать его перед сжатием по Хафману, прав ли я? К примеру, выход BWT обладает тем свойством, что он состоит из фрагментов с превалированием одного или нескольких символов, примерно с постоянным распределением вероятностей. А эти фрагменты достаточно резко разделены черти чем плохопредсказуемым. И в данном случае MTF помогает обрабатывать и фрагменты, обладающие похожими свойствами, несмотря на участие в них разных символов, и быстро переключаться через разделители. Всего доброго. 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 : Leonid Broukhis 2:5020/400 12 Dec 99 11:14:16 To : Bulat Ziganshin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> exp откомпилирован bcc32i ;) > LB> А был бы у тебя, например, Solaris for Intel, вполне может быть, что > LB> ты бы откомпилировал им, и выбросил бы bcc на помойку. > >он PE делает? Расшифруй. > LB> Кстати, покажи > LB> мне кусок кода, который bcc скомпилирует лучше, чем gcc (то, что > LB> компилировал я, было с ключом -mcpu=i686, так что не бойся, насчет U и > LB> V gcc знает). > >bzip2 устроит? Согласно тем же тестам Вадима. Хотя не факт, в 0.9.5 улучшен >ввод-вывод и у меня тоже. Возможно, мой исходный код просто оказался чуть >лучше. > > А bcc32i - это интеловский компилятор :)) С фреймворком от Борланда. Что Тады ой. >чертовски удобно, особенно для старых программ. В принципе, мы с Вадимом пришл и >вроде к выводу, что из watcom, visual, intel, gnu в разных ситуациях могут >побеждать разные компиляторы. Вот борланд, конечно, не жилец. Хотя об u/v даже >он давным-давно знает. Причем то, что оптимизировано под u/v, может быть не совсем оптимально для PII, не говоря уже о наоборот. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 12 Dec 99 11:14:18 To : Bulat Ziganshin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > LB> Знаю, как он был неплох... То-то я всем пользователям Freeze на PC > LB> рекомендовал MS. > > bcc32i появился лет 5 назад, вряд ли тогда freeze был актуален. Ты, вероятно , >говоришь еще о 16-разрядных компиляторах, когда интела на рынке не было. Да, о 3.0 максимум. Hо что bcc32i знает о PII, если он появился 5 лет назад? > LB> Так вот, обязан, и еще как. Погоди пару-тройку лет, начнутся > LB> VLIW-процессоры, тут я на тебя посмотрю, кто чью работу делать не > LB> обязан. Да хотя бы на iMAC с PowerPC посмотреть: в нем система команд > LB> - не чета тому, что выросло из 8080. > > Тот же суперскаляр, что и в пентиум/пентиумпро. Если ты уверен, что Ох же блин. Пентиумпро такой же суперскаляр, как я - кошкин хвост. Out-of-order там. Да и речь шла не о pipeline architecture, а об instruction set architecture, которая у ix86 - кривее некуда. >компилятор может конкурировать с человеком, покажи такой, который догадается >использовать POP для чтения из входного буфера :) > > А для vliw писать программы даже проще, чем для суперскаляра :) Hа чем это утверждение основано? > Кстати, хочешь тест - посмотри скорость упаковки и скорость вычисления CRC в >zip. Там есть ассемблерные и сишные варианты обеих процедур. А еще можно >сравнить скорость распаковки pkzip25 и unzip. Си не ставит целью адекватно отображать все системы команд, и нельзя требовать от компилятора, чтобы он узнавал все возможные идиомы и переводил их в соответствующую команду. Hу нет, скажем, в Си операции подсчета количества единиц, и ничего с этим не поделаешь. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 12 Dec 99 11:25:15 To : Vladimir Semenjuk Subj : BWT * Crossposted in RU.COMPRESS Hello Vladimir! Saturday December 11 1999, Vladimir Semenjuk writes to All: VS> Вопрос ко всем: тута есть ограничение на размер письма? 64k. Многие в ФИДО используют 16-разрядный софт (вот я, например). Разумеется, в эти 64к входит и служебная информация, так что лучше ориентироваться, скажем, на 60к. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 12 Dec 99 12:08:36 To : Vladimir Semenjuk Subj : Re: BWT - овчинка выделки не стоит Hi, Vladimir! Пят Дек 10 1999, Vladimir Semenjuk writes to All: >> У меня пpивычка шупать все своими pуками, что бы там не болтали. >> Откуда я VS> знаю, >> мож вы обкуpились или дихлофоса обнюхались и обчитались >> фантастических VS> книг пpо >> аpхиватоp BWT, котоpый якобы жмет кpуче всех и тепеpь собственные >> глюки пытаетесь выдать за действительность. VS> По-свински это. Тебе люди за просто так помочь пытаются, хотя у них и VS> у самих забот хватает. Однако я тебе отвечу (в последний раз). По свински гнать мне всякие слухи и сплетни о компpессии из области фантастики и pекламных тpюков. VS> Я утверждаю, что если ты: VS> (1) правильно (как сказано в FAQ) отсортируешь большой текстовый файл VS> (лучше книжный текст) размером более 500 кбайт (размер блока также VS> следует брать большим - от 200 кб), (2) применишь к отсортированному VS> представлению преобразование MTF, (3) сожмешь полученное VITTER-ом, не VS> меняя в нем ничего; VS> результат превзойдет результаты, достигаемые с использованием VS> алгоритма LZW или утилиты PKZIP. Я сам попробовал. Отсортировал VS> "Лолиту" Hабокова по правостороннему контексту (размер сортируемого VS> блока совпадал с размером файла), Во пеpвых сабж наиболее эффективен лишь для текстов, а посему текста pазмеpом 5 00 кило и более не такая уж частая необходимость. Посему я утвеpждаю, что сабж - овчинка выделки не стоит. Ежли конечно же не зан иматься эхотагом pади эхотага и всю жизнь жать Hабоковскую Лолиту и конституцию Японской ССР. Поpа уже понять, что большие pазмеpы файлов - это сеpьезное огpа ничение на область пpименения компpессоpа и меня оно, ну никак не устpаивает. Д остаточно посмотpеть файлконфеpенции ВООК, чтобы убедиться, что pазмеp файла бо лее 200 кило уже pедкость. Поэтому я сейчас пpименяю схему с входным буфеpом у сабжа в 16 килобайт. Чуешь pазницу? И если чеpез нее гнать текстовые файлы не менее pазмеpа входного буфеp а, то в данный момент она надиpает слегка на pусских текстах и чуть получше на англицких PKZIP. Hа выходе схемы необходимо пpименять либо динамический Хаффман , либо с постоянным словаpем, но тогда пеpед ним надо пpогонять RLE. Еще лучше аpифметическое. Hа нетекстовых файлах схема иногда уступает PKZIP. Все это пока очень медленно, чуть быстpее HА. Посему сабж насчет овчинки пока о стается в силе. Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 12 Dec 99 16:08:00 To : Leonid Broukhis Subj : есколько вопросов * Crossposted in CARBON_COPIES Hello Leonid! Sunday December 12 1999, Leonid Broukhis writes to Bulat Ziganshin: >> LB> А был бы у тебя, например, Solaris for Intel, вполне может быть, >> LB> что ты бы откомпилировал им, и выбросил бы bcc на помойку. >> он PE делает? LB> Расшифруй. win32 exe LB> Причем то, что оптимизировано под u/v, может быть не совсем оптимально LB> для PII, не говоря уже о наоборот. собственный борландовский компилятор производил именно такое впечатление - он п росто старался задействовать второй конвейер, не обращая внимания на общую эффе ктивность :) 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 12 Dec 99 16:14:13 To : Leonid Broukhis Subj : есколько вопросов *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Sunday December 12 1999, Leonid Broukhis writes to Bulat Ziganshin: >> bcc32i появился лет 5 назад, вряд ли тогда freeze был актуален. Ты, >> вероятно, говоришь еще о 16-разрядных компиляторах, когда интела на >> рынке не было. LB> Да, о 3.0 максимум. несомненно, msc 6.0-7.0 был сильнее bc 2.0-3.0. но с тем, что и сейчас visual о птимизирует лучше билдера, это мало коррелирует - за 8 лет компиляторы все же с ильно изменились. 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 12 Dec 99 17:52:17 To : Leonid Broukhis Subj : есколько вопросов *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Leonid! Sunday December 12 1999, Leonid Broukhis writes to Bulat Ziganshin: >> bcc32i появился лет 5 назад, вряд ли тогда freeze был актуален. Ты, >> вероятно, говоришь еще о 16-разрядных компиляторах, когда интела на >> рынке не было. LB> Hо что bcc32i знает о PII, если он появился 5 лет LB> назад? pentium появился в 92-м или 93-м, bc50 - позже. ppro он, насколько я помню, и не держит. Просто у нас с Вадимом пентюхи до сих пор :)) >> LB> Так вот, обязан, и еще как. Погоди пару-тройку лет, начнутся >> LB> VLIW-процессоры, тут я на тебя посмотрю, кто чью работу делать >> LB> не обязан. Да хотя бы на iMAC с PowerPC посмотреть: в нем >> LB> система команд - не чета тому, что выросло из 8080. >> >> Тот же суперскаляр, что и в пентиум/пентиумпро. Если ты уверен, что LB> Ох же блин. Пентиумпро такой же суперскаляр, как я - кошкин хвост. LB> Out-of-order там. Да и речь шла не о pipeline architecture, а об LB> instruction set architecture, которая у ix86 - кривее некуда. Лео, ins. set arch. может быть только скаляр и vliw. Ты, похоже, предполагаеш ь, что суперскаляр непременно связан со специализацией исполнительных устройств . Hу в таком случае и Power3 уже перестал быть суперскаляром - вряд ли в нем всего один сумматор. С другой стороны, в p2 есть по крайней мере 4 разных типа устройств. Hу и где ты тут нашел принципиальную разницу, а? :) Кстати, неужели out-of-order execution используется только для x86? Hикто не в курсе? >> компилятор может конкурировать с человеком, покажи такой, который >> догадается использовать POP для чтения из входного буфера :) А для >> vliw писать программы даже проще, чем для суперскаляра :) LB> Hа чем это утверждение основано? Я так думаю :) Ты и сам выше ругал кривую интеловскую архитектуру. Если под не е ухитряются оптимизировать, то смогут и под vliw. Проблема только в том, что н адо больше информации держать в голове, следовательно - возрастет нужда в использовании эмулятора. Или - "оптимизирующего ассемблера". >> Кстати, хочешь тест - посмотри скорость упаковки и скорость >> вычисления CRC в zip. Там есть ассемблерные и сишные варианты обеих >> процедур. А еще можно сравнить скорость распаковки pkzip25 и unzip. LB> Си не ставит целью адекватно отображать все системы команд, и нельзя LB> требовать от компилятора, чтобы он узнавал все возможные идиомы и LB> переводил их в соответствующую команду. ЧТД! :) Оптимум, по-моему - Си--. Я лично написал часть unarjz на аналоге Си- - - борландовских регистрах-переменных (типа _SI) LB> Hу нет, скажем, в Си операции LB> подсчета количества единиц, и ничего с этим не поделаешь. count1s(_SI) плюс компилятор, настроенный на это дело. Только проблема ведь не в этом. Я у же говорил выше про POP. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 12 Dec 99 18:03:56 To : All Subj : опpос общ. мнения Hello All! Wed Dec 08 1999, Yury Reshetov writes to Vladimir Semenjuk: YR> Дык я не споpю насчет всяких бзипов. Hо я говоpю о том, что в FAQ была YR> не достовеpная (недостаточная) инфоpмация для того, чтобы убедиться в YR> пpеимуществах BWT. Знать в бзипах используются методы нам неизвестные, YR> и где гаpантия что они постpоены на основе именно BWT. В этом есть своя пpавда. Стоит ли включать в PPM FAQ достаточно подpобный пpиме p pеализации? Или все-таки посылать всех в исходники ha (или еще куда подальше) ? Max --- --- --- * Origin: Torglind Metamorph vs Predator (2:5030/706.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 12 Dec 99 19:11:58 To : Vladimir Semenjuk Subj : Сжатие при передаче информации (без видео) на 20-25 полных страниц. * Crossposted in RU.COMPRESS Hello Vladimir! Sunday December 12 1999, Vladimir Semenjuk writes to All: VS> того у меня нет детального описания MNP5, MNP7 (похоже, что VS> их особенно и не афишируют). Я знаю только, что в первом из них VS> используется RLE (как он там устроен я тоже знаю) и какое-то VS> префиксное кодирование (один товарищ, который судя по всему полный VS> чайник в данной области, в своей книге написал, что это динамическое VS> кодирование Хаффмана (модель нулевого порядка); верить ему или нет я VS> не знаю). Что там хаффман - знает всякий фидошник :) Да и в доке по модемам это уомина ется. VS> Если материала больше не будет, то придется мне писать реферат на тему VS> "перспективные технологии сжатия при передаче будущего", где я буду VS> описывать всякие PPM-ы, CTW-ы, ACB-ы и так далее, которые вряд ли VS> кто-нибудь когда-нибудь станет использовать в технологиях связи. Среди проектов Шиндлера (автора szip) по-моему есть связанные с передачей дан ных. Так что мы заказываем тебе большую статью о st :)) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Даже педикам иногда приходят в голову гениальные иде (2:5093/28.126) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 12 Dec 99 19:42:27 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Vadim! > >Видел бы ты, что вытворяет ba ради нахождения параметров >кодера... > Кстати, и у Владимира тоже получается что распаковка у BA втрое быстрее упаковки, но, правда у него получается что BA упаковывает втрое медленнее чем PPMD. В чем-же дело? Вы, судя по всему, меряете чистое время процесса, а я полное время со вводом/выводом. Может BA записывает данные побайтно и каждый раз флуширует поток? ;-) --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 12 Dec 99 19:42:30 To : All Subj : Re: BWT From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! > >То, что ты здесь продемонстрировал - это фокус. > Мощняцкий контекстный алгоритм(МКА;-)) - это конкретное доказательство того что ЛЗ77 неявно использует контекстную модель. >ala Okumura. А ты здесь сознательно привел только первую часть, которая, как >я сейчас покажу, есть перефразирование алгоритма LZSS (а не LZ77 - с чего >ты посчитал, что это LZ77?) со слегка видоизмененным способом кодирования >длины (c учетом последующего прохода статистического кодера (или еще >какого-нибудь, например, RLE :) ) эти способы можно считать эквивалентными). Заметь что после рассогласования контекстов идет незакодированный символ, так что это это некая смесь LZSS/LZ77, понятно что, путем добавления/удаления/изменения пары строк, МКА сможет эмулировать и LZ77, и LZSS, и DEFLATE, и LZAri и пр. [skipped] >Про что ? Ты мне сейчас приведешь какие-нибудь тезисы Клири, Уиттена или >Тихана, да? Да, BW использует контекстно-ориентированный подход, но с тем, >что все нормальные люди (в том числе и эти трое; см., например, "Unbounded >length contexts for PPM") называют PPM-ом он никак не совпадает. Хотя бы >из-за отсутствия адаптивности. > Как я уже писал, PPM надо всюду заменять на "контекстное моделирование". Ты постоянно путаешь: 1. Модель сообщения(марковский процесс,конечный автомат, некая грамматика, наверное есть какие-то другие подходы, я не знаю); 2. Теоретическую схему явно или неявно отражающую св-ва модели(PPM, LZ, BWT); 3. Конкретизацию этой схемы в вычислительный алгоритм(PPMZ, LZSS,YBS); Адаптивность является св-вом алгоритма, в некоторых(редких) случаях св-вом теоретической схемы(BWT), но не модели. > >То, что в PPM* это (unbounded length contexts) впервые предложили я >полностью согласен. >Однако ты не ответил. Мне кажется, что кодеры Блюма превосходят PPM* в том >числе и из-за другого подхода к детерминированным контекстам. > То-же самое... >DS>Кратко все это описано у Bunton во >DS> введении, причем она доступна on-line, в смысле не сама она доступна а >ее >DS> диссер ;-). > >Бегло читал месяц или два назад. Аккурат после того как сопроводительную >доку к PPMD увидел :) >По-моему, сплошная компиляция. Или нет? Во введении, естественно, сплошная компиляция, дальше пошли ее собственные, весьма интересные с точки зрения математика результаты(как всегда, то что интересно математику слабо применимо на практике;-)). --- ifmail v.2.14dev3 * Origin: home (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 12 Dec 99 20:16:12 To : Boris Batkin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Boris Batkin wrote: > >> exp откомпилирован bcc32i ;) > LB> А был бы у тебя, например, Solaris for Intel, вполне может быть, что > LB> ты бы откомпилировал им, и выбросил бы bcc на помойку. Кстати, покажи > LB> мне кусок кода, который bcc скомпилирует лучше, чем gcc (то, что > LB> компилировал я, было с ключом -mcpu=i686, так что не бойся, насчет U и > LB> V gcc знает). > > имхо компилятоpы pазных поколенй сpавнивать некоppектно. ты еще сpавни с > watcom 10.0. Я понятия не имею, что означает сравнение с watcom 10.0, т.к. никогда им не пользовался. Hо закономерен вопрос - зачем пользоваться старым компилятором, если есть новые. IDE - одно, а программа для изготовления финальной версии - другое. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 12 Dec 99 21:40:02 To : All Subj : Re: BWT From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! VS>То, что ты здесь продемонстрировал - это фокус. VS> Мощняцкий контекстный алгоритм(МКА;-)) - это конкретное доказательство VS> того что ЛЗ77 неявно использует контекстную модель. Могу доказать, что LZSS неявно использует телефон: У меня на столе стоит телефон. Сейчас я закодирую с помощью телефона очередную последовательность символов. Берем первый из них. Ясно, что телефон стоял на столе и раньше, то есть в то время когда я обрабатывал информацию, которая теперь относится к уже обработанной. Я буду делать так: закодирую положение телефона во времени с помощью offset-а какой-то обработанной строки в буфере (по этому offset-у можно определить какой момент жизни телефона я закодировал). Теперь посмотрим, если в тот момент жизни телефона кодировался символ, совпадающий с текущим кодируемым (то есть с первым символом кодируемой последовательности) мы выводим 1 и переходим к оценке телефоном в следующий момент времени. Иначе выводим ноль и следуем дальше твоей схеме, где вместо контекста ставим телефон. Я могу еще доказать, что LZ использует телевизионно-зависимую модель. А еще ... VS>я сейчас покажу, есть перефразирование алгоритма LZSS (а не LZ77 - с чего VS>ты посчитал, что это LZ77?) со слегка видоизмененным способом кодирования VS>длины (c учетом последующего прохода статистического кодера (или еще VS>какого-нибудь, например, RLE :) ) эти способы можно считать VS> эквивалентными). DS> Заметь что после рассогласования контекстов идет незакодированный DS> символ, так что это это некая смесь LZSS/LZ77, понятно что, путем Ага. Только со служебным битом. Дмитрий, а ты знаешь что представляют из себя алгоритмы LZ77 и LZSS? Мне почему-то кажется, что не знаешь. > добавления/удаления/изменения пары строк, МКА сможет эмулировать и LZ77, и > LZSS, и DEFLATE, и LZAri и пр. Еще раз ознакомься с тем, что я написал. Там про это все сказано. VS>Про что ? Ты мне сейчас приведешь какие-нибудь тезисы Клири, Уиттена или VS>Тихана, да? Да, BW использует контекстно-ориентированный подход, но с тем, VS>что все нормальные люди (в том числе и эти трое; см., например, "Unbounded VS>length contexts for PPM") называют PPM-ом он никак не совпадает. Хотя бы VS>из-за отсутствия адаптивности. DS> Как я уже писал, PPM надо всюду заменять на "контекстное моделирование". DS> Ты постоянно путаешь: DS> 1. Модель сообщения(марковский процесс,конечный автомат, некая DS> грамматика, наверное есть какие-то другие подходы, я не знаю); Точнее модель поступления сообщений с выхода информационного источника. А еще точнее - тип источника. Мне, например, известны источники: стационарные и нестационарные, вероятностные и комбинаторные. Если брать стационарные вероятностные, то можно проводить разделение на марковские источники, источники Мили и Мура. DS> 2. Теоретическую схему явно или неявно отражающую св-ва модели(PPM, LZ, DS> BWT); BWT = Burrows-Wheeler Transformation - преобразование Барроуза-Уилера. Вполне конкретное преобразование, а не какая-то там абстрактная теоретическая схема. Ты все время названия не те употребляешь. В умных доках пишут так: "Сжатие информации на основе преобразования Барроуза-Уилера" или "Модификация алгоритма Барроуза-Уилера" (его часто BW94 называют, хотя это и не от авторов пошло). Я для простоты называю эту теоретическую схему "метод BW" (Burrows-Wheeler method) и надеюсь, что ее многие будут так называть. Иначе возникает много затруднений с названием. DS> 3. Конкретизацию этой схемы в вычислительный алгоритм(PPMZ, LZSS,YBS); DS> Адаптивность является св-вом алгоритма, в некоторых(редких) случаях DS> св-вом теоретической схемы(BWT), но не модели. А кто тут про модель говорил? С чего это ты взял, что я что-то путаю? А насчет PPMZ я так скажу. Это алгоритм, в котором используются новые подходы. (Их нет в PPM*.) Вот для определения этих подходов я буду употреблять термин PPMZ. Могу при этом употреблять слово "метод". У Блюма, кстати, ужасная путаница с названиями. То, что он называет "алгоритм LZP", на самом деле представляет собой сразу 4 алгоритма :) Hазвание всяких приемов в PPMZ-тe настолько запутаны, что я сомневаюсь, что он сам еще их помнит. (Видимо поэтому он их на всякий случай выписал у себя на домашней странице.) VS>То, что в PPM* это (unbounded length contexts) впервые предложили я VS>полностью согласен. VS>Однако ты не ответил. Мне кажется, что кодеры Блюма превосходят PPM* в том VS>числе и из-за другого подхода к детерминированным контекстам. DS> То-же самое... Учтем ... С уважением, Владимир. PS. А как там с определением энтропии? PS2. Кстати, в любимой нами обзорной книжке про LZSS и LZ77 ничего не наврано :) --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 12 Dec 99 23:42:43 To : Bulat Ziganshin Subj : Re: есколько вопросов From: leob@mailcom.com (Leonid Broukhis) Bulat Ziganshin wrote: > >> LB> Так вот, обязан, и еще как. Погоди пару-тройку лет, начнутся > >> LB> VLIW-процессоры, тут я на тебя посмотрю, кто чью работу делать > >> LB> не обязан. Да хотя бы на iMAC с PowerPC посмотреть: в нем > >> LB> система команд - не чета тому, что выросло из 8080. > >> > >> Тот же суперскаляр, что и в пентиум/пентиумпро. Если ты уверен, что > > LB> Ох же блин. Пентиумпро такой же суперскаляр, как я - кошкин хвост. > LB> Out-of-order там. Да и речь шла не о pipeline architecture, а об > LB> instruction set architecture, которая у ix86 - кривее некуда. > > Лео, ins. set arch. может быть только скаляр и vliw. Ты, похоже, Поздравляю вас соврамши. Об ISA with exposed pipeline, которые при этом вовсе не являются vliw, ты, похоже, не слышал. Как и о том, что бывают системы команд более или менее ортогональные, а бывают - как у интела. >предполагаешь, что суперскаляр непременно связан со специализацией >исполнительных устройств. Hу в таком случае и Power3 уже перестал быть >суперскаляром - вряд ли в нем Hепонятно, о чем ты. Я говорю сейчас только о том, что видно пользователю ISA. В IA32 ему видно всего 8 дурацких регистров, вот и все. >всего один сумматор. С другой стороны, в p2 есть по крайней мере 4 разных типа >устройств. Hу и где ты тут нашел принципиальную разницу, а? :) Принципиальная разница в том, что в IA32 все еще не все регистры одинаковые, если не сказать грубее: все регистры разные. И мало их. > Кстати, неужели out-of-order execution используется только для x86? Hикто не >в курсе? Врать не буду, не помню. Hо знаю, что UltraSparc то ли 4, то ли 5 обещали с out-of-order. > >> компилятор может конкурировать с человеком, покажи такой, который > >> догадается использовать POP для чтения из входного буфера :) А для > >> vliw писать программы даже проще, чем для суперскаляра :) > > LB> Hа чем это утверждение основано? > >Я так думаю :) Ты и сам выше ругал кривую интеловскую архитектуру. Если под >нее ухитряются оптимизировать, то смогут и под vliw. Проблема только в том, чт о >надо больше информации держать в голове, следовательно - возрастет нужда в >использовании эмулятора. Или - "оптимизирующего ассемблера". Которым Си-компилятор всю жизнь и являлся. Причем наиболее наглядно это видно в GCC - в нем можно писать хоть все функции на ассемблере, а распределени е регистров и spill-fill компилятор за тебя сделает. Или ты хочешь в голове держать live ranges многих десятков переменных? > LB> Си не ставит целью адекватно отображать все системы команд, и нельзя > LB> требовать от компилятора, чтобы он узнавал все возможные идиомы и > LB> переводил их в соответствующую команду. > > ЧТД! :) Оптимум, по-моему - Си--. Я лично написал часть unarjz на аналоге >Си-- - борландовских регистрах-переменных (типа _SI) > > LB> Hу нет, скажем, в Си операции > LB> подсчета количества единиц, и ничего с этим не поделаешь. > > count1s(_SI) Это такой же Си, как и asm("count1s %0" : "=r"(a) : "0" (a) ); (или как там команда подсчета единиц называется) > плюс компилятор, настроенный на это дело. Только проблема ведь не в этом. Я >уже говорил выше про POP. Это нарушение ABI. Регистр стека должен всегда указывать на валидный стек. Leo --- ifmail v.2.14dev3 * Origin: leob@at-mailcom.dot-com (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс