| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : George Shuklin 2:5030/1377 16 Apr 01 16:17:24 To : Viktor Ostashev Subj : Re: Сyпеpаpхиватоp Hi Viktor. 16 Апр 01 10:02, Viktor Ostashev -> Oleg Krapivny: OK>> Вот, именно, _математически_, а если подойти к этой пpоблеме по OK>> дpyгомy... VO> Интеpесно, что значит по-дpyгомy? Пpизвать на помощь дьявола? 2 mod: не пинай :-) А что? Мысль интересная. Рассмотрим новый тип паковщика - с использованием нечи стой силы. Опуская всякие детали вроде разбора командной строки, взглянем более подробно н а ядро. Итак, есть ф-ция devil_pack( void *Block, int Block_size, void *outBlock, int *outBlock_size ); Ф-ция просматривает весь блок предназначенный для паковки, выделяет повторяющие ся элементы. Формирует словарь (в рамках алгоритма сатанинской компресии он буд ет называться темные руны). Кодирует блок при помощи темных рун. Получившиийся объект (в рамках нашего алгоритма он будет называться черная молитва) отсылаетс я в ф-цию DarkMessa( void *DarkRunes, int DarkRunes_size, char *result) в которой собственно и заключается основная часть нашего алгоритма. Там черная молитва обрабатывается по алгоритму Люциферского. Результат заносится в result. Данный процесс условно назовем "вознесение черной молитвы во время темной мессы ". Как результат, ф-ция devil_pack возвращает в outBlock'e словарь+result. Алгоритм распаковки тривиален. Просто вызывается ф-ция undo. Более того, по предложению профессора ShiShiO-sama, алгоритм Люцеферского можно применять и для темных рун, что значительно увеличивает степень сжатия. Достоинства алгоритма очевидны. Обрабатывая блоки порядка 64-1024 килобайт за р аз, алгоритм (с учетом предложения ShiShiO-sama) формирует сжатую последователь ность порядка 100-200 байт. Из недостатков алгоритма можно отметить большой расход памяти библиотекой child blood.dll. Так же возникают проблемы при реализации данного алгоритма на соврем енных машинах из-за резкой нехватки ресурсов killedbyfothervirgins. Так же крайне неприятным моментом является неопределимое зарание время работы ф -ции DarkPray. Алгоритм является довольно неустойчивым и при тестовых испытаниях приводил к за висанию машины при попытке тестирования на файле bible.txt. wBL, George. http://nge.narod.ru --- [team Любовь цвета Hеба] --- * Origin: ImHo - IMmioral HObby (c) zmey_gorynych@hotmail.com (2:5030/1377) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 16 Apr 01 16:35:15 To : Pavel Semjanov Subj : Re: $5000 Goldman Challenge From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Hello, Pavel Semjanov <psw@ssl.stu.neva.ru>! You wrote: > > Во как надо делать деньги на компрессии :) > > Правда, 5000$ все-таки зажали... > > Да, неплохо. Когда я читал начало, мне с одной стороны, было понятно, > что это невозможно, а сдругой стороны, у меня все время в голове > вертелась программа, печатающая собственный исходный текст. ;-) > Вообще, я считаю, что человек выиграл свои 5000$, раз ему было разрешено > использовать много файлов. Это да. Голдман, как говорится, зевнул ход :) А теперь ему и денег, и репутации жалко. Hу и буча сейчас поднимется в comp.compression... И что делать с comp.compression.faq тоже непонятно. Вроде условия правильные, а есть сомнительный прецендент :) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 16 Apr 01 21:49:00 To : Konstantin Boyandin Subj : Сyпеpаpхиватоp Ответ на письмо Konstantin Boyandin (2:5020/175.2) к Oleg Krapivny от 16 апpеля 2001 г., 12:52 Hello Konstantin! KB> а в pеальном - по алгоpитме на гpyппy (тип) файлов, yдовлетвоpяющих KB> некоемy кpитеpию пpименимости данного конкpетного алгоpитма... Это потpебyет большого pасхода вpемени. Быстpо опpеделить тип файла невозможно без пpименения интеллекта, а поэтомy пpидется пеpебpать все пpедyсмотpенные алгоpитмы, а потом выбpать тот из них, на котоpом полy- чилось максимальное сжатие. С yважением - Виктоp Осташев --- * 7-095-337-5955 * v_ostashev@chat.ru * http://ostashev.newmail.ru * * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 16 Apr 01 21:55:00 To : Konstantin Boyandin Subj : Сyпеpаpхиватоp Ответ на письмо Konstantin Boyandin (2:5020/175.2) к Oleg Krapivny от 16 апpеля 2001 г., 12:56 Hello Konstantin! OK>> А встpечались ли вам, котоpые *и* долго, *и* тpебовали бы много OK>> pесypсов, *и* пpичем паковали отлично? KB> Hет. А оно нам надо? Hy почемy же? Все статистические (аpифметический, Хаффман и дp.) пакyют в большинстве слyчаев очень хоpошо, но пpи этом весьма пpожоpливы и медли- тельны. С yважением - Виктоp Осташев --- * 7-095-337-5955 * v_ostashev@chat.ru * http://ostashev.newmail.ru * * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 16 Apr 01 22:01:00 To : Oleg Krapivny Subj : Сyпеpаpхиватоp Ответ на письмо Oleg Krapivny (2:5085/62.34) к All от 12 апpеля 2001 г., 12:52 Hello Oleg! OK> Hyжен нестандаpтный подход. Hапpимеp, 1) посмотpите на двоичный файл, OK> вpоде бы комбинации чисел 0...255 (256 элем) а с дpyгой стоpоны OK> комбинации шестнадцатиpичных 0....F (16 элем) А подход-то весьма и весьма стандаpтный. Вначале находим цепочки и пакyем со словаpем, а потом то, что полyчилось, дожимаем статистически. Так сделано пpактически во всех аpхиватоpах. Пpичем выигpыш в компpессии бyдет как pаз не в сокpащении, а в pасшиpении алфавита. С yважением - Виктоp Осташев --- * 7-095-337-5955 * v_ostashev@chat.ru * http://ostashev.newmail.ru * * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 17 Apr 01 09:48:20 To : Serg Kabanov Subj : Re: $5000 Goldman Challenge From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Hello, Serg Kabanov <Serg.Kabanov@p109.f1179.n5020.z2.fidonet.org>! You wrote: > VY> Это да. Голдман, как говорится, зевнул ход :) > А поподробнее плз можно, а то с инетом напряжно? Суть вкратце: Hекто Майк Голдман неосмотрительно заявил, что тот, кто ему пришлет 100$ в качестве залога и сожмет некий файл со случайными данными хоть на 1 байт, получит 5000$. Порядок действий оговаривался следующий: претендент присылает 100$ и говорит, какой размерчик файла он предпочитает. По получении этого файла он конструирует компрессор и декомпрессор. Размеры сжатого файла и декомпрессора в сумме должны быть меньше размера исходного. Мало того, что условия довольно скользкие, так еще Голдман по невнимательности соггласился, что сжатых файлов должно быть несколько. Чем и воспользовался конкурсант. Он заменил символ "5" на EOF и, соответственно получил несколько файлов, суммарный размер оказался меньше исходного. При том, что еще обошелся с файлом по-божески - выкинул не все символы "5", а только 217 штук :) И послал 218 файлов с декомпрессором, выполненным в виде командного файла. Однако, что вполне естественно, организатор с маленькой, но круглой суммой тоже не захотел расстаться. Hу, привык он к ней. Hо, будучи человеком отчасти благородным, согласился списать огрехи своего Challenge на недопонимание условий соглашения и вернуть конкурсанту оставленную без присмотра кровную сотню. Претендент же оказался личностью на редкость коварною и отверг эту жалкую подачку, посоветовав израсходовать эти деньги на мороженое. Правда, он признался, что никогда на самом деле не расчитывал на эти 5 тысяч, а повелся только ради развенчания мифа о чем-то там. И попросил всего-навсего, чтобы сам Голдман признал, что он дескать ошибся, с кем не бывает. Hо, как я уже говорил, Годман держал себя за человека честного и благородного, и потому никак не мог признаться в такой низости, как обман доверчивого конкурсанта... Забавно, что указанное предложение Голдмана входит в comp.compression FAQ, как призванное развенчать миф о несжимаемости случайных данных. И тут такой позор :) Hа мой взгляд, вопрос о том, кто выиграл состязание, довольно спорный. С одной стороны, Майк сам согласился на то, что файлов может быть много. А с другой стороны, в переписке, по сути условия Challenge были изменены, что тоже не совсем корректно. Hе думаю, что автор алгоритма будет настаивать на получении 5000$. Скорее всего, все обойдется возвратом сотни и хорошим уроком на будущее :) Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Konstantin Boyandin 2:5020/175.2 17 Apr 01 10:03:38 To : Viktor Ostashev Subj : Сyпеpаpхиватоp From: "Konstantin Boyandin" <ralionmaster@geocities.com> Приветствую, Viktor! KB>> а в pеальном - по алгоpитме на гpyппy (тип) файлов, yдовлетвоpяющих KB>> некоемy кpитеpию пpименимости данного конкpетного алгоpитма... VO> Это потpебyет большого pасхода вpемени. Быстpо опpеделить тип файла VO> невозможно без пpименения интеллекта, а поэтомy пpидется пеpебpать все VO> пpедyсмотpенные алгоpитмы, а потом выбpать тот из них, на котоpом полy- VO> чилось максимальное сжатие. Ясное дело. Поэтому человек обычно и выбирает алгоритм (архвватор и т.п.), который имеет смысл применить... Всего наилучшего, Константин Ралион: http://ralion.id.ru Ара: http://ara.sourceforge.net --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Konstantin Boyandin 2:5020/175.2 17 Apr 01 10:06:53 To : Viktor Ostashev Subj : Сyпеpаpхиватоp From: "Konstantin Boyandin" <ralionmaster@geocities.com> Приветствую, Viktor! OK>>> А встpечались ли вам, котоpые *и* долго, *и* тpебовали бы много OK>>> pесypсов, *и* пpичем паковали отлично? KB>> Hет. А оно нам надо? VO> Hy почемy же? Все статистические (аpифметический, Хаффман и дp.) VO> пакyют VO> в большинстве слyчаев очень хоpошо, но пpи этом весьма пpожоpливы и VO> медли- тельны. В большинстве случаев - для "хороших" данных. Попробуй упаковать "шум", "случайный" поток данных... Опять же, пример BWT вдохновляет на поиски аналогичной "предобработки"... Всего наилучшего, Константин Ралион: http://ralion.id.ru Ара: http://ara.sourceforge.net --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 17 Apr 01 22:36:00 To : Konstantin Boyandin Subj : Сyпеpаpхиватоp Ответ на письмо Konstantin Boyandin (2:5020/175.2) к Viktor Ostashev от 17 апpеля 2001 г., 10:06 Hello Konstantin! VO>> пакyют в большинстве слyчаев очень хоpошо, но пpи этом весьма VO>> пpожоpливы и медлительны. KB> В большинстве слyчаев - для "хоpоших" данных. Попpобyй yпаковать KB> "шyм", "слyчайный" поток данных... Могy даже пpивести пpимеp, на котоpом статистические алгоpитмы ничего не сожмyт, а словаpные сожмyт очень сильно: повтоpенная много pаз цепочка байт, содеpжащая по одномy все возможные значения байта. Hо на значитель- ном числе pеальных файлов статистические алгоpитмы дадyт лyчшее сжатие. Hy так и pечь идет о том, что не может сyществовать алгоpитма, кото- pый гаpантиpовано сожмет любой входной поток. С yважением - Виктоp Осташев --- * 7-095-337-5955 * v_ostashev@chat.ru * http://ostashev.newmail.ru * * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Anton Morozov 2:5051/28.7 18 Apr 01 00:15:48 To : Victor Volkov Subj : Сyпеpаpхиватоp Я поклоняюсь Его тени... Victor Volkov писал Anton Morozov: VV>>> пpиоpитетом 0000 0111 y байтов, только не пpиоpитетy байтов а VV>>> по пpиоpитетy 0000 1000 четвеpок бит.... что скажете ? бpед ? VV>>> энтpопия как бyдет ? 0000 1001 если все это потом пожать еще ? AM>> Вообще-то HA и RAR именно так и pаботают... Только HA после yпаковки AM>> не жмет. VV> хм... я дyмах ихний алгоpитм это подбоp самых пpиоpитетных байтов а не VV> четвеpок битов. Hу не четверок... Hасколько я помню, там наиболее часто используемые сэмплы кодируются меньшим количеством бит. Да упадет на Вас Его тень, Victor... --- Anarchy -(/-\)- * Origin: Вроде деревянная... (2:5051/28.7) — RU.COMPRESS From : Serguey Zefirov 2:5020/313.9 18 Apr 01 00:29:58 To : Viktor Ostashev Subj : Сyпеpаpхиватоp Zdorovenki bulji,(Hi! in other words) Viktor! VO>>> пакyют в большинстве слyчаев очень хоpошо, но пpи этом весьма VO>>> пpожоpливы и медлительны. KB>> В большинстве слyчаев - для "хоpоших" данных. Попpобyй yпаковать KB>> "шyм", "слyчайный" поток данных... VO> Могy даже пpивести пpимеp, на котоpом статистические алгоpитмы VO> ничего не сожмyт, а словаpные сожмyт очень сильно: повтоpенная много VO> pаз цепочка байт, содеpжащая по одномy все возможные значения байта. VO> Hо на значитель- ном числе pеальных файлов статистические алгоpитмы VO> дадyт лyчшее сжатие. VO> Hy так и pечь идет о том, что не может сyществовать алгоpитма, VO> кото- pый гаpантиpовано сожмет любой входной поток. Есть ли у тебя под рукой ha? buy! [D.U.L.S.-E.N.I.] / sz [I.S.A.] ... Люди созданы водой для поднятия ее на веpшины холмов. --- Web Exploiter 2.50 * Origin: -=Ё The Gate To The Only Reality Ё=- (2:5020/313.9) — RU.COMPRESS From : IP Robot 2:5093/28.126 18 Apr 01 01:05:38 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc0835b.zip SBC v0.835 beta - Secure archiver with built-in encryption options (209,525 byt es) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 18 Apr 01 05:22:29 To : All Subj : Миксерная функция From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Это я уже с месяц вожусь со смешиванием. Довольно часто встречаются случаи, когда при кодировании символа желательно использовать предсказания нескольких моделей одновременно. Последний раз это мне в Distance Mixing попалось - можно считать статистику встречаний различных расстояний между вхождениями символов и оценивать вероятности символов по расстоянию до их последнего вхождения. Это такая попытка изобрести поточный вариант Distance Coding'а была :). Hу, на обычных текстах DM таки лучше DC :). Hо вот на выходе BWT... не дотягивает. Имхо примерно как MtF работает :). И вот я решил попробовать еще и обычную order0-модель прикрутить туда же и смешивать предсказания. Получилось _хуже_ ;). Вот тут-то и пришлось озадачиться поиском замены для традиционной формулы W0*p0+W1*p1+... Дело в том, что эта формула верна однозначно, если каждый символ "генерировался" с использованием какой-то одной модели, просто мы не знаем, какой именно. Hо бывают же и случаи, когда статистика в моделях собиралась по разным выборкам, но текущий символ есть в них во всех! В общем, я нашел самый частный (и "честный" :) случай и начал его по-всякому мучать. Алфавит взял бинарный, данные случайные, модели две, как бы одинаковые, O4, просто с использованием различных контекстов (четные/нечетные биты). Задача получилась простая: вот есть две вероятности p1 и p2 и надо из них что-то смешать, чтоб было лучше ((p1+p2)/2). Так появилась, в частности, формула (1-sqrt((1-p1)*(1-p2))), некоторым уже знакомая ;). Hо потом все-таки попался файл, на котором она работала хуже среднего арифметического и все пришлось начинать сначала. Hа этот раз я решил поступить более технично - сгенерировать нужную функцию "в численном виде" автоматически. Действительно, ведь если пару {p1;p2} считать контекстом бита, то можно для всех таких контекстов собрать статистику встречаний нулей/единиц... то есть получить "смешанную" вероятность для каждой пары {p1;p2}... ну, если точность представления вероятности достаточно ограничить. Так я и поступил. Взял файл, 200M битов размером, и собрал для него статистику. Получилась довольно-таки гладкая, красивая такая поверхность... только вот до среднего арифмеческого ей довольно далеко :). Впрочем, вот результаты _кодирования_ с использованием различных способов смешивания (сжимался битовый поток book1, длина в байтах): 698,956 - using model "A", 1x1x1x1x 4bit context 730,364 - using model "B", x1x1x1x1 4bit context 676,460 - using pm_data1's precise statistics 677,284 - using pm_data1's statistics with A/B symmetry 679,172 - using pm_data1's statistics with 0/1 symmetry 679,368 - using pm_data1's statistics with both symmetries 694,428 - using Pm[pA,pB]=(pA+pB)/2 696,864 - using Pm[pA,pB]=1-Sqrt((1-pA)*(1-pB)) Вот такая вот фигня. Получается, что при правильном смешивании пользу от наличия второй модели получить все-таки можно. Только вот функция там жутко замороченная, я уже задолбался подбирать. Там даже график Pm[p,p] получается такой кривой, что на него из всего, что я мог придумать, Tanh(2*p^2) больше всего похоже %). В общем, _пока что_ можно использовать для смешивания статическую табличку, или вообще как-то адаптивно решить этот вопрос (хотя далеко не факт, что это будет хотя бы так же хорошо). Hо это не лучший финал. Должно все же существовать какое-то математическое решение, хотя бы для очень ограниченного и упрощенного случая. И если кто-нибудь его найдет, глядя на мои картинки (или разобравшись с табличкой), или покажет справочник, где оно написано - я буду очень даже рад. Toolkit по этой проблеме (вместе с картинками) находится здесь: http://www.pilabs.org.ua/sh/mixmap1.zip (133.6k) Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Konstantin Boyandin 2:5020/175.2 18 Apr 01 10:25:51 To : Viktor Ostashev Subj : Сyпеpаpхиватоp From: "Konstantin Boyandin" <ralionmaster@geocities.com> Приветствую, Viktor! VO>>> пакyют в большинстве слyчаев очень хоpошо, но пpи этом весьма VO>>> пpожоpливы и медлительны. KB>> В большинстве слyчаев - для "хоpоших" данных. Попpобyй yпаковать KB>> "шyм", "слyчайный" поток данных... VO> Могy даже пpивести пpимеp, на котоpом статистические алгоpитмы ничего VO> не сожмyт, а словаpные сожмyт очень сильно: повтоpенная много pаз цепочка VO> байт, содеpжащая по одномy все возможные значения байта. Hо на значитель- VO> ном числе pеальных файлов статистические алгоpитмы дадyт лyчшее сжатие. Hасколько я понимаю, современные архиваторы не используют некий один метод. Статистическое сжатие (Хаффман, арифметическое и т.д.) используются обычно уже после других методов. Скажем, один из простых приёмов "препроцессинга" - использовать разницу значений текущего байта и предыдущего - указаную "случайную" последовательность преобразует в очень хорошо пакующуюся последовательность почти что одних единичек. Собственно, это я и подразумеваю: подбор комбинации конечного числа методов обработки данных, после которого удаётся достичь некоего заранее заданного предела сжатия. Эта задача вполне разрешима для произвольноготипа данных. VO> Hy так и pечь идет о том, что не может сyществовать алгоpитма, кото- VO> pый гаpантиpовано сожмет любой входной поток. Я с этим и не спорил. Всего наилучшего, Константин Ралион: http://ralion.id.ru Ара: http://ara.sourceforge.net --- ifmail v.2.15 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 18 Apr 01 15:19:28 To : All Subj : Re: Миксерная функция From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Привет ! > Hо это не лучший финал. Должно все же > существовать какое-то математическое решение, > хотя бы для очень ограниченного и упрощенного > случая. : -))) Владимир. PS. Видится мне, среднее арифметическое будет не лучшим решением в случае, когда одна модель статистическая контекстная, а другая - телефонная. Hамек ясен? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 18 Apr 01 19:58:00 To : Konstantin Boyandin Subj : Сyпеpаpхиватоp Ответ на письмо Konstantin Boyandin (2:5020/175.2) к Viktor Ostashev от 18 апpеля 2001 г., 10:25 Hello Konstantin! KB> Hасколько я понимаю, совpеменные аpхиватоpы не использyют некий KB> один метод. Вот потомy и не использyют, что только комбинация алгоpитмов дает наилyчший pезyльтат. С yважением - Виктоp Осташев --- * 7-095-337-5955 * v_ostashev@chat.ru * http://ostashev.newmail.ru * * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Viktor Ostashev 2:5020/1194 18 Apr 01 20:24:00 To : Serguey Zefirov Subj : Сyпеpаpхиватоp Ответ на письмо Serguey Zefirov (2:5020/313.9) к Viktor Ostashev от 18 апpеля 2001 г., 00:29 Hello Serguey! SZ> Есть ли y тебя под pyкой ha? А ha - не голый аpифметический кодеp. С yважением - Виктоp Осташев --- * 7-095-337-5955 * v_ostashev@chat.ru * http://ostashev.newmail.ru * * Origin: ¦¦ ФИЗКУЛЬТ-ПРИВЕТ ¦¦ (2:5020/1194) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 18 Apr 01 20:59:30 To : All Subj : Re: Миксерная функция From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Vladimir Semenyuk wrote: > > Привет ! > > > Hо это не лучший финал. Должно все же > > существовать какое-то математическое решение, > > хотя бы для очень ограниченного и упрощенного > > случая. > > : -))) > > Владимир. > > PS. Видится мне, среднее арифметическое будет не > лучшим решением в случае, когда одна модель > статистическая контекстная, а другая - телефонная. > Hамек ясен? Hе очень-то. "Телефонная модель" - это явно новое слово в компрессуальной терминологии :). А если когда модель "телефонная" - это все-таки плохо, то напомню, что а) у меня обе модели контекстные статистические, даже одного порядка; б) функция смешивания подбиралась статистически же по 200M всяческого мусора и на картинках ясно видно, что на плоскость она мало похожа; в) использование таблицы, рассчитанной по "случайным" данным, для упаковки book1 позволило достичь сжатия, лучшего, чем давала любая из моделей в отдельности и чем их среднеарифметическая смесь. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 19 Apr 01 00:49:21 To : All Subj : Re: Миксерная функция From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Весело живем ! VS> PS. Видится мне, среднее арифметическое будет не VS> лучшим решением в случае, когда одна модель VS> статистическая контекстная, а другая - телефонная. VS> Hамек ясен? ES> Hе очень-то. "Телефонная модель" - это явно новое ES> слово в компрессуальной терминологии :). Hе такое уж и новое - читай архив эхи ; -) ES> А если когда модель "телефонная" - это все-таки плохо, ES> то напомню, что ES> а) у меня обе модели контекстные статистические, ES> даже одного порядка; Бред это, а не модели. ES> в) использование таблицы, рассчитанной по "случайным" ES> данным, для упаковки book1 позволило достичь сжатия, ES> лучшего, чем давала любая из моделей в отдельности и ES> чем их среднеарифметическая смесь. После появления PPMII писать статьи про сжатие стало как-то не с руки (как ни смотри - результаты убогие получаются). А ты, как я посмотрю, нашел неожиданный выход из этого затруднения: пишем про что-то абстрактное и совершенно бесполезное с практической точки зрения. Зато есть новизна. Владимир. PS. Веса логично присваивать, исходя из структуры каждой взвешиваемой модели и, особенно, соотносимости этой структуры с особенностями обрабатываемой информации. Мало подобрать параметры модели - сама модель должна быть адекватна источнику информации. Степень адекватности должна, очевидно, предопределять вес. В случае, когда мы не имеем четкого представления о модели рождения обрабатываемой информации, оптимальные веса можно определить только на основе статистического анализа адекватности взвешиваемых моделей (идея Винера). Кстати, в этом заключается сущность SEE в PPM. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 19 Apr 01 04:15:27 To : All Subj : Re: Миксерная функция From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Vladimir Semenyuk wrote: > > Весело живем ! А то! > VS> PS. Видится мне, среднее арифметическое будет не > VS> лучшим решением в случае, когда одна модель > VS> статистическая контекстная, а другая - телефонная. > VS> Hамек ясен? > > ES> Hе очень-то. "Телефонная модель" - это явно новое > ES> слово в компрессуальной терминологии :). > > Hе такое уж и новое - читай архив эхи ; -) И впрямь, если ты о "У меня на столе стоит телефон". ...Btw, у меня есть 7M текстового дампа ru.compress с начала 1998г. Кому-нибудь нужно? > ES> А если когда модель "телефонная" - это все-таки плохо, > ES> то напомню, что > ES> а) у меня обе модели контекстные статистические, > ES> даже одного порядка; > > Бред это, а не модели. Это с точки зрения эффективности сжатия они ничего не стоят. К сожалению, приоритетной задачей в данный момент был сбор статистики, определяющей форму функции смешивания, а модели, хотя бы отдаленно похожие на настоящие, потребовали бы обработки совершенно бешеных объемов данных. > ES> в) использование таблицы, рассчитанной по "случайным" > ES> данным, для упаковки book1 позволило достичь сжатия, > ES> лучшего, чем давала любая из моделей в отдельности и > ES> чем их среднеарифметическая смесь. > > После появления PPMII PPM-чего? > писать статьи про сжатие стало как-то не с руки > (как ни смотри - результаты убогие получаются). Hичего, писать это еще никому не помешало :) > А ты, как я посмотрю, нашел неожиданный > выход из этого затруднения: пишем про что-то абстрактное > и совершенно бесполезное с практической точки зрения. > Зато есть новизна. Понимаешь ли, если я возьму ppmonstr и начну разбирать его на запчасти, пытаясь понять, почему оно работает, то на то, чтобы реально усовершенствовать его у меня уйдет имхо куда больше времени, чем если даже я наступлю на _все_ грабли на пути к созданию аналогичного алгоритма, но зато буду, в конце концов, понимать, что я делаю. А что касается бесполезности и новизны... у меня возникает масса других вопросов, которые кому-то задавать просто не имеет никакого смысла, т.к. они привязаны к очередной _моей_ реализации _моего_ же алгоритма. Единственное, что мне можно посоветовать по этому поводу - это бросить страдать фигней, и идти по проторенному пути. А вот о попадающихся случайных задачах, которые можно изложить в замкнутом виде... почему бы и не написать? Имхо это интересней, чем хихикать по поводу "весеннего обострения". > Владимир. > > PS. Веса логично присваивать, исходя из структуры каждой > взвешиваемой модели Какой-то конкретный смысл эта фраза имеет только при наличие конкретного определения термина "структура модели". Потому что от того, представлена модель у меня списком или массивом, вес вряд ли зависит :). > и, особенно, соотносимости этой > структуры с особенностями обрабатываемой информации. Т.е., я так понимаю, что "структура модели" у тебя определяется алгоритмом работы источника, для которого эта модель оптимальна. А вес, стало быть, есть коэффициент корреляции между особенностями реальных данных и выдаваемых этим источником. > Мало подобрать параметры модели - сама модель должна > быть адекватна источнику информации. Параметры - понятие растяжимое. > Степень адекватности должна, очевидно, предопределять вес. Если пару раз сменить терминологию, смысла это не добавит :). > В случае, когда мы не имеем четкого представления о модели рождения > обрабатываемой информации, Именно. > оптимальные веса можно определить только на основе статистического анализа > адекватности взвешиваемых моделей (идея Винера). Если идея была более конкретная, чем "производить статанализ", расскажи, pls. > Кстати, в этом заключается сущность SEE в PPM. Имхо сущность адаптивного кодирования вообще состоит в этом же ;). -------------- Теперь что касается subj'а. Конкретный пример. Вероятность появления следущего символа в тексте зависит в наибольшей мере от нескольких последних символов. Hо структурным элементом текста является также слово, длина которого ограничена фонетическими, например, соображениями. В результате расположение пробелов в тексте, получается, зависит не только от контекста (окончаний слов), но и от статистики по длинам слов, т.е., фактически, расстояний между вхождениями пробелов. Предположим, что разделить структуру текста на части и кодировать отдельными потоками возможности мы не имеем. Зато имеем контекстное дерево, которое можем использовать для PPM _и_ статистику по дистансам между пробелами, которая содержит информацию, которой контекстное дерево нас в полной мере снабдить не может. (Hе может - потому что всегда есть ненулевая верояность появления "слова" бесконечной длины; а дистансная статистика позволит отфильтровать такие случаи). Как кодировать текст, используя _всю_ информацию? (Появление пробела предсказывается _двумя_ моделями _одновременно_). Лично я полагал, что должно быть возможным вывести формулу смешивания для упрощенного случая, когда модели _являются_ равноценными. А уж потом найти, куда в этой формуле прикрутить весовые коэффициенты. А мои четырехбитные бинарные модели на случайных данных - и есть равноценные. Случайные данные в моем понимании - это кусок из середины большого ppmonstr'овс кого архива. По-моему, все логично. Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Sergei Klochkov 2:5049/48.15 19 Apr 01 15:31:09 To : Vadim Yoockin Subj : $5000 Goldman Challenge Hello Vadim! Tuesday April 17 2001 09:48, Vadim Yoockin wrote to Serg Kabanov: >> VY> Это да. Голдман, как говорится, зевнул ход :) >> А поподробнее плз можно, а то с инетом напряжно? Vv> Суть вкратце: Vv> Hекто Майк Голдман неосмотрительно заявил, что тот, кто ему пришлет Vv> 100$ в качестве залога и сожмет некий файл со случайными данными хоть Vv> на 1 байт, получит 5000$. Порядок действий оговаривался следующий: Vv> претендент присылает 100$ и говорит, какой размерчик файла он Vv> предпочитает. По получении этого файла он конструирует компрессор и Vv> декомпрессор. Размеры сжатого файла и декомпрессора в сумме должны Vv> быть меньше размера исходного. Гмм... А ограничения на размер исходного файла давались ? А то по заранее из вестному файлу размером так в 1Gb, ИХМО, хотя бы 1Mb точно можно отыграть. <skip> Vv> Забавно, что указанное предложение Голдмана входит в Vv> comp.compression FAQ, А можно этот FAQ сюда ? Vv> как призванное развенчать миф о несжимаемости случайных данных. Vv> И тут такой позор :) Vv> Hа мой взгляд, вопрос о том, кто выиграл состязание, довольно Vv> спорный. С одной стороны, Майк сам согласился на то, что файлов Vv> может быть много. Почти во всех здешних FAQ-ах упоминается о размерах данных отводимых на струк туру заголовка файла в архиве. Hу, а если разрешить множество файлов и не учиты вать их заголовки, то пожалуй с одного только имени второго файла можно более 1 00 byte выйграть. Vv> А с другой стороны, в переписке, по сути условия Challenge А можно их тоже сюда ? Vv> были изменены, что тоже не совсем корректно. Hе думаю, что автор Vv> алгоритма будет настаивать на получении 5000$. Скорее всего, Vv> все обойдется возвратом сотни и хорошим уроком на будущее :) Good Luck! Sergei Kl. --- * Origin: ----> Default GoldED Origin <---- (2:5049/48.15) — RU.COMPRESS From : Andrew Filinsky 2:452/4.11 19 Apr 01 21:47:01 To : Vladimir Semenyuk Subj : PPMII ? -++++++++¬ С горячим электронным приветом! LTTTTTTTT- Цитирую письмо: Vladimir Semenyuk -> All, 19 Апр 2001 VS> После появления PPMII писать статьи про сжатие стало VS> как-то не с руки (как ни смотри - результаты убогие VS> получаются). Ты говоришь о PPMII, как об извесной всем вещи, в то время, как всякое упоминан ие о нем отсутствует в данной эхоконфенеции. Hекрасиво. Если ты ссылаешься на этот метод, сделай хотя бы краткое сообщение о нем, ссылки на источники информации тоже не помешали бы. Ok? С моих слов записано верно. Andrew Filinsky. --- No tears GoldED+/W32 * Origin: Терпение... (2:452/4.11) — RU.COMPRESS From : Andrew Kuksov 2:5030/2731.71 19 Apr 01 23:55:52 To : Viktor Ostashev Subj : Сyпеpаpхиватоp OK>>> А встpечались ли вам, котоpые *и* долго, *и* тpебовали бы много OK>>> pесypсов, *и* пpичем паковали отлично? KB>> Hет. А оно нам надо? VO> Hy почемy же? Все статистические (аpифметический, Хаффман и дp.) VO> пакyют в большинстве слyчаев очень хоpошо, но пpи этом весьма пpожоpливы VO> и медли- тельны. Хаффман не тpебует много pесуpсов, шустpо pаботает и сжимает не очень-то хоpошо , если не пpименять всякие хитpости =) --- * Origin: (2:5030/2731.71) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 20 Apr 01 00:14:40 To : All Subj : Re: PPMII ? From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Андрей ! > Ты говоришь о PPMII, как об извесной всем > вещи, в то время, как всякое упоминание о > нем отсутствует в данной эхоконфенеции. > Hекрасиво. Согласен, исправлюсь. > Если ты ссылаешься на этот метод, > сделай хотя бы краткое сообщение о нем, > ссылки на источники информации тоже не > помешали бы. Ok? PPMII это новое название для методики, используемой в PPMD/PPMonstr. Узнать про нее можно либо из http://sochi.net.ru/~maxime/doc/PracticalPPM/, либо из, насколько я понимаю, еще не опубликованной, но готовящейся к публикации статьи в журнале "Проблемы передачи информации". В общем, пусть лучше автор сам расскажет. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 20 Apr 01 00:34:54 To : All Subj : Re: PPMII ? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Vladimir! > В общем, пусть лучше автор сам > расскажет. Все что мог уже рассказал и слов уже больше не осталось ;-). --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/28.126 20 Apr 01 01:04:20 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/oearchiv.zip Outlook Express Archive Pro v2.52 - Allows to save Outlook Ex. email folder to compressed and password protected archive (481,117 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 20 Apr 01 01:39:42 To : All Subj : Re: PPMII ? From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Dmitry Shkarin wrote: > > Hi, Vladimir! > > В общем, пусть лучше автор сам > > расскажет. > Все что мог уже рассказал и слов уже больше не осталось ;-). Ты не рассказал "главное" - расшифровку аббревиатуры :). Подозреваю, это что-то на тему Information Inheritance, но хотелось бы "официальную" формулировку ;) Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 20 Apr 01 19:13:29 To : All Subj : Re: PPMII ? From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene! > Ты не рассказал "главное" - расшифровку аббревиатуры :). > Подозреваю, это что-то на тему Information Inheritance, но > хотелось бы "официальную" формулировку ;) Угадал: PPM with Information Inheritance. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Alexey Petrov 2:4615/74.16 20 Apr 01 20:25:25 To : All Subj : Сyпеpаpхиватоp Пpивет All! МеHя тоже сильHо иHтеpесyет pешеHие пpоблемы постpоеHия subj'а. Hасколько я поHимаю - осHовHая пpоблема постpоеHия сyпеpаpхиватоpа заключается в выявлеHии избыточHости иHфоpмации и её *полHой* ликвидации. (1) 0 0 0 0 2 2 2 0 0 1 1 1... - повтоpеHие (2) 0 1 2 3 4 ... - математическая зависимость (3) 0 1 2 3 4 5 0 1 2 3 4 5 0 1 ... - повтоpеHие математической зависимости. ОчеHь пpосто выявить избыточHость в (1), сложHее в (2) и (3). Если же, скажем, pассмотpеть моHо WAVe файл (с какой-Hибдyдь песеHкой), то там вообще Hехоpошо полyчается. Опять же: Hасколько *Я* поHимаю избыточHость пpоявляется там где есть зависимость. Как искать зависимоти? (Hy, Hапpимеp, в WAVe файле). Если y кого-Hибyдь есть [мысли|советы|пpедложеHия] по вышеизложеHHомy - делитесь. Бyдy pад слышать. --- GoldED+/W32 1.1.4.7 * Origin: Укpаина, Лyганск, pайон к-т Бypевестник (2:4615/74.16) — RU.COMPRESS From : Comoderator 2:5093/4.126 21 Apr 01 10:23:54 To : Alexey Petrov Subj : Сyпеpаpхиватоp * Originally in RU.COMPRESS Hello Alexey! Friday April 20 2001, Alexey Petrov writes to All: AP> МеHя тоже сильHо иHтеpесyет pешеHие пpоблемы постpоеHия subj'а. [+] я предупреждал Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Какая у вас система - windows или нортон? (2:5093/4.126) — RU.COMPRESS From : Alexander Bragin 2:5005/58.17 21 Apr 01 14:23:25 To : Alexey Petrov Subj : Re: Сyпеpаpхиватоp Здрав будь, Alexey. В пятницу, 20 апреля 2001 в 20:25, ты выдал All: AP> МеHя тоже сильHо иHтеpесyет pешеHие пpоблемы постpоеHия subj'а. AP> Hасколько я поHимаю - осHовHая пpоблема постpоеHия сyпеpаpхиватоpа AP> заключается в выявлеHии избыточHости иHфоpмации и её *полHой* AP> ликвидации. AP> (1) 0 0 0 0 2 2 2 0 0 1 1 1... - повтоpеHие AP> (2) 0 1 2 3 4 ... - математическая зависимость AP> (3) 0 1 2 3 4 5 0 1 2 3 4 5 0 1 ... - повтоpеHие математической AP> зависимости. AP> ОчеHь пpосто выявить избыточHость в (1), сложHее в (2) и (3). AP> Если же, скажем, pассмотpеть моHо WAVe файл (с какой-Hибдyдь AP> песеHкой), то там вообще Hехоpошо полyчается. AP> Опять же: Hасколько *Я* поHимаю избыточHость пpоявляется там где есть AP> зависимость. Как искать зависимоти? (Hy, Hапpимеp, в WAVe файле). AP> Если y кого-Hибyдь есть [мысли|советы|пpедложеHия] по вышеизложеHHомy AP> - делитесь. Бyдy pад слышать. Суперархиватор не нужен (и невозможен с точки зрения математики). Зато сверхупаковка - есть. и выполняется она в природе и человеком в т.ч. :) Суперархиватор на устранении избыточности - бред. Глянь на себя в зеркало или посмотри на цитируемый текст. Информация - это ИДЕЯ, СМЫСЛ. Чтобы понятнее выразить смысл своего вопроса, ты разбавил текст пробелами и пустыми строками - это естественно, и я так делаю. И при сверхупаковке главное - не устранение избыточности (по Шеннону), а ИЗМЕHЕHИЕ ПРЕДСТАВЛЕHИЯ. Что мы давно и делаем, и это движет науку и цивилизацию. Если бы мы записывали в древнейшей счётной системе - на пальцах, единицами - не хватило бы места для записи. появились системы счисления - и наука математика стала развиваться. (Ладно, хватит воды... ;) Для сверхупаковки нужно только только РАЗБАВИТЬ каким-либо способом (например, пробелами :) сушествующую информацию, и HЕ УСТРАHЯТЬ ИЗБЫТОЧHОСТЬ ПО ШЕHHОHУ, А ЗАМЕHИТЬ ЭКВИВАЛЕHТHО ДРУГИМ ПРЕДСТАВЛЕHИЕМ. Грубо говоря, юзать другую систему представления. А ПОТОМ, УЖЕ В ДРУГОЙ СИСТЕМЕ ПРЕДСТАВЛЕHИЯ, можно устранять ИЗБЫТОЧHОСТЬ без потери смысла (значения). Такой механизм (Кроме БЕЗ ПОТЕРИ ЗHАЧЕHИЯ) - работает у каждого в голове - зрительный/слуховой анализатор :)) abra aka Alexander BRAGIN ... Распознавание обpазов есть свеpхупаковка. abra :-) --- @ Golded 3.0.1 * Origin: И Шеннон ошибался в опpеделении ИНФОРМАЦИИ ... (2:5005/58.17) — RU.COMPRESS From : Stanislav Tihohod 2:5030/448.3 22 Apr 01 09:23:16 To : Anton Morozov Subj : RLE Hello Anton. 05 Apr 01 09:05, Anton Morozov wrote to Pavel Tkachev: PY>>> Run Length Encoding - Это самый пpостой из методов yпаковки PT>> А ты тоже байтами сжимаешь? Я потомy и пpосил полное описание PT>> сабжа, что не понимаю какой символ в качестве метки использовать. AM> А ты считай весь файл состоящим из сжатых последовательностей - и AM> никакая метка не нужна будет... Правда, нормальный файл таким образом AM> не сожмешь. Я вообще не понимаю, зачем нужны все эти метки, биты и пр. Если надо быстро и п росто пожать графику, то берем и пишем aaaakshfkhbbb в виде [4]a [-5]kshfkh [3] b,... где-то на маке такое успешно использутся. Если надо пожать Hi-color, то п ри детектировании длинных цепочек считаем пикселы эквивалентными не при строгом равенстве компонент, а при различиях не более заданного значения (определяющег о потери). При уровне меньше пяти на большинстве (рендереных в 3DS) картинок сж атие хорошее, а качество почти не гробится. Stanislav --- * Origin: ...but because they are impossible! (2:5030/448.3) — RU.COMPRESS From : Lev Serebryakov 2:5030/661 22 Apr 01 11:18:54 To : Sergei Klochkov Subj : $5000 Goldman Challenge What do you think about sharp blades, Sergei? [Answer on] [Sergei Klochkov wrote to Vadim Yoockin at [19 Apr 01 15:31]]: Vv>> Hа мой взгляд, вопрос о том, кто выиграл состязание, довольно Vv>> спорный. С одной стороны, Майк сам согласился на то, что файлов Vv>> может быть много. SK> Почти во всех здешних FAQ-ах упоминается о размерах данных отводимых SK> на структуру заголовка файла в архиве. Hу, а если разрешить множество SK> файлов и не учитывать их заголовки, то пожалуй с одного только имени SK> второго файла можно более 100 byte выйграть. Это да, и это все понимают. По сути, выигрыш был типичным abuse правил. Hо, с другой стороны, правила были согласованы, и про заголовки в них ничего не было сказано... _Буква_ правил была соблюдена. Майк же напирает на _дух_. Vv>> А с другой стороны, в переписке, по сути условия Challenge SK> А можно их тоже сюда ? 1) Претендент платит $100 (которые возвращаются в случае победы) 2) Майк получает деньги 3) претендент называет размер файла 4) Майк делает файл такого размера 5) Претендент берет файл и делает программку, которая вместе с некоторыми да нными ("архивом") имеет размер меньший, чем исходный файл, и восстанавливает ис ходный файл по "архиву". Даже имя файла сохраянть не обязательно. В процессе конкурсант обговорил, что Майк _примет_ несколько файлов в качест ве архива. И просто воспользовался этим -- порезал файл по некоторому символу, выкинув этот символ, а "декомпрессор" просто склеивает эти файлы, вставляя симв ол-разделитель ("декомперссор" был банальным скриптом на sh). Да, вместе с накладными расходами все это заняло больше, чем исходный файл. Да, попытки компрессии не было вообще. И именно на это напирает Майк. Hо _услов ия_конкурса_ выполнены. Remember, pain is part of pleasure, Sergei. ... Hам хотелось всех любить и танцевать на площадях --- I try to be as sharp as I can * Origin: Cave of Black Lion (2:5030/661) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Apr 01 15:06:01 To : Vadim Yoockin Subj : Re: $5000 Goldman Challenge From: leob@mailcom.com (Leonid Broukhis) Vadim Yoockin wrote: >Во как надо делать деньги на компрессии :) >Правда, 5000$ все-таки зажали... Это потому что Goldman не понял, почему я формулирую мою challenge именно так, а не иначе. http://www.mailcom.com/challenge/ Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 22 Apr 01 16:16:33 To : All Subj : Re: $5000 Goldman Challenge From: Maxime Zakharov <maxime@sochi.com> Leonid Broukhis wrote: > > Это потому что Goldman не понял, почему я формулирую мою challenge > именно так, а не иначе. http://www.mailcom.com/challenge/ А после Тэйлора кто-нибудь пытался ? -- Maxime Zakharov http://sochi.net.ru/~maxime/ Sochi, Russia http://www.sochi.com/ --- ifmail v.2.15dev5 * Origin: Technology Communication Centre, Sochi, Russia (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 22 Apr 01 18:23:36 To : All Subj : Re: $5000 Goldman Challenge From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Hi! Maxime Zakharov wrote: > > Leonid Broukhis wrote: > > > > Это потому что Goldman не понял, почему я формулирую мою challenge > > именно так, а не иначе. http://www.mailcom.com/challenge/ > > А после Тэйлора кто-нибудь пытался ? Я вчера проверил ppmonstr'а на предмет этого challenge'а. Получилось следующее: > HA 0.999с Copyright (c) 1995 Harri Hirvola > > Archive : lb.ha (13 files) > > filename original compressed rate date time m > =========================================================================== > pmm.exe 57344 30628 53.4 % 2000-11-19 16:01 HSC > bib.pmm 23423 23423 100.0 % 2001-04-20 18:49 CPY > geo.pmm 54256 54256 100.0 % 2001-04-20 18:45 CPY > newstran.pmm 114563 114563 100.0 % 2001-04-20 18:51 CPY > book1.pmm 205992 205992 100.0 % 2001-04-20 18:46 CPY > book2.pmm 136751 136751 100.0 % 2001-04-20 18:46 CPY > progc.pmm 10765 10765 100.0 % 2001-04-20 18:51 CPY > progl.pmm 12538 12538 100.0 % 2001-04-20 18:52 CPY > pic.pmm 46004 46004 100.0 % 2001-04-20 18:45 CPY > obj2.pmm 65567 65567 100.0 % 2001-04-20 18:51 CPY > progp.pmm 8684 8684 100.0 % 2001-04-20 18:51 CPY > obj1.pmm 9453 9453 100.0 % 2001-04-20 18:51 CPY > paper.pmm 34861 34861 100.0 % 2001-04-20 18:53 CPY > =========================================================================== > 13 780201 753485 96.5 % Учитывая, что смысл обнаружился только в склеивании paper'ов и news+trans - по второй части результат будет очень близкий (в пределах 755k имхо). Учитывая, что экзешник - это обычный ppmonstr v.G... > -- > Maxime Zakharov http://sochi.net.ru/~maxime/ > Sochi, Russia http://www.sochi.com/ Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Sergey Smagin 2:5054/60 22 Apr 01 18:57:03 To : All Subj : чокнутые паковальщики (в продолжение темы о ZупеR АрХиfаtоRaX) Привет All! Продолжая тему сабжей, выдвигаю алгоритм, дабы насобирать свеженьких овощей... (весна все таки, витамины нужны). Я его назову FreeFTNA :))) 1111111 a 0000000 a d 1111111 a d 0000000 ac d 1111111 ac d 0000000 ac d 1111111 ac d bbbbbbb c ddddddd c ccccccc Это собстно схема :) Входящий поток - 49 бит, располагается квадратом 7x7 Затем вычисляем ключ: напротив данной строки в A заносим бит, равный приимущест венному значению битов в данной строке. Точно так же делаем и со столбцами и ди агоналями. И получается на выходе 26 бит + 16 бит CRC входящего потока = 42 бит а, по-моему нормально :о) если учесть, что каждый блок (49 бит) будет избавлять ся от 7 битов. Каким способом обратно выстраивать биты в соответствии с ключом (диагонали/стро ки/столбца) - не знаю :) получается несколько вариантов и медленно. Хотя первое и варавнивается CRC, но на сколько точно - тоже не знаю. P.S. Все пасленовые в корзинку рядом, если можно :) Sergey [http://4.ussr.to][http://gallerey.ussr.to][http://www.node.da.ru] --- [http://www.clk.da.ru][http://www.kamenskii.da.ru][http://www.kaddr.da.ru] * Origin: Я в фидо прожил где-то 0,863 килодня (2:5054/60) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Apr 01 22:25:43 To : Maxime Zakharov Subj : Re: $5000 Goldman Challenge From: leob@mailcom.com (Leonid Broukhis) Maxime Zakharov wrote: >> Это потому что Goldman не понял, почему я формулирую мою challenge >> именно так, а не иначе. http://www.mailcom.com/challenge/ > >А после Тэйлора кто-нибудь пытался ? Hет. Что странно... Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 22 Apr 01 22:25:43 To : Eugene D. Shelwien Subj : Re: $5000 Goldman Challenge From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >Я вчера проверил ppmonstr'а на предмет этого challenge'а. >Получилось следующее: >> 13 780201 753485 96.5 % > >Учитывая, что смысл обнаружился только в склеивании paper'ов и news+trans - >по второй части результат будет очень близкий (в пределах 755k имхо). >Учитывая, что экзешник - это обычный ppmonstr v.G... Hу не хочет никто $19.20 - не надо... Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 23 Apr 01 10:44:28 To : All Subj : Re: $5000 Goldman Challenge From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, All! > Я вчера проверил ppmonstr'а на предмет этого challenge'а. > Получилось следующее: [skip] Var.H: Archive CALGARY.RAR Name Size Packed Ratio Date Time Attr CRC-32 --------------------------------------------------------------------- _004_GEO.PMM 49639 49639 100% 22-04-01 22:42 .....A 552CD8B8 _216_PIC.PMM 29678 29678 100% 22-04-01 22:42 .....A FA97E43D BIB.PMM 23334 23334 100% 22-04-01 22:42 .....A EBB2CD16 BOOK1.PMM 205165 205165 100% 22-04-01 22:42 .....A CC61F4FB BOOK2.PMM 136077 136077 100% 22-04-01 22:42 .....A 73EB5EAD DEPPMONS.EXE 24576 23061 93% 22-04-01 22:43 .....A 481ECB65 NEWS.PMM 100771 100771 100% 22-04-01 22:42 .....A 7D111EFA OBJ1.PMM 9422 9422 100% 22-04-01 22:42 .....A 8C97E479 OBJ2.PMM 65113 65113 100% 22-04-01 22:42 .....A 08D53A3E PAPER1.PMM 14258 14258 100% 22-04-01 22:42 .....A 7791A38B PAPER2.PMM 21842 21842 100% 22-04-01 22:42 .....A CBA1E692 PROGC.PMM 10721 10721 100% 22-04-01 22:42 .....A 007923B1 PROGL.PMM 12470 12470 100% 22-04-01 22:42 .....A 5E1A0EF4 PROGP.PMM 8609 8609 100% 22-04-01 22:42 .....A 1D1FB4D0 TRANS.PMM 13747 13747 100% 22-04-01 22:42 .....A A273B561 --------------------------------------------------------------------- 15 725422 723907 99% А жаль что не $5000 ;-) --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 23 Apr 01 14:47:29 To : All Subj : Re: $5000 Goldman Challenge From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Dmitry Shkarin wrote: > > Hi, All! > > Я вчера проверил ppmonstr'а на предмет этого challenge'а. > > Получилось следующее: > [skip] > Var.H: > Archive CALGARY.RAR Name Size Packed ¬ -------------------------------- ¬ DEPPMONS.EXE 24576 23061 ¬ 30544 -7483 ¬ BIB.PMM 23334 23334 ¬ 23421 -87 BOOK1.PMM 205165 205165 ¬ 205939 -774 BOOK2.PMM 136077 136077 ¬ 136750 -673 GEO.PMM 49639 49639 ¬ 54180 -4541 NEWS.PMM 100771 100771 ¬ 101187 -416 OBJ1.PMM 9422 9422 ¬ 9457 -35 OBJ2.PMM 65113 65113 ¬ 65554 -441 PAPER1.PMM 14258 14258 ¬ 14312 -54 PAPER2.PMM 21842 21842 ¬ 21899 -57 PIC.PMM 29678 29678 ¬ 45695 -16017 PROGC.PMM 10721 10721 ¬ 10762 -41 PROGL.PMM 12470 12470 ¬ 12523 -53 PROGP.PMM 8609 8609 ¬ 8671 -62 TRANS.PMM 13747 13747 ¬ 13825 -78 -------------------------------- ¬ 15 725422 723907 Сравнил это я твои результаты со "своими"... Основная разница - за счет geo и pic. То ли оно теперь с детерминированными контекстами обращается существенно лучше, то ли на "мусор" меньше внимания обращает. What's new, а? :) Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Vadim Yoockin 2:5020/400 23 Apr 01 15:19:59 To : Sergei Klochkov Subj : Re: $5000 Goldman Challenge From: "Vadim Yoockin" <vy@thermosyn.com> Reply-To: "Vadim Yoockin" <vy@thermosyn.com> Hello, Sergei Klochkov <Sergei.Klochkov@p15.f48.n5049.z2.fidonet.org>! You wrote: > Vv> Hекто Майк Голдман неосмотрительно заявил, что тот, кто ему пришлет > Vv> 100$ в качестве залога и сожмет некий файл со случайными данными хоть > Vv> на 1 байт, получит 5000$. Порядок действий оговаривался следующий: > Vv> претендент присылает 100$ и говорит, какой размерчик файла он > Vv> предпочитает. По получении этого файла он конструирует компрессор и > Vv> декомпрессор. Размеры сжатого файла и декомпрессора в сумме должны > Vv> быть меньше размера исходного. > > Гмм... А ограничения на размер исходного файла давались ? Hет, ограничений не было. > А то по заранее > известному файлу размером так в 1Gb, ИХМО, хотя бы 1Mb точно можно отыграть. Тогда считай, 5k$ у тебя в кармане ;-) > Vv> Забавно, что указанное предложение Голдмана входит в > Vv> comp.compression FAQ, > > А можно этот FAQ сюда ? Он все же большеват будет для постинга. Если только Булат не сочтет за труд кинуть его в фэху... > Vv> Hа мой взгляд, вопрос о том, кто выиграл состязание, довольно > Vv> спорный. С одной стороны, Майк сам согласился на то, что файлов > Vv> может быть много. > > Почти во всех здешних FAQ-ах упоминается о размерах данных отводимых на > структуру заголовка файла в архиве. Hу, а если разрешить множество файлов и не > учитывать их заголовки, то пожалуй с одного только имени второго файла можно > более 100 byte выйграть. В условиях данного Challenge не было как следует оговорено, что считать размером данных. Что касается самих условий, их вполне подробно описал Lev Serebryakov. Всего доброго, Вадим. --- ifmail v.2.15dev5 * Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 23 Apr 01 20:27:57 To : Dmitry Shkarin Subj : Re: $5000 Goldman Challenge From: leob@mailcom.com (Leonid Broukhis) Dmitry Shkarin wrote: > DEPPMONS.EXE 24576 23061 93% 22-04-01 22:43 .....A 481ECB65 Hе нужно использовать exe-packer, но нужно перед упаковкой в архив заменить в exe-файле все неиспользуемые текстовые строки на нули. > А жаль что не $5000 ;-) А жаль, что PayPal в России не работает. А то собрался бы, сделал бы архив (или даже два), и я бы страничку обновил. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 23 Apr 01 20:44:09 To : All Subj : Re: $5000 Goldman Challenge From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Leonid Broukhis wrote: > > Dmitry Shkarin wrote: > > > DEPPMONS.EXE 24576 23061 93% 22-04-01 22:43 .....A 481ECB65 > > Hе нужно использовать exe-packer, но нужно перед упаковкой в архив > заменить в exe-файле все неиспользуемые текстовые строки на нули. А еще нужно компилировать с /MD :) > > А жаль что не $5000 ;-) > > А жаль, что PayPal в России не работает. А то собрался бы, сделал бы > архив (или даже два), и я бы страничку обновил. Так что, у тебя только забугорного происхождения entries'ы оплачиваются? :) > Leo Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Serg Tikhomirov 2:5020/122.166 23 Apr 01 20:50:54 To : Vadim Yoockin Subj : Сyпеpаpхиватоp Здpавствyй, Vadim! 10:58 of 14 Apr Vadim Yoockin wrote in a message to Anton Morozov: VV>> 0000 1000 четвеpок бит.... что скажете ? бpед? энтpопия как бyдет? VV>> 0000 1001 если все это потом пожать еще ? AM> Вообще-то HA и RAR именно так и pаботают... Только HA после упаковки не AM> жмет. VY> Hу-ну. VY> - Как pаботает тpансфоpматоp? VY> - Ж-ж-ж... VY> (c) анекдот Если уж на то пошло - пpименительно к тематике эхи лучше дpугой: - Мой папа pаботает как тpансфоpматоp! - Это как? - Получает 220, домой пpиносит 127, на остальные гудит... Всего наилучшего! Jee --- * Origin: Овен Овна овном не накоpмит. (2:5020/122.166) — RU.COMPRESS From : IP Robot 2:5093/28.126 24 Apr 01 00:20:24 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmdh.rar PPMD var.H - Fast PPM Compressor for textual data w/src (58,050 bytes) ftp://ftp.elf.stuba.sk/pub/pc/pack/sbc0840b.zip SBC v0.840 beta - Secure archiver with built-in encryption options (212,018 byt es) --- PktMake.pl * Origin: PktMake.pl (2:5093/28.126) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 24 Apr 01 10:24:39 To : All Subj : Re: $5000 Goldman Challenge From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Eugene! > Сравнил это я твои результаты со "своими"... Основная разница - > за счет geo и pic. То ли оно теперь с детерминированными > контекстами обращается существенно лучше, то ли на "мусор" > меньше внимания обращает. > What's new, а? :) Это я просто смухлевал: транспонировал geo и pic. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 24 Apr 01 10:24:39 To : All Subj : (иногда) быстрый ППМ From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, All! Очередная(?) итерация борьбы с тормозным ПэПээМом находится по адресу ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmdh.rar А SimTel.net кажись скопытился. --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 24 Apr 01 15:05:26 To : Eugene D. Shelwien Subj : Re: $5000 Goldman Challenge From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >> Hе нужно использовать exe-packer, но нужно перед упаковкой в архив >> заменить в exe-файле все неиспользуемые текстовые строки на нули. > >А еще нужно компилировать с /MD :) Это что такое? Я последние 9 лет компилирую только в UNIX. >> > А жаль что не $5000 ;-) >> >> А жаль, что PayPal в России не работает. А то собрался бы, сделал бы >> архив (или даже два), и я бы страничку обновил. > >Так что, у тебя только забугорного происхождения entries'ы оплачиваются? :) Оплачиваются - любые, а вот как их получатель обналичивать будет - личное дело получателя. Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 24 Apr 01 19:09:44 To : All Subj : Re: $5000 Goldman Challenge From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Reply-To: shelwien@thermosyn.com Leonid Broukhis wrote: > >> Hе нужно использовать exe-packer, но нужно перед упаковкой в архив > >> заменить в exe-файле все неиспользуемые текстовые строки на нули. > > > >А еще нужно компилировать с /MD :) > > Это что такое? Я последние 9 лет компилирую только в UNIX. Динамическая линковка в VisualC и IntelC, которым, вроде, компилит Дима. Там половина кода - статически подлинкованный libc. > >> > А жаль что не $5000 ;-) > >> > >> А жаль, что PayPal в России не работает. А то собрался бы, сделал бы > >> архив (или даже два), и я бы страничку обновил. > > > >Так что, у тебя только забугорного происхождения entries'ы оплачиваются? :) > > Оплачиваются - любые, а вот как их получатель обналичивать будет - > личное дело получателя. Т.е. "фонд" - безналичный? Или тебе просто нравится фотки чеков выкладывать? :) Положить 100$ в конвертик и отправить по почте - слабо? :) > Leo Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Leonid Broukhis 2:5020/400 25 Apr 01 09:40:00 To : Eugene D. Shelwien Subj : Re: $5000 Goldman Challenge From: leob@mailcom.com (Leonid Broukhis) Eugene D. Shelwien wrote: >> >> А жаль, что PayPal в России не работает. А то собрался бы, сделал бы >> >> архив (или даже два), и я бы страничку обновил. >> > >> >Так что, у тебя только забугорного происхождения entries'ы оплачиваются? :) >> >> Оплачиваются - любые, а вот как их получатель обналичивать будет - >> личное дело получателя. > >Т.е. "фонд" - безналичный? Или тебе просто нравится фотки чеков В США нет разницы между "наличными" и "безналичными" - это чисто советское изобретение. Любой обеспеченный чек можно превратить в наличные. >выкладывать? :) Положить 100$ в конвертик и отправить по почте - слабо? :) Слабо. Ибо не дойдет, и будет обидно и мне, и получателю. А приз, между прочим, не за ловкость рук на почте, а за сжатие данных (вот и необходимое упоминание эхотага в сообщении). Leo --- ifmail v.2.15dev5 * Origin: leob@at-mailcom.dot-com (2:5020/400) — RU.COMPRESS From : Maxime Zakharov 2:5020/400 26 Apr 01 01:09:01 To : All Subj : Thap compression From: Maxime Zakharov <maxime@sochi.com> http://sochi.net.ru/~maxime/src/Thap102c.zip Получено от Александра Крупника. -- Maxime Zakharov http://sochi.net.ru/~maxime/ Sochi, Russia http://www.sochi.com/ --- ifmail v.2.15dev5 * Origin: Technology Communication Centre, Sochi, Russia (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 26 Apr 01 13:10:34 To : All Subj : адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <VSemenyuk@vss.spb.ru> Всем привет ! Рассмотрим стандартную контекстную статистическую нулевую модель, в которой счетчики появления символов не масштабируются, и зададимся вопросом: насколько адаптивная разновидность такой модели круче полуадаптивной? Для простоты ограничимся случаем двоичного алфавита. Пускай символ "0" появляется с частотой n, а симол "1" - с частотой m. Тогда оптимальная длина кода, полученного с использованием адаптивной модели, будет равна, согласно, например, Жене Шелвину, log2((n+m)!/n!/m!), а длина кода, полученного на основе классической полуадаптивной модели, окажется равной n*log2((n+m)/n)+m*log2((n+m)/m) = log2((n+m)^(n+m)/n^n/m^m). Максимальная разница в длинах кодов будет, очевидно, достигаться при n = m. Так чему же она равна? Вот наглядный ответ: при m+n = 4 - max_diff ~ 1.42 бита при m+n = 8 - max_diff ~ 1.87 бита при m+n = 16 - max_diff ~ 2.35 бита при m+n = 32 - max_diff ~ 2.84 бита при m+n = 64 - max_diff ~ 3.33 бита при m+n = 128 - max_diff ~ 3.83 бита при m+n = 256 - max_diff ~ 4.33 бита при m+n = 512 - max_diff ~ 4.83 бита при m+n = 1024 - max_diff ~ 5.33 бита при m+n = 2048 - max_diff ~ 5.83 бита и т. д. (1 байт потеряется при обработке примерно 40 тыс. двоичных символов) Вывод: если мы имеем дело со стационарным эргодическим источником, если есть такая возможность, лучше использовать полуадаптивную модель, так как проигрыш в эффективности окажется несравнимым с выигрышем в производительности. Владимир. ЗЫ. Хотя на практике, конечно, лучше использовать адаптивную или квазиадаптивную модель ; -) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vladimir Pushkaryov 2:4641/223.50 26 Apr 01 18:28:00 To : All Subj : Сигнатypа "BH" Пpивет All! Интеpесно, какой тип аpхивов начинается с сабжа? 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 : Dmitry Shkarin 2:5020/400 26 Apr 01 21:49:50 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Vladimir! > Для простоты ограничимся случаем > двоичного алфавита. Пускай символ > "0" появляется с частотой n, а симол > "1" - с частотой m. Тогда оптимальная > длина кода, полученного с использованием > адаптивной модели, будет равна, согласно, > например, Жене Шелвину, log2((n+m)!/n!/m!), > а длина кода, полученного на основе классической > полуадаптивной модели, окажется равной > n*log2((n+m)/n)+m*log2((n+m)/m) = > log2((n+m)^(n+m)/n^n/m^m). Максимальная разница > в длинах кодов будет, очевидно, достигаться при > n = m. Так чему же она равна? Хм, а передача частот где у тебя учитывается? В Ховарда-то загляни... --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400) — RU.COMPRESS From : Vladimir Semenyuk 2:5020/400 26 Apr 01 23:00:58 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Vladimir Semenyuk" <semenjuk@green.ifmo.ru> Привет, Дмитрий ! > Хм, а передача частот где у тебя > учитывается? В Ховарда-то загляни... Я говорил об асимптотическом поведении. Формулы-то разные, а результат почти один и тот же. Вот в чем смысл. Владимир. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 27 Apr 01 00:14:06 To : All Subj : Re: адаптивный vs. полуадаптивный From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Владимир! >> при m+n = 4 - max_diff ~ 1.42 бита >> при m+n = 8 - max_diff ~ 1.87 бита >> Вывод: если мы имеем дело со стационарным >> эргодическим источником, если есть такая >> возможность, лучше использовать полуадаптивную >> модель, так как проигрыш в эффективности окажется >> несравнимым с выигрышем в производительности. > Я говорил об асимптотическом поведении. > Формулы-то разные, а результат почти > один и тот же. Вот в чем смысл. m+n = 4, асимптотически, говоришь? ;-) Hа глазок видно, что разность растет как log(m+n). ЗЫ Где-бы еще стационарный источник найти... ЗЗЫ Чой-то это мне напоминает кодирование EOF & bijectivity ;-). --- ifmail v.2.15dev5 * Origin: MTU-Intel ISP (2:5020/400)
Предыдущий блок Следующий блок Вернуться в индекс