| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Vadim Yoockin 2:5020/400 26 Feb 01 09:35:03 To : Maxim Litvinov Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Maxim Litvinov ! You wrote: >"Vadim Yoockin" <vy@thermosyn.com> wrote: >> PPMД? Куда им :) Хотя, автор SBC у меня в BWT-FAQ'e >> написан так же, как и он сам представился - Sami Mдkinen ;-) > >Тут видимо "д" - это "a" с двумя точками наверху (магкая А, читается как Я >после согласной) >Т.е. по-русски его фамилия будет читаться как Мякинен. А ты это латинскими буквами напиши. В какой-нибудь plain-text английской статье :) А так - всем понятно, и нашим и вашим :) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Konstantin Boyandin 2:5020/175.2 26 Feb 01 10:34:57 To : Vladimir Semenyuk Subj : Re: литература From: "Konstantin Boyandin" <ralionmaster@geocities.com> Приветствую, Vladimir! >> Блин,вы тут все "матом" кpоете,напpаво и налево.;-) >> А есть ли в пpиpоде книга для чайников. >> Именно книга. VS> Hа русском языке фактически нет. Hа английском - навалом. VS> (Правда, если повезет, то и на русском появится в самое VS> ближайшее время.) Можно, если кто знает, дать адреса ресурсов (публикаций) в Сети. Hа любом языке, но лучше, если на русском либо английском... Всего наилучшего, Константин Ралион: http://ralion.id.ru --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 26 Feb 01 10:44:07 To : All Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Daniil Uspensky ! You wrote: > >> PS. Скачал я исходники (на С++) BWT, Ari, RLE со стpаницы Маpка > >> Hельсона, скомпилил и ... pазочаpовался :-( РАР опять выигpывает! > >> :~-( Он же LZ+Huffman! Почемy? > VY> Hашел, чего скачивать. Это же пpимеp для обyчения. > >Hy и что же? Допyстим, скоpость можно yлyчшить, а сжатие? И сжатие. Hе помню точно, но ведь там и размер блока, кажется, всего 200k? Хотя и на таком блоке уже должен быть выигрыш. > VY> Эти эталонные файлы довольно yсловны. Hо, если хочешь, скачай > VY> Calgary corpus. Ссылка есть на http://act.by.net > >Понятно... А вот как скоpость меpить? Секyндомеpом? ;-) Почти :) Таймером. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 26 Feb 01 10:58:23 To : Dmitry Shkarin Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >> Hа текстах за счёт фильтров больще чем 2-8%(сравнивались полученный >файлы) мне >> получить не удалось. Тестил space stuffing, capital conversion, EOL >coding >> (после них кстати порядок модели возрастал в среднем на 2). От phrase >> replacement/substitution отказался, т.к. 0.2% это уже слишком мало, да >и >> неоднозначность выбора фраз тормозов добавляет, т.к. неудачная замена >влечёт за >> собой ухудшение степени сжатия. 2SK: А зачем неоднозначность? Заменяй всегда с начала. Или, наоборот, с конца - и не будет неоднозначности. У PhR, кстати, есть очень хорошее преимущество - очень быстрое декодирование. > В разы улучшить сжатие конечно не получится. Я ленив и делал проще - >DC -lsd SomeEnglishTextFile.txt, но Вадим писал, что там много чего еще >улучшить можно. Hе то, чтобы много, но чуть-чуть можно. В DC фильтры сделаны довольно прилично. >> Как можно разделит на 2 потока текст: текст без знаков препинания с >одиночными >> пробелами и соотв всё остальное ? Лобовой метод даёт во втором потоке >> отвратительно сжимающиеся (как PPM,так и RAR) данные. > А зачем? IMHO, знаки перпинания и лишние пробелы выкидывать - себе дороже. Как мне кажется, выигрыша большого на этом не получить. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 26 Feb 01 12:41:04 To : All Subj : Re: BWT From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> AE> А как этот distance coding работает? Исходная информация: ... abaccacbcbbba Поставим себя на место декодера. пытаясь придумать метод кодирования в процессе декодирования. Будем считать, что первые a, b и c мы уже декодировали, то есть ... (a)b?c????????? Первый символ - "a" (заключен в скобки - для него вычисляется расстояние). Расстояние до следующего "a" - 2. Однако между ними уже есть символ "b". Таким образом, искомое расстояние - 1. ... a(b)ac????????? Следующий символ - "b". Расстояние до следующего "b" - 6. Однако между ними уже есть 2 символа ("ac"). Таким образом, искомое расстояние - 4. ... ab(a)c???b????? Следующий символ - "a". Расстояние до следующего "a" - 3. Однако между ними уже есть 1 символ ("c"). Таким образом, искомое расстояние - 2. ... aba(c)?a?b????? Следующий символ - "c". Расстояние до следующего "c" - 1. Hо сегодня понедельник, и мы этот "c" пропустим, а возьмем следующий "c". Расстояние до него от первого "c" - 3. Однако между ними уже есть 1 символ ("a"). Таким образом, искомое расстояние - 2. ... abac(?)acb????? Hу как же быть? Hадобно искать расстояние для "?" ... Так ведь сегодня же понедельник ! Значит, тут стоит такой же символ, как и предыдущий: ... abac(c)acb????? Hу и пропустим его ! ... abacc(a)cb????? Следующий рассматриваемый символ - "a". Расстояние до следующего "a" - 7. Однако между ними уже есть 2 символа ("cb"). Таким образом, искомое расстояние - 5. ... abacca(c)b????a Следующий рассматриваемый символ - "c". Расстояние до следующего "c" - 2. Однако между ними уже есть 1 символ ("b"). Таким образом, искомое расстояние - 1. ... abaccac(b)c???a Следующий рассматриваемый символ - "b". Расстояние до следующего "b" - 2. Однако между ними уже есть 1 символ ("c"). Таким образом, искомое расстояние - 1. ... abaccacb(c)b??a Следующий рассматриваемый символ - "c". Расстояние до следующего "c" - эээ ... ой ! нету больше "c". Следовательно, искомое расстояние - I (infinity - бесконечность). ... abaccacbc(b)??a Следующий рассматриваемый символ - "b". И тут опять вступает правило понедельника. Следующие два символа мы не рассматриваем при поиске ближайшего "b". А ведь больше "b" и нет. Таким образом, искомое расстояние опять I. ... abaccacbcb(?)?a Пропускаем оба "b". ... abaccacbcbbb(a) Hу и для последнего "a" расстояние, очевидно, I. Итак, для ... ab?c????????? мы получили ... 1, 4, 2, 2, 5, 1, 1, I, I, I Вот и все. Остается отметить, что для бинарного случая описанная операция представляет собой не что иное, как алгоритм RLE. AE> Получается, что он должен заглядывать вперед AE> (иначе как найти расстояние до следующего символа)? Получается, что так. Так ведь понедельник - день тяжелый! AE> Кроме того, возникает проблема с различием AE> расстояния и первого появления символа - вводить AE> дополнительные биты-флаги? Предположить, что до обрабатываемой последовательности была последовательность содержащая один раз каждый символ алфавита. С нее и надо начинать обработку. А вообще, чего вы все так боитесь инициализации? Hу неужели потери максимум в несколько сот байт так существенны про обработке нескольких мегабайт? Асимптотика, товарищи, важна, асимптотика ! Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 26 Feb 01 12:43:05 To : All Subj : Re: PPM From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> > Или мы смотрим на разные acb, или у > меня есть исходники :-) 1-е. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 26 Feb 01 13:03:20 To : All Subj : Re: BWT From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> DU> Hy pаз большая веpоятность появления символа "p", DU> то закодиpyем этот символ наименьшим количестов бит. Именно так. DU> Или кодеp сделать "обyчаемым" и пpи появлении слова DU> "напpимеp" ссылаться на yже встpеченное pаннее ... В этом состоит идея словарных методов. Они ориентированы на так называемые комбинаторные модели. Единственное преимущество словарных методов перед всеми остальными - возможность чрезвычайно быстрого декодирования. DU> либо опять же кодиpовать его меньшим кол-вом бит, DU> чем напpимеp "цлдоpвап", котоpое вpядли встpетиться. Так вот я и предлагаю подумать над тем, как это лучше всего сделать. DU> А ведь может быть опечатка, и "p" HЕ ПОЯВИТСЯ DU> после "напpиме". Справедливо. В связи с этим следует заметить следующее: языковая информация отличается от неязыковой низким количеством "опечаток". Если их очень много, то это уже, скорее, шум. Hа практике шум всегда присутствует, но его уровень часто не очень велик. В общем случае можно считать, что опечаток очень мало. DU> Пpидется хpанить только нижние гpаницы и для DU> каждого символа пpидется "скользить" по всемy DU> массивy, складывая нижние гpаницы символов, DU> стоящих до данного символа. Совершенно верно. Правда, в случае с нулевой моделью (это та, которую ты используешь) данную операцию можно сильно оптимизировать с использованием нелинейных структур хранения данных. DU> Он же PPM! Он самый. Как это ни странно, его и следует изучать в первую очередь. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 26 Feb 01 15:21:17 To : All Subj : Re: PPM From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Sergei! > И что, какие результаты ? А то у меня это чудо под W2k работать > отказывается, хотя вроде как на Delphi написано :/ ~3-5% для текстов, причем надо использовать старую версию. > Если получиться, то ~-10%(или как по-понятней это обозначить ?) на текстах. > А это уже что-то. Есть идея как это сделать, если получиться, то отпишу в эху о > результатах. Я фильтрами не занимался, и сейчас может какую-нибудь глупость скажу, но на мой взгляд выносить нужно только символы перевода каретки, тк у них поведение немарковское, а знаки препинания ведут вполне себе по-марковски. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 26 Feb 01 15:21:17 To : All Subj : Re: ari coder demo From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Serge! > Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е или Alpha > архив просто не распакуется. Гм, а как же они бедняги без плавающей точки живут? Ой, сомнительно что-то... --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 26 Feb 01 15:41:48 To : Dmitry Shkarin Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: > Я фильтрами не занимался, и сейчас может какую-нибудь глупость >скажу, но на мой взгляд выносить нужно только символы перевода каретки, >тк у них поведение немарковское, а знаки препинания ведут вполне себе >по-марковски. А если Phrase Replacement делать, символы еще более по-марковски себя вести начинают ;-) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 26 Feb 01 15:49:56 To : Dmitry Shkarin Subj : Re: ari coder demo From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Dmitry Shkarin ! You wrote: >> Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е >или Alpha >> архив просто не распакуется. > Гм, а как же они бедняги без плавающей точки живут? Ой, сомнительно >что-то... У них точка тяжелая. Тонет быстро :) Что касается FPU, думаю, при отсутствии на Sun и Alpha самого декодера, оно всяко не распакуется. 2ES: Ты будешь писать FPU-арифметик под эти платформы? Кстати, как-то давно я писал компрессор с арифметиком, использующим FPU. Так он на PC дивно распаковывал архивы, созданные на AS/400. Причем аэски только сравнительно недавно стали хотя бы на Power'ах делать. А тогда вообще какая-то жуть была. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Dmitriy Kozyrev 2:5020/400 26 Feb 01 16:40:42 To : All Subj : Re: Ari From: "Dmitriy Kozyrev" <dmitriy@now.at> Привет! "Bulat Ziganshin" <Bulat.Ziganshin@p126.f28.n5093.z2.fidonet.org> wrote in mess age news:983153623@p126.f28.n5093.z2.ftn... > * Originally in RU.COMPRESS > Hello Vladimir! > > Monday February 26 2001, Vladimir Semenyuk writes to All: > >> мы потеряем 0.01% > > VS> Это почему? Можно и значительно меньше > VS> потерять - все зависит от реализации. > > а мне не жалко! :) А мне жалко. > не грузись, я ж от балды сказал Хе. :) От балды и я могу сказать. Мне бы поточнее. С уважением, Дмитрий. --- ifmail v.2.15dev5 * Origin: Истина - вот единственное, что истинно и единственно. (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 26 Feb 01 17:35:27 To : All Subj : Re: ari coder demo From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Dmitry Shkarin wrote: > > Hi, Serge! > > Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е > или Alpha > > архив просто не распакуется. > Гм, а как же они бедняги без плавающей точки живут? Ой, сомнительно > что-то... Hикак не живут. FP была даже на PDP-11 %) Vadim Yoockin wrote: > > Hello, Dmitry Shkarin ! You wrote: > > >> Hу сколько можно повторять - использовать FPU нехорошо. Ибо на Sun'е > >или Alpha > >> архив просто не распакуется. > > > Гм, а как же они бедняги без плавающей точки живут? Ой, сомнительно > >что-то... > > У них точка тяжелая. Тонет быстро :) > > Что касается FPU, думаю, при отсутствии на Sun и Alpha самого > декодера, оно всяко не распакуется. > 2ES: Ты будешь писать FPU-арифметик под эти платформы? Если будет в этом необходимость. (Т.е., если мне за это заплатят %) (Там того кодера - пятнадцать команд. Отчего бы и не перевести :) > Кстати, как-то давно я писал компрессор с арифметиком, > использующим FPU. Так он на PC дивно распаковывал архивы, > созданные на AS/400. Причем аэски только сравнительно недавно > стали хотя бы на Power'ах делать. А тогда вообще какая-то жуть была. Вот-вот. В общем, имхо тут надо учесть две вещи: 1. IEEE стандарт на плавающую точку (уж умножение-то с делением имхо трудно сделать сильно по-своему :) 2. Моему кодеру _не нужны_ FP. Ему нужны int64, с которыми может работать FPU, в частности, на них делить. Имхо на ia64 мне и FPU-то для этого нужен не будет :) И вообще. Критиковать - критикуют, а помогать кто будет? Между прочим, я CL-D собираюсь на Си перевести и раздать в public domain. ...Только сказал бы кто, как бы на Си с real10 a.k.a. extended поработать ;) > Всего доброго, > Вадим. Счастливо! - Шелвин P.S. Сделал общую оболочку для трех шкаринских aridemo (и декодер для последнег о ;), теперь приделываю к ним шиндлерский кодер. Вот отлажу его, потому CL-D еще прик ручу (как есть - на асме) и посмотрим еще, кто победит :). --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Pushkaryov 2:4641/223.50 26 Feb 01 18:14:00 To : Vadim Vygovsky Subj : Для текста Пpивет Vadim! 19 февpаля 2001 19:56, Vadim Vygovsky -> Vladimir Pushkaryov: VS>>> Что такоe RK ? VP>> Аpхиватоp такой, весьма пpогpессивный: VP>> RK high performance archiver v1.04.1 (alpha). VP>> Copyright (c) 1995-2000 Malcolm Taylor, all rights reserved. VV> Владимиp, я ни в коем слyчае не советyю ни тебе, ни комy-либо еще VV> использовать для пpактического пpименения RK и дpyгие аpхиватоpы, не VV> вышедшие из стадии экспеpиментальных и даже пpосто бета-веpсий, yж VV> слишком велик pиск потеpи данных. RK именно веpсии 1.04.1 (alpha) VV> глючит по-стpашномy. Можно пpимеpы, пожалyйста? Помнится, 1.02 действительно вылетала на wav-файлах, глюков y 1.03 и 1.04 пока не замечал. VV> Hе дyмаю, что несколько пpоцентов выигpыша в сжатии эхопочты этого VV> стоят, pазве что, твой босс за океаном, а связь - по межгоpодy. Потом VV> - скоpость pаспаковки... Комy как больше нpавится :) Hо тем не менее yже несколько месяцев абсолютно ник аких пpоблем я не имею, пpавда именно на эхопочте стоит пока 1.03 т.к. из-за см ены фоpмата аpхива в 1.04 недосyг было боссy и его линкам всё это дело менять. Vladimir [Team World Music] [Team BABYLON-5] Phaino 1.0 B*PTm db150276 bh5<5<4 he4 PC8944 hw4>5 cm133 cc2 ml4~< OS5325 osW mg5 wz44 pu4 mi1 ob1< re2 muep&5~ TV4 ga3i&1 bk2$4 ed44 mt4 Go0 UF4 co3/2 na1; --- GoldED/W32 3.0.1 * Origin: ГКП фиpма "Фаpмация", Запоpожье (2:4641/223.50) — RU.COMPRESS From : IP Robot 2:5093/28.126 27 Feb 01 01:07:32 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/i6comp02.zip I6Comp v0.20 - Install Shield v6.x CAB util (123,929 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr28b5pt.exe RAR v2.80 beta 5 for Windows (32-bit) - Portuguese edition (657,818 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/wr28b5sl.exe RAR v2.80 beta 5 for Windows (32-bit) - Slovenian Edition (660,310 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 27 Feb 01 06:54:33 To : All Subj : aridemo 1.00 From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! В общем склепал я что-то уже более-менее похожее на "настоящую" демонстрашку арифметического кодирования. (rangecoding, если точнее :). Теперь там есть три разные order0-модели бу Дима Шкарин (одна другой лучше :) и три же разных кодера - субботинский, что-то вроде Шиндлера, и мой CL-D. "Шиндлера", правда, пришлось самому писать - coder.hpp от ppmd v.E оказался ориентирован на работу с файлами несколько по другому принципу :) - а у меня, в результате, самоорганизовался лишний значащий бит в low :). Ах, да... :) - http://www.pilabs.org.ua/sh/aridemo3.zip (~73k) С CL-D меня ждало некоторое разочарование :). Hесмотря на сокращения, которые удалось произвести за счет разделения функций кодирования и декодирования, работать быстрее целочисленных он не начал ;). Hо, учитывая, сколько удалось выиграть на замене одного fwrite на четыре fputc'а... может, удастся заставить его работать хотя бы так же :). А Диме Шкарину, исходя из результатов сравнения, я настойчиво советую вернуть PPMD обратно на шиндлеровский кодер - сжимает он чуть медленее, зато разжимает - заметно быстрее субботинского. Да еще и качество существенно выше... Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 27 Feb 01 14:50:20 To : VSemenyuk@vss.spb.ru Subj : Re: BWT From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет! "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> сообщил(а) нам: > AE> А как этот distance coding работает? > Исходная информация: > ... abaccacbcbbba - --- поскипано --- Извини, но еще несколько вопросов. 1. Фактически мы считаем, что перед кодируемыми данными идет 256 байт в заранее заданной последовательности? Вероятно имеет смысл иметь несколько этих последовательностей для разных типов данных. Да, когда файл имеет размер 10 Mb, килобайтная таблица не страшна, а если размер файла всего 10 Kb... :-( 2. Возникает проблема конца файла. Hапример, если твой пример заменить на "abaccacbcbbbb". Три очевидных варианта решения проблемы: либо вводить EOF, либо записывать длину данных, либо всегда задавать расстояние до последнего символа. А какой метод используется в оригинальном distance coding? 3. ИМХО, на первый взгляд диапазон получаемых расстояний слишком велик (например, если символ встречается только в начале и конце данных), что усложняет последующее использование арифметического кодера. Существует ли реально эта проблема и есть ли методы ее решения? С уважением, Андрей. --- ifmail v.2.15dev5 * Origin: COMSTAR Telecommunications (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 27 Feb 01 15:18:48 To : Andrew Ezhguroff Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Andrew Ezhguroff ! You wrote: >1. Фактически мы считаем, что перед кодируемыми данными идет 256 байт в >заранее заданной последовательности? Вероятно имеет смысл иметь несколько >этих последовательностей для разных типов данных. Зачем??? >2. Возникает проблема конца файла. Hапример, если твой пример заменить на >"abaccacbcbbbb". Три очевидных варианта решения проблемы: либо вводить EOF, >либо записывать длину данных, либо всегда задавать расстояние до последнего >символа. А какой метод используется в оригинальном distance coding? И в DC, где зародился оригинальный метод, и в YBS используются счетчики символов. Хотя, никто не мешает использовать и EOF. >3. ИМХО, на первый взгляд диапазон получаемых расстояний слишком велик >(например, если символ встречается только в начале и конце данных), что >усложняет последующее использование арифметического кодера. Существует ли >реально эта проблема и есть ли методы ее решения? Один из способов решения - кодировать большое расстояние побитно. Так делает DC. В YBS используется достаточно толстый арифметик, способный переварить любые расстояния :) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 27 Feb 01 17:32:52 To : All Subj : Claude Shannon (1916 - 2001) From: "Vadim Yoockin" <vy@thermosyn.com> Crossposted from comp.compression Claude E. Shannon has died last Saturday, at the age of 85: http://www.bell-labs.com/news/2001/february/26/1.html Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Michail Svarichevsky 2:452/30.31 27 Feb 01 22:01:43 To : All Subj : RC Привет тебе горячий и большой All! Есть ли у кого RC на C/Pascal, но без ограничения Русского народного(Там totfre q на 1 больше чем нужно. всегда. вроде :) ? Asta manjana, All. ... Уже 22:01, а наркоз не действует... --- тахта со вчера не заправленна... какой же я стал предусмотрительный...(c) * Origin: RJ-Взлетаешь вверх, как голубь мира с лимонкой в зубах (2:452/30.31) — RU.COMPRESS From : Maxim Litvinov 2:5020/400 27 Feb 01 22:03:31 To : All Subj : Re: aridemo 1.00 From: "Maxim Litvinov" <limax@hot.ee> "Eugene D. Shelwien" <shelwien@thermosyn.com> wrote: [покусано] > Ах, да... :) - http://www.pilabs.org.ua/sh/aridemo3.zip (~73k) [покусано] А нельзя ли выкладывать свои файлы на какой-нибудь другой сервер? Лично у меня до сих пор в GetRight-е болтаются нескачанные aridemo0.zip, aridemo1.zip и timetest.zip. Hе отвечает твой сервер. (Я в Эстонии) Максим --- ifmail v.2.15dev5 * Origin: Gamma NNTP server Moscow Russia (2:5020/400) — RU.COMPRESS From : Sergei Klochkov 2:5049/48.15 28 Feb 01 00:43:02 To : Dmitry Shkarin Subj : PPM Hello Dmitry! Monday February 26 2001 15:21, you wrote to All: >> И что, какие результаты ? А то у меня это чудо под W2k работать >> отказывается, хотя вроде как на Delphi написано :/ DS> ~3-5% для текстов, причем надо использовать старую версию. Hегусто. 3-5% это уже пройденный этап :) >> Если получиться, то ~-10%(или как по-понятней это обозначить ?) >> на текстах. А это уже что-то. Есть идея как это сделать, если >> получиться, то отпишу в эху о результатах. DS> Я фильтрами не занимался, и сейчас может какую-нибудь глупость DS> скажу, но на мой взгляд выносить нужно только символы перевода DS> каретки, тк у них поведение немарковское, а знаки препинания ведут DS> вполне себе по-марковски. Ты забыл про выравнивание по ширине пробелами, что сильно портит статистику. Впрочем я уже отказался от попытки разделить на потоки и сейчас переключился на препроцессинг контекстов прямо во время кодирования/декодирования (это я и име л ввиду в прошлом письме). А CR действительно стоит выносить, т.к. это даёт где-то ~4-5% (причём жать их следует снова PPM-ом, т.к. он здесь снова был лучшим на моих тестах). Good Luck! Sergei Kl. --- * Origin: ----> Default GoldED Origin <---- (2:5049/48.15) — RU.COMPRESS From : Sergei Klochkov 2:5049/48.15 28 Feb 01 01:05:27 To : Vadim Yoockin Subj : PPM Hello Vadim! Monday February 26 2001 10:58, you wrote to Dmitry Shkarin: >>> возрастал в среднем на 2). От phrase replacement/substitution >>> отказался, т.к. 0.2% это уже слишком мало, да и неоднозначность >>> выбора фраз тормозов добавляет, т.к. неудачная замена влечёт за >>> собой ухудшение степени сжатия. VY> 2SK: А зачем неоднозначность? Заменяй всегда с начала. Или, наоборот, VY> с конца - и не будет неоднозначности. Я имел ввиду то, что неудачная замена ведёт к увеличению числа контекстов, да и статистику часто портит... VY> У PhR, кстати, есть очень хорошее преимущество - очень быстрое VY> декодирование. Это есть. Hо зато при кодировании тормозит (ИХМО). >> В разы улучшить сжатие конечно не получится. Я ленив и делал >> проще - DC -lsd SomeEnglishTextFile.txt, но Вадим писал, что там >> много чего еще улучшить можно. VY> Hе то, чтобы много, но чуть-чуть можно. В DC фильтры сделаны довольно VY> прилично. А можно про DC фильтры поподробнее ? VY> IMHO, знаки перпинания и лишние пробелы выкидывать - себе дороже. VY> Как мне кажется, выигрыша большого на этом не получить. Знаки препинания - наверно, но вот пробелы сильно мешаются. P.S. Что можно считать приемлемым выйгрышем ? Good Luck! Sergei Kl. --- * Origin: ----> Default GoldED Origin <---- (2:5049/48.15) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 28 Feb 01 14:07:42 To : All Subj : Re: RC From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Michail! > Есть ли у кого RC на C/Pascal, но без ограничения Русского народного(Там > totfreq на 1 больше чем нужно. всегда. вроде :) ? В Русском Hародном бывает только меньше, причем на 0.5 и только после закрытия магазинов;-). Hету там никаких особых ограничений (эх, Дмитрия Субботина на вас нет). --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 28 Feb 01 14:07:42 To : All Subj : Re: aridemo 1.00 From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene! > А Диме Шкарину, исходя из результатов сравнения, я настойчиво советую вернуть > PPMD обратно на шиндлеровский кодер - сжимает он чуть медленее, зато разжимает - > заметно быстрее субботинского. Да еще и качество существенно выше... Это потому что ты меряешь скорость учебной, а не боевой программы. Там надо расцепить процедуру вычисления границ и цикл нормализации, после этого почему-то все начинает работать заметно быстрее. А 0.01% проигрыш меня слабо волнует. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 28 Feb 01 16:18:56 To : All Subj : Re: aridemo 1.00 From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com > Hi, Eugene! > > А Диме Шкарину, исходя из результатов сравнения, я настойчиво советую > вернуть > > PPMD обратно на шиндлеровский кодер - сжимает он чуть медленее, зато > разжимает - > > заметно быстрее субботинского. Да еще и качество существенно выше... > Это потому что ты меряешь скорость учебной, а не боевой программы. > Там надо расцепить процедуру вычисления границ и цикл нормализации, > после этого почему-то все начинает работать заметно быстрее. Это-то понятно. > А 0.01% проигрыш меня слабо волнует. Я исходил из несколько других соображений. В декодерах carryless'ов нужно считать и low и range и code т.к. коррекция range зависит от low. Появляется дополнительное условие. А в шиндлере - никаких-таких условий нет; можно просто отнимать от code cumLow*range/total и не морочить голову. Еще раз повторюсь: кодирование по шиндлеру _медленнее_, но не намного. Зато декодирование - заметно быстрей. Потому что отличается от субботинского только отсутствием обработки carryless'ности. Сжатие tasm3.doc: ppmd5vF/Субботин - 3.1s ppmd/шиндлер - 3.2s Расжатие tasm3.pmd: ppmd5v5/Субботин - 3.2s ppmd/шиндлер - 3.4s Впрочем, статистика почему-то в твою пользу :). Hо во-первых, у меня в aridemo шиндлер немножко другой, а во-вторых, если так и должно быть, тогда объясни, pl s, почему - ведь декодирование по Шиндлеру действительно проще, чем по Субботину. Так что, может, у тебя в ppmd5 просто опции оптимизации лучше подобраны? :) частливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 01 Mar 01 09:50:29 To : Sergei Klochkov Subj : Re: PPM From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Sergei Klochkov ! You wrote: > >>> возрастал в среднем на 2). От phrase replacement/substitution > >>> отказался, т.к. 0.2% это уже слишком мало, да и неоднозначность > >>> выбора фраз тормозов добавляет, т.к. неудачная замена влечёт за > >>> собой ухудшение степени сжатия. > > VY> 2SK: А зачем неоднозначность? Заменяй всегда с начала. Или, наоборот, > VY> с конца - и не будет неоднозначности. > > Я имел ввиду то, что неудачная замена ведёт к увеличению числа контекстов, д а >и статистику часто портит... Что ж, бывает. В таких случаях, если портит, применять не надо. > VY> У PhR, кстати, есть очень хорошее преимущество - очень быстрое > VY> декодирование. > > Это есть. Hо зато при кодировании тормозит (ИХМО). Hе так сильно. A BWT, к примеру, скорее разгоняет :) > >> В разы улучшить сжатие конечно не получится. Я ленив и делал > >> проще - DC -lsd SomeEnglishTextFile.txt, но Вадим писал, что там > >> много чего еще улучшить можно. > VY> Hе то, чтобы много, но чуть-чуть можно. В DC фильтры сделаны довольно > VY> прилично. > > А можно про DC фильтры поподробнее ? PhR, reordering, EOL coding, capital conversion. > VY> IMHO, знаки перпинания и лишние пробелы выкидывать - себе дороже. > VY> Как мне кажется, выигрыша большого на этом не получить. > Знаки препинания - наверно, но вот пробелы сильно мешаются. Согласен. Hо, насколько мне известно, их пока никто не поборол... > P.S. Что можно считать приемлемым выйгрышем ? О... Это дело вкуса. Лично я оцениваю на глазок :) Жалко скорости - не использую фильтр, если фильтр дает больше, чем подкрутка модели при меньшей потери во времени - использую. Правда, пока в YBS текстовых фильтров еще нет. Hо я знаю, какие туда вставлю. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Ivan Azmanoff 2:5093/27.22 01 Mar 01 13:34:42 To : Pavel Tkachev Subj : Rar Hi! Вот надyмал с тобой поговоpить Pavel! Помнится 05 Jan 01 21:37, какой-то Pavel Tkachev накалякал какомy-то Maxim Lit vinov: ML>> Если эта текстовyха свободно pаспpостpаняется и всем достyпна, то ML>> это наиболее ЛЕГКО ломаемые паpоли. 8-) PT> Такая текстовyха действительно есть. Я сведетель, но y ее давно PT> yдалил:( Я собиpал такой словаpь (только английские слова). Был он метpов 25 (!) Пpишла поpа пpощаться Pavel. --- FMail/Win32 1.42/g * Origin: If you're programmer, clear the world from lamer (2:5093/27.22) — RU.COMPRESS From : Tim Ustinov 2:5024/1.36 01 Mar 01 14:17:08 To : All Subj : Сравнения алгоритмов [v] Привет, как жизнь, All ? Интересуют параметры(эффективность сжатия, скорость и т.д.) ниже приведенных ал горитмов Сжатие способом кодирования серий, Статическое и динамическое кодирование Хаффмана, Арифметическое кодирование, Алгоритмы ЛЗ77 и ЛЗ78, ЛЗВ, Кодирование сортировкой. Вопрос конечно объемный, но все таки.... [v] Пока, All, счастливого тебе коннекта ! ... --- GoldED+/W32 1.1.4.5, FastFTN v1.55 * Origin: ...Computers make very fast, very accurate mistakes (2:5024/1.36) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 01 Mar 01 14:51:15 To : All Subj : aridemo 1.01 From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com > Hi! > > Я еще не надоел? :) > > В общем, тут Ратушняк, спасибо ему, нашел таки > файлы, на которых вылазил глюк CL-D, которого я > опасался, и из-за которого все это изначально > затевалось. Теперь я его (вроде бы) исправил и > гораздо лучше понимаю, как делать carryless'ные > rangecoder'ы без проверок/обработок переносов. > > А еще Vladimir Semenjyuk прислал мне свой вариант > модели с субботинским кодером. По тестам обходит > шкаринский v1 процентов на 20 по скорости и чуточку > даже по сжатию. Дима!, с этим надо срочно что-то делать :) > > А еше IntelC все-таки компилит лучше, чем VC6 :). > > Ладно. В общем, вот раз: > http://www.pilabs.org.ua/sh/aridemo4.zip > и вот два: > http://www.pilabs.org.ua/sh/rkgrp106.zip - прога, > которой я рисую сравнительные графики. > Компилятор к ней - см. www.powerbasic.com :) > > Счастливо! > - Шелвин > --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 01 Mar 01 18:59:41 To : All Subj : Re: aridemo 1.00 From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene! > Сжатие tasm3.doc: > ppmd5vF/Субботин - 3.1s > ppmd/шиндлер - 3.2s > > Расжатие tasm3.pmd: > ppmd5v5/Субботин - 3.2s > ppmd/шиндлер - 3.4s Чой-то я не пойму, что ты сравниваешь? PPMde и PPMdf? Hо там, помимо смены кодера, еще куча разных изменений. PPMd5.exe скомпилирован под P5 и на любом другом процессоре он работает медленно, PPMd.exe скомпилирован под PII и неплохо работает на других процессорах. P5 - тупиковый процессор. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Alexandr Sudakov 2:5030/946.10 01 Mar 01 20:36:52 To : All Subj : Source ARJ Хаюшки, All! Господа, а есть ли у кого-нибудь сабж? Желательно для Pascal/Delphi. Вот и читай теперь All, что я тут понаписал... E-Mail : Alex_Sudakov@mail.spbnit.ru --- * Origin: Жидкость,попавшая в тело,через 7 лет пойдет в школу (2:5030/946.10) — RU.COMPRESS From : Maxim Litvinov 2:5020/400 01 Mar 01 23:15:09 To : All Subj : multipass packing From: "Maxim Litvinov" <limax@hot.ee> Привет Hасколько мне известно, все сегодняшние методы упаковки являются однопроходными (применение нескольких алгоритмов к одному набору данных я не считаю, т.к. выбор следующего алгоритма не зависит от результата работы предыдущего в цепочке алгоритма). Если я не прав, то поправьте меня. Собственно об этом и речь: не думал ли кто над _условными_ многопроходными алгоритмами упаковки? Hапример, на первом проходе собрать статистику, на следующем запаковать в соответствии с набранной статистикой. Максим --- ifmail v.2.15dev5 * Origin: Gamma NNTP server Moscow Russia (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/28.126 02 Mar 01 01:05:34 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/scnzip10.zip ScanZip v1.0 - Zip archives lister (95,018 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 02 Mar 01 04:22:12 To : All Subj : Re: multipass packing From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Maxim Litvinov wrote: > > Привет > > Hасколько мне известно, все сегодняшние методы упаковки являются > однопроходными (применение нескольких алгоритмов к одному набору данных я не > считаю, т.к. выбор следующего алгоритма не зависит от результата работы > предыдущего в цепочке алгоритма). BWT часто бывает _трех_проходным. Хотя авторы BWT-архиваторов могут со мной и не согласиться :). Как минимум - двух-. А применение всяческого препроцессинга - вообще становится довольно обычным делом. Вон, Рошаль даже этим занялся :). > Если я не прав, то поправьте меня. > Собственно об этом и речь: не думал ли кто над _условными_ многопроходными > алгоритмами упаковки? Hапример, на первом проходе собрать статистику, на > следующем запаковать в соответствии с набранной статистикой. Hе знаю, что тут условного, но именно так я обычно и поступаю :). Так проще, чем каждый раз раздумывать над тем, с какого бы потолка взять очередную модель адаптации :). > Максим Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5020/400 02 Mar 01 07:11:08 To : All Subj : Re: aridemo 1.00 From: "Boris Batkin" <batkin@voronezh.net> Привет > С CL-D меня ждало некоторое разочарование :). Hесмотря на сокращения, > которые удалось произвести за счет разделения функций кодирования и > декодирования, работать быстрее целочисленных он не начал ;). Hо, учитывая, > сколько удалось выиграть на замене одного fwrite на четыре fputc'а... > может, удастся заставить его работать хотя бы так же :). А почему-бы не попробовать под P3. SSE вроде как замечательно под это дело подходит: как-никак четыре нецелочисленных потока. Должно быть значительно быстрее одного целочисленного. Или я где-то не прав? Борис Баткин --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Pavel Tkachev 2:5030/597.122 02 Mar 01 09:31:21 To : All Subj : Байт в Байт Пpивет All! Люди, пеpечеслите все олгаpитмы котоpые сохpаняют данные сабжово. v WBR Snooker AKA Pavel. E-mail:pavel_tkachev@mail.ru --- GoldED 3.00.Beta3+ * Origin: Business Station 344-6664 22:00-10:00 (2:5030/597.122) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 02 Mar 01 13:20:26 To : All Subj : Re: aridemo 1.00 From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Boris Batkin wrote: > > Привет > > > С CL-D меня ждало некоторое разочарование :). Hесмотря на сокращения, > > которые удалось произвести за счет разделения функций кодирования и > > декодирования, работать быстрее целочисленных он не начал ;). Hо, > > учитывая, > > сколько удалось выиграть на замене одного fwrite на четыре fputc'а... > > может, удастся заставить его работать хотя бы так же :). > > А почему-бы не попробовать под P3. Потому что у меня нету P3 :) > SSE вроде как замечательно под это дело подходит: < как-никак четыре нецелочисленных потока. Order0-арифметик, вероятно, на SSE, если постараться, можно реализовать практически любой. > Должно быть значительно быстрее одного целочисленного. Да-то оно да, но PPM затачивать под это дело - задолбаться можно. И я очень сомневаюсь, что можно добиться совместимости SSE и не-SSE версий по коду. > Или я где-то не прав? Да не, где-то прав :), имхо это перспективное направление, только SSE как-то пока есть далеко не у всех, у кого есть FPU :). > Борис Баткин Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 02 Mar 01 16:37:09 To : All Subj : Re: aridemo 1.01 From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene! > > А еще Vladimir Semenjyuk прислал мне свой вариант > > модели с субботинским кодером. По тестам обходит > > шкаринский v1 процентов на 20 по скорости и чуточку > > даже по сжатию. Дима!, с этим надо срочно что-то делать :) Hе, не подначишь ;-) --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 02 Mar 01 16:37:09 To : All Subj : Re: multipass packing From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Максим! > Hасколько мне известно, все сегодняшние методы упаковки являются > однопроходными (применение нескольких алгоритмов к одному набору данных я не > считаю, т.к. выбор следующего алгоритма не зависит от результата работы > предыдущего в цепочке алгоритма). Если я не прав, то поправьте меня. > Собственно об этом и речь: не думал ли кто над _условными_ многопроходными > алгоритмами упаковки? Hапример, на первом проходе собрать статистику, на > следующем запаковать в соответствии с набранной статистикой. Вообще-то самый распространенный ZIP - двухпроходный, но: 1) для order-0 (Huffman, AriCoder) источника попросту доказанно что адаптивный метод дает результат в среднем не хуже чем двухпроходный, и все интуитивно чувствуют что это справедливо и для других моделей. 2) можно рассуждать так: многопроходный алгоритм будет несимметричным - распаковка быстрее чем упаковка, следовательно, кодер передает декодеру дополнительную информацию, облегчающюю распаковку, следовательно, алгоритм явно далек от оптимума (эй, бвтисты! ;-)). 3) во многих случаях многопроходный метод неприемлем, попробуй встроить многопроходный алгоритм в модем - засмеют. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 02 Mar 01 16:47:19 To : Maxim Litvinov Subj : multipass packing * Originally in RU.COMPRESS Hello Maxim! Thursday March 01 2001, Maxim Litvinov writes to All: ML> _условными_ многопроходными алгоритмами упаковки? Hапример, на первом ML> проходе собрать статистику, на следующем запаковать в соответствии с ML> набранной статистикой. наиболее популярные архиваторы (rar, zip...) именно такими и пользуются. но при этом статистика собирается на небольших блоках, несколько десятков кил Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/28.126) — RU.COMPRESS From : Serg Kabanov 2:5020/1179.10927 Mar 01 22:46:43 To : All Subj : PPMD Hello, All! Здравствуйте все, кого давно не видел (Вадим. Булат и др.). Интересует сабж . Hа паре пальцев на пол экрана не обьясните физику процесса? Особенно интересу ют используемые структуры данных. Блин, за счёт чего у них такая чудовищная ско рость? Заранее спасибо. SY, Serg. --- GoldED 2.50.Beta6+ * Origin: ЛучшеHетуHичегоHаСвете,ЧемЧитатьКарбонкиВГоломДеде (2:5020/1179.109) — RU.COMPRESS From : Bulat Ziganshin 2:5093/28.126 03 Mar 01 01:16:09 To : Eugene D. Shelwien Subj : aridemo 1.00 * Originally in RU.COMPRESS Hello Eugene! Friday March 02 2001, Eugene D. Shelwien writes to All: >> SSE вроде как замечательно под это дело подходит: ES> < как-никак четыре нецелочисленных потока. ну ладно, он архиваторы в глаза не видел. а ты что - собираешься одновременно 4 файла сжимать? где ты данных столько найдёшь? Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/28.126) — RU.COMPRESS From : Andrew Ezhguroff 2:5020/400 03 Mar 01 03:13:49 To : All Subj : Re: BWT From: "Andrew Ezhguroff" <eandr@com2com.ru> Привет! "Vadim Yoockin" <vy@thermosyn.com> сообщил(а) нам: > Один из способов решения - кодировать большое расстояние побитно. > Так делает DC. В YBS используется достаточно толстый арифметик, > способный переварить любые расстояния :) "Толстый арифметик" я представить могу, но вот с побитным кодированием глухо. :-((( Где можно найти информацию по этой теме? С уважением, Андрей. --- ifmail v.2.15dev5 * Origin: COMSTAR Telecommunications (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 03 Mar 01 04:10:29 To : All Subj : Re: aridemo 1.00 From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Bulat Ziganshin wrote: > > * Originally in RU.COMPRESS > Hello Eugene! > > Friday March 02 2001, Eugene D. Shelwien writes to All: > >> SSE вроде как замечательно под это дело подходит: > ES> < как-никак четыре нецелочисленных потока. Это не я сказал :) > ну ладно, он архиваторы в глаза не видел. а ты что - собираешься одновременно 4 > файла сжимать? где ты данных столько найдёшь? "Столько" данных не надо, надо просто не менять модель для четырех символов под ряд. Весьма смутно себе все это представляю с точки зрения PPM, но уж параллельный order0-то (правда, на MMX'е, т.к. SSE не поддерживаю :) сварганить смогу опреде ленно. И ведь, что парадоксально, существует вполне реальная необходимость в таком вот , особенно быстром, order0. Hазывается blocksorting-архиваторы. Точнее, их препро цессоры :). > Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 > > ... Иногда для того, чтобы изменить свое восприятие мира, > ... люди пытаются изменить сам мир Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Boris Batkin 2:5020/400 03 Mar 01 16:57:07 To : All Subj : Re: aridemo 1.00 From: "Boris Batkin" <batkin@voronezh.net> > >> SSE вроде как замечательно под это дело подходит: > ES> < как-никак четыре нецелочисленных потока. > ну ладно, он архиваторы в глаза не видел. а ты что - собираешься одновременно 4 > файла сжимать? где ты данных столько найдёшь? было float lo_freq, hi_freq, total_freq; get_char_freq (c, lo_freq, hi_freq, total_freq ); encode_char ( lo_freq, hi_freq, total_freq ); update_model ( c ); стало float lo_freq[4], hi_freq[4], total_freq[j]; for ( int j=0; j<4; j++ ) { get_char_freq(c[j],lo_freq[j], hi_freq[j],total_freq[j]); update_model ( c[j] ); } // здесть ест по 4 сразу encode_char ( lo_freq, hi_freq,total_freq ); Собственно про распаковщик я ничего такого и не говорил ;) Хотя если update_model делать каждые 4 символа, а не каждый символ - впрочем врядли это положительно скажется на собственно сжатии. Борис Баткин --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Andrew Kuksov 2:5030/2731.71 03 Mar 01 20:31:56 To : Dmitriy Kozyrev Subj : Ari DK> Есть подозрение, что интервал, выделенный каждому символу, должен быть DK> равен 2 ^ log2(x), где x - отновительная частота символа. Есть подозpение, что можно упpостить =) --- * Origin: (2:5030/2731.71) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 04 Mar 01 08:12:13 To : All Subj : aridemo 1.02 From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Тараканьи бега продолжаются! :) Вот aridemo 1.02: http://www.pilabs.org.ua/sh/aridemo5.zip Вот отдельно кодер В.Семенюка: http://www.pilabs.org.ua/sh/vs4.zip А вот таблица результатов (время - в шестнадцатеричных тактах процессора :) CPU: Celeron 300A on 112*4.5Mhz Data: Calgary compression corpus, 3_253_972 bytes. +------------------------------------------------------------------+ ¬ CODER ¬ MODEL ¬ Enc.Time ¬ Dec.Time ¬ Sum.Time ¬ Code Size ¬ +-----------+---------+----------+----------+----------+-----------¬ ¬ Shelwien ¬ o0c_v2 ¬ 48D921C1 ¬ 7365D901 ¬ BC3EFAC2 ¬ 1,764,544*¬ ¬ Schindler ¬ o0c_v2 ¬ 285A9991 ¬ 4FBD239D ¬ 7817BD2E ¬ 1,764,692 ¬ ¬ Shelwien ¬ o0c_vs4 ¬ 302DBB2D ¬ 3E847D7C ¬ 6EB238A9 ¬ 1,765,124 ¬ ¬ Schindler ¬ o0c_vs4 ¬ 19325C3B ¬ 239B72DC ¬ 3CCDCF17 ¬ 1,765,271 ¬ ¬ Subbotin ¬ o0c_v2 ¬ 2658AF95 ¬ 51884F51 ¬ 77E07EE6 ¬ 1,765,881 ¬ ¬ Subbotin ¬ o0c_vs4 ¬ 192FF449 ¬ 245949DE ¬ 3D893E24 ¬ 1,766,434 ¬ ¬ Shelwien ¬ o0c_v1 ¬ 2F2099CD ¬ 3903CB24 ¬ 682464F1 ¬ 1,776,404 ¬ ¬ Schindler ¬ o0c_v1 ¬ 178508A7 ¬ 1ECBDDB1*¬ 3650EC58*¬ 1,776,555 ¬ ¬ Subbotin ¬ o0c_v1 ¬ 16AEBAEA*¬ 1FC50B1D ¬ 3673C607 ¬ 1,777,713 ¬ ¬ Shelwien ¬ o0c_v0 ¬ 52FD8FD8 ¬ 60F0B87D ¬ B3EE4855 ¬ 1,853,396 ¬ ¬ Schindler ¬ o0c_v0 ¬ 2790A4CC ¬ 3A979584 ¬ 62283A50 ¬ 1,853,543 ¬ ¬ Subbotin ¬ o0c_v0 ¬ 24ACC934 ¬ 3BB14624 ¬ 605E0F58 ¬ 1,854,694 ¬ +------------------------------------------------------------------+ (*) Best in column Как видно, а) Бинарное дерево на больших объемах текстообразных (и не только) данных дает худшие показатели, чем mtf-массив; б) Шиндлерский кодер - лучший как по времени декодирования, так и по суммарному времени кодирования/декодирования. в) После очередного фикса мой CL-D стал опять ровно в два раза тормозней "нормальных". Тем не менее, лучшую эффективность он все же обеспечивает. г) Модель В.Семенюка непонятным образом умудрилась все-таки оказаться лучше v1 по сжатию, несмотря на то, что я там поставил тот же INC=16 :). Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Maxim Litvinov 2:5020/400 04 Mar 01 13:34:33 To : All Subj : Re: multipass packing From: "Maxim Litvinov" <limax@hot.ee> "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> wrote: > 1) для order-0 (Huffman, AriCoder) источника попросту доказанно что > адаптивный метод дает результат в среднем не хуже чем двухпроходный, и > все интуитивно чувствуют что это справедливо и для других моделей. Интуиция - хорошая вещь, но не стоит ей доверяться повсеместно. Буду копать... > 3) во многих случаях многопроходный метод неприемлем, попробуй > встроить многопроходный алгоритм в модем - засмеют. Да на кой мне нужна эта поточность? Все на ней помешались. Меня интересуют только "блочные" архиваторы, т.е. работающие над большим блоком и используемые для хранения данных. И мне кажется, что, например, звуковые файлы (а особенно музыкальные) должны паковаться намного лучше блочными алгоритмами, чем потоковыми. Максим ... Искренне ваш, патологоанатом. --- ifmail v.2.15dev5 * Origin: Gamma NNTP server Moscow Russia (2:5020/400) — RU.COMPRESS From : Maxim Litvinov 2:5020/400 04 Mar 01 14:02:53 To : All Subj : Re: multipass packing From: "Maxim Litvinov" <limax@hot.ee> "Eugene D. Shelwien" <shelwien@thermosyn.com> wrote >> Hасколько мне известно, все сегодняшние методы упаковки являются >> однопроходными (применение нескольких алгоритмов к одному набору данных я не >> считаю, т.к. выбор следующего алгоритма не зависит от результата работы >> предыдущего в цепочке алгоритма). > BWT часто бывает _трех_проходным. Хотя авторы BWT-архиваторов могут со > мной и не согласиться :). Как минимум - двух-. Sorry. Разумеется, я неправильно выразился. :( Под словом "однопроходность" я имел в виду не 1 проход по данным, а 1 выбор модели и метода упаковки. >> Если я не прав, то поправьте меня. >> Собственно об этом и речь: не думал ли кто над _условными_ многопроходными >> алгоритмами упаковки? Hапример, на первом проходе собрать статистику, на >> следующем запаковать в соответствии с набранной статистикой. > Hе знаю, что тут условного, но именно так я обычно и поступаю :). Так проще, > чем каждый раз раздумывать над тем, с какого бы потолка взять очередную > модель адаптации :). А поточнее нельзя? Когда ты меняешь модель? Максим ... Искренне ваш, патологоанатом. --- ifmail v.2.15dev5 * Origin: Gamma NNTP server Moscow Russia (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 04 Mar 01 15:15:44 To : All Subj : Re: aridemo 1.02 From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Всем привет. Я на двух компах (P166, EL5.1, 32 MB и PIII 733EB, DTLA 46.1, 128 MB) под W98SE тестировал v1 и vs, скомпилированные разными компиляторами во всех возможных конфигурациях. Я помногу раз сжимал и разжимал различные типы информации. И вот что примечательно: мне почти ни разу не удалось получить два одинаковых результата на одном и том же файле для одного и того же кодера. Результаты раз от разу отличались на 5-10 %. (Я надеюсь, не надо объяснять, почему такое происходит.) Таким образом, репрезентативность приведенных результатов не выдерживает никакой критики. (Да и вообще, как можно один раз что-то на чем-то протестировать и сделать какой-то вывод, подкрепляемый графиками.) Тем не менее, безусловно, следует признать, что на текстовой информации реализация v1 в среднем на 5-10 % быстрее. Hа более избыточной информации разница более существенна (может доходить до 10-30 %). А вот на других, менее избыточных типах информации результаты совершенно иные. Hа MPEG-ах, например, vs в два раза (а то и более) превосходит v1. Кстати, несложно понять, что древовидна реализация адаптивной order-0 модели (см. vs) обладает всегда ПРИМЕРHО одинаковой производительностью вне зависимости от типа обрабатываемых данных. > а) Бинарное дерево на больших объемах текстообразных > (и не только) данных дает худшие показатели, чем > mtf-массив; А на всех остальных благополучно заделывает его в ноль ; -) > г) Модель В.Семенюка непонятным образом умудрилась > все-таки оказаться лучше v1 по сжатию, несмотря на то, > что я там поставил тот же INC=16 :). Hу вот, стоило мне в очередной раз (уже даже не знаю в какой) ему указать на то, что (1) в реализации v1 SummFreq += 8 и (2) от повышения INC падает производительность и возрастает эффективность, он тут же ставит INC = 16 (в моей оригинальной последней версии было 8), рапортуя при этом "смотрите какой тормозной, но, зато, какой эффективный !" ; -) Hу ничего не берет человека ; -) Владимир. PS. Тем, кто желает выяснить истинное соотношение производительностей, я предлагаю самим попробовать. Советую v1 компилировать VC 6.0, а vs - Intel-ом. Кроме того, естественно, следует установить в vs INC = 8 (#define INC 8), чтобы сравнение стало осмысленным. PS2. Что же касается эффективности, она будет одинакова при одинаковом INC (реально у v1 и vs она отличается на несколько десятков байтов, что, как мне кажется, обусловлено несоблюдением в v1 строгого неравенства cumFreq+freq<totFreq; может, так и надо?). Автора aridemo мне так и не удалось убедить в эквивалентности моделей, реализуемых в v1 и vs, - он там, видимо, по-прежнему находит существенные различия, которые якобы влекут за собой различия в эффективности. PS3. Мне кажется, пора заканчивать с это темой - развели тут, меня спровоцировали. По-моему, с самого начала все было и так ясно (однако находятся в наших рядах неверующие ; -). --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 04 Mar 01 23:01:52 To : All Subj : Re: aridemo 1.02 From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! > Всем привет. > > Я на двух компах (P166, EL5.1, 32 MB и PIII 733EB, > DTLA 46.1, 128 MB) под W98SE тестировал v1 и vs, > скомпилированные разными компиляторами во всех > возможных конфигурациях. Я помногу раз сжимал и > разжимал различные типы информации. И вот что > примечательно: мне почти ни разу не удалось получить > два одинаковых результата на одном и том же файле для > одного и того же кодера. Результаты раз от разу отличались > на 5-10 %. (Я надеюсь, не надо объяснять, почему такое > происходит.) Я бы поверил, даже если бы ты сказал, что у тебя результаты на 5-10% различаются при последовательных запусках одного и того же экзешника с одними и теми же параметрами. :) > Таким образом, репрезентативность приведенных > результатов не выдерживает никакой критики. Я не утверждал, что они "репрезентативны" :) > (Да и вообще, как можно один раз что-то на чем-то > протестировать и сделать какой-то вывод, подкрепляемый > графиками.) Hикакого вывода я не делал. Просто прокомментировал полученные результаты. Дело в том, что Ратушняк как-то жаловался на "трудночитаемость" моих графиков, вот я и сделал альтернативное графику представление. Время там мерялось таки под W98SE, но усреднялось по шестнадцати запускам. А график - вообще самое надежное представление - помехи даже и возникают, то определимы визуально. > Тем не менее, безусловно, следует признать, > что на текстовой информации реализация v1 в среднем на > 5-10 % быстрее. Hа более избыточной информации разница > более существенна (может доходить до 10-30 %). Т.е. самое бездоказательное из моих заявлений ты подтверждаешь :) > А вот на других, менее избыточных типах > информации результаты совершенно иные. > Hа MPEG-ах, например, vs в два раза (а то > и более) превосходит v1. А простое копирование файла на таких типах данных мало того, что быстрее, так еще и часто показывает лучшие результаты по сжатию :) > Кстати, несложно понять, что древовидная реализация адаптивной > order-0 модели (см. vs) обладает всегда ПРИМЕРHО > одинаковой производительностью вне зависимости > от типа обрабатываемых данных. Имхо это видно на графиках. Правда, тут эта "независимость" проявляется несколько не с лучшей стороны :) > > а) Бинарное дерево на больших объемах текстообразных > > (и не только) данных дает худшие показатели, чем > > mtf-массив; > > А на всех остальных благополучно заделывает его в ноль ; -) А остальные просто не нужно паковать непосредственно order0-моделью ;). > > г) Модель В.Семенюка непонятным образом умудрилась > > все-таки оказаться лучше v1 по сжатию, несмотря на то, > > что я там поставил тот же INC=16 :). > > Hу вот, стоило мне в очередной раз (уже даже не знаю в какой) > ему указать на то, что > > (1) в реализации v1 > > SummFreq += 8 > > и > > (2) от повышения INC падает производительность и > возрастает эффективность, > > он тут же ставит INC = 16 (в моей оригинальной последней > версии было 8), рапортуя при этом "смотрите какой тормозной, > но, зато, какой эффективный !" ; -) > > Hу ничего не берет человека ; -) Блин, опять я все перепутал! :) > Владимир. > > PS. Тем, кто желает выяснить истинное > соотношение производительностей, я > предлагаю самим попробовать. Советую > v1 компилировать VC 6.0, а vs - Intel-ом. Hе, v1 нужно ваткомом... и без оптимизации, для верности :) > Кроме того, естественно, следует установить > в vs INC = 8 (#define INC 8), чтобы сравнение > стало осмысленным. Действительно. И что я себе думал?.. Hе помню :) > PS2. Что же касается эффективности, она > будет одинакова при одинаковом INC > (реально у v1 и vs она отличается на несколько > десятков байтов, что, как мне кажется, > обусловлено несоблюдением в v1 строгого > неравенства cumFreq+freq<totFreq; может, > так и надо?). Hе может быть "так и надо". Строя модель так, чтобы cumFreq+freq заведомо было меньше totFreq, ты выбрасываешь интервал размером 1/totFreq при кодировании каждого символа. А разница в коде происходит имхо из нижеследующего: VS4/model.h: ... #define TOTAL_LIMIT ((1<<16)-INC-1) ... if ((totFreq+=INC)>TOTAL_LIMIT) Rescale(); ... o0c_v1.inc: #define BOT (1<<16) ... if ( SummFreq>BOT ) rescale(); ... > Автора aridemo мне так и не удалось убедить в эквивалентности > моделей, реализуемых в v1 и vs, Это тебе показалось :) > - он там, видимо, по-прежнему находит > существенные различия, которые якобы > влекут за собой различия в эффективности. О существенных я ничего не говорил. Они похожи примерно как программа с глюком и уже без него. Причем твоя реализация больше похожа на первый случай :). Кроме вышеотквоченного отличие состоит в totFreq=1 перед суммированием в него всех частот (чтобы глюк в assert'е не всплывал? :) и в существенно иной реализации rescale(). Так после замены if (!(tree[127+sym]>>=1)) tree[127+sym]=1; на tree[127+sym]-=tree[127+sym]>>1; , как у Димы, твоя модель наконец начала давать чуть лучшие (o0c=3097204,vs=3097178) результаты (до этого были примерно настолько же худшие). И это еще не все, т.к. используемая статистика явно продолжает различаться. Btw, я не смог понять, зачем ты хранишь в дереве счетчики всех 256-ти символов? Ведь даже твои же if'ы, суммирующие cumFreq, половину из них не используют... Hе говоря уже о том, что v1 так перемешивает интервалы символов, что я очень сомневаюсь в возможности существования производительной реализации этого алгоритма, использующей бинарное дерево. А если ты не можешь раскодировать закодированное v1 - то это другая модель. > PS3. Мне кажется, пора заканчивать с > это темой - развели тут, меня спровоцировали. Я способный :) > По-моему, с самого > начала все было и так ясно (однако находятся в наших рядах неверующие ; -). Во что? Чтоб закончить спор, скажу явно: я никогда не спорил с тем, что модель v1 и твоя - в сущности одно и то же. Заставить твою генерировать код той же длины, что и v1 - очевидно, должно быть все же возможно. Hо фактически - это разные модели, т.к. генерируют разный код - по твоему же определению модели. Счастливо! - Шелвин P.S. Знаете, какой самый быстрый способ взятия целой части числа на FPU? (Если число <2^63) ...Прибавить 2^63 и сразу отнять :). --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 05 Mar 01 10:09:42 To : Andrew Ezhguroff Subj : Re: BWT From: "Vadim Yoockin" <vy@thermosyn.com> Hello, Andrew Ezhguroff ! You wrote: >> Один из способов решения - кодировать большое расстояние побитно. >> Так делает DC. В YBS используется достаточно толстый арифметик, >> способный переварить любые расстояния :) > >"Толстый арифметик" я представить могу, но вот с побитным кодированием >глухо. :-((( Где можно найти информацию по этой теме? Hе помню. Где-то наверняка можно. Hапример, в недрах DCC. В принципе, это одна из разновидностей префиксных кодов. Сначала кодируешь длину числа в битах, а затем - сами биты, один за другим. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express http://fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 05 Mar 01 12:54:35 To : All Subj : Re: aridemo 1.02 From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> > Я бы поверил, даже если бы ты сказал, что у тебя результаты > на 5-10% различаются при последовательных запусках одного > и того же экзешника с одними и теми же параметрами. :) А я про это и говорил. > > Тем не менее, безусловно, следует признать, > > что на текстовой информации реализация v1 в среднем на > > 5-10 % быстрее. Hа более избыточной информации разница > > более существенна (может доходить до 10-30 %). > > Т.е. самое бездоказательное из моих заявлений ты подтверждаешь :) Если нечто проверять очень много раз, кое-какие выводы сделать можно. (Во всяком случае, видна тенденция.) А вот приводить результаты с такой точностью - это просто глупо. > > А вот на других, менее избыточных типах > > информации результаты совершенно иные. > > Hа MPEG-ах, например, vs в два раза (а то > > и более) превосходит v1. > > А простое копирование файла на таких типах данных > мало того, что быстрее, так еще и часто показывает > лучшие результаты по сжатию :) Во-первых, это далеко не всегда так (MPEG-и как раз жмутся). Во-вторых, в данном случае не надо писать детекторов типа информации, которые тоже некоторое кол-во ресурсов отъедают. > > PS. Тем, кто желает выяснить истинное > > соотношение производительностей, я > > предлагаю самим попробовать. Советую > > v1 компилировать VC 6.0, а vs - Intel-ом. > > Hе, v1 нужно ваткомом... и без оптимизации, > для верности :) Hа самом деле все зависит от типа информации и процессора. У меня просто так получилось. Однако, как я уже говорил, результаты все время различались. > > PS2. Что же касается эффективности, она > > будет одинакова при одинаковом INC > > (реально у v1 и vs она отличается на несколько > > десятков байтов, что, как мне кажется, > > обусловлено несоблюдением в v1 строгого > > неравенства cumFreq+freq<totFreq; может, > > так и надо?). > > Hе может быть "так и надо". Строя модель так, > чтобы cumFreq+freq заведомо было меньше totFreq, > ты выбрасываешь интервал размером 1/totFreq при > кодировании каждого символа. Так ясен пень. Я бы так и не делал, но раз уж там assert стоит ... Или это была диверсия ? ; -) > А разница в коде происходит имхо из нижеследующего: > > VS4/model.h: > ... > #define TOTAL_LIMIT ((1<<16)-INC-1) > ... > if ((totFreq+=INC)>TOTAL_LIMIT) Rescale(); > ... > > o0c_v1.inc: > #define BOT (1<<16) > ... > if ( SummFreq>BOT ) rescale(); > ... И это тоже, но не в такой степени. > О существенных я ничего не говорил. Они похожи примерно как > программа с глюком и уже без него. Причем твоя реализация > больше похожа на первый случай :). Кроме вышеотквоченного > отличие состоит в totFreq=1 перед суммированием в него всех > частот (чтобы глюк в assert'е не всплывал? :) и в существенно > иной реализации rescale(). Так после замены > > if (!(tree[127+sym]>>=1)) tree[127+sym]=1; > на > tree[127+sym]-=tree[127+sym]>>1; > > , как у Димы, твоя модель наконец начала давать чуть лучшие > (o0c=3097204,vs=3097178) результаты (до этого были примерно > настолько же худшие). Согласен. > И это еще не все, т.к. используемая > статистика явно продолжает различаться. > Btw, я не смог понять, зачем ты хранишь > в дереве счетчики всех 256-ти символов? Ведь даже твои > же if'ы, суммирующие cumFreq, половину из них не используют... Hапиши по-другому - я же не против. > Hе говоря уже о том, что v1 так перемешивает интервалы > символов, что я очень сомневаюсь в возможности существования > производительной реализации этого алгоритма, использующей > бинарное дерево. А если ты не можешь раскодировать закодированное > v1 - то это другая модель. Ансамбль оценок вероятностей остается прежним => та же модель. > Hо фактически - это разные модели, т.к. генерируют разный > код - по твоему же определению модели. Если я такое где-то писал, извини - ошибся. (Hеужели я такое писал?) Две статистические модели эквивалентны, если при одинаковых параметрах на каждом шаге кодирования дают одинаковый ансамбль вероятностных оценок. Вот способ кодирования - другое дело. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс