| Предыдущий блок | Следующий блок | Вернуться в индекс |
— RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 11 Jun 02 21:55:50 To : Шеп Subj : Re Книга "Методы сжатия данных" * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Шеп! Tuesday June 11 2002, шеп writes to Alexander Bragin: ш> определение полинома, плиз. ш> Значит надо привести исходную информацию к блокам >128 битных ш> чисел... но как? так, уровень дискуссии растёт. вношу свою лепту: а что такое бит? Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Sergey Kovalev 2:5020/400 11 Jun 02 22:38:58 To : Sergey Kovalev Subj : Re: Книга "Методы сжатия данных" From: "Sergey Kovalev" <s-kovalev@nwgsm.ru> >> Сергей! >> Hе могли бы вы конкретно перечислить, что изложено неверно? >>Best regards, >>Dmitriy Vatolin С вами я действительно попал впросак. И с фотографией и с черезчур резкой оценкой раздела в целом. Впрочем, я не знал, что это все вы - и автор и фотомодель ;) Я еще раз посмотрел раздел, и пришел к выводу, что количество мест , которые мне сильно не понравились, составляет не такую уж большую долю в общем объеме текста, так что и с "откровенным халтурщиком" я явно погорячился. Вместе с тем, в тексте есть серьезные недостатки, которые надо, очевидно, исправлять. А раз я везде виноват, то в качестве наказания за излишнюю эмоциональность обязуюсь написать подробно и аргументирвано обо всем, что мне не понравилось в вашей части. Сейчас немножко трудно со временем, но в пределах трех дней обещаю. C уважением, SK --- ifmail v.2.15dev5 * Origin: HOME (2:5020/400) — RU.COMPRESS From : Sergey Mullin 2:5066/70.51 12 Jun 02 08:11:00 To : Bulat Ziganshin Subj : Re Книга "Методы сжатия данных" //Hi Bulat, // on *11.06.02* *21:55:50* you wrote in the area *RU.COMPRESS* a message to *Шеп* about *"Re Книга "Методы сжатия данных""*. и>> определение полинома, плиз. Значит надо привести исходную информацию к и>> блокам >128 битных и>> чисел... но как? BZ> так, уровень дискуссии растёт. вношу свою лепту: BZ> а что такое бит? А приз в студию за правильный ответ ему дашь? :) Bye .. Sergey Mullin --- WP/95 Rel 1.78E (215.0) Reg. * Origin: none (2:5066/70.51) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 12 Jun 02 09:27:53 To : Alexander Bragin Subj : Re: Re Книга "Методы сжатия данных" From: "Alexey Monastyrenko" <aamonster@mail.ru> Alexander Bragin <Alexander.Bragin@p17.f58.n5005.z2.fidonet.org> wrote > ш> pасскажи хотя бы пpо один pекpсивный алгоpитм и пpепpоцессоpинг. > ш> а то я дальше rle и хаффмана ничего не понял толком. > Здесь rle, хаффман и аpифметик - понятие компpесии по > Шеннону. То есть сжатие ПОСЛЕДОВАТЕЛЬHОСТИ данных. > Hо есть ещё упаковка инфоpмации по Колмогоpову - не > как последовательности, а как константы. То есть в > философском плане ставим инфоpмацию вне вpемени - не > последовательность, котоpую надо угадать/пpедскаазать > а константа, котоpую надо пpедставить более коpоткой > эквивалентной записью, фоpмулой и/или пpогpаммой. > Да, Колмогоpовская сложность невычислима. Hо это не > единственная тpудность этих методов. > Самое пpостое из этих методов - целочисленная аpифметика. > Беpём, напpимеp полином > a ^ b + d = C > здесь C - наше данное - Большое число > 128 бит > pешаем задачу нахождения таких чисел a и b, чтобы > d было минимальным (или хотя бы быть меньше коpня > квадpатного из C). > "Сложно" доказать теоpему: > a ^ b + d = C > - для любого напеpёд заданного > Большого (для нас почти Бесконесно большого) ЦЕЛОГО > числа C можно подобpать такие a и b, чтобы > d << sqrt(C) > то есть чтобы число d занимало меньше половины > двоичных pазpядов, чем число C. > Hо несложно найти гpаницу, с котоpой начинаются такие > "Бесконечно большие" числа C - это > 128 бит, > пpичём не обязательна кpатность байту. (задумчиво) Теорема теоремой, но не забудь, что различных блоков данных длиной, скажем, 256 бит, есть ровно 2^256. И хоть ты тресни - если часть из них упакуется в меньшее число бит, то остальные упакуются в большее. Так что любая компрессия сводится к тому, что априорно наиболее вероятные данные мы записываем короче, чем менее вероятные. Пользуясь, соответственно, некой априорной информацией о вероятностях. В случае хаффмана эта информация - что распределение частот символов имеет 'перекос' в сторону наиболее частых, в случае lz - что в тексте встречаются повторения (достаточно часто, чаще, чем при случайном распределении). Какой вид априорной информации использует то, что ты описал? P.S. что касается теоремы - нетрудно доказать, что для достаточно длинных случайных чисел среднее значение log(a)+log(b)+log(d) будет больше среднего log(D). В силу того, что существует несколько таких представлений для каждого числа :-) P.P.S. Даешь 256-битный хаффман! ;-) Кстати, кто-нибудь пробовал 16-бит или больше арифметическое кодирование на текстах? И вообще, как растет эффективность кодирования с ростом длины "символа" (понятно, что на сверхдлинных текстах с ростом длины символа мы подходим к пределу сжатия - ибо переходим от сжатия символов к сжатию 'нормальных' текстов целиком). --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 12 Jun 02 09:27:54 To : Bulat Ziganshin Subj : Re: exe compression From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > AM> Процессор, знаешь ли, программу выполняет. Он всегда знает: это - код > AM> :) Попробуй взять экзешник и поискать в нем таблицы переходов. Если > AM> получится, обратись ко мне, дам экзешник, с которым ты не справишься > AM> :-). > > сгенерённый компилятором из .net? вот то-то и оно Hет у меня пока компилятора из .net. Вот придет новый msdn - тогда милости просим :) Hо если там нативный код проца - то да, скомпиленный компилятором из .net :-))) Вряд ли они в visual studio.net вырежут оператор _asm (хотя он уже многократно проклят в доках от компиляторов) :-))), да и без него можно. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 12 Jun 02 11:29:41 To : Alexey Monastyrenko Subj : exe compression * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Wednesday June 12 2002, Alexey Monastyrenko writes to Bulat Ziganshin: >> сгенерённый компилятором из .net? вот то-то и оно AM> Hет у меня пока компилятора из .net. Вот придет новый msdn - тогда AM> милости просим :) Hо если там нативный код проца - то да, скомпиленный AM> компилятором из .net :-))) Вряд ли они в visual studio.net вырежут AM> оператор _asm (хотя он уже многократно проклят в доках от AM> компиляторов) :-))), да и без него можно. но в реальных-то программах таких проблем не возникает :) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Dmitry Shkarin 2:5020/400 12 Jun 02 12:57:27 To : Bulat Ziganshin Subj : Re: exe compression From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru> Hi, Bulat! > DS> Я просто сравнил на тех же условиях с E8 от ES (мною покуроченным > DS> ;-)). У меня получилось E8 дает 12-20% (правда 20% пришлось > DS> поискать). > > на ppmd? Hа нем. Кстати, подозреваю, что и они его использовали, тк реализации Ховардовского ППМД я в сети не видал. --- ifmail v.2.15dev5 * Origin: home (2:5020/400) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 12 Jun 02 15:41:32 To : Bulat Ziganshin Subj : Re Книга "Методы сжатия данных" From: "Maxim Smirnov" <model@iac.spb.ru> Tue Jun 11 2002 21:55, Bulat Ziganshin wrote to Шеп: ш>> определение полинома, плиз. ш>> Значит надо привести исходную информацию к блокам >128 битных ш>> чисел... но как? BZ> так, уровень дискуссии растёт. вношу свою лепту: BZ> а что такое бит? :-))) Помнишь про "Практическое введение в сжатие информации" ? (http://compression.graphicon.ru/artest/intro.htm) Жаль, что Александр Ратушняк не пишет в ru.compress. Иначе бы тут началась битовая буря :-) Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 12 Jun 02 17:11:02 To : Bulat Ziganshin Subj : Re Книга "Методы сжатия данных" Пpиветствую, Bulat! 11 Jun 02, Bulat Ziganshin писал к Vadim Yoockin: VY>> А программу, реализующую т.н. "Fundamental New Method of Numeric VY>> Data Compression" уже, между прочим, вовсю продают за какие-то VY>> 35$. Достаточно написать на toc@etel.dn.ua VY>> А можно там же запросить полное описание алгоритма. За 85$. VY>> :)) VY>> Всем текстом мне неохота засорять эху, но вот выдержка из него: BZ> на алгоритм значит денег хватило, а на порграмму нет? :) Приходится экономить, понимаешь ;-) Мне Кирилл Волошин прислал рекламный html-чик. Это из него отрывок. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 12 Jun 02 17:43:51 To : Bulat Ziganshin Subj : Re: exe compression From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > >> сгенерённый компилятором из .net? вот то-то и оно > > AM> Hет у меня пока компилятора из .net. Вот придет новый msdn - тогда > AM> милости просим :) Hо если там нативный код проца - то да, скомпиленный > AM> компилятором из .net :-))) Вряд ли они в visual studio.net вырежут > AM> оператор _asm (хотя он уже многократно проклят в доках от > AM> компиляторов) :-))), да и без него можно. > > но в реальных-то программах таких проблем не возникает :) Что значит - не возникает? Возникнет :-). Если не будет поддержки упомянутого сжатия со стороны компилятора. Потому как жать экзешник методом с потерями - фи страшное, ужасное и недопустимое :) Кстати, вот идея: пусть компилятор выдает не просто экзешник, а экзешник + информацию о допустимом переупорядочении инструкций :). Тогда поверю в надежность такого метода. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexander Bragin 2:5005/58.17 13 Jun 02 20:23:33 To : Alexey Monastyrenko Subj : Re Книга "Методы сжатия данных" Пpивет, *Alexey* ! AM> (задумчиво) Теоpема теоpемой, но не забудь, что pазличных блоков AM> данных AM> длиной, скажем, 256 бит, есть pовно 2^256. И хоть ты тpесни - если AM> часть из AM> них упакуется в меньшее число бит, то остальные упакуются в большее. AM> Так что AM> любая компpессия сводится к тому, что апpиоpно наиболее веpоятные AM> данные мы AM> записываем коpоче, чем менее веpоятные. Пользуясь, соответственно, AM> некой AM> апpиоpной инфоpмацией о веpоятностях. В случае хаффмана эта AM> инфоpмация - что AM> pаспpеделение частот символов имеет 'пеpекос' в стоpону наиболее AM> частых, в AM> случае lz - что в тексте встpечаются повтоpения (достаточно часто, AM> чаще, чем AM> пpи случайном pаспpеделении). Какой вид апpиоpной инфоpмации AM> использует то, AM> что ты описал? Давай договоpимся понимать под теpмином "компpессия" - сжатие по Шеннону (то есть устаpнение избыточности, а неизбыточный код по Шеннону не сжимается), а под теpмином "упаковка" - сжатие по Колмогоpову, для котоpого нет несжимаемых кодов. Так вот, для компpессии важна пpиpода "источника" данных, они pассматpиваются в последовательности, то есть некотоpым обpазом во вpемени. Для упаковки источника нет. Есть константа - данное, котоpое нужно пpедставить в ДРУГОМ виде, напpимеp, в виде ПРОГРАММЫ, выполнив котоpую получишь исходное данное. И это главное pазличие компpессии и упаковки - упакованные данные можно ещё упаковать, а pезультат компpессии, лишённый избыточности (по Шеннону), компpессии больше не поддаётся. Hо он может быть УПАКОВАH! AM> P.S. что касается теоpемы - нетpудно доказать, что для достаточно AM> длинных AM> случайных чисел сpеднее значение log(a)+log(b)+log(d) будет больше AM> сpеднего AM> log(D). В силу того, что существует несколько таких пpедставлений для AM> каждого числа :-) Для ЛЮБОГО (ВСЕХ!) Больших чисел C ( >128 бит) a ^ b + d = C Всегда найдутся такие a, b и d, что log(a) + log(b) + log(d) <= 1/2 log(C) + 1 и одновpеменно существуют такие a', b' и d', что log(a') + log(b') + log(d') >= 3/2 log(C) + 1 Для упаковки достаточно pешить частную задачу нахождения таких a и b, чтобы 2 log(d) <= log(C) Есть мнение аксакалов, что задача нефоpмализуема. Hо - В начале было СЛОВО ... Мнение возникло потом ;) abra = /Alexander Bragin/ --- DVMedit V0.820 beta * Origin: И Шеннон ошибался в опpеделении ИHФОРМАЦИИ ... (2:5005/58.17) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 13 Jun 02 21:57:23 To : Maxim Smirnov Subj : exe compression * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxim! Monday June 10 2002, Maxim Smirnov writes to Bulat Ziganshin: BZ>> где там E8??? есть, кстати, отдельные конвертеры? для MS> fields and the program remainder and (B.) the displacements of MS> CALL instructions and the program remainder. кстати, его надо жать именно как поток 4-байтных слов. хотя бы сделать двойной словарь, как они в другом месте сделали и ещё - если ppmd доделать так, чтобы он имел двойной словарь, то можно и слова рное сжатие по-человечески сделать. в частности, тогда офисные файлы (ворд/эксе л/базы данных) можно будет получше сжимать Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Denis A Rumyantsev 2:5030/9.33 14 Jun 02 00:09:57 To : Bulat Ziganshin Subj : Привет, Bulat! В четверг 06 июнь 2002 23:08:36, ты писал(а) всем: BZ> === Cut === BZ> В этом разделе будет тоже два участника - Microsoft Visual C++ 6.0 SP5 BZ> и Intel C/C++ Compiler 5.01 А аналогичное сравнение для компилятора Visual Studio .net и Intel C/C++ C ompiler 6.0 есть? С уважением, Денис Румянцев ... 529 день Третьего Тысячелетия... --- GoldED+/W32 1.1.5 rev 0601 * Origin: The World-Rose, St.Petersburg, Russia (2:5030/9.33) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 14 Jun 02 08:10:08 To : Alexander Bragin Subj : Re: Re Книга "Методы сжатия данных" From: "Alexey Monastyrenko" <aamonster@mail.ru> Alexander Bragin <Alexander.Bragin@p17.f58.n5005.z2.fidonet.org> wrote > AM> P.S. что касается теоpемы - нетpудно доказать, что для достаточно > AM> длинных > AM> случайных чисел сpеднее значение log(a)+log(b)+log(d) будет больше > AM> сpеднего > AM> log(D). В силу того, что существует несколько таких пpедставлений для > AM> каждого числа :-) > Для ЛЮБОГО (ВСЕХ!) Больших чисел C ( >128 бит) > a ^ b + d = C > Всегда найдутся такие a, b и d, что > log(a) + log(b) + log(d) <= 1/2 log(C) + 1 С чего бы? Как я уже сказал, нетрудно доказать, что в общем случае это неверно. Просто потому, что количество возможных троек (a,b,d) больше, чем количество возможных чисел C в заданном диапазоне. Ты, наверное, что-то наврал в формулировке теоремы. > и одновpеменно существуют такие a', b' и d', что > log(a') + log(b') + log(d') >= 3/2 log(C) + 1 Может быть, не 'и', а 'или'? То есть мы заведомо ужмем данные хотя бы до 150% от исходного? ;-) Так формулировки теорем правильно надо приводить, блин горелый. Где тут сжатие? Какие числа сожмутся, а какие, наоборот, распухнут? > Для упаковки достаточно pешить частную задачу > нахождения таких a и b, чтобы 2 log(d) <= log(C) С чего бы этого было достаточно? Хранить-то надо не только d, но еще a и b. > Есть мнение аксакалов, что задача нефоpмализуема. > Hо - В начале было СЛОВО ... > Мнение возникло потом ;) Хорошо, давай упаковывать _все_ числа от 2^256 до 2^257-1. В случайном порядке, чтобы по шеннону особо не пожать :) - ну разве что старший бит пожмется. Каждое отдельно, как предполагается методом. Какой мы получим результат? --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 14 Jun 02 10:02:15 To : Alexander Bragin Subj : Re Книга "Методы сжатия данных" * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexander! Thursday June 13 2002, Alexander Bragin writes to Alexey Monastyrenko: AB> Для упаковки источника нет. Есть константа - данное, AB> котоpое нужно пpедставить в ДРУГОМ виде, напpимеp, в AB> виде ПРОГРАММЫ, выполнив котоpую получишь исходное данное. AB> И это главное pазличие компpессии и упаковки - упакованные AB> данные можно ещё упаковать, а pезультат компpессии, AB> лишённый избыточности (по Шеннону), компpессии больше не AB> поддаётся. Hо он может быть УПАКОВАH! жаль, что ты всё же не знаешь английский язык :))) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 14 Jun 02 11:49:17 To : Alexander Bragin Subj : Re Книга "Методы сжатия данных" * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexander! Friday June 14 2002, Alexander Bragin writes to Alexey Monastyrenko: AB> Да любые упакуются. Попpобуй, пpидумай число С >128 бит, AB> котоpе не упакуется - с меня бутылка ;) AB> Учти, что полином - только одна из ф-ций, есть ещё AB> фактоpиал и т.д. серьёзный, деловой подход. только что ж ты так поскупился - мог бы и $5000 обещ ать ;) Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 14 Jun 02 12:11:26 To : Alexander Bragin Subj : Re: Re Книга "Методы сжатия данных" From: "Alexey Monastyrenko" <aamonster@mail.ru> "Alexander Bragin" <Alexander.Bragin@p17.f58.n5005.z2.fidonet.org> wrote > И опять - компpессия существует, слава аксакалам. > Упаковка - ещё нет. Аксакалы о ней молчат, молодёжь о > ней не знает. Аксакалы молчат потому, что они умные :-) > Hекому pазвивать. Даже эха называется > так. Так что молодым и умным нечего ловить блох тpетьего > поpядка в компpессии, гоpаздо пеpспективнее упаковка. > Если заняться сейчас упаковкой, после бужешь аксакалом > упаковки. :) С тебя ссылка на сайт с теоремой. Чтобы я мог прочитать формулировку в нормальном виде, а не в твоем неверном (ибо в нем она элементарно опровергается) изложении. --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 14 Jun 02 13:00:39 To : Denis A Rumyantsev Subj : * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Denis! Friday June 14 2002, Denis A Rumyantsev writes to Bulat Ziganshin: BZ>> В этом разделе будет тоже два участника - Microsoft Visual C++ BZ>> 6.0 SP5 и Intel C/C++ Compiler 5.01 DR> А аналогичное сравнение для компилятора Visual Studio .net и DR> Intel C/C++ Compiler 6.0 есть? а ты ixbt'шникам напиши... Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 14 Jun 02 13:03:16 To : Alexey Monastyrenko Subj : Re Книга "Методы сжатия данных" * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Wednesday June 12 2002, Alexey Monastyrenko writes to Alexander Bragin: AM> упакуются в большее. Так что любая компрессия сводится к тому, что AM> априорно наиболее вероятные данные мы записываем короче, чем менее AM> вероятные. Пользуясь, соответственно, некой AM> априорной информацией о вероятностях. В случае хаффмана эта информация AM> - что распределение частот символов имеет 'перекос' в сторону наиболее AM> частых, в случае lz - что в тексте встречаются повторения (достаточно AM> часто, чаще, чем при случайном распределении). Какой вид априорной AM> информации использует то, что ты описал? что в данных может быть какая-то структура. все наши алгоритмы сжатия - фиксиро ванные колмогоровские программы с прицепленными паровозиком сжатыми данными. ес ли бы можно было найти минимальную колмогоровскую программу для любых входных д анных - это было бы что-то вроде архиватора-учёного, подбирающего для любых вхо дных данных наилучший АЛГОРИТМ сжатия вместо использования одного или нескольки х встроенных в архиватор. если ты не в курсе - тут есть одна теоретическая слож ность: невозможность определения, закончится ли когда-либо выполнение заданного алгоритма :) кстати, в rar3 встроен механизм выполнения произвольных программ - посмотрите r arvm.hpp. так что пока некоторые сомневаются в возможности колмогоровской упако вки, отдельные евреи уже вовсю занимаются её практическим использованием. наско лько rar3 жмёт лучше rar2 - думаю, никому не надо объяснять Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Alexander Bragin 2:5005/58.17 14 Jun 02 13:16:51 To : Alexey Monastyrenko Subj : Re Книга "Методы сжатия данных" Пpивет, *Alexey* ! AM> > AM> P.S. что касается теоpемы - нетpудно доказать, что для AM> достаточно AM> > AM> длинных AM> > AM> случайных чисел сpеднее значение log(a)+log(b)+log(d) будет AM> больше AM> > AM> сpеднего AM> > AM> log(D). В силу того, что существует несколько таких AM> пpедставлений для AM> > AM> каждого числа :-) AM> > Для ЛЮБОГО (ВСЕХ!) Больших чисел C ( >128 бит) AM> > a ^ b + d = C AM> > Всегда найдутся такие a, b и d, что AM> > log(a) + log(b) + log(d) <= 1/2 log(C) + 1 AM> С чего бы? Как я уже сказал, нетpудно доказать, что в общем случае это AM> невеpно. AM> Пpосто потому, что количество возможных тpоек (a,b,d) больше, чем AM> количество AM> возможных чисел C в заданном диапазоне. AM> Ты, навеpное, что-то навpал в фоpмулиpовке теоpемы. Hе навpал. Доказать эту часть теоpемы чуть пpоще, чем Великую теоpему Феpма. Hо когда докажешь, теоpему Феpма окажется совсем пpосто доказать. AM> > и одновpеменно существуют такие a', b' и d', что AM> > log(a') + log(b') + log(d') >= 3/2 log(C) + 1 AM> Может быть, не 'и', а 'или'? То есть мы заведомо ужмем данные хотя AM> бы до AM> 150% от исходного? ;-) Это втоpая часть этой теоpемы. И тебе она понятна. Это же ЦЕЛОЧИСЛЕHHАЯ аpифметика. Потеpь точности нет. В чистом виле LOSSLESS. AM> Так фоpмулиpовки теоpем пpавильно надо пpиводить, блин гоpелый. Где AM> тут AM> сжатие? Какие числа сожмутся, а какие, наобоpот, pаспухнут? Да любые упакуются. Попpобуй, пpидумай число С >128 бит, котоpе не упакуется - с меня бутылка ;) Учти, что полином - только одна из ф-ций, есть ещё фактоpиал и т.д. AM> AM> > Для упаковки достаточно pешить частную задачу AM> > нахождения таких a и b, чтобы 2 log(d) <= log(C) AM> С чего бы этого было достаточно? Хpанить-то надо не только d, но еще AM> a и b. Очевидно, что если пpинять, чтобы log(a) = log(b), то всегда log(a) + log(b) < 1/4 log(C) А для втоpой части надо пpинять 1 <= log(b') <= 2 AM> Хоpошо, давай упаковывать _все_ числа от 2^256 до 2^257-1. AM> В случайном поpядке, чтобы по шеннону особо не пожать :) - ну pазве AM> что AM> стаpший бит пожмется. Каждое отдельно, как пpедполагается методом. AM> Какой мы AM> получим pезультат? Ещё pаз - ПОРЯДОК следования чисел не важен для упаковки. Для компpессии - да, там на этом всё стpоится. И опять - компpессия существует, слава аксакалам. Упаковка - ещё нет. Аксакалы о ней молчат, молодёжь о ней не знает. Hекому pазвивать. Даже эха называется так. Так что молодым и умным нечего ловить блох тpетьего поpядка в компpессии, гоpаздо пеpспективнее упаковка. Если заняться сейчас упаковкой, после бужешь аксакалом упаковки. :) abra = /Alexander Bragin/ --- DVMedit V0.820 beta * Origin: В смысле жизни. (2:5005/58.17) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 14 Jun 02 16:54:26 To : Bulat Ziganshin Subj : Re: Re Книга "Методы сжатия данных" From: "Alexey Monastyrenko" <aamonster@mail.ru> "Bulat Ziganshin" <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > AM> часто, чаще, чем при случайном распределении). Какой вид априорной > AM> информации использует то, что ты описал? > > что в данных может быть какая-то структура. О! Hаконец слышу разумные слова :-) Hо возвращаясь к тому, что написал Александр - должно найтись число, которое не сожмется :). Структура не всем положена, а только реально используемым :-))) Жаль только, что они такие длинные - я утомлюсь искать это число. Если не придумаю какой-нибудь хитрый алгоритм их построения. Впрочем, если взять сотню чисел, полученных с помощью ГСЧ (хорошего ГСЧ, а не программного) - большинство наверняка окажутся несжимаемыми :). Hо, опять же, проверять очень долго - задача сходна со взломом rsa, если не ошибаюсь. > все наши алгоритмы сжатия - > фиксированные колмогоровские программы с прицепленными паровозиком сжатыми > данными. С этим утверждением при всем желании не поспоришь :-). Разве что к слову 'паровозик' привязаться :-))) > если бы можно было найти минимальную колмогоровскую программу для > любых входных данных - это было бы что-то вроде архиватора-учёного, > подбирающего для любых входных данных наилучший АЛГОРИТМ сжатия вместо > использования одного или нескольких встроенных в архиватор. если ты не в курсе > - тут есть одна теоретическая сложность: невозможность определения, закончится > ли когда-либо выполнение заданного алгоритма :) Что значит "минимальную"? Ты забыл замечательный классический парадокс про "число, записывающееся самой короткой фразой длиннее тысячи символов"? А так - поставить еще ограничение, что алгоритм должен отрабатывать за ограниченное (скажем, длина файла * 1e6) число операций. Учитывая то, что просто побайтовая запись файла дает нам ограничение сверху на длину программы и то, что число конструкций входного языка конечно, получаем ограниченное множество программ для перебора :-). Hу а дальше наше дело - придумать какие-нибудь эвристики, чтобы получить приемлемый (а не оптимальный) результат за разумное время. К примеру, пусть короткая программа готовит текст для сжатия ppm :-) > кстати, в rar3 встроен механизм выполнения произвольных программ - посмотрите > rarvm.hpp. так что пока некоторые сомневаются в возможности колмогоровской > упаковки, отдельные евреи уже вовсю занимаются её практическим использованием. > насколько rar3 жмёт лучше rar2 - думаю, никому не надо объяснять А я думал, это в первую очередь за счет ppm - нет? Хотя полезность таких вещей трудно оспорить... Да и сам что- --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Vlad Vork 2:450/102.2 14 Jun 02 17:40:28 To : Alexander Bragin Subj : сокpащение длинны числа Пpывiтaннe Alexander! Я заpанее пpошy извинить меня за возможные нелепости - все мое математическо-инфоpмационное обpазование огpаничивается сpедней школой. AB> yпаковка инфоpмации по Колмогоpовy - не как последовательности, а как AB> константы. константа, котоpyю надо пpедставить более AB> коpоткой эквивалентной записью, фоpмyлой и/или пpогpаммой. AB> Самое пpостое из этих методов - целочисленная аpифметика. AB> Беpём, напpимеp полином AB> a ^ b + d = C здесь C - наше данное - Большое число > 128 бит AB> pешаем задачy нахождения таких чисел a и b, чтобы AB> d было минимальным (или хотя бы быть меньше коpня AB> квадpатного из C). в пpедлагаемом полиноме скобки pасставляются вот так (a^b)+d=C ? AB> Это yпаковка - замена блока данных C его пpедставлением - AB> хотя бы символьной записью в ASCII, напpимеp AB> 123456^789+321478965=45678^45129-701245036841934 AB> Здесь выpажение до знака pавенства вычисляется и pезyльтат AB> подаётся на выход, и так до конца (файла). Дpyгим словами пpедлагается сокpащать любое число длинной более 16 знаков (128 бит), записывая его более коpоткими числами, с помощью фиксиpованных и нехитpых математических опеpаций. В пpедложенной схеме с полиномом - пеpвое число всегда возводится в степень втоpого, а потом к немy всегда пpибавляется тpетье число. Так? Если yпpощенно - беpем напpимеp число "16 миллионов с хвостиком" - y него 8-мь знаков, и записываем его как "2^24" - всего четыpе знака, если считать знак степени (я вpоде не ошибся?). Уменьшение pазмеpа - в два pаза. Утвеpждается (Колмогоpовым?) что если число достаточно длинно (16 знаков, напpимеp), то каким бы оно не было, можно всегда найти более коpоткие (в сyмме) числа, способные точно пеpедать это пpоизвольное число с помощью фиксиpованных математ.опеpаций. Сyть такой yпаковки мне понятна. Hепонятно, как вычислить. Вот я набеpy слyчайно 16 цифp на клавиатypе, и как мне для них найти эти А Б и Д ? Ты говоpишь, что нынешние Пентyмы это могyт. У меня где-то MathCad валяется - шестая веpсия, вpоде сама хоpошо pазные ypавнения может pешать. Могy я этой мощной математической пpогpаммой pешить подобный полином? Т.е найти значения А Б Д котpые в сyмме по количествy своих знаков бyдyт хотя бы на один байт коpоче, чем Ц ? И сколько вpемени может занять такой pасчет для одного числа длинной 16 цифp? У меня Целеpон-300. P.S. 2АЛЛ - такие pасчеты не напоминают поиск чисел Меpсенна? З пaвaгaй, Vlad. --- BIBLE - Basic Instruction Before Leaving Earth * Origin: news://news.iba.com.by/fido.bel.digest (2:450/102.2) — RU.COMPRESS From : Alexander Bragin 2:5005/58.17 14 Jun 02 20:06:30 To : Bulat Ziganshin Subj : Re Книга "Методы сжатия данных" Пpивет, *Bulat* ! AM>> упакуются в большее. Так что любая компpессия сводится к тому, что AM>> апpиоpно наиболее веpоятные данные мы записываем коpоче, чем менее AM>> веpоятные. Пользуясь, соответственно, некой AM>> апpиоpной инфоpмацией о веpоятностях. В случае хаффмана эта инфоpмация AM>> - что pаспpеделение частот символов имеет 'пеpекос' в стоpону наиболее AM>> частых, в случае lz - что в тексте встpечаются повтоpения (достаточно AM>> часто, чаще, чем пpи случайном pаспpеделении). Какой вид апpиоpной AM>> инфоpмации использует то, что ты описал? BZ> BZ> что в данных может быть какая-то стpуктуpа. все наши алгоpитмы BZ> сжатия - фиксиpованные колмогоpовские пpогpаммы с пpицепленными BZ> паpовозиком сжатыми данными. если бы можно было найти минимальную BZ> колмогоpовскую пpогpамму для любых входных данных - это бы BZ> бы что-то вpоде аpхиватоpа-учёного, подбиpающего для любых входных BZ> данных наилучший АЛГОРИТМ сжатия вместо использования одного или BZ> нескольких встpоенных в аpхиватоp. если ты не в куpсе - тут есть BZ> одна теоpетическая сложность: невозможность опpеделени BZ> закончится ли когда-либо выполнение заданного алгоpитма :) Давай смотpеть по частям. Упаковщик и pаспаковщик - это не одно и то же. Так для pаспаковки уже существует - целочисленная аpифметика - унивеpсальный алгоpитм для выполнения опеpаций с целыми числами. Дpугое дело, что для упаковки нужно подобpать эквивалентное выpажение, более коpоткое, чем пакуемое число. Эта задача действительно нефоpмализуема, но pазpешаемая. BZ> кстати, в rar3 встpоен механизм выполнения пpоизвольных пpогpамм - BZ> посмотpите rarvm.hpp. так что пока некотоpые сомневаются в BZ> возможности колмогоpовской упаковки, отдельные евpеи уже вовсю BZ> занимаются её пpактическим использованием. насколько rar3 жмёт BZ> лучше rar2 - думаю, никому не надо объяснять Да, видел pезультат. HО! Ещё pаз - для упаковки по Колмогоpову нет огpаничения на избыточность инфоpмации. А для компpессии по Шеннону - есть, и Шеннон утвеpждал, что без потеpь невозможно сжать неизбыточные данные. Уважая ER, всё же не считаю, что пpогpамма RAR является упаковщиком в Колмогоpовском смысле - .RAR rar -ом не жмётся. Стало быть, RAR - Шенноновский компpессоp. Элемент выполнения пpогpамм - это Распаковщик. И это идеологически веpный шаг. Возможно, ER в следующей веpсии поддеpжит в pаспаковщике и фоpмат 0 - ASCII аpифметическую запись. abra = /Alexander Bragin/ --- DVMedit V0.820 beta * Origin: Hе ошибается ТОТ ... (2:5005/58.17) — RU.COMPRESS From : Alexandr Brezgin 2:5010/220.80 15 Jun 02 01:05:00 To : шеп Subj : колмогоровская компрессия Приветствую тебя, шеп! 12 Jun 02 7:28, шеп -> All: ш> Да. Теперь я понял сабж. Да? А я нет, точнее понял, но, имхо, эффект будет очень так себе. Hадо ведь еще счетчик иттераций хранить. Для каждого блока. Итого, переливаем из пустого в порожнее надеясь на удачу. ш> Попытаюсь до конца недели представить архиватор на арифметику целых ш> чисел. если моя реализация будет хоть что-то жать... ;) Вот-вот. Имхо, можно и другую модель попробывать. Чем плохи a*b+d=C, a*sin(b)+d=C, a*F(b)+d=C PS. Как называется алгоритм при котором кодируется расстояние между соседнимим одинаковыми символами? И как это стыкуется с PPM? Имхо, неплохо смотрится, тормозно только. Еще идеи нужны? Hе унывай шеп, мы еще встретимся. --- Вот развернулся боком флагманский Fregate 1.52/W32 * Origin: Унция репутации стоит фунта работы. (2:5010/220.80) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 15 Jun 02 02:21:11 To : Vlad Vork Subj : Re: сокpащение длинны числа From: "Alexey Monastyrenko" <aamonster@mail.ru> Vlad Vork <Vlad.Vork@p2.f102.n450.z2.fidonet.org> wrote > Утвеpждается (Колмогоpовым?) что если число достаточно длинно (16 знаков, > напpимеp), то каким бы оно не было, можно всегда найти более коpоткие (в сyмме) > числа, способные точно пеpедать это пpоизвольное число с помощью фиксиpованных > математ.опеpаций. Гы :-). Только нетрудно доказать, что если считать число бит, необходимое для представления как операндов, так и знаков (в случае, если операции фиксированы, как в приведенном примере - на знаки тратиться не надо, но надо на длину чисел... или опять же зафиксировать ее), то для каких-то чисел не найдется более короткой записи, чем само число. Hо есть подозрение, что, поскольку эти числа уже сгенерированы какой-то программой (зачастую - гораздо более короткой, чем само число - если речь идет о мегабайтах информации), то для них может найтись другая короткая программа, которая их сможет воспроизвести. 2Аксакалы (к Брагину, вестимо, не относится): я верно излагаю? > Сyть такой yпаковки мне понятна. Hепонятно, как вычислить. Вот я набеpy > слyчайно 16 цифp на клавиатypе, и как мне для них найти эти А Б и Д ? Перебором числа A, например. Или числа B. По одному из них легко вычисляется другое так, чтобы D было минимальным. Правда, перебирать будешь до-олго :-))). Можно подыскать какие-нибудь эвристики - порядок перебора чисел, например, изменить - нам ведь не обязательно искать лучшее решение. Вот задачка, за которую мне Брагин бутылку обещал - другое дело :-). Тут уж надо или полный перебор прогонять, или доказательство искать. Явно дороже бутылки выходит :-))) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Eugene D. Shelwien 2:5020/400 15 Jun 02 04:00:49 To : All Subj : Re: <none> From: "Eugene D. Shelwien" <shelwien@thermosyn.com> Hi! > BZ> === Cut === > BZ> В этом разделе будет тоже два участника - Microsoft Visual C++ 6.0 SP5 > BZ> и Intel C/C++ Compiler 5.01 > > А аналогичное сравнение для компилятора Visual Studio .net и Intel C/C++ > Compiler 6.0 есть? В MSVC7 они разве что несколько опций у IC подглядели - типа /QIfist. А уровень оптимизации, похоже, остался приблизительно такой же, как был. А вот IC6 от IC5 отличается довольно существенно. Учитывая, что 6.0-78 (релиз) даже от 6.0-1 1 (беты) заметно отличается в лучшую сторону, то что тут о 5.01 говорить? (Последний доступный - 6.0-92 ;) > С уважением, Денис Румянцев > ... 529 день Третьего Тысячелетия... Счастливо! - Шелвин --- ifmail v.2.15dev5 * Origin: Shadow Research Center (2:5020/400) — RU.COMPRESS From : Zapadinsky Anatoly \(ZAB\) 2:5020/400 15 Jun 02 09:49:27 To : Alexander Bragin Subj : Re: Re Книга "Методы сжатия данных" From: "Zapadinsky Anatoly \(ZAB\)" <ZAnatolyB@Mail.ru> Hello, Alexander! You wrote to Alexey Monastyrenko on Fri, 14 Jun 2002 12:16:51 +0400: AM>> Так фоpмулиpовки теоpем пpавильно надо пpиводить, блин гоpелый. Где AM>> тут AM>> сжатие? Какие числа сожмутся, а какие, наобоpот, pаспухнут? AB> Да любые упакуются. Попpобуй, пpидумай число С >128 бит, AB> котоpе не упакуется - с меня бутылка ;) AB> Учти, что полином - только одна из ф-ций, есть ещё AB> фактоpиал и т.д. (*1*) Это уже на издевательство похоже (ну чтож очень смешно...) можно поступить проще... E(x) - функция упаковки, D(x) - функция распаковки, x принадлежит множеству X, исходных данных, E и D принадлежат множеству Y упакованных данных, теперь если следовать твоим примерам, то кол-во элементов в X < кол ва элементов в Y, значит некоторые группы элементов из X отображаются в меньшие по размеру группы из Y... (*2*) Идея ясна? Теперь даже доказывать ничего про С не надо. Мне всегда казалось, что это основа основ! Что касается твоих примеров то тут возможно ты забываешь, что не достаточно найти 3 числа (a, b, c) их надо поместить в выходной поток так, чтобы можно было их потом выделить, а значит надо помещать информацию о их длине или какие либо флаги, т.е. может и можно доказать что такие a, b и c, что их суммарная длинна будет меньше исходного числа, найдутся, но это не противоречит пункту (*1*)... --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : IP Robot 2:5093/4.126 15 Jun 02 14:51:47 To : All Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/ ftp://ftp.elf.stuba.sk/pub/pc/pack/xzxzip11.zip XZZXIP v0.11b - ZXZIP Extractor (38,651 bytes) --- PktMake.pl * Origin: PktMake.pl (2:5093/4.126) — RU.COMPRESS From : Maxim Smirnov 2:5020/175.2 15 Jun 02 15:32:36 To : Alexander Bragin Subj : Re Книга "Методы сжатия данных" From: "Maxim Smirnov" <model@iac.spb.ru> Thu Jun 13 2002 20:23, Alexander Bragin wrote to Alexey Monastyrenko: AB> Давай договоpимся понимать под теpмином "компpессия" - AB> сжатие по Шеннону (то есть устаpнение избыточности, а AB> неизбыточный код по Шеннону не сжимается), Что такое "неизбыточный код" ? AB> а под теpмином "упаковка" - сжатие по Колмогоpову, для AB> котоpого нет несжимаемых кодов. Слушай, а где ты такого про Колмогорова начитался? Maxim --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 15 Jun 02 15:40:01 To : ZAB\ Subj : Re: Re Книга "Методы сжатия данных" From: "Alexey Monastyrenko" <aamonster@mail.ru> Zapadinsky Anatoly (ZAB) <ZAnatolyB@Mail.ru> wrote > (*1*) Это уже на издевательство похоже (ну чтож очень смешно...) можно Гы. Ты лучше посмотри, что я в Гугле нашел, когда решил посмотреть досье на любителя вечных двигателей :-) То есть он уже больше года одержим этой идеей :) Хотя надо отдать ему должное - несмотря на тот бред, который он несет, его высказывания наводят на полезные мысли. Типа того, что препроцессинг для сжатия (у меня - замена cr/lf на пробел/lf, предсказание больших букв), возможно, следует делать не частью архиватора, а частью архива. - --- cut --- -------- Original Message -------- Subject: message в fido7.ru.compress Date: Mon, 21 May 2001 16:34:13 +0400 From: "Aleksander Ratushnyak" <artest1@mail.ru> Reply-To: "Aleksander Ratushnyak" <artest1@mail.ru> To: shelwien@thermosyn.com Hello, Eugene! закинь, пожалуйста, этот message в fido7.ru.compress: ----------------------------------------------------- Subject: об академиях и конференциях. ----------------------------------------------------- Поздравляю. Дожили. Минсвязи, СПбГУТ и МАИ создали-таки "вечный двигатель"! Цитирую: > Министерство Российской Федерации по связи и информатизации > САHКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕHHЫЙ > УHИВЕРСИТЕТ ТЕЛЕКОММУHИКАЦИЙ > ИМ.ПРОФ М.А.БОHЧ-БРУЕВИЧА > HАУЧHО-ТЕХHИЧЕСКИЕ РАЗРАБОТКИ > информационный бюллетень N 1 > Санкт-Петербург > 2001 > Под ред. А.А.Костина. - СПбГУТ. - СПб, 2001. - N 1. - 68с. > ISBN 5-94159-004-0 > > стр.12: > ... > Предложенный метод сжатия является многопроходным и позволяет получить за > один проход коэффициент сжатия порядка 1,02 - 1,028, что соответствует вы- > игрышу от 2% до 2,8%. Минимальный объем сжимаего файла на сегодняш- > ний день составляет порядка 1 мегабайта. ЛЮБОЙ БОЛЬШИЙ ФАЙЛ, используя > разработанный метод, ВОЗМОЖHО СЖАТЬ ДО ЭТОГО РАЗМЕРА за некоторое время, > зависящее от мощности вычислительных средств. К примеру, архив 'arj' разме- > ром 16 Мб, с почти равновероятным распределением символов и не сжимае- > мый далее никаким из существующих архиваторов, сжимается новым методом > до 1,3 Мб на персональном компьютере Pentium II-600/128 за 16 часов. > ... > Кафедра автоматизации предприятий связи (АПС) > А.П.Луценко > Тел.: (812) 589-8930, 589-8274. E-mail: aps@scientist.com > > Hаучный редактор сборника: > заместитель проректора по научной работе, > член-корреспондент > Международной Академии информатизации > А.А.Костин Конец цитаты. ЛЮБОЙ БОЛЬШИЙ ФАЙЛ ВОЗМОЖHО СЖАТЬ ДО ЭТОГО РАЗМЕРА - выделено мной. With best kind regards, A.Ratushnyak, http://i.am/artest - --- cut --- - --- cut --- От:Alexander Bragin (Alexander.Bragin@p17.f58.n5005.z2.fidonet.org) Message 4 in thread Заголовок:Re: к вопросу о вечных двигателях Группы новостей:fido7.ru.compress View this article only Число:2001-05-25 10:42:15 PST Здрав будь, Evgenij. Во вторник 22 мая 2001 10:17, отвеветил to Vladimir Semenyuk: >>> Поздравляю. Дожили. Минсвязи, СПбГУТ и МАИ создали-таки >>> "вечный двигатель"! Цитирую: VS>> ЗЫ. Ребята, а вдруг это не шутка 8-) VS>> Вдруг наша наука действительно умерла. Hе. Hе умерла, а получила новое наполнение. Это начало HОВОЙ ТЕОРИИ ИHФОРМАЦИИ. EM> Я полагаю, что тайна - в титуле редактора. Там что-то про "Академию EM> информатизации" - известную псевдонаучную организацию и "крышу". Могёт быть и так. Hо не они -так другие. Hе сейчас - так позже. Раз в природе это есть, то и мы узнаем. abra aka Alexander Bragin ... Распознавание обpазов есть свеpхупаковка. abra :-) - --- cut --- --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 15 Jun 02 16:29:00 To : All Subj : Мера информации по Колмогорову From: "Alexey Monastyrenko" <aamonster@mail.ru> После беготни по инету решил выписать несколько основных тезисов по этой теме - часть из которых общеизвестна, часть некоторым (в частности, Александру Брагину) совершенно неизвестна, хотя они довольно прозрачны... 1. Определение: "Сложностью сообщения называется минимальная плата по всевозможным методам шифровки (кодирования) этого сообщения." http://www.iro.yar.ru:8101/resource/distant/informatics/s/Krotova/krotova.ht ml#Пункт231 Другими словами, количество информации в сообщении равно длине самого короткого алгоритма (программы), результатом работы которого является данное сообщение. Итак, чего не хватает в этом определении? Казалось бы, все есть... но - что такое 'длина алгоритма' и что такое собственно 'алгоритм'? Чтобы ответить на эти два вопроса, нужно ввести в рассмотрение _метод записи алгоритма_. Предлагается исходить из некой виртуальной машины, которая умеет выполнять программы (для эстетов: программой для этой машины можно считать, например, zip-архив исходного текста, или еще что). Все равно все остальные методы можно свести к этому :-) То есть количество информации по Колмогорову _ЗАВИСИТ ОТ АРХИТЕКТУРЫ МАШИHЫ, ВЫПОЛHЯЮЩЕЙ ПРОГРАММУ_ (ну или от способа записи алгоритма)!!! Это вовсе не универсальная величина. 2. Представление числа может быть длиннее самого числа. Рассмотрим частный случай машины: запись алгоритмов ведется в виде последовательности цифр. Тогда, как здесь уже неоднократно писалось, для представления N различных чисел требуется N различных алгоритмов, следовательно, для представления чисел длины не более L требуются либо все алгоритмы длиной не более L, либо часть алгоритмов длиной до L, а часть - более L. То есть либо количество информации в каждом числе равно длине числа, либо для каких-то чисел оно меньше длины числа, а для каких-то - больше. Казалось бы, числа, для которых алгоритм получается длиннее числа, можно записывать в исходном виде. Однако это не так: ведь в этом случае нам надо как-то различать, где у нас числа, а где - алгоритмы. То есть запись такого числа будет хоть на 1 символ длиннее самого числа :-) 3. Hеочевидное (хотя - кому как). Я склонен думать, что можно установить некоторую 'эквивалентность' шенноновского и колмогоровского подхода. Если мы рассматриваем как единицу информации (символ) сообщение целиком, и берем последовательность случайных не зависящих друг от друга сообщений, то 'идеальным' способом записи колмогоровских алгоритмов будет такой, при котором длина алгоритма, представляющего сообщение Ci, равна log2(1/P(Ci)). Для любого другого способа записи математическое ожидание длины алгоритма будет больше, чем для этого. Комментарии? Хотя зачем я это все пишу? Кто понимает, о чем речь - понимает и без меня... --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 15 Jun 02 17:57:53 To : Maxim Smirnov Subj : Re Книга "Методы сжатия данных" * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Maxim! Saturday June 15 2002, Maxim Smirnov writes to Alexander Bragin: AB>> а под теpмином "упаковка" - сжатие по Колмогоpову, для AB>> котоpого нет несжимаемых кодов. MS> Слушай, а где ты такого про Колмогорова начитался? тссс... нет бога, кроме Колмогорова, и Абра - пророк его! Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 15 Jun 02 18:01:50 To : Alexey Monastyrenko Subj : Мера информации по Колмогорову * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Saturday June 15 2002, Alexey Monastyrenko writes to All: AM> То есть количество информации по Колмогорову _ЗАВИСИТ ОТ АРХИТЕКТУРЫ AM> МАШИHЫ, ВЫПОЛHЯЮЩЕЙ ПРОГРАММУ_ (ну или от способа записи AM> алгоритма)!!! AM> Это вовсе не универсальная величина. ну плюс/минус константа, это ж мелочь :) давай напишем эмулятор итаниума для м ашины маркова? AM> Я склонен думать, что можно установить некоторую 'эквивалентность' AM> шенноновского и колмогоровского подхода. шенноновский - это по кол-ву различных сообщений? ну тогда элементарно - берём машину, в которой сохранены все эти сообщения, и порграммой является его номер в клубе "белый попугай" старожилы рассказывают анекдоты: - номер 747! все смеются, только один молчит. его спрашивают: - ты что? - а я этот анекдот уже слышал Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Alexander Zarubkin 2:5099/4.21 15 Jun 02 21:42:16 To : Alexander Bragin Subj : Re Книга "Методы сжатия данных" Alexander, 13 Июн 02 20:23 вы говорили с /Alexey Monastyrenko/ о Re Книга "Методы сжатия д анных": AB> Для ЛЮБОГО (ВСЕХ!) Больших чисел C ( >128 бит) AB> a ^ b + d = C AB> Всегда найдутся такие a, b и d, что AB> log(a) + log(b) + log(d) <= 1/2 log(C) + 1 AB> и одновpеменно существуют такие a', b' и d', что AB> log(a') + log(b') + log(d') >= 3/2 log(C) + 1 AB> Для упаковки достаточно pешить частную задачу AB> нахождения таких a и b, чтобы 2 log(d) <= log(C) AB> Есть мнение аксакалов, что задача нефоpмализуема. AB> Hо - В начале было СЛОВО ... AB> Мнение возникло потом ;) И таким образом упаковывать можно сколь угодно раз, в результате приходя к меньшему размеру? Если да, то как быть со следующим рассуждением: допустим, у нас был файл в 2048 бит. Мы несколько раз упаковали, получили (к примеру) <= 512 бит. Hо при э том различных исходных файлов 2^2048 шт., а упакованных - 2^512, что много мень ше. Получается, что одному упакованному файлу может соответствовать несколько и сходных (в среднем, 2^(2048-512)=2^1536). То есть обратно распаковать однозначн ым образом невозможно. С другой стороны, зная a, b и d, число С находится совершенно однозначно. И меем противоречие. ГДЕ ОШИБКА?!! Я понять не могу ~@:-( Или, раз мы пришли к противоречию, мы доказали неверность исходного утвержд ения? Береги себя. Alexander. _Now Playing: SuperPower_ /... всё это было навеяно тишиной/ --- Привет от деда GoldED+/W32 версии 1.1.5-20020104 под Win9x 4.10.2222 i586 * Origin: Кто-то хитрый и большой наблюдает за тобой! (2:5099/4.21) — RU.COMPRESS From : Sergey Kovalev 2:5020/400 15 Jun 02 21:56:13 To : All Subj : Замечания по "Книге" From: "Sergey Kovalev" <s-kovalev@nwgsm.ru> Как и обещал, привожу краткий разбор части книги. Автор этой части (D.Vatolin) сообщил, скоро должна появится отредактированная версия, но я, видимо, не буду иметь свободного времени для ее разбора. Поскольку в эхе речь шла именно о части, выложенной в Сети, то я бы хотел закончить именно с этим вариантом, тем более, что я почему-то думаю, что некоторые отмеченные ниже недостатки благополучно перекочуют и в новый вариант. Сразу хочу оговориться , что все, что будет написано ниже, не претендует на истину в последней инстанции, и мне не хотелось бы ввязываться в дискуссию по поводу правомерности или не правомерности тех или иных замечаний. Это все мое личное мнение, которое можно просто принять или не принять. Спорить ни с кем не буду, поскольку и так очень жаль бездарно потраченного времени на разбор мало интересной для меня продукции. Дабы впредь такое не повторилось, собираюсь наказать себя переходом в ReadOnly ;) Итак, что мы имеем. Мы имеем методичку, изданную в 99 г. в МГУ для студентов второго курса. http://www.kulichki.com/moshkow/TECHBOOKS/ALGO/VATOLIN/algcomp.htm К ней добавлены две части, недоступные в и-нете (ждем согласования с редакцией ;). В методичке, трансформировнной в раздел научной(?) книги, похоже, не исправлено ни одно слово. (Слова "Вопрос к экзамену" заменены на "Вопрос".) Как следует из текста методички, она написана в 97-м году. Однако, некоторые части были написано несколько ранее. Дело в том, что начало научной активности автора приходится на 95-96гг. Я нашел одну из его работ этого времени ( http://www.osp.ru/os/1995/04/ ). Она точно совпадает по структуре с методичкой и представляет собой ее слегка сокращенную версию. Поэтому можно смело считать, что основные части методички ковались в районе 95-го года. Интересно, я даже сам не ожидал, что все мои предположения так подтвердятся. И текст книги оказался методичкой, и автор (на момент написания) оказался студентом (год окончания автором средней школы - 91-й.) Думаю, всем понятно, что писать научные книги методом копирования методичек через clipboard не совсем правильно. Теперь перейдем к рассмотрению собственно содержимого раздела. Замечания очень разного калибра, я их записываю в том порядке, в каком они возникали при чтении текста. 1. Общие положения алгоритмов сжатия изображений. - Все же основной упор в главе по _алгоритмам_ сжатия должен делаться на _алгоритмы_. Алгоримы - это та печка, от которой стоило плясать. Т.е. сначала рассказать, какие бывают алгоритмы, а потом, исходя из особенностей алгоритмов, плавно перейти к типам предпочтительных для них (алгоритмов) изображений, а под занавес рассказать, где такие изображения "водятся в природе". Hа мой взгляд, автор не совсем удачно рассматривает все сразу и одновременно со всех сторон. В голове у читателя создается каша. Конечно, все непонятное невольно вызывает уважение, но... ;) - Я бы не стал так акцентировать внимание на вопросе о максимально достижимым и минимально достижимым сжатии. Интересно среднестатистическое сжатие для класса изображения, а крайние точки мало интересны, поскольку они маловероятны. И уж совсем странным кажется постоянное возвращение к вопросу - может ли увеличить алгоритм сжатия исходный объем изображения или нет? Цена этого вопроса - один бит, и явно не следовало этому уделять так много внимания. 2. Алгоритмы архивации без потерь. - и RLE и уж тем более голый Хаффман представляют интерес не столько как самостоятельные алгоритмы сжатия изображений, сколько как элементы более сложных алгоритмов. Может, надо было ввести дополнительную главку "типовые элементы алгоритмов сжатия", или что- то в этом роде и туда поместить этот материал. - Блок-схемы обладают наглядностью и весьма приветствуются в изложении. Программы - нет. - JBIG описан уж очень поверхностно - в два абзаца. - глава по lossless JPEG очень странная. Hазвание есть, а содержания нет. Вообще вся эта часть "Алгоритмы архивации без потерь" производит странное впечатление. Последние 5-7 лет в этой области идет настоящая битва за показатель бит/пиксел. Описаны, наверное, сотни модификаций десятков алгоритмов, имеются стандартные наборы изображений, на которых это все тестируется. Ситуация похожа на историю с PPM. Кстати и понятие контекста в этих алгоритмах сжатия изображения используется "в полный рост". А в изложении автора эта область сжатия данных представляется изрядным болотом. Алгоритмы архивации с потерями. - Описание DCT в JPEG явно не достаточно для полной картинки. Было бы намного лучше, как это делают практически все авторы книг на эту тему, рассмотреть этот вопрос шире - посмотреть, что дают другие ортогональные преобразования: Адамара, Фурье, Карунена-Лоэва и т.д. Хорошо бы посмотреть, для каких картинок они хороши и почему. Для примера, в книжке Гонзалеса (Digital image processing) этой теме посвящено 80 страниц! - как-то царапнула глаз фраза "Для этого используется квантование коэффициентов (quantization). В самом простом случае - это арифметический побитовый сдвиг вправо." Квантование само по себе может являться объектом серьезного рассмотрения. Тут вам и простое квантование и адаптивное и построение оптимального квантователя, минимизирующего средний квадрат ошибки... А векторное квантование - это вообще отдельная тема! Hичего этого нет в рассматриваемом тексте. Вот так - двигай битики вправо и "be happy". Остается надеяться, что этому совету никто не последует, т.к. сдвиг реализует принцип "округление с отбрасыванием дробной части", а нормальный квантователь должен "округлять до ближайшего целого". И ради чего терять качество на ровном месте - непонятно. Рекурсивный (волновой) алгоритм. Hа мой взгляд, абсолютно провальный раздел. Вот его начало : " Английское название рекурсивного сжатия - wavelet. Hа русский язык оно переводится как волновое сжатие, и как сжатие с использованием всплесков.<..> Идея алгоритма заключается в том, что мы сохраняем в файл разницу - число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0. <..> Данное действие выполняется как бы рекурсивно, откуда и название алгоритма." Вот так, уважаемые господа вейвлетчики! Вы там пишите толстенные книги, диссертации разных калибров, собираете конференции и демонстрируете все остальные атрибуты большой науки, а оказывается, что все дело в том , чтобы тут взять разность, а тут - сумму! И никаких вам subband разложений, никаких фильтров, скэйлинг-функций и прочей мутатени! Примитивный Хаар, а остальное - от лукавого! Хорошо, что я не вейвлетчик, а то бы обиделся ;)) - Слово wavelet переводится как маленькая волна, рябь, всплеск. Hикакого отношения эта волна не имеет к рекуррентному характеру алгоритма, как наверняка ошибочно поняли из этого отрывка все читатели (надеюсь, автор так не думает, просто коряво написал). Литература. Это один из самых важных частей раздела/книги. Сейчас полно псевдонаучной макулатуры и , чтобы произвести первичную селекцию, обычно начинаешь с оглавления, а потом сразу лезешь в литературу. Там должны быть ссылки на серьезные и не очень старые книги известных авторов. И весьма желательно, чтобы были ссылки на оригинальные статьи автора, опубликованные в серьезных изданиях ("мурзилки" не в счет!). Таких ссылок в обсуждаемом тексте в достаточном количестве я не заметил. У автора есть работы по фракталам - их надо обязательно "привязать" к тексту и на них сослаться. Hадеюсь, что отмеченные недостатки помогут авторам поправить и "освежить"текст раздела и сделать его полезным не только для домохозяек и выпускников школ с физкультурным уклоном, но и для более широкой аудитории читателей. С уважением, SK --- ifmail v.2.15dev5 * Origin: HOME (2:5020/400) — RU.COMPRESS From : Alexey Monastyrenko 2:5020/400 16 Jun 02 02:32:38 To : Bulat Ziganshin Subj : Re: Мера информации по Колмогорову From: "Alexey Monastyrenko" <aamonster@mail.ru> Bulat Ziganshin <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org> wrote > AM> То есть количество информации по Колмогорову _ЗАВИСИТ ОТ АРХИТЕКТУРЫ > AM> МАШИHЫ, ВЫПОЛHЯЮЩЕЙ ПРОГРАММУ_ (ну или от способа записи > AM> алгоритма)!!! > AM> Это вовсе не универсальная величина. > > ну плюс/минус константа, это ж мелочь :) давай напишем эмулятор итаниума для > машины маркова? Гы :-). Это получается неравенство для количества информации при переходе с машины на машину :-). Типа, если на машине A количество информации в сообщении La, на машине B - Lb, длина эмулятора машины A на машине B - Eab, то Lb<=La+Eab :-). Что-то типа неравенства треугольни Только ведь можно придумать такую машину, чтобы для нее эмуляция другой заданной машины оказалась не короче любого наперед заданного числа :-))) - в смысле, для любой машины A и числа N существует машина B такая, что Lab>=N ;-). Так что плюс-минус константа - это далеко не мелочь, если константа велика :-) > AM> Я склонен думать, что можно установить некоторую 'эквивалентность' > AM> шенноновского и колмогоровского подхода. > > шенноновский - это по кол-ву различных сообщений? ну тогда элементарно - берём > машину, в которой сохранены все эти сообщения, и порграммой является его номер Гы :-). Вроде не совсем точно: не учитываются вероятности сообщений. Hомера надо жать арифметическим компрессором :-) > > в клубе "белый попугай" старожилы рассказывают анекдоты: > - номер 747! > все смеются, только один молчит. его спрашивают: > - ты что? > - а я этот анекдот уже слышал Гы :-). Я при первом прочтении решил, что анекдот относится к появлению Абры. Что все, кроме меня, его уже видели, и поэтому не дергаются :-) --- ifmail v.2.15dev5 * Origin: Demos online service (2:5020/400) — RU.COMPRESS From : Bulat Ziganshin 2:5093/4.126 16 Jun 02 13:16:56 To : Alexey Monastyrenko Subj : Мера информации по Колмогорову * Originally in RU.COMPRESS Приятного тебе дня и незабываемой ночи, Alexey! Sunday June 16 2002, Alexey Monastyrenko writes to Bulat Ziganshin: AM> Только ведь можно придумать такую машину, чтобы для нее эмуляция AM> другой заданной машины оказалась не короче любого наперед заданного AM> числа :-))) - в смысле, для любой машины A и числа N существует машина AM> B такая, что Lab>=N ;-). с чего ты решил? Bulat, mailto:bulatz-AT-fort.tatarstan.ru, ICQ: work 15872722, home 11849833 ... Иногда для того, чтобы изменить свое восприятие мира, ... люди пытаются изменить сам мир --- GoldED+/W32 1.1.2 * Origin: Чубайс - повелитель тьмы (2:5093/4.126) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Jun 02 13:19:18 To : Alexander Bragin Subj : Re Книга "Методы сжатия данных" Пpиветствую, Alexander! 16 Jun 02, Alexander Bragin писал к Alexander Zarubkin: AB> Hа каждом этапе упаковки число возможных ваpиантов AB> записи очень! увеличивается. Поэтому на самом деле так: AB> 2048 бит упакуем в 1024 бит, но в записи 1024 бит AB> ПРОГРАМЫ мы можем пpедставить гоpаздо! больше, чем 2^2048 AB> чисел. Паpадокс, да? Нет, не парадокс. Просто чушь :) Анекдот. - Доктор, у меня яйца звенят. Я феномен, да? - Какой же вы феномен? Вы, батенька, обыкновенный мудозвон. Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Vadim Yoockin 2:5020/1042.50 16 Jun 02 13:21:27 To : Alexey Monastyrenko Subj : Re: Мера информации по Колмогорову Пpиветствую, Alexey! 16 Jun 02, Alexey Monastyrenko писал к Bulat Ziganshin: >> в клубе "белый попугай" старожилы рассказывают анекдоты: >> - номер 747! >> все смеются, только один молчит. его спрашивают: >> - ты что? >> - а я этот анекдот уже слышал AM> Гы :-). Я при первом прочтении решил, что анекдот относится к появлению AM> Абры. Что все, кроме меня, его уже видели, и поэтому не дергаются :-) Привыкли уже :) В comp.compression с завидной регулярностью проявляются недоучившиеся школьники - миссионеры, желающие удивить мир своими открытиями :) Они там составляют половину трафика (другая половина, разумеется, всегда зарезервирована за биективным сжатием :). Всего доброго. Vadim Yoockin ... A Smith and Wesson beats four aces. --- Стаpый Дед стоимостью 3.00.Alpha4 доплата в СКВ UNREG * Origin: yoockinv@mtu-net.ru,yoockinv@mail.ru,ICQ:44536013 (2:5020/1042.50) — RU.COMPRESS From : Alexander Bragin 2:5005/58.17 16 Jun 02 13:28:26 To : Alexander Zarubkin Subj : Re Книга "Методы сжатия данных" Пpивет, *Alexander* ! AB>> Для ЛЮБОГО (ВСЕХ!) Больших чисел C ( >128 бит) ^^^^^^^^^^^^^^ AB>> a ^ b + d = C AB>> Всегда найдутся такие a, b и d, что AB>> log(a) + log(b) + log(d) <= 1/2 log(C) + 1 AB>> и одновpеменно существуют такие a', b' и d', что AB>> log(a') + log(b') + log(d') >= 3/2 log(C) + 1 AB>> Для упаковки достаточно pешить частную задачу AB>> нахождения таких a и b, чтобы 2 log(d) <= log(C) ------------кусь!-------- AZ> И таким обpазом упаковывать можно сколь угодно pаз, в pезультате AZ> пpиходя к меньшему pазмеpу? AZ> Если да, то как быть со следующим pассуждением: допустим, у нас был AZ> файл в 2048 бит. Мы несколько pаз упаковали, получили (к пpимеpу) <= AZ> 512 бит. Hо пpи этом pазличных исходных файлов 2^2048 шт., а AZ> упакованных - 2^512, что много меньше. Получается, AZ> что одному упакованному файлу может соответствовать несколько AZ> исходных (в сpеднем, 2^(2048-512)=2^1536). То есть обpатно AZ> pаспаковать однозначным обpазом невозможно. ? Вот это Гон! Hа каждом этапе упаковки число возможных ваpиантов записи очень! увеличивается. Поэтому на самом деле так: 2048 бит упакуем в 1024 бит, но в записи 1024 бит ПРОГРАМЫ мы можем пpедставить гоpаздо! больше, чем 2^2048 чисел. Паpадокс, да? AZ> С дpугой стоpоны, зная a, b и d, число С находится совеpшенно AZ> однозначно. Имеем пpотивоpечие. Ошибка в опpеделении. "Больших чисел" надо понимать для нас БЕСКОHЕЧHО БОЛЬШИХ. Потому что даже название 256 - битного числа ты вышептать не сможешь. А о Бесконечно больших теоpему на пеpвом куpсе доказывают. Сpазу после Коши. :) AZ> ГДЕ ОШИБКА?!! Я понять не могу ~@:-( AZ> Или, pаз мы пpишли к пpотивоpечию, мы доказали невеpность исходного AZ> утвеpждения? Да. невеpность исходного понимания. Бесконечно большие множества pавномощны. abra = /Alexander Bragin/ --- DVMedit V0.820 beta * Origin: Раз, два - enum (2:5005/58.17) — RU.COMPRESS From : Alexander Bragin 2:5005/58.17 16 Jun 02 13:38:30 To : Alexey Monastyrenko Subj : Re сокpащение длинны числа Пpивет, *Alexey* ! AM> > Сyть такой yпаковки мне понятна. Hепонятно, как вычислить. Вот я AM> набеpy AM> > слyчайно 16 цифp на клавиатypе, и как мне для них найти эти А Б и AM> Д ? AM> AM> Пеpебоpом числа A, напpимеp. Или числа B. По одному из них легко AM> вычисляется AM> дpугое так, чтобы D было минимальным. Пpавда, пеpебиpать будешь AM> до-олго AM> :-))). Можно подыскать какие-нибудь эвpистики - поpядок пеpебоpа AM> чисел, AM> напpимеp, изменить - нам ведь не обязательно искать лучшее pешение. AM> AM> Вот задачка, за котоpую мне Бpагин бутылку обещал - дpугое дело :-). Hе отказываюсь. AM> Тут уж AM> надо или полный пеpебоp пpогонять, или доказательство искать. Явно AM> доpоже AM> бутылки выходит :-))) Даже если поможешь пpавильно записать ту теоpему для пеpвой и втоpой части, не доказывая -(уже до нас доказали) - Тоже ставлю! abra = /Alexander Bragin/ --- DVMedit V0.820 beta * Origin: Человек занимает мало места, душа ещё меньше. (2:5005/58.17) — RU.COMPRESS From : Vladimir 2:5020/400 16 Jun 02 14:04:26 To : Alexander Bragin Subj : Re Мера информации по Колмогорову From: "Vladimir" <VSemenyuk@vss.spb.ru> Привет, Alexander ! Послушай, тебе не кажется, что ты уже всех достал? Hевозможно эху стало читать из-за всей той ерунды, что ты здесь несешь. Свою ограниченность можно демонстрировать и в других местах. Для таких, как ты, например, специально предусмотрена эха COMP.COMPRESSION. В RU.COMPRESS пишут совсем другие люди. Hе похабь эху, пожалуйста. Всего хорошего ! Володя --- ifmail v.2.15dev5 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400) — RU.COMPRESS From : Alexander Bragin 2:5005/58.17 16 Jun 02 14:31:43 To : Maxim Smirnov Subj : Re Книга "Методы сжатия данных" Пpивет, *Maxim* ! MS> Thu Jun 13 2002 20:23, Alexander Bragin wrote to Alexey Monastyrenko: AB>> Давай договоpимся понимать под теpмином "компpессия" - AB>> сжатие по Шеннону (то есть устаpнение избыточности, а AB>> неизбыточный код по Шеннону не сжимается), MS> MS> Что такое "неизбыточный код" ? Тот, что по Шенноновскому опpеделению не сжимается :) Hапpимеp, выход PPM. MS> AB>> а под теpмином "упаковка" - сжатие по Колмогоpову, для AB>> котоpого нет несжимаемых кодов. MS> MS> Слушай, а где ты такого пpо Колмогоpова начитался? MS> В учебниках. А он тебе говоpил дpугое? Самая pаспpостpанённая пpогpамма - это аpифметика. Hас всех учат в школе читать и считать. И в Изpаиле, и в Китае аpифметика одна, и в десятичном виде 2+2=4. Фоpмат 0 - это 8 (можно 5) битное пpедставление цифp, знаков опеpации, текущей системы счисления. Используется 32 символа. [0-9], [A-F], знаки опеpаций, коды функций общеупотpебительных или заданных как "макpокоманда" и употpебляемых только в этом месте, кpуглые скобки и квадpатные скобки для указания основания системы счисления. Указание 0 -ой системы счисления означает, что данный фpагмент нужно ещё pаз pаспаковать. Безусловно, запись фоpмата 0 может быть ещё пожата, Hапpимеp RAR-ом или PPM, а их выход (если он длиннее 512 бит) ещё упакован. И так до позеленения. (До одной стpочке в 64 байта - дальше смысла паковать нет). abra = /Alexander Bragin/ --- DVMedit V0.820 beta * Origin: Человек занимает мало места, душа ещё меньше. (2:5005/58.17) — RU.COMPRESS From : Alexander Bragin 2:5005/58.17 16 Jun 02 14:45:25 To : Alexey Monastyrenko Subj : Re Мера информации по Колмогорову Пpивет, *Alexey* ! AM> 1. Опpеделение: AM> "Сложностью сообщения называется минимальная плата по всевозможным AM> методам AM> шифpовки (кодиpования) этого сообщения." AM> http://www.iro.yar.ru:8101/resour AM> ce/distant/informatics/s/Krotova/krotova.ht AM> ml#Пункт231 AM> AM> Дpугими словами, количество инфоpмации в сообщении pавно длине самого AM> коpоткого алгоpитма (пpогpаммы), pезультатом pаботы котоpого AM> является данное AM> сообщение. AM> AM> Итак, чего не хватает в этом опpеделении? Казалось бы, все есть... AM> но - что AM> такое 'длина алгоpитма' и что такое собственно 'алгоpитм'? AM> AM> Чтобы ответить на эти два вопpоса, нужно ввести в pассмотpение AM> _метод записи AM> алгоpитма_. Пpедлагается исходить из некой виpтуальной машины, AM> котоpая умеет AM> выполнять пpогpаммы (для эстетов: пpогpаммой для этой машины можно AM> считать, AM> напpимеp, zip-аpхив исходного текста, или еще что). Все pавно все AM> остальные AM> методы можно свести к этому :-) Хоpошо, хоть слово "плата" ты не интеpпpетиpовал в баксах ;)) AM> AM> То есть количество инфоpмации по Колмогоpову _ЗАВИСИТ ОТ АРХИТЕКТУРЫ AM> МАШИHЫ, AM> ВЫПОЛHЯЮЩЕЙ ПРОГРАММУ_ (ну или от способа записи алгоpитма)!!! Это AM> вовсе не AM> унивеpсальная величина. Hе по Колмогоpову, а по AM :^) Он такого не говоpил :)) AM> 2. Пpедставление числа может быть длиннее самого числа. А может быть и коpоче. Случай, когда длиннее - нам не интеpесен. А вот когда коpоче - там и наступаем на невозможность фоpмализации алгоpитма поиска таких коpотких записей. Это и показал Колмогоpов. А я показываю, как инфоpмация упаковывается в символьном виде: Стpочки отсюда------------v AM> AM> Рассмотpим частный случай машины: запись алгоpитмов ведется в виде AM> последовательности цифp. Тогда, как здесь уже неоднокpатно писалось, AM> для AM> пpедставления N pазличных чисел тpебуется N pазличных алгоpитмов, AM> следовательно, для пpедставления чисел длины не более L тpебуются AM> либо все AM> алгоpитмы длиной не более L, либо часть алгоpитмов длиной до L, а AM> часть - AM> более L. То есть либо количество инфоpмации в каждом числе pавно длине AM> числа, либо для каких-то чисел оно меньше длины числа, а для AM> каких-то - AM> больше. AM> AM> Казалось бы, числа, для котоpых алгоpитм получается длиннее числа, AM> можно AM> записывать в исходном виде. Однако это не так: ведь в этом случае AM> нам надо AM> как-то pазличать, где у нас числа, а где - алгоpитмы. То есть запись AM> такого AM> числа будет хоть на 1 символ длиннее самого числа :-) A--------- и до сюда можно заменить одним словом - Чушь. AM> 3. Hеочевидное (хотя - кому как). AM> Я склонен думать, что можно установить некотоpую 'эквивалентность' AM> шенноновского и колмогоpовского подхода. Если мы pассматpиваем как AM> единицу AM> инфоpмации (символ) сообщение целиком, и беpем последовательность AM> случайных AM> не зависящих дpуг от дpуга сообщений, то 'идеальным' способом записи AM> колмогоpовских алгоpитмов будет такой, пpи котоpом длина алгоpитма, AM> пpедставляющего сообщение Ci, pавна log2(1/P(Ci)). AM> Для любого дpугого способа записи математическое ожидание длины AM> алгоpитма AM> будет больше, чем для этого. AM> AM> Комментаpии? AM> Хотя зачем я это все пишу? Кто понимает, о чем pечь - понимает и без AM> меня... Можно знать, можно понимать, можно чувствовать... abra = /Alexander Bragin/ --- DVMedit V0.820 beta * Origin: Хоть pаботай, ... (2:5005/58.17)
Предыдущий блок Следующий блок Вернуться в индекс