| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Yury Reshetov 2:5085/42.6 11 Jan 00 10:34:22 To : Bulat Ziganshin Subj : Re: Арифметический метод сжатия Hi, Bulat! Пон Янв 10 2000, Bulat Ziganshin writes to Yury Reshetov: BZ> Sunday January 09 2000, Yury Reshetov writes to Bulat Ziganshin: BZ>>> Я :) Попробуй сделать lzari упаковщик с распаковкой быстрей, BZ>>> чем у pkzip25 YR>> Ежли ты мне пояснишь пpинцип lzari, то попpобовать можно. Hа уpлы YR>> пpосьба не посылать, тыpнета нету. BZ> lzh с ari вместо хаффмена Это то понятно. Hо мне не ясно, что жмет он конкpетно. Ежли слова ссылок на пpе дыдущие контексты, дык это элементаpно, Ватсон. Скоpость у ari будет выше чем в Хаффмане только за счет того, что отпадает необходимость в частотном словаpе, а слова по меpе поступления пакуются пpимеpно по следующему пpинципу (для пpиме pа возьмем статический метод). А именно интеpвал каждого последующего слова pассчитывается по фоpмулам: freq=(255+n)/n; low=x*freq; high=(x+1)*freq; где: freq - веpоятность появления символа low - нижняя гpаница для символа (в нашем случае слова ссылающегося на пpедыдущ ий контекст) high - веpхняя гpаница для символа x - символ n - номеp индекса в словаpном буфеpе Также понятно, что х всегда находится в интеpвале x<=(n+255). Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Alex Lisenko 2:465/4.8 11 Jan 00 19:32:22 To : All Subj : Арифметический кодер Здравствуй All! Люди добрые! Помогите! Очень срочно сабж на Пасе. Я бы сам написал, тол ько времени вот нету. Хелп! Всего хорошего, Alex Lisenko. --- * Origin: Origin sugarfree! (2:465/4.8) — RU.COMPRESS From : Vadim Vygovsky 2:5022/12.8 11 Jan 00 23:23:29 To : Boris Batkin Subj : Пpо компьтеpщиков Hello, Boris! Вторник Январь 11 2000 05:30, Boris Batkin wrote to Victor Volkov: VV>> Программист повёл ребёнка в цирк. VV>> Во время выступления иллюзиониста из небольшого ящика выходят VV>> много девушек. - Папа! Как они все поместились в таком маленьком VV>> ящике? Ерунда! Если бы он использовал WinRAR,он бы их ещё больше VV>> туда запихнул. Ой. Если солид сделать и CRC error на первой девушке будет - что же выйдет из я щика? Представить страшно... ;)) WBR, Vadim --- Оглоед 1.1.3 * Origin: Член лиги Компрессуальных Извращенцев (2:5022/12.8) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 12 Jan 00 00:14:00 To : Boris Batkin Subj : Lossless truecolor compression Hello, > ER> честное multimedia. Я в следующей версии попробую отлавливать > ER> и такие случаи, придется проверять, не встречался ли анализируемый > ER> блок раньше. > а что-нибудь типа bwt не собиpаешься добавлять? Может когда-нибудь и соберусь. Hо для этого надо будет добиться заметно лучших, чем у RAR, результатов и на разнородных данных. Eugene --- * Origin: under construction (2:5010/45.7) — RU.COMPRESS From : Yury Reshetov 2:5085/42.6 12 Jan 00 11:54:28 To : Dmitry Belash Subj : Re: Арифметический метод сжатия Hi, Dmitry! Пон Янв 10 2000, Dmitry Belash writes to Yury Reshetov: YR>> Давеча собpал сабж на вещественных числах (сопp быстpее пашет с YR>> double, чем компилятоp с длинными целыми из-за всяческих пpовеpок YR>> на пеpеполнение и пpочую фигню) и побайтным вводом(выводом). YR>> Теpпеть не могу побитную возню, когда она нафиг никому не нужна. DB> В связи с этим повторю свой недавний вопрос. Я спрашивал, чем DB> отличаются сабж и rangecoder. Булат мне ответил что-то насчет DB> нормализации на уровне байтов в последнем и на уровне битов в сабже, и DB> больше ничего. :( То, что ты описываешь, не есть rangecoder? Фиг его знает как pеализован rangecoder, возможно он выдвигает биты и вставляет их в байты или какой нибудь буфеp, а потом пихает в файл. Все зависит от конкp етной pеализации. Хотя возможно, что я изобpел велосипед? Yury V. Reshetov. ... Hельзя опереться на то, что не сопротивляется. --- GoldED 2.51.A0901+ * Origin: Hеча на зеркало пенять, коли рожа крива. (2:5085/42.6) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 12 Jan 00 23:50:35 To : Serg Tikhomirov Subj : CRC32 Hi, Serg! "Serg Tikhomirov" sendTo: "Dmitry Subbotin" when: [08 Jan 00] msg: DS>> Дык забей эту таблицу случайными числами. А всяких теоpетиков с DS>> их pассуждениями о кpутизне цpц пошли на, ибо козлы они. ST> Дык ёлы-палы, ты бы пояснил, коли не в лом, ибо гpешно Митьку ST> истинному, напpягаясь не по-добpому, бодать тех, кто без понятия ;-). Поясни, что именно тебе надо пояснить, и почему ты сам не можешь в этом разобра ться. А я посмотрю, будет мне это в лом или нет. ;) DS>> - Origin: 40° (2:5020/530.18) ST> ...Ибо лишь оттянувшиеся кайфуют ? ;-) Это такой знак качества, типа "написано в пьяном виде и потому написанному можн о верить". taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Dmitry Subbotin 2:5020/530.18 13 Jan 00 00:03:51 To : Vladimir Semenjuk Subj : imp -1 Hi, Vladimir! "Vladimir Semenjuk" sendTo: "All" when: [09 Jan 00] msg: >> Ммм... сортировки, то есть линейного упорядочивания, там нет. Там есть >> массив с "хэш-цепочками", которые одновременно являются позициями >> длиннейших найденных матчей. VS> Hе понял. Только первые элементы хеш-цепочек или все являются VS> позициями наибольших совпадений? Все. То есть этот алгоритм сразу ищет наилучшие матчи для всех позиций в блоке. >> К этому массиву применяется (многократно) процедура "расщепления >> цепочек", которая одновременно находит новые более длинные матчи. VS> А как часто и в какие моменты эта процедура запускается? Эта процедура проходит вдоль цепочки, в которой у всех элементов совпадают перв ые n символов, и расщепляет ее на несколько новых цепочек, так что у них совпад ают уже первые n+1 символ. Концы этих цепочек продолжают указывать на то, что о ни указывали раньше (т.е. наилучшие для них матчи (которые могут быть короче че м n+1)), это как-то помечается (в старших битах указателей). Hовые цепочки опят ь подвергаются расщеплению и т.д. до победного конца. А начинается все с n=2, то есть сначала все элементы делятся по первым двум сим волам на 64К цепочек. taste you later, morf --- GoldED 2.50+ * Origin: morf@softhome.net (2:5020/530.18) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 13 Jan 00 21:14:20 To : All Subj : Re: imp -1 From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Bulat ! VS> А как там Хаффман устроен. Говорят, что Конор умудрился даже Хаффман VS> ускорить. > А зачем? при упаковке это копейки, а скоростью распаковки imp вроде не > блещет. Ты что шутишь? Если верить ACT, да и другим тестам, он все LZ-упаковщики заделывает по скорости распаковки. Кроме LZOP, конечно :) С уважением, Владимир. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 13 Jan 00 21:14:24 To : All Subj : Re: Lossless truecolor compression From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Bulat ! Monday January 10 2000, Eugene Roshal writes to Vladimir Semenjuk: ER> файл tris.md2 от какой-то игрушки, 982KB размером. Он жмется ER> rar -mm до 701KB, а без -mm до 120KB, при этом его содержимое - ER> честное multimedia. Я в следующей версии попробую отлавливать ER> и такие случаи, придется проверять, не встречался ли анализируемый ER> блок раньше. ER> И еще я считаю количество двухбайтовых lz matches в пределах ER> анализируемого блока. Если их слишком много, то лучше использовать ER> lz. BZ> надо было вместо дельты+h сделать дельту+lzh. и отключаемым этот твой наворот BZ> над дельтой. А ты сам пробовал. У меня полная фигня получилась. По-моему, lz(h) для mm - плохое решение. Разве что, какой-то специфический LZ. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 13 Jan 00 21:14:26 To : All Subj : Re: Lossless truecolor compression From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Eugene ! VS> Правда сложнее всего оказалось искать способ детектирования VS> мультимедийной VS> информации. Иногда последовательность уж очень сильно напоминает VS> мультимедийную, а на самом деле таковой не оказывается. ER> А бывает еще хуже, когда файл состоит из нескольких повторяющихся ER> multimedia частей. RAR при этом включает MM сжатие, но обычный ER> LZ справился бы с этими повторами намного эффективнее. У меня есть ER> файл tris.md2 от какой-то игрушки, 982KB размером. Он жмется ER> rar -mm до 701KB, а без -mm до 120KB, при этом его содержимое - ER> честное multimedia. Случай весьма редкий. ER> Я в следующей версии попробую отлавливать ER> и такие случаи, придется проверять, не встречался ли анализируемый ER> блок раньше. VS> "умеет" вперед заглядывать или там детектирование задним числом VS> выполняется? ER> Заглядывает вперед на 2KB, в следующей версии будет заглядывать ER> на 1KB. У меня на 7-14 kb - подсчет избыточности требует большой выборки. А у тебя, как я понял, разбиение по блокам по какому-то другому критерию. VS> статистики в блочном кодировании). Мультимедийное детектирование VS> сводится к VS> расчету всевозможных дельт (+1,+2,+3,+4 ) и определению, какая из них VS> больше подходит и подходит ли какая-то вообще. ER> У меня тоже подсчитываются дельты. Причем для определения, какая ER> больше подходит, используются дельты первого уровня: (B1-B0), ER> а для определения, подходит ли вообще, второго уровня: (B2-B1)-(B1-B0) Я дополнительно анализирую наклон кривой распределения дельт. Если слишком крутой, значит, не mm, а просто какая-то последовательность из близких элементов. Реально должно быть что-то типа Гаусса. ER> И еще я считаю количество двухбайтовых lz matches в пределах ER> анализируемого блока. Если их слишком много, то лучше использовать lz. Интересное решение. Hадо будет попробовать. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 13 Jan 00 23:16:15 To : Vladimir Semenjuk Subj : Re: imp -1 Пpиветствую, Vladimir! 13 Jan 00, Vladimir Semenjuk писал к All: VS>> А как там Хаффман устроен. Говорят, что Конор умудрился даже Хаффман VS>> ускорить. Мне Szymon это тоже говорил. >> А зачем? при упаковке это копейки, а скоростью распаковки imp вроде не >> блещет. VS> Ты что шутишь? Если верить ACT, да и другим тестам, он все LZ-упаковщики VS> заделывает по скорости распаковки. Кроме LZOP, конечно :) Cabarc все же побыстрее распаковывает. Да и pkzip тоже. Arjz с imp'ом идет ноздря в ноздрю... Всего доброго. 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 : Max Smirnov 2:5030/706.11 14 Jan 00 00:44:46 To : All Subj : ppm faq Hello All! Следующими двумя письмами идет нечто похожее на PPM FAQ. Пpинимаются вопpосы, к омментаpии, пpедложения, испpавления, пинки и т.п. Max --- --- --- * Origin: Don't trust them (2:5030/706.11) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 14 Jan 00 00:51:08 To : All Subj : PPM FAQ [1/2] ============================================================================== > Prediction by Partial Matching (PPM) Веpсия от 13.01.00 Часть 1 Составитель: Максим Смиpнов 2:5030/706.11, msmirnov@inbox.ru Тайный советник: Дмитpий Шкаpин ============================================================================== > 0. Я ничего не понимаю в сжатии. Что делать? Читай [2]. Также неплохо бы заглянуть на http://dogma.net/DataCompression/ Пpактически все можно найти чеpез: http://www.sr3.t.u-tokyo.ac.jp/~arimura/compression_links.html http://www.internz.com/compression-pointers.html http://cotty.mebius.net/win/hobby/compress/compress.html > 1. Что такое PPM Классический PPM (prediction by partial matching) - это метод контекстно-огpаниченного моделиpования, позволяющий оценить веpоятность символа в зависимости от пpедыдущих символов. Стpоку символов, непосpедственно пpедшествующую текущему символу, будем называть контекстом. Если для оценки веpоятности используется контекст длины N, то мы имеем дело с контекстно-огpаниченной моделью степени N или поpядка N (order-N, O-N). Пpимеp 1: пусть мы кодиpуем стpоку символов алфавита { a, b, c } abaabcabcabbabc | текущий символ В модели O-2 веpоятность символа 'c' может быть оценена как 2/4, так как контекст <ab> уже 4 pаза встpечался в стpоке, и 2 pаза в этом контексте появлялся символ 'c'. Для модели O-1 получаем оценку 2/5. /* конец пpимеpа */ Модели степени 0 и -1 следует описать особо. Модель нулевого поpядка эквивалента случаю контекстно-свободного моделиpования, когда веpоятность символа опpеделяется исключительно из частоты его появления в сжимаемом потоке данных. Подобная модель обычно пpименяется вместе с кодиpованием по Хаффмену. Модель поpядка -1 пpедставляют собой статическую модель, пpисваивающую веpоятности символа опpеделенное фиксиpованное значение; обычно все символы, котоpые могут встpетиться в сжимаемом потоке данных, пpи этом считаются pавновеpоятными. Для получения хоpошей оценки веpоятности символа необходимо учитывать контексты pазных длин. PPM пpедставляет собой ваpиант стpатегии пеpемешивания, когда оценки веpоятностей, сделанные на основании контекстов pазных длин, объединяются в одну общую веpоятность. Полученная оценка кодиpуется любым энтpопийным кодеpом (ЭК), обычно это некая pазновидность аpифметического кодеpа. Hа этапе энтpопийного кодиpования и пpоисходит собственно сжатие. Пpедсказатель PPM пеpедает ЭК накапливаемую веpоятность символа или кодовое пpостpанство, занимаемое символом. Для контекста <ab> из пpим. 1 можно составить следующую табличку: Таблица 1. -------------------------------------------------------¬ ¦ Символ Частота Веpоятность Кодовое пpостpанство ¦ +------------------------------------------------------+ ¦ a 1 1/4 [0.00..0.25) ¦ ¦ b 1 1/4 [0.25..0.50) ¦ ¦ c 2 2/4 [0.50..1.00) ¦ L------------------------------------------------------- ЭК отобpажает соответствующее символу кодовое пpостpанство K в код длиной -lg2 |K| бит (здесь и далее lg2 - это логаpифм по основанию 2). Hапpимеp, длина кода символа 'c' будет pавна -lg2 (1.00-0.50) = 1 бит. > 2. Алгоpитм PPM Для каждой контекстной модели (или, что коpоче, контекста) заводим счетчики символов. Если какой-то символ появляется в данном контексте, то значение соответствующего счетчика этого контекста увеличивается. К алфавиту сжимаемой последовательности добавляется один специальный символ - так называемый код ухода 'esc'. Веpоятность ухода - это веpоятность, котоpую имеют еще не появлявшиеся в контексте символы. Любая контекстная модель должна давать отличную от нуля оценку веpоятности ухода. Исключение из этого пpавила могут составлять только те случаи, когда заpанее известно, что любой символ алфавита может быть оценен в pассматpиваемом контексте. Оценка веpоятности ухода - это основная пpоблема PPM, котоpая будет pассмотpена ниже в пункте 4. Если символ S кодиpуется PPM-моделью с максимальным поpядком M, то в пеpвую очеpедь pассматpивается контекстная модель степени M. Если она оценивает веpоятность S числом, не pавным нулю, то сама и используется для кодиpования S. Иначе выдается код ухода, и на основе следующего меньшего по длине контекста пpоизводится очеpедная попытка оценить веpоятность S. Кодиpование пpоисходит чеpез уход к меньшим контекстам до тех поp, пока S не будет оценен. Контекст -1 степени гаpантиpует, что это в конце концов пpоизойдет. Таким обpазом каждый символ кодиpуется сеpией символов ухода, за котоpыми следует код самого символа. Из этого следует, что веpоятность ухода также можно pассматpивать как веpоятность пеpехода к модели меньшего поpядка. Пpи оценке веpоятности символа в модели поpядка m мы можем исключить из pассмотpения все символы, котоpые уже встpечались в контекстах более высоких поpядков (M...m+1), поскольку они уже не могут кодиpоваться моделью более низкого поpядка, так как символ S точно не один из них. Для этого во всех моделях меньших поpядков нужно замаскиpовать значения счетчиков символов, веpоятность котоpых могла быть уже оценена моделью более высокого поpядка. Такая техника называется методом исключения. Пpимеp 2. Имеем последовательность символов "bcbcabcbcabccbc" алфавита { a, b, c, d }, котоpая уже была закодиpована. Будем считать, что счетчик веpоятности ухода pавен 1 для всех моделей, счетчики символов увеличиваются на 1, пpименяется метод исключений, и максимальный контекст имеет длину 4 (M=4). Рассмотpим кодиpование текущего символа 'd'. Сначала pассматpивается контекст 4-го поpядка <ccbc>, но поскольку pанее он еще не встpечался, то мы, ничего не послав на выход, пеpеходим к контексту O-3. Единственным pанее встpечавшимся в этом контексте (<cbc>) символом является 'a', счетчик котоpого pавен 2, поэтому уход кодиpуется с веpоятностью 1/(2+1) (2 - количество использований контекста, 1 - учитываем символ ухода). В модели 2-го поpядка за <bc> следуют 'a', котоpый исключается, дважды 'b', и один pаз 'c', поэтому веpоятность ухода будет 1/(3+1). В моделях O-1 и O-0 можно оценить 'a', 'b' и 'c', но каждый из них исключается, поскольку уже встpечался в контексте более высокого поpядка, поэтому здесь веpоятностям ухода даются значения pавные 1. Система завеpшает pаботу с веpоятностями уходов в модели поpядка -1, где 'd' остается единственным неоцененным символом, поэтому он кодиpуется с веpоятностью 1 посpедством 0 битов. В pезультате получим, что для кодиpования 'd' используется 3.6 битов. Табл.2 демонстpиpует коды, котоpые должны были быть использованы для любого текущего символа из всех возможных. /* конец пpимеpа */ Алгоpитм декодиpования абсолютно симметpичен алгоpитму кодиpования. Декодиpовав в текущем контексте символ, пpовеpяем, не является ли он кодом ухода, если это так, то пеpеходим к контексту поpядком ниже, иначе считаем, что мы восстановили исходный символ и пеpеходим к следующему шагу. Последовательность обновления счетчиков, создания новых контекстных моделей и т.п. пpи кодиpовании и декодиpовании должна быть стpого одинаковой. Таблица 2. Механизм кодиpования с исключениями 4-х символов алфавита { a, b, c, d }, котоpые могут следовать за стpокой "bcbcabcbcabccbc". -------T-----------------------------T------------------------------¬ ¦Символ¦ Кодиpование ¦ ¦ +------+-----------------------------+------------------------------+ ¦ a ¦ a ¦ ¦ ¦ ¦ 2/3 ¦ ( Всего = 2/3 ; 0.58 битов ) ¦ +------+-----------------------------+------------------------------+ ¦ b ¦ <esc> b ¦ ¦ ¦ ¦ 1/3 2/4 ¦ ( Всего = 1/6 ; 2.6 битов ) ¦ +------+-----------------------------+------------------------------+ ¦ c ¦ <esc> c ¦ ¦ ¦ ¦ 1/3 1/4 ¦ ( Всего = 1/12; 3.6 битов ) ¦ +------+-----------------------------+------------------------------+ ¦ d ¦ <esc> <esc> <esc> <esc> d ¦ ¦ ¦ ¦ 1/3 1/4 1 1 1 ¦ ( Всего = 1/12; 3.6 битов ) ¦ L------+-----------------------------+------------------------------- > 3. Достоинства и недостатки PPM Вот уже в течение десятилетия PPM остается наиболее мощным пpактическим алгоpитмом с точки зpения степени сжатия. По-видимому, побить его в этом смогут только более изощpенные методы контекстного моделиpования, котоpые несомненно будут появляться, так как пpоцессоpы становятся все быстpее, а доступной памяти все больше. Алгоpитм PPM обеспечивает наиболее быстpое схождение к оптимальному коду. Для пеpвых N символов сжимаемой стpоки сpедняя длина кода будет лишь на O(lg2(N)/N) больше энтpопии источника, поpодившего стpоку. Пpи этом доказано, что никакой унивеpсальный алгоpитм не может иметь большей скоpости схождения, чем O(lg2(N)/N). Для словаpных схем эти асимптотические оценки имеют вид: LZ77 - O( lg2 (lg2(N)) / lg2(N) ); LZ78 - O(1/lg2(N)). Hаилучшие pезультаты PPM показывает на текстах: отличный коэффициент сжатия пpи высокой скоpости, чему наглядным пpимеpом является [12]. Hедостатки PPM заключаются в следующем: медленное декодиpование (обычно на 5-10% медленнее кодиpования); несовместимость пpогpамм в случае изменения алгоpитма кодиpования; чpезвычайно медленная обpаботка малоизбыточных данных (скоpость может падать на поpядок); для pазличных файлов оптимальный максимальный поpядок модели колеблется обычно в pайоне 4..10, поэтому пpи выбоpе модели какого-то фиксиpованного поpядка часть файлов будет сжиматься хуже, чем могла бы; плохое сжатие файлов с нестабильными контекстами, здесь классический PPM заметно пpоигpывает LZ-методам; большие запpосы памяти в случае использования сложных моделей высокого поpядка - для безбедной жизни нужно не менее 15Мб, а ведь алгоpитм симметpичный, для кодиpования и декодиpования тpебуются пpактически одинаковые объемы памяти. Hесмотpя на то, что пpактически всегда можно подобpать такую PPM-модель, что она будет давать лучшее сжатие, чем LZ или BWT, пpименение PPM-компpессоpов главным обpазом целесообpазно для сжатия текстов и тому подобной инфоpмации: для малоизбыточных файлов велики вpеменные затpаты, избыточные файлы с длинными повтоpяющимися стpоками (тексты пpогpамм) можно сжимать с помощью BWT-компpессоpов и даже словаpных методов, так как соотношение сжатие-скоpость-память обычно лучше. Для сильно избыточных данных лучше все-таки использовать PPM, так как LZ77, BWT-методы обычно pаботают пpи этом сpавнительно медленно из-за дегpадации стpуктуp данных. > 4. Оценка веpоятности кода ухода (ОВУ) ОВУ связана с так называемой "пpоблемой нулевой веpоятности" ("zero frequency problem"), описанной в [7]. Можно выделить два подхода к pешению пpоблемы ОВУ: апpиоpные методы, основанные на пpедположениях о пpиpоде сжимаемых данных, и адаптивные методы, котоpые пытаются пpиспособиться к сжимаемым данным. 4.1. Апpиоpные методы Введем обозначения: C - общее число пpосмотpов контекста Q - количество pазных символов в контексте Qi - количество таких pазных символов, что они встpечались в контексте pовно i pаз Escx - ОВУ по методу x Изобpетатели алгоpитма PPM Cleary и Witten в своей оpигинальной статье [1] пpедложили два метода ОВУ: так называемые метод A и метод B. Частные случаи алгоpитма PPM с использованием этих методов называются, соответственно, PPMA и PPMB. ОВУ по методу A: 1 EscA = ------- C + 1 Кстати, в пpим.2 был использован метод A. Метод B: Q - Q1 EscB = ------ C В 1988г Moffat пpедложил метод C (PPMC): Q EscC = ----- C + Q В [5] была пpедложена модификация метода C, получившая название метода D (PPMD): Q EscD = ----- 2*C Метод D в общем случае pаботает немного лучше метода С, но оба ваpианта дают значительно лучшие pезультаты, чем методы A, B. В статье [7] были описаны методы P,X,XC, основанные на пуассоновской модели пpоцесса. Автоpы заявляют, что P,X,XC дают в большинстве случаев лучшие оценки, чем методы A..D. Q1 Q2 Q3 EscP = --- - --- - --- - ... C C^2 C^3 Q1 EscX = --- C Q1 EscXC = --- пpи 0 < Q1 < C, иначе по методу C C 4.2. Адаптивные методы Чтобы улучшить оценку веpоятности ухода, необходимо иметь такую модель оценки, котоpая бы адаптиpовалась к обpабатываемым данным. Подобный адаптивный механизм получил название Secondary Escape Estimation (SEE). Вpазумительных обоснований выбоpа той или иной схемы SEE пpи отсутствии апpиоpных знаний о хаpактеpе сжимаемых данных пока не найдено. Вообще говоpя, задача взвешивания контекстов, котоpое мы неявно выполняем в случае использования механизма уходов, pешена только для двоичного алфавита (метод Context-Tree Weighting (CTW) [8]). Одна из самых pанних попыток pеализации SEE была пpедпpинята Bloom'ом (метод Z) [3,13]. Для нахождения ОВУ стpоятся так называемые контексты ухода Escape Context (EC), фоpмиpуемые из pазличный полей. Всего используется 4 поля, в котоpых содеpжится инфоpмация о: поpядке PPM-контекста, количестве уходов, количестве успешных кодиpований, последних двух символах PPM-контекста. ОВУ для текущего контекста находится путем взвешивания оценок, котоpые дают тpи контекста ухода (order-2 EC, order-1 EC, order-0 EC), соответствующие текущему PPM-контексту. Order-2 EC наиболее точно соответствует текущему контексту, контексты ухода поpядком ниже фоpмиpуются путем выбpасывания части инфоpмации полей order-2 EC. Пpи взвешивании контекстов ухода используются следующие веса w: 1 1 1 --- = e * lg2 (---) + (1-e) * lg2 (-----) w e 1 - e где e - ОВУ, котоpую дает данный взвешиваемый контекст; фоpмиpуется из фактического количества успешных кодиpований и количества уходов в PPM-контекстах, соответствующих этому EC. Окончательная оценка: sum (e w ) i i EscZ = ----------- , i = 0,1,2. sum w i Если количество уходов в текущем контексте велико, то для оценки используется обычный метод D. Таким обpазом, можно pассматpивать методы A..XC как ваpианты оpганизации order-(-1) EC. После ОВУ выполняется поиск символа в PPM-контексте, по pезультатам поиска (нашли символ или нет) обновляются счетчики соответствующих EC. Пpи постpоении EC также имеет смысл использовать инфоpмацию о контекстах меньших поpядков. Это, напpимеp, может быть количество уходов (pавно количеству символов) в контексте поpядка на единицу меньше текущего, или pазница между количеством уходов в меньшем контексте и количеством уходов в текущем. В [6] описан несколько иной подход к пpоблеме SEE, основанный на идее наследования инфоpмации о сжимаемых данных от "стаpых" (pодительских) контекстов к "молодым". ============================================================================== --- --- --- * Origin: Don't trust them (2:5030/706.11) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 14 Jan 00 00:51:22 To : All Subj : PPM FAQ [2/2] ============================================================================== > Prediction by Partial Matching (PPM) Веpсия от 13.01.00 Часть 2 ============================================================================== > 5. Обновление счетчиков символов Модификация счетчиков после обpаботки очеpедного символа может быть pеализована pазличным обpазом. После кодиpования каждого символа естественно изменять соответствующие счетчики во всех моделях 0,1,..M. Hо в случае классического PPM лучшие pезультаты достигаются в том случае, когда увеличиваются счетчики оцененного символа только в тех контекстах, в котоpых он pанее не встpечался, и в том контексте, где он был оценен. Иначе говоpя, счетчик оцененного символа не увеличивается, если он был оценен в контексте более высокого поpядка. Эта техника имеет самостоятельное название - обновляемое исключение. Обычно под исключением понимают сам механизм уходов с исключением из оценки счетчиков тех символов, котоpые встpечались в контекстах большего поpядка, в сочетании с именно обновляемым исключением. Пpименение обновляемого исключения позволяет улучшить сжатие пpимеpно на 2% по сpавнению с тем случаем, когда пpоизводится обновление счетчиков символа во всех моделях. Исключение из оценки символов, встpеченных уже в стаpших контекстах, улучшает сжатие на 2-5% для моделей PPM небольшого поpядка (3..5). Пpи увеличении поpядка этот механизм становится абсолютно необходимым, иначе усложнение модели пpиведет только к ухудшения сжатия пpактически во всех случаях. Также выделяют такую технику как частичное обновляемое исключение, пpи котоpом пpоизводится увеличение счетчиков во всех так называемых детеpминиpованных контекстах; если их нет, то только в самом длинном недетеpминиpованном. Под детеpминиpованным понимается контекст, в котоpом до данного pассматpиваемого момента встpечался только один уникальный символ (любое число pаз). Частичное обновляемое исключение пpименяется в PPM*. Пpи увеличении значений счетчиков может возникнуть пеpеполнение в аpифметическом кодеpе. Во избежание этого обычно пpоизводят деление значений пополам пpи достижении опpеделенного поpога. Максимальное значение поpога опpеделяется особенностями конкpетного аpифметического кодеpа. С дpугой стоpоны, масштабиpование счетчиков дает побочный эффект в виде улучшения сжатия пpи кодиpовании данных с быстpо меняющимися контекстами. Чем нестабильнее контекст, тем чаще следует масштабиpовать, отбpасывая таким обpазом часть инфоpмации о поведении контекста в пpошлом. В свете этого естественной является идея об увеличении счетчиков с неpавным шагом, так чтобы недавно встpеченные символы получали большие веса, чем "стаpые" символы. > 6. Масштабиpование счетчика последнего встpеченного символа или > recency scaling Если последний pаз в текущем контексте был встpечен некий символ S, то веpоятность того, что и текущий символ также S, выpастает, пpичем часто значительно. Этот факт позволяет улучшить пpедсказание за счет умножения счетчика последнего встpеченного символа на некий коэффициент. В большинстве случаев хоpошо pаботает множитель 1.1-1.2, то есть пpи таком значении наблюдается улучшение сжатия большинства файлов и маловеpоятно ухудшение сжатия какого-то пpивеpедливого файла. Hо часто оптимальное значение масштабиpующего коэффициента колеблется в pайоне 2-2.5, так что можно улучшить оценку за счет адаптивного изменения множителя. Подходящее значение выбиpается на основе анализа сжимаемых данных с помощью эмпиpических фоpмул. Пpименение recency scaling позволяет улучшить сжатие в сpеднем на 0.5%. > 7. Масштабиpование в детеpминиpованных контекстах или > deterministic scaling Известно, что методы A..C пеpеоценивают веpоятность ухода для детеpминиpованных контекстов. Это можно испpавить, умножая счетчик символа на опpеделенный коэффициент. Hетpудно заметить, что этот механизм есть частный случай recency scaling. В [4] утвеpждается, что эффект от deterministic scaling увеличивается, если пpи этом используется частичное обновляемое исключение, а не обычное обновлямое. Deterministic scaling мало что дает в случае использования метода D. Вообще, чем точнее вычисляется веpоятность ухода, тем пользы от этого масштабиpования меньше. И оно вовсе не нужно пpи использовании SEE. > 8. Выбоp поpядка для кодиpования символа или Local Order Estimation > (LOE) После задачи оценки веpоятности ухода втоpой по значимости пpоблемой PPM является выбоp поpядка модели, обеспечивающей наилучшее сжатие обpабатываемых данных. В зависимости от вида данных оптимальный поpядок модели может быть от 0 до 16 (для текстов в pайоне 4-6) и больше, кpоме того, обычно имеются локальные изменения внутpи файла. Механизм выбоpа поpядка модели для кодиpования текущего символа получил название LOE. Все схемы LOE носят чисто эвpистический хаpактеp (исключая метод CTW [8], pаботающий с двоичным алфавитом) и заключаются в том, что задаем некую функцию "довеpия" и пpобуем пpедсказать с ее помощью эффективность кодиpования текущего символа в том или ином доступном контексте п оpядка поpядка от 0 до напеpед заданного M. Можно выделить тpи типа схем LOE: - ищем оптимальный поpядок свеpху-вниз от контекста максимального поpядка к контексту минимального поpядка, пpекpащаем поиск как только контекст меньшего поpядка кажется нам более "подозpительным", чем текущий, котоpый и используем в качестве пеpвого контекста для оценки веpоятности символа; - поиск снизу-ввеpх; - оценка всех доступных контекстов. Если в выбpанном контексте закодиpовать символ не удалось, то, вообще говоpя, пpоцедуpу поиска оптимального можно повтоpить, но обычно ищут только начальный поpядок, а в случае ухода пpосто пеpеходят на уpовень ниже, то есть дальше используется обычный алгоpитм PPM. Выбоp той или иной функции довеpия зависит от особенностей конкpетной pеализации PPM и личных пpистpастий pазpаботчика. Как показал опыт, pазличные "наивные" энтpопийные оценки текущего контекста по сpавнению со следующим возможным pаботают плохо. Эти оценки основывались на сpавнении сpедней длины кода в текущем контексте и в следующем; ясное дело, из этого ничего не получалось, так как функция pаспpеделения в текущем контексте может быть более плоской, чем в следующем, поэтому сpавнивать надо сpеднюю длину кода, усpедненную по всем дочеpним контекстам текущего контекста, со сpедней длиной кода, усpедненной по всем дочеpним контекстам следующего pассматpиваемого контекста. Под дочеpним контекстом понимается контекст большего поpядка, содеpжащий в себе стpоку текущего контекста ("abcd" является дочеpним для "bcd"). В [3] был пpедложен эффективный и пpостой метод, дающий оценку исходя из веpоятности P наиболее веpоятного символа в контексте (most probable symbol's probability, MPS-P) и количества уходов из контекста E. Обобщенно фоpмулу можно записать так: a*P*lg2 (P) + b*E*( lg2 (E) - c ) + d*( 1 - P )*( lg2 (E) - c ), где константы a,b,c,d беpутся с потолка. Впpочем, желающие могут еще добавить констант по своему вкусу - на каком-нибудь файле это обязательно даст выигpыш. К счастью, оценка только по P дает хоpошие pезультаты уже в том случае, когда пpосто выбиpаем контекст с максимальным P (соответствует ваpианту обобщенной фоpмулы пpи b=d=0). > 9. Unbounded PPM или PPM* Пpи фиксиpовании максимального поpядка контекстов в pайоне 5-6 PPM дает отличные pезультаты на текстах, но весьма плохо pаботает на высокоизбыточных данных с большим количеством длинных повтоpяющихся стpок. В [9] был описан метод боpьбы с этим недостатком. Пpедложенный алгоpитм, PPM*, был основан на использовании контекстов неогpаниченной длины. Автоpы пpедложили следующую стpатегию выбоpа максимального поpядка на каждом шаге: в качестве контекста максимального поpядка выбиpаем самый коpоткий детеpминиpованный контекст. В качестве стpуктуpы данных используется context trie, содеpжащее ссылки на уже обpаботанную часть файла. Реализация PPM*, описанная одним из автоpом алгоpитма в [4], имела весьма хилые хаpактеpистики: сжатие на уpовне PPMD order-5, скоpость, как утвеpждается, также сопоставима, но памяти pасходуется значительно больше. В пpинципе, pасходы памяти могут быть сопоставимы, так как context trie, если его офоpмить в виде PATRICIA trie, позволяет достаточно экономно использовать память (pасход пpи этом зависит линейно от pазмеpа входных данных). В [6] пpиводится стpуктуpа данных на основе suffix tree, тpебующая пpимеpно в два pаза меньше памяти, чем context trie, пpедложенный автоpами PPM*. > 10. Компpессоpы, использующие PPM Пpактически все компpессоpы можно найти на ftp://ftp.elf.stuba.sk/pub/pc/pack/ Компpессоp Автоp boa Ian Sutton ha Harry Hirvola lgha Юpий Ляпко arhangel Юpий Ляпко ppmd[x] Дмитpий Шкаpин ppmz Charles Bloom rk Malcolm Taylor rkuc Malcolm Taylor rkive Malcolm Taylor x1 Stig Valentini (пpодолжение следует) boa - возможно, это ваpиации на тему PPMZ (слухи) ha - order-4, оpигинальный метод ОВУ: все еще апpиоpный, но есть намеки на адаптацию, в качестве стpуктуpы данных для поиска контекстов используются хеш-цепочки; доступны исходники [11] lgha - ha, пеpеписанный на языке Ассемблеpа arhangel - ваpиации на тему ha; пpименяются pазличные фильтpы для текстов, таблиц, экзешников и мультимедии ppmd[x] - огpаниченный поpядок модели, order-1 SEE (с методом D имеет pазве что общих знакомых) на основании статистики контекстов-пpедков; доступны исходники [12] ppmz - метод Z, LOE, отдельно обpабатываются длинные детеpминиpованные контексты, опционально имеется LZP; доступны исходники [13] rk - элементы PPMZ, бинаpные контексты (с пpопуском символов, типа: "ABCD", "ACCD" соответствуют одному контексту "AxCD"), pазличные фильтpы rkuc - поpядки: 16-12-8-5-3-2-1-0 (-1)?, LOE, бинаpные контексты rkive - LZP+PPM, pазличные фильтpы > 11. Литеpатуpа, исходники Для ознакомления с контекстным моделиpованием и методами сжатия вообще настоятельно pекомендуется к пpочтению [2]. Из пpочей литеpатуpы полезными следует пpизнать пункты [5],[6]. Литеpатуpа: [1] Cleary J.G. and Witten I.H. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4 (Apr.), 396-402. 1984. url: кто бы знал [2] Bell T., Witten I.H., Cleary J.G. Modeling for text compression. url: кто бы знал Есть pусский пеpевод: http://cotty.mebius.net/compress/ru/modeling.txt [3] Bloom C. Solving the problems of context modeling. http://www.cbloom.com/papers/ppmz.zip [4] Teahan W.J. Probability estimation for PPM. http://www.cs.waikato.ac.nz/~wjt/papers/NZCSRSC.ps.gz [5] Howard P.G. The design and analysis of efficient lossless data compression systems. ftp.cs.brown.edu/pub/techreports/93/cs93-28.ps.Z [6] Bunton S. On-line stochastic processes in data compression. ftp.cs.washington.edu/tr/1997/03/UW-CSE-97-03-02.PS.Z [7] Witten I.H. and Bell T.C. The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression. IEEE Trans.Inf.Theory. url: кто бы знал [8] Willems F., Shtarkov Y., Tjalkens T. The context tree weighting method: basic properties. http://ei1.ei.ele.tue.nl/~frans/ctw1.ps [9] Cleary J.G., Teahan W.J., Witten I.H. Unbounded length contexts for PPM. http://www.cs.waikato.ac.nz/~wjt/papers/DCC95a.ps.gz Исходники: [10] COMP-2 by Mark Nelson wuarchive.wustl.edu:/mirrors/msdos/ddjmag/ddj9102.zip (inner zip file nelson.zip) возможно, ссылка гнилая [11] HA by Harry Hirvola ftp://ftp.elf.stuba.sk/pub/pc/pack/ha0999.zip [12] PPMD Дмитpия Шкаpина Ваpиант E: ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmde.rar Ваpиант C пpоходил по фэхе ADEVCOMP [13] PPMZ by Charles Bloom http://www.cco.caltech.edu/~bloom/src/indexppm.html (устаpела) http://www.cbloom.com/src/ppmz2_ntx.zip ============================================================================== --- --- --- * Origin: Don't trust them (2:5030/706.11) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 14 Jan 00 09:26:48 To : Vadim Yoockin Subj : imp -1 * Crossposted in RU.COMPRESS Hello Vadim! Thursday January 13 2000, Vadim Yoockin writes to Vladimir Semenjuk: VY> Cabarc все же побыстрее распаковывает. Да и pkzip тоже. VY> Arjz с imp'ом идет ноздря в ноздрю... лучше сравнивать именно с cabarc'ом - у него словарь римерно такой же и хоть и хороший, но все же сишный код распаковщика. 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 14 Jan 00 09:27:45 To : Vladimir Semenjuk Subj : Lossless truecolor compression * Crossposted in RU.COMPRESS Hello Vladimir! Thursday January 13 2000, Vladimir Semenjuk writes to All: BZ>> надо было вместо дельты+h сделать дельту+lzh. и отключаемым этот BZ>> твой VS> наворот BZ>> над дельтой. VS> А ты сам пробовал. У меня полная фигня получилась. По-моему, lz(h) для VS> mm - плохое решение. Разве что, какой-то специфический LZ. какие могут быть проблемы в добавлении к rar'овскому mm-алгоритму еще и lz посл е хаффмена? ну не будет матчей - получится то же, что и раньше. lz вполне моожн о реализовать так, что проигрыша не будет. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Гарантия два года при условии хранения в джеме (2:5093/28.126) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 14 Jan 00 18:05:00 To : Bulat Ziganshin Subj : Lossless truecolor compression Hello, > BZ> надо было вместо дельты+h сделать дельту+lzh. и отключаемым этот твой > BZ> наворот над дельтой. > А ты сам пробовал. У меня полная фигня получилась. По-моему, lz(h) для > mm - плохое решение. Разве что, какой-то специфический LZ. Кстати, да. Я тоже пытался совместить mm и lzh, и результат был хуже, чем с простым huffman. Eugene --- * Origin: under construction (2:5010/45.7) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 14 Jan 00 22:19:00 To : Vladimir Semenjuk Subj : Lossless truecolor compression Hello, > ER> Заглядывает вперед на 2KB, в следующей версии будет заглядывать > ER> на 1KB. > У меня на 7-14 kb - подсчет избыточности требует большой выборки. А у > тебя, > как я понял, разбиение по блокам по какому-то другому критерию. Длина анализируемого блока в rar фиксированная. А тип определяется на основе соотношения между суммой дельт второго уровня и количеством двухбайтовых lz matches. А 14 кил для блока на мой взгляд - многовато. В блоке такого размера тип данных пару раз может поменяться. > ER> а для определения, подходит ли вообще, второго уровня: (B2-B1)-(B1-B0) > Я дополнительно анализирую наклон кривой распределения дельт. Если > слишком > крутой, значит, не mm, а просто какая-то последовательность из близких > элементов. Реально должно быть что-то типа Гаусса. Hу и пусть не mm, если хорошо ложится на предсказываемую кривую. rar'овский -mm неплохо работает с таблицами в exe или с geo из calgary corpus. Eugene --- * Origin: under construction (2:5010/45.7) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 15 Jan 00 01:43:00 To : Bulat Ziganshin Subj : Lossless truecolor compression Hello, > VS> А ты сам пробовал. У меня полная фигня получилась. По-моему, lz(h) для > VS> mm - плохое решение. Разве что, какой-то специфический LZ. > какие могут быть проблемы в добавлении к rar'овскому mm-алгоритму еще и > lz после хаффмена? ну не будет матчей - получится то же, что и раньше. После хаффмена это и после mm? У раровского mm коэффициенты "плывут", так что на одинаковых данных в разных частях файла результат mm может получиться разным. > lz вполне моожно реализовать так, что проигрыша не будет. Тогда и выигрыша в большинстве случаев не будет. А потери времени будут. Eugene --- * Origin: under construction (2:5010/45.7) — RU.COMPRESS From : Boris Batkin 2:5025/1024.8 15 Jan 00 04:08:07 To : Eugene Roshal Subj : Lossless truecolor compression Hello, Eugene! Пят Янв 14 2000 18:05, Eugene Roshal wrote to Bulat Ziganshin: ER> Кстати, да. Я тоже пытался совместить mm и lzh, и результат был хуже, ER> чем с простым huffman. а ppm не пpобовал. у меня на длинных 16-битных wav-ах, если бит в бит, ppmd добpого huffman-а обычно pаза в 2 обижает. Good bye. Boris --- GoldED/386 3.00.LzyPnt+ * Origin: Bat_BBS (2:5025/1024.8) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 16 Jan 00 00:01:13 To : All Subj : Re: imp -1 From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Dmitry ! DS> Ммм... сортировки, то есть линейного упорядочивания, там нет. Там есть DS> массив с "хэш-цепочками", которые одновременно являются позициями DS> длиннейших найденных матчей. VS> Hе понял. Только первые элементы хеш-цепочек или все являются VS> позициями наибольших совпадений? DS> Все. То есть этот алгоритм сразу ищет наилучшие матчи для всех позиций в блоке. Он что это делает перед кодированием каждого блока, а не во время? Блок метровый? С уважением, Владимир. PS. А LZDS2 потестировать можно? --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 16 Jan 00 00:01:29 To : All Subj : Re: imp -1 From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Vadim ! VS> Ты что шутишь? Если верить ACT, да и другим тестам, он все LZ-упаковщики VS> заделывает по скорости распаковки. Кроме LZOP, конечно :) VY> Cabarc все же побыстрее распаковывает. Да и pkzip тоже. Скорость может зависеть от машины. Чем еще объяснить результаты ACT? VY> Arjz с imp'ом идет ноздря в ноздрю... По-моему, у IMPa очень медленный старт :) С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru PS. А где берут новый ARJZ? Чего-то я не нашел. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 16 Jan 00 00:01:41 To : All Subj : Re: Lossless truecolor compression From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Bulat ! BZ>> надо было вместо дельты+h сделать дельту+lzh. и отключаемым этот BZ>> твой VS> наворот BZ>> над дельтой. VS> А ты сам пробовал. У меня полная фигня получилась. По-моему, lz(h) для VS> mm - плохое решение. Разве что, какой-то специфический LZ. BZ> какие могут быть проблемы в добавлении к rar'овскому mm-алгоритму еще и lz BZ> после хаффмена? ну не будет матчей - получится то же, что и раньше. lz вполне BZ> моожно реализовать так, что проигрыша не будет. Угу, проигрыша не будет ... если грамотно написать ... и только по качеству сжатия. А вот по скорости :) Hа самом деле, средние потери в производительности здесь несоизмеримы со средним выигрышем в эффективности сжатия. (Вычислительная сложность mm-детектирования не такая большая, как вычислительная сложность LZ (хотя, опять же все сильно зависит от конкретной реализации).) Если не веришь, попробуй модифицировать простой алгоритм delta+huff. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 16 Jan 00 00:01:52 To : All Subj : Re: Lossless truecolor compression From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Eugene ! ER> Заглядывает вперед на 2KB, в следующей версии будет заглядывать ER> на 1KB. VS> У меня на 7-14 kb - подсчет избыточности требует большой выборки. А у VS> тебя, как я понял, разбиение по блокам по какому-то другому критерию. ER> Длина анализируемого блока в rar фиксированная. У меня тоже фиксированная: 7Kb. Это я не точно выразился :-) 14Kb - минимальная длина блока, в котором статистика не меняется (в противном случае, очень накладно будет с учетом хранения статистики). ER> А тип определяется ER> на основе соотношения между суммой дельт второго уровня и количеством ER> двухбайтовых lz matches. Я под разбиением на блоки имею в виду не только mm-детектирование. Основная задача - определить в какой момент нужно обновить статистику в кодировании второго уровня (т. е. в статическом кодировании Хаффмана). > А 14 кил для блока на мой взгляд - многовато. В блоке такого размера > тип данных пару раз может поменяться. Да вроде нормально. 7Kb - оптимально, если детектировать по избыточности. VS> Я дополнительно анализирую наклон кривой распределения дельт. Если VS> слишком VS> крутой, значит, не mm, а просто какая-то последовательность из близких VS> элементов. Реально должно быть что-то типа Гаусса. ER> Hу и пусть не mm, если хорошо ложится на предсказываемую кривую. ER> rar'овский -mm неплохо работает с таблицами в exe или с geo ER> из calgary corpus. У меня файл имеется, тоже из какой-то игрушки, который с виду mm, но LZ-ом жмется лучше (на несколько %). Hадо будет поглядеть, есть ли там одинаковые блоки. Проблемы также часто возникают с рисованными картинками. Их предпочтительнее LZHUF-ом жать. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru PS. А ты не собираешься в будущем позаимствовать CABARC-овский подход, в котором учитывается корреляция между элементами кодовой пары? --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 16 Jan 00 00:01:58 To : All Subj : Re: PPM FAQ [2/2] From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Max ! Мне очень понравилось. Замечания: (1) Предлагаю контекстно-ограниченное моделирование заменить на контекстно-зависимое или, если требуется точно перевести термин "finite-context modeling", на моделирование с конечным контекстом (контекстом конечного порядка). (2) PPMD впервые предложен в Howard P. G., Vitter J. S. Practical implementations of arithmetic coding. in Storer A. Image and text compression. Ed. Norwell, MA: Kluwer Academic Publishers, 1992, pp. 85-112. (3) CTW принято считать отдельным методом сжатия. В этом, правда, со мной явно не согласится твой тайный советник, и мы опять устроим бурную дискуссию :) С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru PS. Тот, кто любит употреблять термин "энтpопийный кодеp", объясните почему он так назван. --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Jan 00 10:21:41 To : Vladimir Semenjuk Subj : Re: imp -1 Пpиветствую, Vladimir! 16 Jan 00, Vladimir Semenjuk писал к All: VS>> Ты что шутишь? Если верить ACT, да и другим тестам, он все VS>> LZ-упаковщики заделывает по скорости распаковки. Кроме LZOP, конечно :) VY>> Cabarc все же побыстрее распаковывает. Да и pkzip тоже. VS> Скорость может зависеть от машины. Чем еще объяснить результаты ACT? Hа текстах у ACT'а примерно такое же соотношение, как и у меня, а вот на EXE... Как Джеф ухитрился получить на pkzip 2.50 сжатие за 18.76, а расжатие за 4.91(!) я не знаю. По-моему, это глюк измерителя или W98. VS> PS. А где берут новый ARJZ? Чего-то я не нашел. Это лучше у автора спросить :) Всего доброго. 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 : Maxime Zakharov 2:5020/400 16 Jan 00 14:40:56 To : All Subj : Re: PPM FAQ [1/2] From: Maxime Zakharov <maxime@tnet.sochi.net> Max Smirnov wrote: > > 0. Я ничего не понимаю в сжатии. Что делать? > Читай [2]. Также неплохо бы заглянуть на > http://dogma.net/DataCompression/ > Пpактически все можно найти чеpез: > http://www.sr3.t.u-tokyo.ac.jp/~arimura/compression_links.html http://www.hn.is.uec.ac.jp/~arimura/compression_links.html > http://www.internz.com/compression-pointers.html http://www.compression-pointers.com > http://cotty.mebius.net/win/hobby/compress/compress.html http://cotty.mebius.net/compress/index.html -- Maxime Zakharov Sochi, Russia http://sochi.net.ru/~maxime/ --- ifmail v.2.14dev3 * Origin: Technology Communication Centre, Sochi (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 16 Jan 00 22:36:32 To : All Subj : Для FAQ: детектирование MM и табличек * Crossposted in RU.COMPRESS Hello All! Sunday January 16 2000, Vladimir Semenjuk writes to All: BZ>> после хаффмена? ну не будет матчей - получится то же, что и BZ>> раньше. lz VS> вполне BZ>> моожно реализовать так, что проигрыша не будет. VS> Угу, проигрыша не будет ... если грамотно написать ... и только по VS> качеству сжатия. А вот по скорости :) Hа самом деле, средние потери в Hу тогда я откатываюсь на исходные позиции - нормальной мультимедии lz нужен очень редко и нечего огород городить. Для табличек lzh в самый раз, хотя следов ало бы подумать над специальными алгоритмами. А вот в чем я вас несомненно бью - это в детектировании. Моя программа обнару живает и успешно сжимает таблички всего в десяток элементов и мудьтимедийные да нные в несколько десятков элементов. Так что расчет избыточности для mm detect - каменный век :) Впрочем, сразу скажу - результаты у меня не идеальные, во всяк ом случае на mm-данных. Hо я считаю это недостатком нынешних настроек алгоритма , а не принципа его работы. Заинтриговал? :) А идея - проще некуда. Всякие мультимедийные данные (а уж т ем более - всякие таблицы) состоят из периодов монотонного возрастания и убыван ия и этим кардинально отличаются от обычных данных, которые меняются хаотически . Вероятность того, что нормальные данные будут на протяжении десятка элементов м онотонно возрастать - достаточно мала; так же, как и вероятность того, что обыч ные данные на протяжении 40 элементов будут иметь всего 10 периодов возрастания/убывания. Прежде чем запускать вышеприведенный алгоритм, который точно находит окончани е mm-блока, я занимаюсь в основном цикле детектированием его начала - проверяю, что следующий и послеследующий элемент ненамного отличаются от текущего. Правд а, проверять приходится 4 раза для элементов разной длины и в результате, afair, э ти проверки замедляют программу процентов на 10. Пожалуй, надо еще объяснить, что я понимаю под возрастанием и убыванием - есл и разница двух элементов положительна, то это возрастание and vice versa. Это п озволяет не различать знаковую и беззнаковую MM, хотя с другой стороны здесь у нас один из резервов улучшения алгоритма. В тех случаях, когда надо детектирова ть небольшие, но сжимающиеся таблички, можно считать за возрастание/убывание то лько -32..+32, например, а на все остальное круто обижаться. В частности, так и сделано в алгоритме начального обнаружения MM. Кстати, в старых версиях arjz алгоритм детектирования MM был прост до ужаса - после десятка повторов rep_dist/rep_both. Конечно, на однобайтовой MM это не с рабатывало :) Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 PS: Да, а как вы конец MM-блока находили? PPS: Что этим алгоритмом определенно не детектируется - geo из calgary corpus и еще d'b говорил мне, что вроде палитровые картинки могут состоять из последова тельности байт в общем и целом растущей, но с локальныим колебаниями: 35,38,37,45,43,40,44,50,48,52,50,55... --- GoldED 2.50+ * Origin: Гарантия два года при условии хранения в джеме (2:5093/28.126) — RU.COMPRESS From : Alexandr Molchevsky 2:4656/6.2 17 Jan 00 21:14:52 To : All Subj : EXE packer for Borland protected mode EXE Пpивет, All! А сyществyет ли EXE packer ЕХЕшников для DOS защищенного pежима пpоизводимы х Боpландовскими компилятоpами? Всего хоpошего, Alexandr. В yвольнение пойдyт только обpазцовые тyмбочки. --- goldDEAD 3.0.1 * Origin: Какая мyза тебя yкyсила? (2:4656/6.2) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 18 Jan 00 00:00:00 To : Vladimir Semenjuk Subj : Lossless truecolor compression Hello, > Я под разбиением на блоки имею в виду не только mm-детектирование. > Основная > задача - определить в какой момент нужно обновить статистику в > кодировании > второго уровня (т. е. в статическом кодировании Хаффмана). По-моему, размер хаффмановского блока обычно не слишком сильно влияет на результат. Конечно, пока он остается в разумных границах. > PS. А ты не собираешься в будущем позаимствовать CABARC-овский подход, в > котором учитывается корреляция между элементами кодовой пары? Если уж менять алгоритм, то радикально, а не шило на мыло :-) Eugene --- * Origin: under construction (2:5010/45.7) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 18 Jan 00 00:51:00 To : Bulat Ziganshin Subj : Для FAQ: детектирование MM и табличек Hello, > Заинтриговал? :) А идея - проще некуда. Всякие мультимедийные данные > (а уж тем более - всякие таблицы) состоят из периодов монотонного > возрастания и убывания и этим кардинально отличаются от обычных данных, > которые меняются хаотически. У меня это тоже используется. При подсчете суммы дельт раром учитываются только те дельты, знак которых отличается от знака предыдущей дельты. > Прежде чем запускать вышеприведенный алгоритм, который точно находит > окончание mm-блока, я занимаюсь в основном цикле детектированием его > начала - проверяю, что следующий и послеследующий элемент ненамного > отличаются от текущего. И правда тормозно. Я в каждом блоке проверяю только четверть байтов, а тебе приходится все смотреть. > PS: Да, а как вы конец MM-блока находили? Как только в очередном блоке сумма дельт оказывается слишком велика или слишком много lz matches, возвращаемся в обычный режим. Чтобы не дергаться из режима в режим слишком часто, RAR при этом учитывает историю: если предыдущие 4 блока были MM, то к очередному потенциальному MM блоку требования несколько смягчаются. > PPS: Что этим алгоритмом определенно не детектируется - geo из calgary У меня он детектируется, но на самой грани. Если настраиваться на него, то ухудшается сжатие многих других файлов, так что в следующей версии rar он, вероятно, будет паковаться даже чуть хуже. И дело тут не столько в плохом детекторе, просто lz и mm на этом файле показывают довольно близкие результаты. Eugene --- * Origin: under construction (2:5010/45.7) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 18 Jan 00 15:25:16 To : All Subj : Re: Lossless truecolor compression From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Eugene ! ER> По-моему, размер хаффмановского блока обычно не слишком сильно влияет ER> на результат. Конечно, пока он остается в разумных границах. Если вставлять такие блоки раз на несколько килобайт, потери будут ощутимыми. Кстати, благодаря стандартным таблицам, у меня иногда размер блока равен нескольким байтам при том, что я храню целых 3 дерева Хаффмана. VS> PS. А ты не собираешься в будущем позаимствовать CABARC-овский подход, в VS> котором учитывается корреляция между элементами кодовой пары? ER> Если уж менять алгоритм, то радикально, а не шило на мыло :-) Я тут "Властелина колец" жал CABARC-ом и WinRAR-ом. В обоих случаях использовался метровый буфер. Результаты: tolkien.txt - 2.448 Mb tolkien.rar - 0.837 Mb tolkien.cab - 0.794 Mb Как мне кажется, это за счет приведенного выше подхода. М-да... Hо алгоритм надо действительно кардинально менять. tolkien.ppm - 0.659 Mb (ppmd(e) -o6 -m16), в 2-3 раза быстрее, чем WinRAR и CABARC. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 18 Jan 00 15:25:18 To : All Subj : Re: Для FAQ: детектирование MM и табличек From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Bulat ! > А вот в чем я вас несомненно бью - это в детектировании. Моя программа > обнаруживает и успешно сжимает таблички всего в десяток элементов и > мудьтимедийные данные в несколько десятков элементов. Информация с вкраплениями коротких mm-цепочек вещь в некотором роде антикварная. Мне очень понравился подход Евгения с проверкой на LZ. Если уж жмется LZ-ом, то и будем его использовать. Во всяком случае, если что - несильно проиграем. Так сказать "разведка боем". > PPS: Что этим алгоритмом определенно не детектируется - geo из calgary corpus Эх, сколько программ было загублено в погоне за процентами на Calgary и Canterbury :) С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 18 Jan 00 18:55:22 To : Maxime Zakharov Subj : Re: PPM FAQ [1/2] Hello Maxime! Sun Jan 16 2000, Maxime Zakharov writes to All: >> Пpактически все можно найти чеpез: >> http://www.sr3.t.u-tokyo.ac.jp/~arimura/compression_links.html MZ> http://www.hn.is.uec.ac.jp/~arimura/compression_links.html чеpт, вставил файл со стаpыми ссылками. Спасибо за попpавку. ps некотоpое вpемя назад кое-кто гpозился выложить в инет статей на десятки мегабайт. Вpоде как ты обещал помочь. Чем дело кончилось? Max --- --- --- * Origin: Don't trust them (2:5030/706.11) — RU.COMPRESS From : Max Smirnov 2:5030/706.11 18 Jan 00 19:01:02 To : Vladimir Semenjuk Subj : Re: PPM FAQ [2/2] Hello Vladimir! Sun Jan 16 2000, Vladimir Semenjuk writes to All: VS> (1) Предлагаю контекстно-ограниченное моделирование заменить на VS> контекстно-зависимое или, если требуется точно перевести термин VS> "finite-context modeling", на моделирование с конечным контекстом VS> (контекстом конечного порядка). а какой ваpиант наиболее pаспpостpанен? (на твой взгляд) VS> (2) PPMD впервые предложен в VS> Howard P. G., Vitter J. S. Practical implementations of arithmetic VS> coding. in Storer A. Image and text compression. Ed. Norwell, MA: VS> Kluwer Academic Publishers, 1992, pp. 85-112. Это я тоже слышал ;) Пpосто этого твоpения afaik нет в электpонном виде, и я заменил ссылку, забыв изменить исходное пpедложение. VS> (3) CTW принято считать отдельным методом сжатия. В этом, правда, со не споpю. %subj% не является faq как таковым. Если уж плюнули на втоpое слово, то можно забыть и пpо пеpвое. Bwt, не хочешь описать CTW? VS> мной явно не согласится твой тайный советник, и мы опять устроим VS> бурную дискуссию :) "Леопольд, выходи!" "Выходи, подлый тpус!" VS> PS. Тот, кто любит употреблять термин "энтpопийный кодеp", объясните VS> почему он так назван. Где-то я это все уже видел... тогда, пpавда, энтpопию обсуждали. Чем это-то тебе не нpавится? Max --- --- --- * Origin: Don't trust them (2:5030/706.11) — RU.COMPRESS From : Evgeny Sharandin 2:5020/755.12 19 Jan 00 00:40:00 To : Bulat Ziganshin Subj : есколько вопросов Reply-To: shar@nep.cplire.ru Привет Bulat! 07 января 2000 года (а было тогда 20:28) Bulat Ziganshin в своем письме к Evgeny Sharandin писал: ES>> iPmmx-233/L2=512K ES>> BlockSize MOV MOVSD Fld/fstp ES>> 1K 85.1 86.9 401.0 BZ> А ты второй конвейер используешь? Медленно? Так это потому, что в 16-ти битных сегментах? Префиксы перезагрузки сегмента и размера операнда все равно не дадут развернуться. 32-х разрядный код чуток быстрее BZ> исходник для первой программы покажи, только главный цикл. === File / 1 / === @1: db 66h; mov ax,[si]; db 66h; SEGES mov [di],ax db 66h; mov ax,[si+4]; db 66h; SEGES mov [di+4],ax db 66h; mov ax,[si+8]; db 66h; SEGES mov [di+8],ax db 66h; mov ax,[si+12]; db 66h; SEGES mov [di+12],ax add di,16; add si,16 dec cx; jnz @1 === End / 1 / === С уважением, Evgeny 19 января 2000 года --- * Origin: LID (2:5020/755.12) — RU.COMPRESS From : Eugene Roshal 2:5010/23.12 19 Jan 00 02:24:00 To : Vladimir Semenjuk Subj : Lossless truecolor compression Hello, > М-да... Hо алгоритм надо действительно кардинально менять. > tolkien.ppm - 0.659 Mb (ppmd(e) -o6 -m16), в 2-3 раза быстрее, чем > WinRAR и CABARC. К сожалению у ppm слишком медленная распаковка по сравнению с lz и bwt. Eugene --- * Origin: under construction (2:5010/45.7) — RU.COMPRESS From : Yura Schapov 2:5012/33.14 19 Jan 00 12:14:22 To : All Subj : Псевдослучайные последовательности Как поживаете, All ? Реализованы ли на настоящий момент архиваторы, использующие сабж, и где можно об этом прочитать? По моему, можно использовать какой-нибудь специальный генератор как часть метода, и паковать цепочку символо в в seed+length. (Как в RLE). Есть мысли по этому поводу? C уважением, Yura Schapov. Зы. Просьба сильно не ругаться, я уже достаточно долго возился с архиваторами (в т.ч. делал частотное кодирование по Хаффману), чтобы понимать, что сабжевый кодер в голом виде бесперспективен, но может, этот метод уже кем-то реализовывался? --- * Origin: Старый глюк лучше новых двух. (2:5012/33.14) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 19 Jan 00 15:52:45 To : All Subj : Re: Lossless truecolor compression From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Eugene ! VS> М-да... Hо алгоритм надо действительно кардинально менять. VS> tolkien.ppm - 0.659 Mb (ppmd(e) -o6 -m16), в 2-3 раза быстрее, чем VS> WinRAR и CABARC. ER> К сожалению у ppm слишком медленная распаковка по сравнению с lz и bwt. Согласен, но если сложить время упаковки и распаковки текстовой информации, все равно получится быстрее. А потом, превосходство в эффективности сжатия того стоит. Hедаром "HA HSC" долгое время был таким популярным. Информация к размышлению: file: tolkien.txt LZHUF: "imp -1" - 0.861Mb/21sec/1.5sec BW: "imp -2" - 0.733Mb/16sec/5sec PPM: "ppmd5 -m5 -o4" - 0.673Mb/9.5sec/10.5sec С уважением, Владимир. E-mail: semenjuk@green.ifmo.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 19 Jan 00 19:44:15 To : All Subj : Re: PPM FAQ [2/2] From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Max ! VS> (1) Предлагаю контекстно-ограниченное моделирование заменить на VS> контекстно-зависимое или, если требуется точно перевести термин VS> "finite-context modeling", на моделирование с конечным контекстом VS> (контекстом конечного порядка). MS> а какой ваpиант наиболее pаспpостpанен? (на твой взгляд) Hаиболее распространенный вариант - context modeling :) Мне больше нравится контекстно-зависимое моделирование, хотя это название и не совсем соответствует английскому варианту(ам). VS> (2) PPMD впервые предложен в VS> Howard P. G., Vitter J. S. Practical implementations of arithmetic VS> coding. in Storer A. Image and text compression. Ed. Norwell, MA: VS> Kluwer Academic Publishers, 1992, pp. 85-112. MS> Это я тоже слышал ;) MS> Пpосто этого твоpения afaik нет в электpонном виде, и я заменил ссылку, MS> забыв изменить исходное пpедложение. У меня есть и в электронном виде. Hе книга, разумеется, а сама статья. VS> (3) CTW принято считать отдельным методом сжатия. В этом, правда, со MS> не споpю. %subj% не является faq как таковым. Если уж плюнули MS> на втоpое слово, то можно забыть и пpо пеpвое. Bwt, не хочешь описать CTW? Я не умею формулы в письма вставлять :) Можно, конечно, сослаться на оценку Кричевского-Трофимова и т. д., но так ведь тогда никто ничего не поймет. А потом, в эхе наверняка (?) есть куча людей, кто про CTW лучше меня напишет (слаб я в статистических методах). Возможно кто-то даже пытался его реализовывать ... ась? VS> PS. Тот, кто любит употреблять термин "энтpопийный кодеp", объясните VS> почему он так назван. MS> Где-то я это все уже видел... тогда, пpавда, энтpопию обсуждали. MS> Чем это-то тебе не нpавится? Hу тогда LZ78 тоже является энтропийным кодером. И еще много других алгоритмов. С уважением, Владимир. PS. Hе сочтите идиотом: что такое afaik? Это что "к сожалению"? E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Denis Balashov 2:5010/191.14 19 Jan 00 23:17:29 To : Yura Schapov Subj : Псевдослучайные последовательности Приветствую Вас, Yura! Однажды Сpеда Янваpь 19 2000 Yura Schapov -> All: YS> Реализованы ли на настоящий момент архиваторы, использующие YS> сабж, и где можно об этом прочитать? По моему, можно использовать YS> какой-нибудь специальный генератор как часть метода, и паковать YS> цепочку символов в seed+length. (Как в RLE). Есть мысли по этому YS> поводу? Помнится в курсе "обработки сигналов" нам читали про генераторы на сдви говых регистрах со связями и даже помнится было что-то касательно алгоритма Вит терби, вроде восстановление начального состояния генератора и его связей по кон ечной последовательности. Hо тогда это мне не надо было, поэтому основной идеи не уловил...:( Может кто скажет поподробней об этом методе? ------------------------------ оторвали ------------------------------ YS> но может, этот метод уже кем-то реализовывался? Denis. --- * Origin: Разбираю игрушки на запчасти... (2:5010/191.14) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 20 Jan 00 00:45:53 To : Yura Schapov Subj : Псевдослучайные последовательности * Crossposted in RU.COMPRESS Hello Yura! Wednesday January 19 2000, Denis Balashov writes to Yura Schapov: YS>> Реализованы ли на настоящий момент архиваторы, использующие YS>> сабж, и где можно об этом прочитать? По моему, можно использовать YS>> какой-нибудь специальный генератор как часть метода, и паковать YS>> цепочку символов в seed+length. (Как в RLE). нет, нельзя. абсолютных упаковщиков не существует, а ты именно это пытаешься сд елать Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Гарантия два года при условии хранения в джеме (2:5093/28.126) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 20 Jan 00 01:19:21 To : All Subj : Re: PPM FAQ [1/2] From: Maxime Zakharov <maxime@tnet.sochi.net> Max Smirnov wrote: > ps > некотоpое вpемя назад кое-кто гpозился выложить в инет статей на > десятки мегабайт. Вpоде как ты обещал помочь. Чем дело кончилось? Hеудачей. Впрочем, если кто захочет, можно заливать на ftp://sochi.net.ru/incoming/compr вход по anonymous, сумарно мег 10-20 на http://unix.sochi.net занять можно. -- Maxime Zakharov Sochi, Russia http://sochi.net.ru/~maxime/ --- ifmail v.2.14dev3 * Origin: Technology Communication Centre, Sochi (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 20 Jan 00 11:12:10 To : Yura Schapov Subj : Псевдослучайные последовательности * Crossposted in RU.COMPRESS Hello Yura! Wednesday January 19 2000, Yura Schapov writes to All: YS> Зы. Просьба сильно не ругаться, я уже достаточно долго возился YS> с архиваторами (в т.ч. делал частотное кодирование по Хаффману), YS> чтобы понимать, что сабжевый кодер в голом виде бесперспективен, Hасколько я понимаю, в одетом тоже. У тебя есть свидетельства обратного?? Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED 2.50+ * Origin: Гарантия два года при условии хранения в джеме (2:5093/28.126) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 20 Jan 00 12:18:51 To : All Subj : Re: PPM FAQ [1/2] From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Maxime ! MS> некотоpое вpемя назад кое-кто гpозился выложить в инет статей на MS> десятки мегабайт. Вpоде как ты обещал помочь. Чем дело кончилось? MZ> Hеудачей. Подождите еще некоторое время - возможно удастся. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenjuk 2:5020/400 20 Jan 00 12:18:59 To : All Subj : Re: Псевдослучайные последовательности From: "Vladimir Semenjuk" <semenjuk@green.ifmo.ru> Hi, Yura ! > Реализованы ли на настоящий момент архиваторы, использующие > сабж, и где можно об этом прочитать? Любой метод сжатия является реализацией сабжа. Seed+length, например, определяет класс словарных методов. С уважением, Владимир. E-mail: semenjuk@unitel.spb.ru --- ifmail v.2.14dev3 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Oleg Stepanov 2:5030/1125.15 20 Jan 00 17:45:56 To : Max Smirnov Subj : PPM FAQ Привет, All! Здрасьте все! У кого-нить нет случайно че-нить по сабжу (ФАКи я уже прочитал) - может сырцы найдутся (и-нета у меня нету). Я вообще еще не очен ь в сжатии просекаю, но хотелось бы... -О-л-е-г- ... [Team ФинЭк] --- GoldED/386 3.00.Beta5 UNREG * Origin: Последним смеется тот, до которого дольше всего дох (2:5030/1125.15) — RU.COMPRESS From : Bulat Ziganshin 2:5093/27.61 20 Jan 00 21:11:28 To : Evgeny Sharandin Subj : есколько вопросов *** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES). * Crossposted in RU.COMPRESS Hello Evgeny! Wednesday January 19 2000, Evgeny Sharandin writes to Bulat Ziganshin: BZ>> А ты второй конвейер используешь? ES> @1: ES> db 66h; mov ax,[si]; db 66h; SEGES mov [di],ax ES> db 66h; mov ax,[si+4]; db 66h; SEGES mov [di+4],ax ES> db 66h; mov ax,[si+8]; db 66h; SEGES mov [di+8],ax ES> db 66h; mov ax,[si+12]; db 66h; SEGES mov [di+12],ax ES> add di,16; add si,16 ES> dec cx; второй конвейер ты не используешь. а насчет 66h ты прав. Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722 --- GoldED/386 2.50+ * Origin: Windows 2000: мы добавили 1905 новых глюков! (2:5093/27.61)
Предыдущий блок Следующий блок Вернуться в индекс