Новинки:

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

 Предыдущий блок Следующий блок Вернуться в индекс
 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)
 Предыдущий блок Следующий блок Вернуться в индекс